- 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>
public class SzwarcfiterLauerSimpleCycles<V,E> extends java.lang.Object implements 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
Fields Modifier and Type Field Description private java.util.Map<V,java.util.Set<V>>
bSets
private java.util.function.Consumer<java.util.List<V>>
cycleConsumer
private Graph<V,E>
graph
private V[]
iToV
private java.util.Set<V>
marked
private int[]
position
private boolean[]
reach
private java.util.Map<V,java.util.Set<V>>
removed
private java.util.ArrayDeque<V>
stack
private java.util.List<V>
startVertices
private java.util.Map<V,java.lang.Integer>
vToI
-
Constructor Summary
Constructors Constructor Description SzwarcfiterLauerSimpleCycles()
Create a simple cycle finder with an unspecified graph.SzwarcfiterLauerSimpleCycles(Graph<V,E> graph)
Create a simple cycle finder for the specified graph.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
clearState()
private boolean
cycle(int v, int q)
void
findSimpleCycles(java.util.function.Consumer<java.util.List<V>> consumer)
Find the simple cycles of the graph.private java.util.Set<V>
getBSet(V v)
Graph<V,E>
getGraph()
Get the graphprivate java.util.Set<V>
getRemoved(V v)
private void
initState(java.util.function.Consumer<java.util.List<V>> consumer)
private void
noCycle(int x, int y)
void
setGraph(Graph<V,E> graph)
Set the graphprivate java.lang.Integer
toI(V v)
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 Detail
-
cycleConsumer
private java.util.function.Consumer<java.util.List<V>> cycleConsumer
-
iToV
private V[] iToV
-
vToI
private java.util.Map<V,java.lang.Integer> vToI
-
stack
private java.util.ArrayDeque<V> stack
-
marked
private java.util.Set<V> marked
-
position
private int[] position
-
reach
private boolean[] reach
-
startVertices
private java.util.List<V> startVertices
-
-
Method Detail
-
findSimpleCycles
public void findSimpleCycles(java.util.function.Consumer<java.util.List<V>> consumer)
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
private void initState(java.util.function.Consumer<java.util.List<V>> consumer)
-
clearState
private void clearState()
-
toI
private java.lang.Integer toI(V v)
-
toV
private V toV(int i)
-
-