CSCE 411 Lecture 19

Lecture Slides

« previous | Wednesday, October 10, 2012 | next »

Strongly Connected Components

A directed graph is strongly connected iff you can go from any node to any other node

A strongly connected component (SCC) is a maximal set of nodes with a directed path between every pair of nodes.

For example: Packaging software modules

• Construct directed graph of which modules call which other modules
• SCC is a set of mutually interacting modules
• Put those modules in the same SCC

Algorithm

DFS tells us which nodes are reachable from roots of individual trees, but we need information about the "other direction": is the root reachable from its descendants? (reverse direction of edges)

1. Call DFS($G$) to compute finishing times (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(V+E)} )
2. Compute Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G^T} (transpose of adjacency matrix graph; reverse direction of all edges) (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(V+E)} ; assuming adjacency list)
3. Call DFS($G^{T}$), considering nodes in decreasing order of finishing times ($O(V+E)$)
4. Each tree from (3) is a separate SCC of $G$

Total running time: $O(V+E)$

Example

Finish times for step 1:

1 2 3     4 5     6 7 8     9 10 11 12 13    14 15 16
| | '--c--' '--d--' | '--e--'  |  |  |  '--h--'  |  |
| '--------b--------'          |  |  '-----g-----'  |
'---------------a--------------'  '--------f--------'

Thus order of nodes for step 3 is: f, g, h, a, e, b, d, c

Finish times for step 2:

1 2 3     4 5 6 7 8     9 10 11 12    13 14 15    16
| | '--g--' | | | '--e--'  |  |  '--c--'  |  '--d--'
| '----h----' | '----a-----'  '-----b-----'
'------f------'

Thus {f, h, g}, {a,e}, {b,c}, and {d} are SCCs

Correctness

Let $C_{i}$ represent a strongly connected component in $G$

Draw a graph using $C_{i}$'s as vertices, and edges from $C_{i}$ to $C_{j}$ iff $G$ has an edge from a vertex in $C_{i}$ to a vertex in $C_{j}$.

The resulting graph does not have any cycles.

Proof

Let $d(C)$ be the earliest discovery time of any node in $C$, and likewise let $f(C)$ be the latest finishing time in $C$.

We claim that $f(C')>f(C)$ if there is an edge in $G$ from component $C'$ to $C$

Case 1: $d(C')<d(C)$. Suppose $x$ is the first node discovered in $C'$. DFS would take all nodes in $C'$ and $C$ as descendents of $x$, so $x$ is the last node in $C'$ to finish and finishes after all nodes in $C$. Thus $f(C')>f(C)$

Case 2: $d(C')>d(C)$. Suppose $y$ is the first node discovered in $C$. DFS would accept all nodes in $C$ as descendents of $y$, so $y$ is the last node to finish. Since $C'\rightarrow C$, no node in $C'$ is reachable from $y$, so $y$ finishes before any node in $C'$ is discovered. Thus $f(C')>f(C)$

Induction on number of trees in step 3 (Calling DFS on $G^{T}$): The first $k$ trees found constitute $k$ SCCs of $G$.

Basis: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k=0} , no work to do.

Induction: Assume the first Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} trees constructed in step 3 correspond to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} SCCs. Consider the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (k+1)} ^st tree: (let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} be the root of the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (k+1)} ^st tree) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} is part of SCC Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} , and by inductive hypothesis, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} is one of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} SCCs already found, and all nodes in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} are unvisited when Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} is discovered.

Q.E.D.