topological sort

A BFS algo that takes a directed graph and returns an array of the nodes where each node appears before all the nodes it points to.

• Does not work on cyclic or undirected graphs
• A graph can have more than one valid topological ordering.

Steps:

1. Identify nodes with no inbound edges and add them to the ordering
   • safe to add first since they have nothing that needs to come before them
   • must exist since there is no cycle
2. Remove their outbound edges from the graph
3. Repeat until all nodes have been added

The algo:

1. Create an empty queue order to store the valid sort

2. Create a queue processNext to store the next nodes to process

3. Count the number of inbound edges of each node and set a class variable node.inbound

   Note: nodes typically only store their outbound edges. We count the inbound edges by walking through each node n - for each of its outgoing edges (n, x), increment x.inbound

4. Walk through the nodes again and add to processNext where x.inbound == 0

5. While processNext is not empty:

   • remove first node n from processNext
   • for each edge (n, x), decrement x.inbound. If it is 0, append x to processNext.
   • append n to order

6. If order contains all the nodes, then the topological sort has succeeded. O/w it has failed due to a cycle.

• Implementation tweak: instead of removing nodes (and destroying input), track the number of incoming edges for each node

  def topological_sort(digraph): 
    # digraph (directed graph): dict
    # key: node
    # value: {adjacent nodes}
    
    # create dict mapping nodes to # incoming edges
    indegrees = {node : 0 for node in digraph}
    for node in digraph:
      for neighbor in digraph[node]:
        indegrees[neighbor] += 1
              
    # track nodes with no incoming edges
    nodes_with_no_incoming_edges = []
    for node in digraph:
      if indegrees[node] == 0:
        nodes_with_no_incoming_edges.append(node)
              
    # initially, no nodes in our ordering
    topological_ordering = [] 
    
    while len(nodes_with_no_incoming_edges) > 0:
   
      # add one of those nodes to the ordering
      node = nodes_with_no_incoming_edges.pop()
      topological_ordering.append(node)
   
      # decrement the indegree of that node's neighbors
      for neighbor in digraph[node]:
        indegrees[neighbor] -= 1
        if indegrees[neighbor] == 0:
            nodes_with_no_incoming_edges.append(neighbor)
    
  	# we've run out of nodes with no incoming edges
    # did we add all the nodes or find a cycle?
      if len(topological_ordering) == len(digraph):
          return topological_ordering  # got them all
      else:
          raise Exception("Graph has a cycle! No topological ordering exists.")