Applications Of Strongly Connected Components

Division of a graph whose components are reachable from all vertices

Graph with strongly continued components marked

In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly continued components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the potent connectivity of a graph, or to observe its strongly connected components, in linear time (that is, Θ(V +Due east)).

Definitions [edit]

A directed graph is called strongly connected if in that location 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 some other path exists from the 2d vertex to the first. In a directed graph G that may non 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 continued 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 maximal with this property: no additional edges or vertices from G tin can exist included in the subgraph without breaking its holding of being strongly connected. The collection of strongly connected components forms a division of the set of vertices of G. A strongly connected component $C$ is called trivial when $C$ consists of a unmarried vertex which is not connected to itself with an edge and non-little otherwise.^[ane]

The yellow directed acyclic graph is the condensation of the bluish directed graph. It is formed by contracting each strongly connected component of the blue graph into a single yellow vertex.

If each strongly continued component is contracted to a single vertex, the resulting graph is a directed acyclic graph, the condensation of Chiliad. A directed graph is acyclic if and but if it has no strongly connected subgraphs with more than one vertex, because a directed cycle is strongly connected and every non-petty strongly continued component contains at to the lowest degree one directed wheel.

Algorithms [edit]

DFS-based linear-time algorithms [edit]

Several algorithms based on depth-first search compute strongly continued components in linear time.

Kosaraju's algorithm uses two passes of depth-start search. The first, in the original graph, is used to choose the order in which the outer loop of the second depth-showtime search tests vertices for having been visited already and recursively explores them if not. The 2nd depth-offset search is on the transpose graph of the original graph, and each recursive exploration finds a single new strongly connected component.^[2] ^[three] It is named after Due south. Rao Kosaraju, who described information technology (but did not publish his results) in 1978; Micha Sharir later on published it in 1981.^[4]
Tarjan'due south strongly connected components algorithm, published by Robert Tarjan in 1972,^[5] performs a unmarried pass of depth-beginning search. Information technology maintains a stack of vertices that have been explored by the search merely not yet assigned to a component, and calculates "low numbers" of each vertex (an alphabetize number of the highest antecedent reachable in one step from a descendant of the vertex) which it uses to make up one's mind when a set up of vertices should be popped off the stack into a new component.
The path-based strong component algorithm uses a depth-showtime search, similar Tarjan's algorithm, merely with 2 stacks. One of the stacks is used to keep track of the vertices non nevertheless 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 unproblematic, Tarjan's and the path-based algorithm require simply 1 depth-kickoff search rather than two.

Reachability-based algorithms [edit]

Previous linear-time algorithms are based on depth-get-go search which is more often than not considered hard to parallelize. Fleischer et al.^[7] in 2000 proposed a divide-and-conquer arroyo based on reachability queries, and such algorithms are commonly chosen reachability-based SCC algorithms. The idea of this approach is to pick a random pivot vertex and apply forrard and backward reachability queries from this vertex. The two queries partition the vertex set into four subsets: vertices reached past both, either one, or none of the searches. One tin can bear witness that a strongly continued component has to be contained in one of the subsets. The vertex subset reached by both searches forms a strongly connected component, and the algorithm then recurses on the other three subsets.

The expected sequential running fourth dimension of this algorithm is shown to be O(n logn), a factor of O(logn) more than the archetype algorithms. The parallelism comes from: (i) the reachability queries tin can be parallelized more easily (e.g. past a breadth-get-go search (BFS), and information technology can be fast if the bore of the graph is small); and (ii) the independence between the subtasks in the separate-and-conquer process. This algorithm performs well on existent-world graphs,^[3] but does not have theoretical guarantee on the parallelism (consider if a graph has no edges, the algorithm requires O(n) levels of recursions).

Blelloch et al.^[viii] in 2016 shows that if the reachability queries are applied in a random order, the toll spring of O(n logn) notwithstanding holds. Furthermore, the queries then can be batched in a prefix-doubling manner (i.e. 1, 2, 4, eight queries) and run simultaneously in one round. The overall span of this algorithm is log_ii northward reachability queries, which is probably the optimal parallelism that can exist achieved using the reachability-based approach.

