edu.princeton.cs.algs4

Class TransitiveClosure

java.lang.Object

edu.princeton.cs.algs4.TransitiveClosure

public class TransitiveClosure
extends java.lang.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 time proportional to V(V + E) (in the worst case) and uses space proportional to V², 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 Summary

Constructors

Constructor and Description
TransitiveClosure(Digraph G) Computes the transitive closure of the digraph G.

Method Summary

Modifier and Type	Method and Description
static void	main(java.lang.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 java.lang.Object

equals, 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:

java.lang.IllegalArgumentException - unless 0 <= v < V

java.lang.IllegalArgumentException - unless 0 <= w < V

main

public static void main(java.lang.String[] args)

Unit tests the TransitiveClosure data type.

Parameters:

args - the command-line arguments