Transitive closure

The transitive closure of a relation contains exactly the pairs linked by a finite chain of relation steps. In a directed graph, it records which vertices are reachable from which others.

Reachability: The existence of a path from one vertex or state to another. The closure encodes reachability for every pair of vertices.
Binary relation: A set of ordered pairs drawn from two sets, often one set paired with itself. A graph's edges define a binary relation whose closure is being formed.
Dependency graph: A directed graph representing prerequisite, dependence, or ordering relationships among entities. Its closure lists dependencies that hold through chains of intermediate tasks or components.
Reflexive transitive closure: The smallest reflexive and transitive relation containing a given relation. Unlike positive-length reachability, it includes every element's pair with itself.
Warshall's algorithm: A dynamic programming algorithm that computes reachability between all vertex pairs in a directed graph. It builds the closure by allowing intermediate vertices one at a time.
Transitive relation: A relation where xRy and yRz always imply xRz. The closure is the smallest transitive relation containing the original relation.
Dataflow analysis: A compiler technique that computes information flowing through a program's control-flow graph. Reachability helps determine which statements can influence other statements.
Transitive reduction: A minimal edge relation that preserves a directed graph's reachability relation. It removes redundant edges, reversing closure's expansion into all reachable pairs.
Boolean matrix multiplication: Matrix multiplication using logical OR for addition and logical AND for multiplication. Powers of an adjacency matrix reveal paths of increasing lengths.
Directed graph: A graph whose edges have directions, each running from one vertex to another. Directed edges provide the paths whose endpoint pairs enter the closure.

Linked from 9 pages