java.lang.Object
org.jgrapht.alg.cycle.JohnsonSimpleCycles<V,E>
- Type Parameters:
V
- the vertex type.E
- the edge type.
- All Implemented Interfaces:
DirectedSimpleCycles<V,
E>
Find all simple cycles of a directed graph using the Johnson's algorithm.
See:
D.B.Johnson, Finding all the elementary circuits of a directed graph, SIAM J. Comput., 4 (1975),
pp. 77-84.
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate int
private V[]
private ArrayDeque
<V> private ArrayDeque
<V> -
Constructor Summary
ConstructorsConstructorDescriptionJohnsonSimpleCycles
(Graph<V, E> graph) Create a simple cycle finder for the specified graph. -
Method Summary
Modifier and TypeMethodDescriptionprivate void
private void
private boolean
findCyclesInSCG
(int startIndex, int vertexIndex, Graph<V, E> scg) findMinSCSG
(int startIndex) findSCCS
(int startIndex) void
findSimpleCycles
(Consumer<List<V>> consumer) Find the simple cycles of the graph.private void
getSCCs
(int startIndex, int vertexIndex) private void
private void
private Integer
private V
private void
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface org.jgrapht.alg.cycle.DirectedSimpleCycles
findSimpleCycles
-
Field Details
-
graph
-
cycleConsumer
-
iToV
-
vToI
-
blocked
-
bSets
-
stack
-
foundSCCs
-
index
private int index -
vIndex
-
vLowlink
-
path
-
pathSet
-
-
Constructor Details
-
JohnsonSimpleCycles
Create a simple cycle finder for the specified graph.- Parameters:
graph
- - the DirectedGraph in which to find cycles.- Throws:
IllegalArgumentException
- if the graph argument isnull
.
-
-
Method Details
-
findSimpleCycles
Find the simple cycles of the graph.- Specified by:
findSimpleCycles
in interfaceDirectedSimpleCycles<V,
E> - Parameters:
consumer
- Consumer that will be called with each cycle found.
-
findMinSCSG
-
findSCCS
-
getSCCs
private void getSCCs(int startIndex, int vertexIndex) -
findCyclesInSCG
-
unblock
-
initState
-
clearState
private void clearState() -
initMinSCGState
private void initMinSCGState() -
clearMinSCCState
private void clearMinSCCState() -
toI
-
toV
-
getBSet
-