4
\$\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\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – Mark Lavin
    Mar 16 at 15:34

1 Answer 1

3
\$\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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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