Strongly connected components

In a network of one-way streets, being able to drive from u to v says nothing about driving back. This lesson groups the vertices of a directed graph by a stronger rule: you can get from each one to the other, both ways. These groups split every directed graph into parts, and the parts always line up in an order with no cycle.

Reaching both ways

In a directed graph, u reaches v when there is a path from u to v along the edges, in their direction. Every vertex reaches itself, by a path of no edges. Two vertices u and v are strongly connected when u reaches v and v reaches u.

In an undirected graph this is the same as being in one connected part (GRPH-3), because every path can be walked backwards. In a directed graph it is not. In the figure below, A reaches D (A → B → C → D), but D cannot get back to A: no street leads from C, D, G or H to A, B or E.

Groups that split the graph

Being strongly connected has three properties:

• Every vertex is strongly connected to itself.
• If u is strongly connected to v, then v is strongly connected to u: the rule is the same both ways.
• If u is strongly connected to v, and v to w, then u is strongly connected to w. A path from u to v followed by a path from v to w is a path from u to w, and the same holds on the way back.

A rule with these three properties splits the vertices into groups: each vertex is in exactly one group, and two vertices are in the same group exactly when the rule holds between them. These groups are the strongly connected components. This course calls them groups for short. A vertex that no cycle passes through is a group on its own.

One fact follows at once: every cycle lies inside one group, because every vertex on a cycle reaches every other along the cycle. And any edge u → v inside a group lies on a cycle: v reaches u, and the edge closes the loop. So a group is the largest set of vertices that cycles can join together.

The group of one vertex

To find the group of a vertex s, two searches are enough. The first search follows the edges from s, and marks every vertex s reaches. The second search follows the edges backwards: it uses the reversed graph, where every edge u → v is turned round to v → u. A path from v to s in the graph is a path from s to v in the reversed graph, so the second search marks every vertex that reaches s. The group of s is the set of vertices marked by both.

def same_group(n, edges, u, v):
    out = [[] for _ in range(n)]
    back = [[] for _ in range(n)]      # the reversed graph
    for a, b in edges:
        out[a].append(b)
        back[b].append(a)
    # u reaches v, and v reaches u (u reaches v in the reversed graph)
    return reach(out, u)[v] and reach(back, u)[v]

Here reach is any search that returns a list of True and False: BFS (GRPH-2) or a depth-first search with its own stack (GRPH-3). Each search costs O(V + E), where V is the number of vertices and E the number of edges. The same two lists give the whole group of u: every vertex marked True in both. So the group of one vertex also costs O(V + E). Doing this again from each vertex not yet in a group finds every group, but each round can cost O(V + E) and there can be V groups, so the total can reach O(V · (V + E)). On 100,000 vertices that is billions of steps. Lesson 2 finds every group with two searches in total, or with one.

Now try CONN-P1, The junction’s group.

The graph of groups has no cycle

Shrink each group to a single point, and keep one edge from group X to group Y whenever some edge of the graph goes from a vertex of X to a vertex of Y (with X and Y different). The result is the graph of groups (often called the condensation). Step through the figure’s second variant.

Suppose it had a cycle X₁ → X₂ → … → X₁. Take any vertex x in X₁ and any vertex y in X₂. Inside a group every vertex reaches every other, so following the cycle of groups gives a path from x to y, and going on round the cycle gives a path from y back to x. Then x and y are strongly connected, so X₁ and X₂ are the same group, which is not allowed for an edge of the graph of groups. So there is no cycle.

A DAG (a directed graph with no cycle) has a topological order (GRPH-5): an order of its vertices in which every edge goes forward. So the groups of any directed graph can be numbered 0, 1, 2, … so that every edge goes from a group to the same group or a later one. Lesson 2 shows that both methods for finding groups give this order on the way, and CONN-P2 asks for it.

Where groups appear

• One-way streets. A town’s street plan works for everyone exactly when the whole graph is one group. Checking this needs only the two searches above from any one junction.
• Programs. Functions that call each other in a loop form a group of the call graph. Compilers and tools that check imports work group by group, in topological order.
• Spreadsheets and build tools. A group of more than one cell is a set of formulas that depend on each other in a loop (GRPH-4’s cycles, all found at once).
• Logic. Lesson 4 turns rules with two conditions into a graph whose groups decide whether the rules can all hold.
• The web. Studies of web links found one huge group of pages that all reach each other, with pages that only lead into it and pages that only lead out of it.