2. Toplogical Sorting & Strongly Connected Components

Directed Acyclic Graphs (DAGs)

Directed Acyclic Graph

A graph $G=(V,E)$ is said to be a directed acyclic graph:

• if it is a irreflexive relation
• if it does not contain any cycles of length $\ge 2$

If there is a path $u⇝v$ then there is no path $v⇝u$.

Link to original

Topological Sort

Topological Sort

A topological sort of a Directed Acyclic Graph $G=(V,E)$ is an ordered list of vertices $L=⟨v_1,v_2,\dots ,v_n⟩$, such that:

$$\text{if }{v}_i⇝v_j\text{ then }i<j\text{for all }i,j\le n$$

All the arrows point ‘downstream’ from $v_1$ to $v_n$.

Link to original

Algorithm: Topological Sort

Topological Sort (Algorithm)

$\text{TOPOLOGICAL\_SORT}(G)$:

1. While vertices remain unsorted:
   1. Select any unsorted vertex and add to a stack
   2. While stack is not empty:
      1. Inspect top element $u$ on stack
      2. If $u$ has no unsorted neighbours:
         1. Pop $u$ from stack and add to list $L$
      3. Else: add unsorted neighbours of $u$ to stack
2. Return sorted list $L$

Link to original

Below is an example input and output list $L$:

Strongly Connected Components

Strongly Connected Component

We can define a binary relation $\sim \subseteq V\times V$ on the set of vertices such that:

$$u\sim v⟺u=v\text{ or there is a path }u⇝v\text{ and a path }v⇝u$$

A strongly connected component is therefor a maximal subset $C\subseteq V$ such that $u\sim v$ for all $u,v\in C$.

Link to original

Component Graph

The component graph of $G$ is a new graph $G^{SCC}=(V^{SCC},E^{SCC})$ where:

$$\begin{array}{rl}{V}^{SCC}=& \{\text{all strongly connected components of }G\}\\ (A,B)\in E^{SCC}⟺& (a,b)\in E\text{ for some }a\in A\text{ and }b\in B\\ & \text{where }A\ne B\end{array}$$

(vertices consist of Strongly Connected Components)

Link to original

Example Component Graph

For example, given the graph below, we have 4 strongly connected components:

If we ignore the vertices and focus on the groups, we get the following graph: (this is the component graph)

Theorem: The component graph $G^{SCC}$ is a DAG, for any directed graph $G$.

1. Suppose, for contradiction, that there is a cycle $⟨C_1,C_2,\dots ,C_n,C_1⟩$:
2. Chose any $a\in C_i$ and $b\in C_j$ for some $C_i\ne C_j$.
3. It follows that there must be a path $a⇝b$ and $b⇝a$.
4. But this means that $a$ and $b$ must belong to the same component, which is a contradiction.
5. Hence, by contradiction, $G^{SCC}$ cannot contain any cycle, as required.

Algorithm: Identify SCCs

Identify Strongly Component Components (Algorithm)

$\text{SCC}(G)$:

1. Call Topological Sort (Algorithm) to generate list $L$.
2. While $L$ is not empty:
   1. Inspect first element $u$ in the list.
   2. Perform Depth First Search (Algorithm) on the Transpose Graph $G^T$ from $u$.
   3. Add all visited vertices to a new component $S$.
   4. Remove these vertices from the list $L$.
3. Return all components identified.

Link to original