edu.princeton.cs.algorithms

Class TransitiveClosure

java.lang.Object

edu.princeton.cs.algorithms.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 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 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

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 java.lang.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

main

public static void main(String[] args)

Unit tests the TransitiveClosure data type.