edu.princeton.cs.algs4

## Class TransitiveClosure

• Object
• edu.princeton.cs.algs4.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.

Author:
Robert Sedgewick, Kevin Wayne
• ### Constructor Summary

Constructors
Constructor and Description
`TransitiveClosure(Digraph G)`
Computes the transitive closure of the digraph `G`.
• ### Method Summary

All Methods
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?
• ### Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### TransitiveClosure

`public TransitiveClosure(Digraph G)`
Computes the transitive closure of the digraph `G`.
Parameters:
`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?
Parameters:
`v` - the source vertex
`w` - the target vertex
Returns:
`true` if there is a directed path from `v` to `w`, `false` otherwise
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
`IllegalArgumentException` - unless `0 <= w < V`
• #### main

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