Kahn's Algorithm


#graph #topological sort
- 2 minutes read - 345 words

Kahn’s Algorithm

To figure out the topological sort order of a directed acyclic graph

  • Creat a graph given a list of edges, preferable using Adjacency List
  • Calculate the in-degree of each vertex of the graph
  • Enqueue the vertices with the in-degree of 0.
  • Keep a counter called visited
  • While the queue is not empty:
  • Dequeue a vertex.
  • Add this vertex to the result.
  • Increment the visited variable by 1.
  • Decrement the in-degree of all its neighboring vertices by 1
  • Enqueue the neighboring vertices with the in-degree of 0.
  • In the end if visited is equal to the number of vertices then you have your order
  • If its not equal to vertices then either there was a cycle or the graph was disjoint

Code


def kahn(adjl, indegree):
    N = len(adjl)
    
    queue = []
    visited = 0
    order = []
    for k, v in indegree.items():
        if v == 0:
            queue.append(k)
    
    while len(queue) != 0:
        node = queue.pop(0)
        del indegree[node]
        visited += 1
        order.append(node)
        for child in adjl[node]:
            indegree[child] -= 1
            if indegree[child] == 0:
                queue.append(child)

    if N == visited:
        return order
    else:
        return []

def createGraph(edges):
    """Create Adjacency List"""
    al = {}
    for edge in edges:
        u = edge[0]
        v = edge[1]
        if not v in al:
            al[v] = set()
        if not u in al:
            al[u] = set()
        al[u].add(v)
    return al

def getdegrees(graph):
    """Calculate in and out degrees"""
    indegree = {}
    outdegree = {}
    for k in graph.keys():
        outdegree[k] = len(graph[k])
        indegree[k] = 0
        for v in graph.values():
            if k in v:
                indegree[k] += 1
    return indegree, outdegree
    
def validate(outdegree, indegree):
    """There must be at least one vertex 
    with 0 indegree (root) and at least
    one with 0 outdegree
    if its a DAG
    """
    isValid = False
    for k, v in outdegree.items():
        if v == 0:
            isValid = True
    if not isValid:
        return False
    isValid = False
    for k, v in indegree.items():
        if v == 0:
            isValid = True
    return isValid
    
if __name__ == "__main__":
    edges = [
        [1,2],
        [2,3],
        [3,4]
    ]
    graph = createGraph(edges)
    indegree, outdegree = getdegrees(graph)
    if validate(outdegree, indegree):
        order = kahn(graph, indegree)
    print(order)