Topological Sort

Our goal in topological sort is this:

Given a set of tasks to be completed with precedence constraints (eg: module prerequisites), in which order should we schedule the tasks?

Topological sort works on Directed Acyclic Graphs (DAG).

Process#

We apply DFS from a source node.
Return the vertices in reverse postorder.

We add the vertex into a stack when we cannot DFS further from it anymore. We need to ensure all vertices are visited. To do so, we run a for loop through all vertices to see if they are marked. Else, we perform dfs starting from that vertex.

Post-Order

The order in which we were "finished" with the vertices when performing DFS. Reversing this order gives us the topological order.

Topological Sort

0 -> 1 -> 4 (done -> add to stack) -> 1 (done) -> 0
0 -> 5 -> 2 (done) -> 5 (done) -> 0 (done)
We pick one of the other remaining vertices. 3 -> 6 (done)
3 (done)
Final stack: [4,1,2,5,0,6,3]
Topological Sort: [3,6,0,5,2,1,4]

Implementation#

from Graph import Graph

class TopologicalSort:
    def __init__(self, g):
        self.post_order = []
        self.marked = {}
        self.init_marked(g.get_vertices())
        self.perform_dfs(g)
        
    def init_marked(self, vertices):
        for vertex in vertices:
            self.marked[vertex] = False
    
    def perform_dfs(self, g):
        for vertex in g.get_vertices():
            if(vertex in self.marked and not self.marked[vertex]):
                self.dfs(g, vertex)
                
    def dfs(self, g, v):
        self.marked[v] = True
        for w in g.get_adjacent(v):
            w_id = w.get_id()
            if(w_id in self.marked and not self.marked[w_id]):
                self.dfs(g, w_id)
        # we have completed dfs on v
        self.post_order.append(v)
    
    # returns the reversed post order
    def get_reverse_post_order(self):
        return self.post_order[::-1]

Analysis#

Topological sort has a time complexity of O(E + V) where V is the number of vertices in the graph and E is the number of edges.