The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.4.5 Transitive Closure and Reduction

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: A directed graph G=(V,E).

Problem: For transitive closure, construct a graph G'=(V,E') with edge (i,j) \in E' iff there is a directed path from i to j in G. For transitive reduction, construct a small graph G'=(V,E') with a directed path from i to j in G' iff (i,j) \in E.

Excerpt from The Algorithm Design Manual: Transitive closure can be thought of as establishing a data structure that makes it possible to solve reachability questions (can I get to x from y?) efficiently. After the preprocessing of constructing the transitive closure, all reachability queries can be answered in constant time by simply reporting a matrix entry. Transitive closure is fundamental in propagating the consequences of modified attributes of a graph G. For example, consider the graph underlying any spreadsheet model, where the vertices are cells and there is an edge from cell $i$ to cell j if the result of cell j depends on cell i. When the value of a given cell is modified, the values of all reachable cells must also be updated. The identity of these cells is revealed by the transitive closure of G. Many database problems reduce to computing transitive closures, for analogous reasons.


Implementations

  • Boost: C++ Libraries (C++) (rating 10)
  • Scott Cotton's graphlib (Java) (rating 8)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 5)
  • Combinatorica (Mathematica) (rating 4)

  • Recommended Books

    Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica by S. Pemmaraju and S. Skiena Handbook of Theoretical Computer Science : Algorithms and Complexity by J. Van Leeuwen The Design and Analysis of Computer Algorithms by A. Aho and J. Hopcroft and J. Ullman

    Related Problems


      
    Connected Components
      
    Shortest Path



    This page last modified on 2008-07-10 .
    www.algorist.com