# Python implementation of Kahn's Algorithm

Please provide any suggestions on the below code for Kahn's algorithm. Can it be implemented in a better manner, or be improved:

def kahn(graph):
in_degree = {u : 0 for u in graph}
for vertices, neighbors in graph.items():
in_degree.setdefault(vertices, 0)
for neighbor in neighbors:
in_degree[neighbor] = in_degree.get(neighbor, 0) + 1

no_indegree_vertices = {vertex for vertex, count in in_degree.items() if count == 0}

topological_sort = []
while no_indegree_vertices:
vertex = no_indegree_vertices.pop()
topological_sort.append(vertex)
for neighbor in graph.get(vertex, []):
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:

if len(topological_sort) != len(in_degree):
print("Graph has cycles; It is not a directed acyclic graph ... ")
return None
else:


Test Data:

test_graph1 = {
'A' : set(['B','S']),
'B' : set(['A']),
'C' : set(['D','E','F','S']),
'D' : set(['C']),
'E' : set(['C','H']),
'F' : set(['C','G']),
'G' : set(['F','S']),
'H' : set(['E','G']),
'S' : set(['A','C','G'])
}

test_graph2 = {
'A': [],
'B': ['A'],
'C': ['B']
}

test_graph3 = {
5: ,
5: ,
4: ,
4: ,
2: ,
3: 
}

test_graph4 = {
1: ,
2: ,
4: ,
5: 
}


• I don't think the assignment to test_graph3 makes sense; you can't have a Python dictionary with keys used more than once. I think you want something like a list of lists or tuple of tuples. Mar 16 at 15:34

• I suspect that it's a bad idea to allow nodes that are not present in the keys. Conventionally, an adjacency list should have one entry for each node, whether they have outward edges or not. Moreover, it causes a lot of headache in implementations(To access a dictionary, we had to use get() method instead of the more straightforward square bracket notation).
in_degree = {u: sum(u in v for v in graph.values()) for u in graph}

• topological_sort sounds like a verb. Try use a noun for variable names, such as sorted_nodes.