Python implementation of Kahn's Algorithm

Question

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:
 no_indegree_vertices.add(neighbor)
 if len(topological_sort) != len(in_degree):
 print("Graph has cycles; It is not a directed acyclic graph ... ")
 return None
 else:
 return topological_sort

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: [2],
 5: [0],
 4: [0],
 4: [1],
 2: [3],
 3: [1]
}
test_graph4 = {
 1: [2],
 2: [3],
 4: [2],
 5: [3]
}

• Mark Lavin: 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.

Answer 1

• Be explicit about the data structure you're using, and the assumptions. For example, a comment like this would be helpful for any future readers(including yourself): "We represent a graph as adjacency list stored in a Python dictionary. The adjacency list can contain nodes that are not present in the keys of the dictionary, and they should be treated as nodes that contain no outward edges."
• 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).
• The first five lines of your function essentially counts each nodes' occurrence. If you require that all nodes should be present in the keys of the dictionary, it can be implemented in a single line:

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.