java.lang.Object
org.jgrapht.alg.cycle.SzwarcfiterLauerSimpleCycles<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 Schwarcfiter and Lauer's algorithm.
See:
J.L.Szwarcfiter and P.E.Lauer, Finding the elementary cycles of a directed graph in $O(n + m)$
per cycle, Technical Report Series, #60, May 1974, Univ. of Newcastle upon Tyne, Newcastle upon
Tyne, England.
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate V[]
private int[]
private boolean[]
private ArrayDeque
<V> -
Constructor Summary
ConstructorsConstructorDescriptionCreate a simple cycle finder with an unspecified graph.SzwarcfiterLauerSimpleCycles
(Graph<V, E> graph) Create a simple cycle finder for the specified graph. -
Method Summary
Modifier and TypeMethodDescriptionprivate void
private boolean
cycle
(int v, int q) void
findSimpleCycles
(Consumer<List<V>> consumer) Find the simple cycles of the graph.getGraph()
Get the graphgetRemoved
(V v) private void
private void
noCycle
(int x, int y) void
Set the graphprivate Integer
private V
toV
(int i) private void
unmark
(int x) 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
-
bSets
-
stack
-
marked
-
removed
-
position
private int[] position -
reach
private boolean[] reach -
startVertices
-
-
Constructor Details
-
SzwarcfiterLauerSimpleCycles
public SzwarcfiterLauerSimpleCycles()Create a simple cycle finder with an unspecified graph. -
SzwarcfiterLauerSimpleCycles
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
-
getGraph
Get the graph- Returns:
- graph
-
setGraph
Set the graph- Parameters:
graph
- graph
-
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.
-
cycle
private boolean cycle(int v, int q) -
noCycle
private void noCycle(int x, int y) -
unmark
private void unmark(int x) -
initState
-
clearState
private void clearState() -
toI
-
toV
-
getBSet
-
getRemoved
-