Graphs/Topological Sort

Notes

To sort a graph topologically, the graph must be a directed acyclic graph (see DAGs).

The goal of topological sorting is to come up with an ordering $ v_1, \dots, v_n $ of the vertices of the graph G such that, for every directed edge $ (v_i, v_j) $, the condition i < j is true. If the graph is traversed in this order, the vertices are traversed in increasing order.

A topological sorted order is not necessarily unique.

Procedure

To perform a topological sort, we must start at the root vertex. Any DAG must have at least one root vertex that has no incoming edges. The root vertex (or, the first root vertex we select) is numbered 1.

Next, we remove the root vertex. The result is another DAG, which has at least one root vertex with no incoming edges. This root vertex (or, the first root vertex we select) is numbered 2.

This procedure is repeated until we have removed the last vertex from the DAG.

Pseudocode

The pseudocode starts by computing the in-degree of each vertex in the DAG. it then traverses the DAG, searching for root vertices, "removing" them from the graph, decrementing the in-degree of each neighbor node, then finding the next root vertex.

def topo_sort(g):

    topo = empty list, to store vertices in topologically sorted order
    roots = empty list, to store root vertices
    indegree = empty map, maps vertex to in-degree (integer)

    # find root nodes on the entire graph
    for vertex u in vertices of g:
        indegree[u] = get degree of u
        if indegree[u] is 0:
            add u to roots

    while roots is not empty:

        # pop the next root node
        u = pop from roots
        add u to topo list

        # find new root nodes that neighbored the popped node
        for edge e in incident edges to u:
            v = opposite vertex to u on edge e
            indegree[v] -= 1

            # find next root node
            if indegree[v] is 0:
                add v to roots

    return topo

Big O Cost

A topological sort requires us to visit each node, and examine each edge at each node, for a total cost of $ O(n+m) $

Any vertex that is on a directed cycle will never be visited. Any other vertex will be visited exactly once.