Topological Sorting

Definition

Topological sorting is concerned with ordering all nodes of a directed acyclic graph.

We can describe this process using the example of scheduling university courses each semester. Suppose the courses include “Programming”, “Algorithmic Languages”, “Advanced Mathematics”, “Discrete Mathematics”, “Compiler Technology”, “General Physics”, “Data Structures”, and “Database Systems”. In the example schedule, when we want to study “Data Structures”, we must first learn “Discrete Mathematics”; after completing that course, we obtain the prerequisite for studying “Compiler Technology”. Of course, “Compiler Technology” has an even earlier prerequisite, “Algorithmic Languages”. These courses correspond to several vertices $u$, and a directed edge $(u,v)$ between vertices corresponds to the order in which the courses are learned. The process by which the academic affairs office arranges these courses into a schedule consistent with the logical relationships is topological sorting.

But suppose that one day the teacher scheduling the courses dozes off and says that anyone who wants to study Data Structures must first study Operating Systems, while Operating Systems itself requires Data Structures as a prerequisite. Which one should be studied first (ignoring the possibility of studying them simultaneously)? A cycle has appeared between Data Structures and Operating Systems, so students can no longer determine what they need to learn first and topological sorting cannot be performed. Therefore, if a directed graph contains a cycle, topological sorting is impossible.

Thus, in a DAG (directed acyclic graph), we can order the vertices of the graph linearly so that, for every directed edge from $u$ to $v$, denoted $(u,v)$, $u$ appears before $v$.

Given a DAG, if there is an edge from $i$ to $j$, then $j$ is said to depend on $i$. If there is a path from $i$ to $j$ ($i$ can reach $j$), then $j$ is said to depend indirectly on $i$.

The goal of topological sorting is to order all nodes so that no node appearing earlier depends on a node appearing later.

AOV Network

In daily life, a large project can be viewed as a collection of several subprojects. There must be a certain precedence relation among these subprojects: some subprojects can begin only after some others have been completed.

We use a directed graph to represent the precedence relations among subprojects, with directed edges representing those relations. Such a directed graph is called an AOV network (Activity On Vertex Network). An AOV network must be a directed acyclic graph, that is, it must not contain a cycle. Unlike a DAG in general, the activities in an AOV network are represented by vertices. (The example graph above is an AOV network.)

In an AOV network, vertices represent activities and arcs represent precedence relations between activities. An AOV network should contain no cycles, so we can find a vertex sequence in which the predecessor activities of the activity represented by each vertex all appear before it. Such a sequence is called a topological sequence (an AOV network may have more than one topological sequence), and the process of constructing a topological sequence from an AOV network is called topological sorting. Thus, topological sorting can also be understood as arranging all activities in an AOV network into a sequence so that the predecessor activities of each activity appear before it (an AOV network may also have more than one topological ordering).

• Predecessor activity: the activity at the start of a directed edge is called a predecessor activity of the activity at its end (an activity can be performed only after all of its predecessor activities have been completed).

• Successor activity: the activity at the end of a directed edge is called a successor activity of the activity at its start.

To detect whether an AOV network contains a cycle, construct a topological sequence and check whether it contains all vertices.

Steps for Constructing a Topological Sequence

1. Select a vertex with indegree zero from the graph.
2. Output the vertex, and remove it and all its outgoing edges from the graph.

Repeat the two steps above until all vertices have been output and topological sorting is complete, or until no vertex with indegree zero exists in the graph. In the latter case, the graph contains a cycle, topological sorting cannot be completed, and the process is deadlocked.

Critical Paths and AOE Networks

The counterpart of an AOV network is an AOE network (Activity On Edge Network), in which edges represent activities. An AOE network is a weighted directed acyclic graph whose vertices represent events and whose arcs represent activity durations. It is commonly used to estimate project completion time. An AOE network should be acyclic and should have a unique starting vertex with indegree zero (the source) and a unique completion vertex with outdegree zero (the sink).

