public class TransitiveClosure extends Object
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 Θ(V^{2}) 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 |
---|
TransitiveClosure(Digraph G)
Computes the transitive closure of the digraph
G . |
Modifier and Type | Method and Description |
---|---|
static void |
main(String[] args)
Unit tests the
TransitiveClosure data type. |
boolean |
reachable(int v,
int w)
Is there a directed path from vertex
v to vertex w in the digraph? |
public TransitiveClosure(Digraph G)
G
.G
- the digraphpublic boolean reachable(int v, int w)
v
to vertex w
in the digraph?v
- the source vertexw
- the target vertextrue
if there is a directed path from v
to w
,
false
otherwiseIllegalArgumentException
- unless 0 <= v < V
IllegalArgumentException
- unless 0 <= w < V
public static void main(String[] args)
TransitiveClosure
data type.args
- the command-line arguments