public class TransitiveClosure extends Object
TransitiveClosureclass 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.
|Constructor and Description|
Computes the transitive closure of the digraph
|Modifier and Type||Method and Description|
Unit tests the
Is there a directed path from vertex
public TransitiveClosure(Digraph G)
G- the digraph
public boolean reachable(int v, int w)
win the digraph?
public static void main(String args)
args- the command-line arguments