View source for Transitive closure of a directed graph

== Formulation of the problem ==

Let <math>G = (V, E)</math>  be a directed graph. The sequence <math>P(u, v)</math> of edges <math>e_1 = (u, w_1)</math>, <math>e_2 = (w_1, w_2)</math>, …, <math>e_k = (w_{k-1}, v)</math> is called a "path'' from the vertex <math>u</math> to <math>v</math>. We say that 
<math>v</math> is ''reachable'' from <math>u</math> if there exists at least one path <math>P(u, v)</math>. Each vertex is reachable from itself. 

It is required to construct the '''transitive closure''' <math>G^+ = (V, E^+)</math> of the graph <math>G</math>; namely,  an edge <math>(v, w) \in E^+</math> if and only if the vertex <math>w</math> is reachable in the graph <math>G</math> from the vertex <math>v</math>.

An equivalent formulation is as follows: Given a reflexive binary relation <math>R</math>, construct the minimal (with respect to inclusion) relation  <math>R^+</math> that contains <math>R</math> and has the transitivity property; that is, if <math>aR^+b</math> and <math>bR^+c</math>, then  <math>aR^+c</math>. If the original relation <math>R</math> is symmetric, then <math>R^+</math> is an equivalence relation, and it suffices to find the corresponding equivalence classes. 

== Properties of the problem ==

If vertices <math>v</math> and <math>w</math> belong to the same [[Связность в графах|strongly connected component]] of the graph <math>G</math>, then the transitive closure contains the edges <math>(v, w)</math> and <math>(w, v)</math>. In an undirected graph, the edge <math>(v, w)</math> belongs to the transitive closure if and only if the vertices <math>v</math> and <math>w</math> belong to the same connected component. Consequently, for an undirected graph, the search for transitive closure is equivalent to finding connected components.

If vertices <math>x</math> and <math>y</math> belong to the same strongly connected component of the graph <math>G</math>, while vertices <math>z</math> and <math>t</math> belong to the other component, then the edges <math>(x, z)</math>, <math>(x, t)</math>, <math>(y, z)</math>, and <math>(y, t)</math> simultaneously belong or not belong to the transitive closure <math>G^+</math>. It follows that the search for the transitive closure of the graph <math>G</math> can be reduced to finding the transitive closure of the acyclic graph obtained from <math>G</math> by merging each strongly connected component into a single vertex. This idea underlies Purdom's algorithm [[алгоритм Пурдома]].

In terms of vertices, the graph <math>G</math> and its transitive closure <math>G^+</math> have the same strongly connected components.

== Algorithms for solving the problem ==

In an '''undirected''' graph, a vertex <math>w</math> is reachable from a vertex <math>v</math> if and only if both belong to the same connected component. The transitive closure of such graph reduces to finding its [[Связность в графах| connected components]] and can be constructed by the following algorithms:
* a systematic application of the [[Поиск в ширину (BFS)|breadth first search]]. The time complexity is <math>O(m)</math>;
* the use of a [[Система непересекающихся множеств|system of disjoint sets]]<ref>Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.</ref> The time complexity is <math>O(m \alpha(m, n))</math>. An effective multithreaded implementation is possible <ref>Anderson, Richard J, and Heather Woll. “Wait-Free Parallel Algorithms for the Union-Find Problem,” 370–80, New York, New York, USA: ACM Press, 1991. doi:10.1145/103418.103458.</ref>;
* the parallel algorithm of [[Алгоритм Шилоаха-Вишкина поиска компонент связности|Shiloach-Vishkin]]<ref>Shiloach, Yossi, and Uzi Vishkin. “An <math>O(\log n)</math> Parallel Connectivity Algorithm.” Journal of Algorithms 3, no. 1 (March 1982): 57–67. doi:10.1016/0196-6774(82)90008-6.</ref> The time complexity is <math>O(\ln n)</math>, provided that <math>n + 2m</math> processors are used.

For a '''directed''' graph, the transitive closure can be reduced to the search for shortest paths in a graph with unit weights. It can then be found by the following algorithms: 
* '''[[Алгоритм Флойда-Уоршелла|Floyd--Warshall algorithm]]'''<ref>Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.</ref><ref>Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.</ref>. The complexity is <math>O(n^3)</math>. (The first published algorithm for transitive closure <ref>Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.</ref> is exactly the Floyd--Warshall algorithm for graphs with unit weights);
* a repeated application of the '''[[Поиск в ширину (BFS)|breadth first search]]'''. The complexity is <math>O(mn)</math>;
* '''[[Purdom's algorithm]]'''<ref name=Purdom>Purdom, Paul, Jr. “A Transitive Closure Algorithm.” Bit 10, no. 1 (March 1970): 76–94. doi:10.1007/BF01940892.</ref>.  The complexity is <math>O(m + \mu n)</math>.

Notation: <math>m</math>  is the number of edges, <math>n</math> is the number of vertices, and <math>\mu \le m</math> is the number of edges that connect [[Связность в графах|strongly connected components]].

== Parallelization resource ==

The problem can be solved by applying the [[Поиск в ширину (BFS)|breadth first search]] to all the vertices of the graph. For different vertices, the calculations are independent and may be performed in parallel. 

Since the size of the output data and the complexity of calculations are quadratic, it makes sense to perform a preliminary processing of the data and use various graph decompositions in order to reduce the original problem to the parallel finding of shortest paths on smaller subgraphs <ref>Banerjee, Dip Sankar, Ashutosh Kumar, Meher Chaitanya, Shashank Sharma, and Kishore Kothapalli. “Work Efficient Parallel Algorithms for Large Graph Exploration on Emerging Heterogeneous Architectures.” Journal of Parallel and Distributed Computing, December 2014. doi:10.1016/j.jpdc.2014.11.006.</ref>: 
* [[Алгоритм Шилоаха-Вишкина поиска компонент связности|selection of connected components]];
* [[Алгоритм Тарьяна поиска «мостов» в графе| selection of subgraphs connected only by bridges]] (that is, by edges whose removal makes the graph disconnected);
* [[Алгоритм Тарьяна поиска компонент двусвязности|selection of biconnected components]] connected only by joints (also called articulation points or cut vertices; these are vertices вершины, whose removal makes the graph disconnected);
* removal of hanging vertices (that is, vertices having at most one adjacent vertex).

Which decompositions are advantageous in a specific situation depends on the structure of the graph and can be determined only by analyzing this structure. 

== References ==
<references />

[[Category:Articles in progress]]

[[Ru: Поиск транзитивного замыкания орграфа]]