3
\$\begingroup\$

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]
}

\$\endgroup\$
2
\$\begingroup\$
  • 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.
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.