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.