10 Topological Ordering, Directed Graphs, Representing Graphs on Computers, Topological Sort Algorithm

Lecture from: 14.11.2024 | Rui Zhangs Notes | Video: Videos ETHZ

Topological Ordering

Imagine a directed graph representing a set of tasks and their dependencies. Vertices represent tasks, and a directed edge $(u,v)$ indicates that task $u$ must be completed before task $v$ can begin. A topological ordering (or topological sort) of this graph is a linear ordering of the vertices such that for every directed edge $(u,v)$, vertex $u$ comes before vertex $v$ in the ordering. Essentially, it’s a valid sequence in which to perform the tasks.

Existence of Topological Orderings

Not all directed graphs have a topological ordering. The presence of directed cycles prevents a valid topological sort.

Example of a graph with no topological ordering:

In this circular dependency, it’s impossible to start any task because each task depends on another.

General Rule

A directed graph has a topological ordering if and only if it is a Directed Acyclic Graph (DAG), meaning it contains no directed cycles.

Proof

Let’s prove that a directed graph has a topological sort if and only if it contains no directed cycles. We can express this formally as:

A directed graph $G$ has a topological ordering $⟺$ $G$ is a DAG (Directed Acyclic Graph).

1. $⟹$ (If $G$ has a topological ordering, then $G$ is a DAG):

We will prove this direction by contraposition. Suppose $G$ is not a DAG, meaning it contains a directed cycle. Let the cycle be $v_1\to v_2\to \cdots \to v_n\to v_1$. Assume, for the sake of contradiction, that a topological ordering exists. In this ordering, there must be some vertex in the cycle, say $v_i$, that comes first. However, since $v_i$ is part of a cycle, there’s an edge $(v_{i-1},v_i)$ (where $v_{i-1}$ is the preceding vertex in the cycle, or $v_n$ if $i=1$). This means $v_{i-1}$ must come before $v_i$ in any topological ordering, contradicting our assumption that $v_i$ comes first in the cycle. Hence, a graph with a directed cycle cannot have a topological ordering.

TLDR: Look at the example above…

2. $⟸$ (If $G$ is a DAG, then $G$ has a topological ordering):

We will prove this direction constructively by outlining an algorithm to produce a topological ordering for any DAG. This will be covered in the following sections.

Examples of Topological Sorting

Topological sorting finds applications in various algorithms and scenarios where dependencies between tasks or operations exist. Here are a few examples:

• Karatsuba’s Multiplication Algorithm: The recursive nature of Karatsuba’s algorithm can be visualized as a dependency graph, where the computation of smaller products must precede the calculation of the final product.

• Fibonacci Number Calculation: Computing Fibonacci numbers recursively also exhibits dependencies, as the $n$-th Fibonacci number depends on the $(n-1)$-th and $(n-2)$-th numbers.

• Edit Distance Problem: Calculating the edit distance between two strings involves a dynamic programming approach, where the value of a cell in the table depends on the values of its neighboring cells.

Directed Graphs

A directed graph (or digraph) $G=(V,E)$ is similar to an undirected graph, but its edges are ordered pairs.

• Edges as Ordered Pairs: An edge in a digraph is represented as $(u,v)$, where $u,v\in V$ and $u\ne v$. This signifies a directed edge from $u$ to $v$.
• No Parallel Edges (in this definition): The provided definition disallows parallel edges, meaning there can be at most one edge from $u$ to $v$.
• Predecessors and Successors: If $(u,v)$ is an edge in the digraph, we say $u$ is a direct predecessor (or parent) of $v$, and $v$ is a direct successor (or child) of $u$.

Degree of a Vertex

In directed graphs, we distinguish between in-degree and out-degree:

• In-degree (${\text{deg}}_{in}(u)$): The number of edges directed into vertex $u$.
• Out-degree (${\text{deg}}_{out}(u)$): The number of edges directed out of vertex $u$.

Special Cases:

• Source (or Quelle): A vertex $u$ with ${\text{deg}}_{in}(u)=0$ is called a source. It has no incoming edges.
• Sink (or Senke): A vertex $u$ with ${\text{deg}}_{out}(u)=0$ is called a sink. It has no outgoing edges.

Walks, Paths, and Cycles

Similar to undirected graphs, we define walks, paths, and cycles in digraphs, but with the added constraint of direction:

• Directed Walk: A sequence of alternating vertices and edges $v_1,(v_1,v_2),v_2,(v_2,v_3),\dots ,v_{n-1},(v_{n-1},v_n),v_n$ where each $(v_i,v_{i+1})$ is a directed edge.
• Directed Path: A directed walk with distinct vertices.
• Directed Cycle: A directed path that starts and ends at the same vertex.

Representing Graphs on a Computer

Storing graphs efficiently on a computer is crucial for implementing graph algorithms. Let’s consider a graph $G=(V,E)$ with vertices $V=\{1,2,\dots ,n\}$ and $m=|E|$ edges. We’ll examine two common representations: adjacency matrices and adjacency lists.

Suppose we want to store this graph:

Adjacency Matrix

