Package org.jgrapht.alg
Class CycleDetector<V,E>
- java.lang.Object
-
- org.jgrapht.alg.CycleDetector<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
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
-
-
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 class
CycleDetector.ProbeIterator
Version of DFS which maintains a backtracking path used to probe for cycles.
-
Field Summary
Fields Modifier and Type Field Description (package private) DirectedGraph<V,E>
graph
Graph on which cycle detection is being performed.
-
Constructor Summary
Constructors Constructor Description CycleDetector(DirectedGraph<V,E> graph)
Creates a cycle detector for the specified graph.
-
Method Summary
All Methods Instance Methods Concrete Methods 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(java.util.Set<V> s, V v)
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.
-
-
-
Field Detail
-
graph
DirectedGraph<V,E> graph
Graph on which cycle detection is being performed.
-
-
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.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
-
-