Class TransitiveClosure

  • public class TransitiveClosure
    extends Object
    The TransitiveClosure class represents a data type for computing the transitive closure of a digraph.

    This implementation runs depth-first search from each vertex. The constructor takes Θ(V(V + E)) in the worst case, where V is the number of vertices and E is the number of edges. Each instance method takes Θ(1) time. It uses Θ(V2) extra space (not including the digraph).

    For large digraphs, you may want to consider a more sophisticated algorithm. Nuutila proposes two algorithm for the problem (based on strong components and an interval representation) that runs in Θ(E + V) time on typical digraphs. For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    Robert Sedgewick, Kevin Wayne
    • Constructor Detail

      • TransitiveClosure

        public TransitiveClosure​(Digraph G)
        Computes the transitive closure of the digraph G.
        G - the digraph
    • Method Detail

      • reachable

        public boolean reachable​(int v,
                                 int w)
        Is there a directed path from vertex v to vertex w in the digraph?
        v - the source vertex
        w - the target vertex
        true if there is a directed path from v to w, false otherwise
        IllegalArgumentException - unless 0 <= v < V
        IllegalArgumentException - unless 0 <= w < V
      • main

        public static void main​(String[] args)
        Unit tests the TransitiveClosure data type.
        args - the command-line arguments