An adjacency matrix represents the graph as an $n\times n$ matrix $A$, where:

• $A[u][v]=1$ if there’s an edge from $u$ to $v$.
• $A[u][v]=0$ otherwise.

Example:

Operations and Runtime

Pros and Cons

Adjacency List

An adjacency list represents a graph as an array of lists. Each list corresponds to a vertex $u$ and stores the vertices $v$ such that $(u,v)$ is an edge. Often, these lists are implemented using linked lists for efficient insertion and deletion of edges.

Example:

Operations and Runtime

Pros and Cons

Choosing the Right Representation

• Adjacency Matrix: Simpler, constant-time edge lookup, suitable for dense graphs.
• Adjacency List: More space-efficient for sparse graphs, efficient neighbor iteration, more commonly used in practice. The choice between the two depends on the specific application and the characteristics of the graph being represented.

Topological Sort Algorithm

Let’s explore a topological sort algorithm and its connection to the absence of directed cycles.

Core Idea: The algorithm repeatedly finds and removes sinks (vertices with no outgoing edges) from the graph.

1. Find a Sink: Locate a vertex with ${\text{deg}}_{out}(v)=0$.
2. Append to List: Add the sink to the end of the topological ordering list.
3. Remove and Recurse: Remove the sink and all its incoming edges from the graph. Repeat the process on the remaining subgraph.

Initial Approach (using path)

The path function aims to find a sink by exploring a path from a given vertex:

def path(u):
	u.mark()
	if any(v in u.successors() and not v.isMarked() for v in u.successors()):
		path(v)

Example:

Calling path(A) might produce the marked path A, B, E, F, G. The topological order would be initialized with G, F, E, B, A (built by prepending).

Properties of path:

1. Marks a Path: path(u) marks a directed path $P$ starting at $u$.
2. End Node Properties: The end vertex $v$ of $P$ has all its successors either already marked or has no successors (a sink).

Claim: If there are no directed cycles, the end vertex $v$ found by path(u) is a sink.

Proof (by Contrapositive): If $v$ is not a sink, the graph contains a directed cycle.

1. Assume $v$ is not a sink: $v$ has a successor $w$. By path’s properties, $w$ must already be marked.
2. $w$ is on the path: Since $w$ is marked, it must lie on the path $P$ from $u$ to $v$.
3. Cycle Exists: The edge $(v,w)$ and the path segment from $w$ to $v$ form a cycle.

Improved Approach (using visit and DFS)

The path function is inefficient because it restarts the search after finding each sink. The visit function improves this:

def visit(u, topological_order):
	u.mark()
	for v in u.successors():
		if not v.isMarked():
			visit(v, topological_order)
	topological_order.insert(0, u)   # Prepend u to maintain order

Example:

visit processes all reachable vertices from a given vertex before adding it to the order. This means it’s more efficient and doesn’t discard work.

Depth-First Search (DFS):

def dfs_topological_sort(G):
	G.unmarkAll()
	topological_order = []
	for u in G.nodes():
		if not u.isMarked():
			visit(u, topological_order)
	return topological_order

dfs_topological_sort uses visit to perform a depth-first traversal, ensuring all vertices are visited and added to the topological order.

DFS Tree:

The DFS creates a tree structure that captures the dependencies between vertices, enabling the topological sort. By adding nodes after all descendants have been visited, we create the correct ordering.

Let’s analyze the topological sort procedure more deeply by augmenting the visit function with pre- and post-visit timestamps.

def visit(u, topological_order, pre, post, T):
    pre[u] = T
    T += 1
    u.mark()
    for v in u.successors():
        if not v.isMarked():
            T = visit(v, topological_order, pre, post, T) # T is modified recursively.
    topological_order.insert(0, u)
    post[u] = T
    T += 1
    return T

We’ve introduced pre and post dictionaries (or arrays) to store timestamps. pre[u] records the time when vertex u is first visited, and post[u] records the time when the visit(u) call completes. T is a global counter (or a parameter passed by reference) that keeps track of the current time. Note how T is recursively updated and passed down.

Example with Pre- and Post-visit Times:

Starting the DFS from vertex A, we obtain the pre- and post-visit times shown in the image.

Pre- and Post-order Sort:

• Pre-order: The pre-order is not necessarily a topological sort. Note that vertices are prepended to topological_order and not added. The pre-order sorting is, however, the order in which the recursive visit calls begin.

• Post-order: The post-order is a topological sort. The post-order is the order in which the recursive visit calls complete. This is because, by definition, when a visit(u) call completes, it means that all of u’s successors have also completed their visit calls. Thus, it’s safe to place u before its successors in the topological order.

Interval Pattern (Nesting):

The intervals defined by [pre[u], post[u]] exhibit a nesting pattern. This nesting directly corresponds to the recursion tree of the DFS.

Edge Classifications based on Intervals

Note for readers: I suggest watching this less confusing explanation

Given an edge $(u,v)$, we can classify it based on the intervals $[pre(u),post(u)]$ and $[pre(v),post(v)]$:

