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

Properties

Some interesting/useful properties of topological sort follow:

Any vertex that is on a directed cycle will never be visited (a consequence of the fact that a vertex will only be visited if the in-degree reaches 0, implying that all predecessor nodes have already been visited). Any other vertex will be visited exactly once.

The topological sort will either compute the topological ordering of the entire graph, or will fail to exclude some vertices that are part of a directed cycle.

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)$

The amount of storage required by a topological sort is $O(n)$ - this is the space used by the various containers (list of vertices in topological order, and in-degree counting map)

Flags

Graphs/Topological Sort

From charlesreid1

Contents