Some activities in an AOE network can be performed in parallel, so the shortest time to complete the entire project is the length of the longest activity path from the start to the completion point (here, path length means the sum of the durations of all activities on the path, that is, the sum of arc weights, not the number of arcs on the path). Because every activity in the project must be completed, the longest activity path is also the critical path, and it determines the total project completion time.

Basic Concepts in an AOE Network

• Activity: in an AOE network, an arc represents an activity. The weight of an arc represents the activity duration, and the activity starts after its predecessor event (the start of the arc) is triggered.

• Event: in an AOE network, a vertex represents an event. The event is triggered after all its predecessor activities (the arcs pointing to that edge) have been completed.

• Earliest occurrence time of event (vertex) $v_i$: the earliest possible time for the event to occur, denoted by $ve(i)$. It determines the earliest start time of activities beginning at this vertex; clearly, the earliest occurrence time of the source is 0. Since an event can occur only after all its predecessor activities have been completed, it equals the maximum path length from the initial vertex to that vertex. Recursively, $ve(i) = \max\{ve(j) + val^j_i ~\vert~ j \in pre_i\}$, where $val^j_i$ is the weight of the edge from j to i (that is, the duration of the activity from j to i), and $pre_i$ is the set of all predecessor events of i.

• Latest occurrence time of event (vertex) $v_i$: the latest time at which the event can occur without delaying the overall project duration, denoted by $vl(i)$. It determines the latest occurrence times of all activities ending at this event, and equals the minimum of the latest start times of all successor activities of the event: $vl(i) = \min\{vl(j) - val^i_j ~\vert~ j \in nxt_i\}$, where $val^i_j$ is the weight of the edge from i to j (that is, the duration of the activity from i to j), and $nxt_i$ is the set of all successor events of i.

• Earliest start time of activity (arc) $(u, v)$: the earliest possible time for the activity to occur, denoted by $e(u,v)$. Clearly, it equals the earliest occurrence time of its predecessor event, namely $e(u,v)=ve(u)$.

• Latest start time of activity (arc) $(u, v)$: the latest time at which the activity can start without delaying the overall project duration, denoted by $l(u,v)$. It equals the latest occurrence time of its successor event minus the duration (weight) of that event, namely $l(u,v)=vl(v)-val^u_v$, where $val^u_v$ is the weight of the edge from u to v (that is, the duration of the activity from u to v).

• Critical path: the length of the longest path from the source to the sink in an AOE network.

• Critical activity: an activity on the critical path; its earliest start time equals its latest start time.

Recursively Computing Earliest and Latest Occurrence Times

Compute them in topological order: recurse forward for earliest occurrence times and backward for latest occurrence times, using the recurrences shown above in Basic Concepts in an AOE Network.

Kahn's Algorithm

Process

Initially, the set $S$ contains all vertices with indegree $0$, and $L$ is an empty list.

At each step, remove from $S$ a vertex $u$ (any choice is allowed) and put it into $L$, then delete all edges from $u$, namely $(u, v_1), (u, v_2), (u, v_3) \cdots$. For an edge $(u, v)$, if deleting the edge makes the indegree of $v$ become $0$, put $v$ into $S$.

Repeat this process until the set $S$ is empty. Check whether any edge remains in the graph. If one does, the graph must contain a cycle; otherwise, return $L$; the vertex order in $L$ is the constructed topological sequence.

First, consider the pseudocode from Wikipedia.

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is not empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else
    return L (a topologically sorted order)

The core of the code is maintaining a set of vertices with indegree 0.

The following figure may help:

The result of sorting it is: 2 -> 8 -> 0 -> 3 -> 7 -> 1 -> 5 -> 6 -> 9 -> 4 -> 11 -> 10 -> 12

Time Complexity

