Click or drag to resize
TransitiveClosure Class

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

Inheritance Hierarchy
SystemObject
  Algs4NetTransitiveClosure

Namespace: Algs4Net
Assembly: Algs4Net (in Algs4Net.dll) Version: 1.0.0.0 (1.0.0.0)
Syntax
C#
Copy
public class TransitiveClosure

The TransitiveClosure type exposes the following members.

Constructors
  NameDescription
Public methodTransitiveClosure
Computes the transitive closure of the digraph G.
Top
Methods
  NameDescription
Public methodStatic memberMainTest
Demo test the TransitiveClosure data type.
Public methodReachable
Is there a directed path from vertex v to vertex w in the digraph?
Top
Remarks

For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

This class is a C# port from the original Java class TransitiveClosure implementation by the respective authors.

See Also