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 time proportional to V(V + E) (in the worst case) and uses space proportional to V2, where V is the number of vertices and E is the number of edges.
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