Transitive closure
What is transitive closure?
Consider a directed graph G=(V,E), where V is the
set of vertices and E is the set of
edges. The transitive closure of G is a graph G+ =
(V,E+) such that for all v,w in V there is an edge
(v,w) in E+ if and only if there is a non-null path from
v to w in G.
Why and where is it needed?
Finding the transitive closure of a directed graph is an important
problem in many computational tasks. It is required, for instance, in
the reachability analysis of transition networks representing
distributed and parallel systems and in the construction of parsing
automata in compiler construction. Recently, efficient transitive
closure computation has been recognized as a significant subproblem in
evaluating recursive database queries, since almost all practical
recursive queries are transitive.
Despite the increased efficiency of computers the need for faster
transitive closure algorithms remains. This is for two reasons. First,
the size of the inputs seems to grow in proportion to the growth of
the memory capacity. Since the CPU speed has grown at the same rate as
the memory capacity, only linear algoritms retain their execution
times on typical inputs. Traditional transitive closure algorithms,
such as Warshall's algorithm, are not linear. Second, typical inputs
(and outputs) in the area of databases do not fit into the main
memory. Traditional transitive closure algorithms are mostly designed
for main memory operation.
To find out more about transitive closure computation, read my PhD
thesis Efficient Transitive Closure
Computation in Large Digraphs. In the thesis, I describe the
transitive closure problem and other related problems and give an
extensive listing of previous transitive closure algorithms and data
representations. My main contributions are two new efficient
transitive closure algorithms and two new compact transitive closure
representations for cyclic digraphs. I show analytically and
experimentally that my new algorithm STACK_TC and the so called
interval representation are more efficient than previous algorithms
and representations.
You can also check the following articles and reports:
- Esko Nuutila, An efficient
transitive closure algorithm for cyclic digraphs, Information
Processing Letters 52 (1994) 207-213. (596K PostScript
file). In this article, I describe a very efficient transitive closure
algorithm that is based on strong component detection and compare it
to Schmitz's algorithm.
- Esko Nuutila and Eljas Soisalon-Soininen, A Single-Pass Algorithm for Transitive
Closure, Helsinki University of Technology, Laboratory of
Information Processing Science, Technical Report TKO-B95, 1993.
(208K PostScript file). A previous version of the algorithm.
- Esko Nuutila and Eljas Soisalon-Soininen, Efficient Transitive Closure Computation,
Helsinki University of Technology, Laboratory of
Information Processing Science, Technical Report TKO-B113, 1993.
(208K PostScript file). Presents another version of the algorithm and
the interval representation. Contains interesting test results showing
that the interval representation outperforms the traditional
representations.
- Esko Nuutila and Eljas Soisalon-Soininen, On finding the strongly connected components in a
directed graph, Information Processing Letters 49 (1993)
9-14. (137K PostScript file). In this article, we present improvements
on Tarjan's strong component detection algorithm.
- Esko Nuutila and Eljas Soisalon-Soininen, On Finding the Strong Components in a
Directed Graph, Helsinki University of Technology, Laboratory of
Information Processing Science, Technical Report TKO-B94, 1993.
(446K PostScript file). A more thorough elaboration on the same
subject.
- Esko Nuutila,
An experimental study on transitive closure representations, Helsinki University of Technology, Laboratory of
Information Processing Science, Technical Report TKO-B134, 1996.
(1MB PostScript file).
- Vesa Hirvisalo, Esko Nuutila, Eljas Soisalon-Soininen
Transitive closure algorithm DISK_TC and its performance analysis, Helsinki University of Technology, Laboratory of
Information Processing Science, Technical Report TKO-B135, 1996.
(1.5MB PostScript file). Describes the disk behavior of the algorithm
DISK_TC
Back to Esko's homepage.
Last modified: Oct. 9, 1995
enu@cs.hut.fi