Path-based strong component algorithm

In graph theory, the strongly connected components of a directed graph may be found using an algorithm that uses depth-first search in combination with two stacks, one to keep track of the vertices in the current component and the second to keep track of the current search path. Versions of this algorithm have been proposed by Purdom (1970), Munro (1971), Dijkstra (1976), Cheriyan & Mehlhorn (1996), and Gabow (2000); of these, Dijkstra's version was the first to achieve linear time.

Description

The algorithm performs a depth-first search of the given graph G, maintaining as it does two stacks S and P (in addition to the normal call stack for a recursive function). Stack S contains all the vertices that have not yet been assigned to a strongly connected component, in the order in which the depth-first search reaches the vertices. Stack P contains vertices that have not yet been determined to belong to different strongly connected components from each other. It also uses a counter C of the number of vertices reached so far, which it uses to compute the preorder numbers of the vertices.

When the depth-first search reaches a vertex v, the algorithm performs the following steps:

1. Set the preorder number of v to C, and increment C.
2. Push v onto S and also onto P.
3. For each edge from v to a neighboring vertex w:
   • If the preorder number of w has not yet been assigned (the edge is a tree edge), recursively search w;
   • Otherwise, if w has not yet been assigned to a strongly connected component (the edge is a forward/back/cross edge):
     • Repeatedly pop vertices from P until the top element of P has a preorder number less than or equal to the preorder number of w.
4. If v is the top element of P:
   • Pop vertices from S until v has been popped, and assign the popped vertices to a new component.
   • Pop v from P.

The overall algorithm consists of a loop through the vertices of the graph, calling this recursive search on each vertex that does not yet have a preorder number assigned to it.

History and development

The path-based algorithm family for finding strongly connected components was developed from several key historical contributions. The earliest version was proposed as Paul Purdom's 1970 transitive closure algorithm, which utilized naive cycle contraction. This was optimized by J. Ian Munro in 1971 using a set-merging approach, running in O(m + n log n) time. Edsger W. Dijkstra, in his 1976 book, introduced the first linear-time O(m + n) non-recursive implementation of the algorithm using three main arrays: rank, knar (the backwards spelled rank array mapping rank to vertex), and cc (used to track component boundaries). In 1976, Dijkstra also derived the path-based algorithm using these three arrays—rank, knar, and cc—to track component boundaries and achieve O(m + n) time. Later formulations and refinements to the path-based strongly connected components algorithm were proposed by Cheriyan and Mehlhorn in 1996 and by Gabow in 2000.

Related algorithms

Like this algorithm, Tarjan's strongly connected components algorithm also uses depth first search together with a stack to keep track of vertices that have not yet been assigned to a component, and moves these vertices into a new component when it finishes expanding the final vertex of its component. However, in place of the stack P, Tarjan's algorithm uses a vertex-indexed array of preorder numbers, assigned in the order that vertices are first visited in the depth-first search. The preorder array is used to keep track of when to form a new component.

References

• Cheriyan, J.; Mehlhorn, K. (1996), "Algorithms for dense graphs and networks on the random access computer", Algorithmica, 15 (6): 521–549, doi:10.1007/BF01940880, S2CID 8930091.
• Dijkstra, Edsger (1976), A Discipline of Programming, NJ: Prentice Hall, Ch. 25.
• Gabow, Harold N. (2000), "Path-based depth-first search for strong and biconnected components" (PDF), Information Processing Letters, 74 (3–4): 107–114, doi:10.1016/S0020-0190(00)00051-X, MR 1761551.
• Munro, Ian (1971), "Efficient determination of the transitive closure of a directed graph", Information Processing Letters, 1 (2): 56–58, doi:10.1016/0020-0190(71)90006-8.
• Purdom, P. Jr. (1970), "A transitive closure algorithm", BIT, 10: 76–94, doi:10.1007/bf01940892, S2CID 20818200.
• Sedgewick, R. (2004), "19.8 Strong Components in Digraphs", Algorithms in Java, Part 5 – Graph Algorithms (3rd ed.), Cambridge MA: Addison-Wesley, pp. 205–216.