Python implementation of Kahn's Algorithm

Question 1

Please provide any suggestions on the below code forKahn'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]}

Question 2

I don't think the assignment totest_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.

Question 3

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 useget() 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 assorted_nodes.

Yizhe Sun 1787 bronze badges · Accepted Answer · 2020-03-18 12:57:39Z

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 useget() 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 assorted_nodes.

Movatterモバイル変換

Stack Exchange Network

Python implementation of Kahn's Algorithm

1 Answer1

You mustlog in to answer this question.

Related

Hot Network Questions

Subscribe to RSS