1. Tree Edge: If $pre(u)<pre(v)<post(v)<post(u)$, then $(u,v)$ is a tree edge. This means $v$ is a descendant of $u$ in the DFS tree. The visit(u) call directly leads to the visit(v) call. Example: (A, B), (B, E).

   

2. Back Edge: If $pre(v)<pre(u)<post(u)<post(v)$, then $(u,v)$ is a back edge. This indicates a cycle in the graph. $u$ is a descendant of $v$, and the edge $(u,v)$ goes back to an ancestor. Examples: (F, B), (D, A).

   

3. Forward Edge: If $pre(u)<pre(v)<post(v)<post(u)$, then $(u,v)$ is a forward edge. This means $v$ is a descendant of $u$, but the edge is not part of the DFS tree. There is a path u to v in the tree but a direct edge as well. Examples: (A, F), (B, G).

   

4. Cross Edge: If $pre(v)<post(v)<pre(u)<post(u)$, then $(u,v)$ is a cross edge. This means $u$ and $v$ are in different branches of the DFS tree, and there is no ancestor-descendant relationship between them. They belong to different subtrees that don’t overlap. Examples: (H, G), (D, H).

   

Impossible Cases:

• Overlapping but not Nested Intervals: Due to the recursive nature of DFS, two intervals cannot partially overlap without one completely containing the other.

• $pre(u)<pre(v)<post(u)<post(v)$: This case is impossible because visit(u) would call visit(v) if v was not yet marked, so the interval of v can’t end before u.

Observations and Topological Sort Justification

Let’s connect the edge classifications to the existence of directed cycles and justify why the reverse post-order provides a topological sort.

Observations:

1. Back Edge Implies Cycle: If a back edge $(u,v)$ exists, then there is a directed cycle. This is because a back edge connects a vertex $u$ to an ancestor $v$ in the DFS tree. The path from $v$ to $u$ in the DFS tree, combined with the back edge $(u,v)$, forms a cycle.

2. Non-Back Edges and Post-Order: For all non-back edges $(u,v)$, we have $post(u)>post(v)$. Let’s justify this for each non-back edge type:

   • Tree Edge: By definition, $post(u)>post(v)$ for a tree edge $(u,v)$.
   • Forward Edge: Similarly, for a forward edge $(u,v)$, $post(u)>post(v)$.
   • Cross Edge: For a cross edge $(u,v)$, the DFS finishes visiting $v$ and its descendants before starting to visit $u$. Therefore, $post(v)<pre(u)<post(u)$.

Connecting to Topological Sort:

• No Cycles Imply No Back Edges: If there are no directed cycles in the graph, then observation 1 tells us there can be no back edges.

• Reverse Post-Order is Topological Sort: If there are no back edges, then for every edge $(u,v)$ in the graph (all of which are now non-back edges), $post(u)>post(v)$ (observation 2). This means that if we sort the vertices in reverse post-order, for every edge $(u,v)$, $u$ will come before $v$ in the sorted list. This is precisely the definition of a topological sort.

Runtime of Topological Sort

The runtime of the topological sort algorithm depends on the graph representation. Let $n=|V|$ be the number of vertices and $m=|E|$ be the number of edges.

Adjacency Matrix

• visit calls: The visit function is called at most once for each vertex. Therefore, there are at most $n$ calls to visit.

• Work per visit call: Inside visit, the main work is iterating through the successors of a vertex u. With an adjacency matrix, this requires checking all n entries in the row corresponding to u to determine its successors.

• Total Runtime: Consequently, the total runtime using an adjacency matrix is $O(n\cdot n)=O(n^2)$.

Adjacency List

• visit calls: Similar to the adjacency matrix case, the visit function is called at most n times.

• Work per visit call: For a vertex u, the work inside visit involves iterating through the successors of u. With an adjacency list, this takes $O(1+{\text{deg}}_{out}(u))$ time, where ${\text{deg}}_{out}(u)$ is the out-degree of u. Additionally, the recursive calls of visit do their work.

• Total Runtime: Summing up the work across all visit calls gives us: ${\sum }_{u\in V}O(1+{\text{deg}}_{out}(u))=O\left({\sum }_{u\in V}1\right)+O\left({\sum }_{u\in V}{\text{deg}}_{out}(u)\right)$

  Since ${\sum }_{u\in V}1=n$ and ${\sum }_{u\in V}{\text{deg}}_{out}(u)=m$ (the total number of edges — the Handshaking lemma for directed graphs), the runtime simplifies to $O(n+m)$.

TLDR:

• Adjacency Matrix: $O(n^2)$
• Adjacency List: $O(n+m)$

For sparse graphs where $m<<n^2$, the adjacency list representation leads to a significantly faster topological sort algorithm. For dense graphs where $m$ is closer to $n^2$, the difference in performance might be less pronounced. However, the adjacency list representation generally offers better overall performance, especially for large or sparse graphs.

Continue here: 11 Shortest Path Algorithms, Cheapest Walks in Weighted Graphs, Acyclical Graphs and Topological Sort, Dijkstra’s Algorithm