Class CycleDetector<V,E>

java.lang.Object

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

Type Parameters:

V - the graph vertex type

E - the graph edge type

public class CycleDetector<V,E>
extends 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.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static class	CycleDetector.CycleDetectedException	Exception thrown internally when a cycle is detected during a yes/no cycle test.
private static class	CycleDetector.ProbeIterator<V,E>	Version of DFS which maintains a backtracking path used to probe for cycles.

Field Summary

Fields

Modifier and Type	Field	Description
private Graph<V,E>	graph	Graph on which cycle detection is being performed.

Constructor Summary

Constructors

Constructor	Description
CycleDetector(Graph<V,E> graph)	Creates a cycle detector for the specified graph.

Method Summary

Modifier and Type	Method	Description
boolean	detectCycles()	Performs yes/no cycle detection on the entire graph.
boolean	detectCyclesContainingVertex(V v)	Performs yes/no cycle detection on an individual vertex.
private void	execute(Set<V> s, V v)
Set<V>	findCycles()	Finds the vertex set for the subgraph of all cycles.
Set<V>	findCyclesContainingVertex(V v)	Finds the vertex set for the subgraph of all cycles which contain a particular vertex.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

graph

private Graph<V,E> graph

Graph on which cycle detection is being performed.

Constructor Details

CycleDetector

public CycleDetector(Graph<V,E> graph)

Creates a cycle detector for the specified graph. Currently only directed graphs are supported.

Parameters:

graph - the directed graph in which to detect cycles

Method Details

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 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 Set<V> findCyclesContainingVertex(V v)

Finds the vertex set for the subgraph of all cycles which contain a particular vertex.

REVIEW jvs 25-Aug-2006: This implementation is not guaranteed to cover all cases. If you want to be absolutely certain that you report vertices from all cycles containing v, it's safer (but less efficient) to use StrongConnectivityAlgorithm instead and return the strongly connected component containing v.

Parameters:

v - the vertex to test

Returns:

set of all vertices reachable from v via at least one cycle

execute

private void execute(Set<V> s,
 V v)