Generating random strongly continued graphs [edit]

Peter G. 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 whatever strongly connected graph on n nodes, without restriction on the kinds of structures that can exist generated.

Applications [edit]

Algorithms for finding strongly connected components may be used to solve two-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 just if there is a variable v such that five and its complement are both contained in the same strongly continued component of the implication graph of the instance.^[10]

Strongly connected components are also used to compute the Dulmage–Mendelsohn decomposition, a nomenclature of the edges of a bipartite graph, according to whether or not they tin be part of a perfect matching in the graph.^[11]

[edit]

A directed graph is strongly continued 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 bike sharing i vertex with previous subgraphs, or a path sharing its two endpoints with previous subgraphs.

Co-ordinate to Robbins' theorem, an undirected graph may be oriented in such a way that it becomes strongly connected, if and simply if it is two-edge-continued. One way to prove this result is to detect an ear decomposition of the underlying undirected graph and and then orient each ear consistently.^[12]

Run across also [edit]

Clique (graph theory)
Connected component (graph theory)
Modular decomposition
Weak component

References [edit]

^ https://www.fi.muni.cz/reports/files/2010/FIMU-RS-2010-10.pdf^{[ bare URL PDF ]}
^ Thomas H. Cormen, Charles Eastward. Leiserson, Ronald Fifty. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Printing and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.5, pp. 552–557.
^ ^a ^b Hong, Sungpack; Rodia, Nicole C.; Olukotun, Kunle (2013), "On fast parallel detection of strongly continued components (SCC) in small-globe graphs" (PDF), Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis - SC '13, pp. 1–11, doi:10.1145/2503210.2503246, ISBN9781450323789, S2CID 2156324
^ Sharir, Micha (1981), "A stiff-connectivity algorithm and its applications in data catamenia assay", Computers & Mathematics with Applications, 7: 67–72, doi:10.1016/0898-1221(81)90008-0
^ Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing, one (two): 146–160, doi:10.1137/0201010
^ Dijkstra, Edsger (1976), A Field of study of Programming, NJ: Prentice Hall, Ch. 25 .
^ Fleischer, Lisa K.; Hendrickson, Bruce; Pınar, Ali (2000), "On Identifying Strongly Continued Components in Parallel" (PDF), Parallel and Distributed Processing, Lecture Notes in Reckoner Science, vol. 1800, pp. 505–511, doi:10.1007/3-540-45591-4_68, ISBN978-3-540-67442-9
^ Blelloch, Guy E.; Gu, Yan; Shun, Julian; Lord's day, Yihan (2016), "Parallelism in Randomized Incremental Algorithms" (PDF), Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures - SPAA 'xvi, pp. 467–478, doi:10.1145/2935764.2935766, ISBN9781450342100 .
^ Maurer, P. Thou., Generating strongly continued random graphs (PDF), Int'l Conf. Modeling, Sim. and Vis. Methods MSV'17, CSREA Press, ISBN1-60132-465-0 , retrieved December 27, 2019
^ Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert Eastward. (1979), "A linear-time algorithm for testing the truth of certain quantified boolean formulas", Information Processing Letters, 8 (iii): 121–123, doi:10.1016/0020-0190(79)90002-4 .
^ Dulmage, A. 50. & Mendelsohn, Northward. S. (1958), "Coverings of bipartite graphs", Can. J. Math., 10: 517–534, doi:10.4153/cjm-1958-052-0, S2CID 123363425 .
^ Robbins, H. East. (1939), "A theorem on graphs, with an awarding to a trouble on traffic control", American Mathematical Monthly, 46 (5): 281–283, doi:x.2307/2303897, JSTOR 2303897 .

External links [edit]

Coffee implementation for ciphering of strongly continued components in the jBPT library (run into StronglyConnectedComponents class).
C++ implementation of Strongly Connected Components