org.jscience.computing.graph.algorithms
Class CycleDetector

java.lang.Object
  extended by org.jscience.computing.graph.algorithms.CycleDetector

public class CycleDetector
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

Constructor Summary
CycleDetector(DirectedGraph graph)
          Creates a cycle detector for the specified graph.
 
Method Summary
 boolean detectCycles()
          Performs yes/no cycle detection on the entire graph.
 boolean detectCyclesContainingVertex(java.lang.Object v)
          Performs yes/no cycle detection on an individual vertex.
 java.util.Set findCycles()
          Finds the vertex set for the subgraph of all cycles.
 java.util.Set findCyclesContainingVertex(java.lang.Object 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 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(java.lang.Object 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 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 findCyclesContainingVertex(java.lang.Object 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