Strongly connected component
Relevant topics on |
Graph connectivity |
---|
In the
Definitions
A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph. That is, a path exists from the first vertex in the pair to the second, and another path exists from the second vertex to the first. In a directed graph G that may not itself be strongly connected, a pair of vertices u and v are said to be strongly connected to each other if there is a path in each direction between them.
The binary relation of being strongly connected is an equivalence relation, and the induced subgraphs of its equivalence classes are called strongly connected components. Equivalently, a strongly connected component of a directed graph G is a subgraph that is strongly connected, and is
If each strongly connected component is
Algorithms
DFS-based linear-time algorithms
Several algorithms based on depth-first search compute strongly connected components in linear time.
- Kosaraju's algorithm uses two passes of depth-first search. The first, in the original graph, is used to choose the order in which the outer loop of the second depth-first search tests vertices for having been visited already and recursively explores them if not. The second depth-first search is on the transpose graph of the original graph, and each recursive exploration finds a single new strongly connected component.[2][3] It is named after S. Rao Kosaraju, who described it (but did not publish his results) in 1978; Micha Sharir later published it in 1981.[4]
- Tarjan's strongly connected components algorithm, published by Robert Tarjan in 1972,[5] performs a single pass of depth-first search. It maintains a stack of vertices that have been explored by the search but not yet assigned to a component, and calculates "low numbers" of each vertex (an index number of the highest ancestor reachable in one step from a descendant of the vertex) which it uses to determine when a set of vertices should be popped off the stack into a new component.
- The path-based strong component algorithm uses a depth-first search, like Tarjan's algorithm, but with two stacks. One of the stacks is used to keep track of the vertices not yet assigned to components, while the other keeps track of the current path in the depth-first search tree. The first linear time version of this algorithm was published by Edsger W. Dijkstra in 1976.[6]
Although Kosaraju's algorithm is conceptually simple, Tarjan's and the path-based algorithm require only one depth-first search rather than two.
Reachability-based algorithms
Previous linear-time algorithms are based on depth-first search which is generally considered hard to parallelize. Fleischer et al.
The expected sequential running time of this algorithm is shown to be O(n log n), a factor of O(log n) more than the classic algorithms. The parallelism comes from: (1) the reachability queries can be parallelized more easily (e.g. by a
Blelloch et al.[8] in 2016 shows that if the reachability queries are applied in a random order, the cost bound of O(n log n) still holds. Furthermore, the queries then can be batched in a prefix-doubling manner (i.e. 1, 2, 4, 8 queries) and run simultaneously in one round. The overall span of this algorithm is log2 n reachability queries, which is probably the optimal parallelism that can be achieved using the reachability-based approach.
Generating random strongly connected graphs
Peter M. Maurer describes an algorithm for generating random strongly connected graphs,[9] based on a modification of an algorithm for strong connectivity augmentation, the problem of adding as few edges as possible to make a graph strongly connected. When used in conjunction with the Gilbert or Erdős-Rényi models with node relabelling, the algorithm is capable of generating any strongly connected graph on n nodes, without restriction on the kinds of structures that can be generated.
Applications
Algorithms for finding strongly connected components may be used to solve 2-satisfiability problems (systems of Boolean variables with constraints on the values of pairs of variables): as Aspvall, Plass & Tarjan (1979) showed, a 2-satisfiability instance is unsatisfiable if and only if there is a variable v such that v and its complement are both contained in the same strongly connected component of the implication graph of the instance.[10]
Strongly connected components are also used to compute the Dulmage–Mendelsohn decomposition, a classification of the edges of a bipartite graph, according to whether or not they can be part of a perfect matching in the graph.[11]
Related results
A directed graph is strongly connected if and only if it has an ear decomposition, a partition of the edges into a sequence of directed paths and cycles such that the first subgraph in the sequence is a cycle, and each subsequent subgraph is either a cycle sharing one vertex with previous subgraphs, or a path sharing its two endpoints with previous subgraphs.
According to
See also
- Clique (graph theory)
- Connected component (graph theory)
- Modular decomposition
- Weak component
References
- ISBN 0-262-03293-7. Section 22.5, pp. 552–557.
- ^ S2CID 2156324
- S2CID 16467262
- Dijkstra, Edsger(1976), A Discipline of Programming, NJ: Prentice Hall, Ch. 25.
- ISBN 978-3-540-67442-9
- ISBN 9781450342100.
- ISBN 978-1-60132-465-8, retrieved December 27, 2019
- .
- S2CID 123363425.
- JSTOR 2303897.
External links
- Java implementation for computation of strongly connected components in the jBPT library (see StronglyConnectedComponents class).
- C++ implementation of Strongly Connected Components