org.jgrapht.alg
Class CycleDetector<V,E>

java.lang.Object
  extended by org.jgrapht.alg.CycleDetector<V,E>

public class CycleDetector<V,E>
extends java.lang.Object

Performs cycle detection on a graph. The inspected graph is specified at construction time and cannot be modified. Currently, the detector supports only directed graphs.

Since:
Sept 16, 2004
Author:
John V. Sichi

Constructor Summary
CycleDetector(DirectedGraph<V,E> graph)
          Creates a cycle detector for the specified graph.
 
Method Summary
 boolean detectCycles()
          Performs yes/no cycle detection on the entire graph.
 boolean detectCyclesContainingVertex(V v)
          Performs yes/no cycle detection on an individual vertex.
 java.util.Set<V> findCycles()
          Finds the vertex set for the subgraph of all cycles.
 java.util.Set<V> findCyclesContainingVertex(V v)
          Finds the vertex set for the subgraph of all cycles which contain a particular vertex.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

CycleDetector

public CycleDetector(DirectedGraph<V,E> graph)
Creates a cycle detector for the specified graph. Currently only directed graphs are supported.

Parameters:
graph - the DirectedGraph in which to detect cycles
Method Detail

detectCycles

public boolean detectCycles()
Performs yes/no cycle detection on the entire graph.

Returns:
true iff the graph contains at least one cycle

detectCyclesContainingVertex

public boolean detectCyclesContainingVertex(V v)
Performs yes/no cycle detection on an individual vertex.

Parameters:
v - the vertex to test
Returns:
true if v is on at least one cycle

findCycles

public java.util.Set<V> findCycles()
Finds the vertex set for the subgraph of all cycles.

Returns:
set of all vertices which participate in at least one cycle in this graph

findCyclesContainingVertex

public java.util.Set<V> findCyclesContainingVertex(V v)
Finds the vertex set for the subgraph of all cycles which contain a particular vertex.

Parameters:
v - the vertex to test
Returns:
set of all vertices reachable from v via at least one cycle