Suppose that for the graph $G = (V, E)$, initializing the set of vertices with indegree $0$, $S$, requires traversing the entire graph and checking every edge, giving a complexity of $O(E+V)$. Operating on this set also clearly takes $O(E+V)$ time.

Therefore, the total time complexity is $O(E+V)$.

Implementation

C++

int n, m;
vector<int> G[MAXN];
int in[MAXN];  // Store the indegree of each vertex

bool toposort() {
  vector<int> L;
  queue<int> S;
  for (int i = 1; i <= n; i++)
    if (in[i] == 0) S.push(i);
  while (!S.empty()) {
    int u = S.front();
    S.pop();
    L.push_back(u);
    for (auto v : G[u]) {
      if (--in[v] == 0) {
        S.push(v);
      }
    }
  }
  if (L.size() == n) {
    for (auto i : L) cout << i << ' ';
    return true;
  }
  return false;
}

Python

from collections import defaultdict, deque

def topo_sort(graph):
    lst = []
    in_degree = defaultdict(int)
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    s = deque([u for u in graph if in_degree[u] == 0])
    while s:
        u = s.popleft()
        lst.append(u)
        for v in graph.get(u, []):
            in_degree[v] -= 1
            if in_degree[v] == 0:
                s.append(v)

    return None if any(in_degree.values()) else lst

DFS Algorithm

Implementation

C++

using Graph = vector<vector<int>>;  // Adjacency list

struct TopoSort {
  enum class Status : uint8_t { to_visit, visiting, visited };

  const Graph& graph;
  const int n;
  vector<Status> status;
  vector<int> order;
  vector<int>::reverse_iterator it;

  TopoSort(const Graph& graph)
      : graph(graph),
        n(graph.size()),
        status(n, Status::to_visit),
        order(n),
        it(order.rbegin()) {}

  bool sort() {
    for (int i = 0; i < n; ++i) {
      if (status[i] == Status::to_visit && !dfs(i)) return false;
    }
    return true;
  }

  bool dfs(const int u) {
    status[u] = Status::visiting;
    for (const int v : graph[u]) {
      if (status[v] == Status::visiting) return false;
      if (status[v] == Status::to_visit && !dfs(v)) return false;
    }
    status[u] = Status::visited;
    *it++ = u;
    return true;
  }
};

Python

from enum import Enum, auto

class Status(Enum):
    to_visit = auto()
    visiting = auto()
    visited = auto()

def topo_sort(graph: list[list[int]]) -> list[int] | None:
    n = len(graph)
    status = [Status.to_visit] * n
    order = []

    def dfs(u: int) -> bool:
        status[u] = Status.visiting
        for v in graph[u]:
            if status[v] == Status.visiting:
                return False
            if status[v] == Status.to_visit and not dfs(v):
                return False
        status[u] = Status.visited
        order.append(u)
        return True

    for i in range(n):
        if status[i] == Status.to_visit and not dfs(i):
            return None

    return order[::-1]

Time complexity: $O(E+V)$; space complexity: $O(V)$.

Correctness Proof

Consider a graph. If deleting a vertex with indegree $0$ leaves a graph that can be topologically sorted, then the original graph can also be topologically sorted. Conversely, if the original graph can be topologically sorted, then the graph after deletion can too.

Applications

Topological sorting can determine whether a graph contains a cycle, and can also determine whether a graph is a chain. It can be used to find the critical path in an AOE network and estimate the shortest project completion time.

Finding the Lexicographically Largest/Smallest Topological Order

Replace the queue in Kahn's algorithm with a priority queue implemented by a max-heap/min-heap. The total time complexity is then $O(E+V \log{V})$.

Exercises

CF 1385E: construction requires topological sorting.

Luogu P1347: a topological sorting template.

References

1. Discrete Mathematics and Its Applications. ISBN:9787111555391
2. Topological sorting - Wikipedia
3. Lecture 9 on Data Structures (Graphs: Topological Sorting, Critical Paths, and Shortest Paths) - Zhihu Column