Package org.jgrapht.alg.cycle
Class JohnsonSimpleCycles<V,E>
- 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>
public class JohnsonSimpleCycles<V,E> extends java.lang.Object implements 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
Fields Modifier and Type Field Description private java.util.Set<V>
blocked
private java.util.Map<V,java.util.Set<V>>
bSets
private java.util.List<java.util.List<V>>
cycles
private DirectedGraph<V,E>
graph
private int
index
private V[]
iToV
private java.util.ArrayDeque<V>
path
private java.util.Set<V>
pathSet
private java.util.List<java.util.Set<V>>
SCCs
private java.util.ArrayDeque<V>
stack
private java.util.Map<V,java.lang.Integer>
vIndex
private java.util.Map<V,java.lang.Integer>
vLowlink
private java.util.Map<V,java.lang.Integer>
vToI
-
Constructor Summary
Constructors Constructor Description JohnsonSimpleCycles()
Create a simple cycle finder with an unspecified graph.JohnsonSimpleCycles(DirectedGraph<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
clearMinSCCState()
private void
clearState()
private boolean
findCyclesInSCG(int startIndex, int vertexIndex, DirectedGraph<V,E> scg)
private java.lang.Object[]
findMinSCSG(int startIndex)
private java.util.List<java.util.Set<V>>
findSCCS(int startIndex)
java.util.List<java.util.List<V>>
findSimpleCycles()
Finds the simple cycles of the graph.
Note that the full algorithm is executed on every call since the graph may have changed between calls.private java.util.Set<V>
getBSet(V v)
DirectedGraph<V,E>
getGraph()
Returns the graph on which the simple cycle search algorithm is executed by this object.private void
getSCCs(int startIndex, int vertexIndex)
private void
initMinSCGState()
private void
initState()
void
setGraph(DirectedGraph<V,E> graph)
Sets the graph on which the simple cycle search algorithm is executed by this object.private java.lang.Integer
toI(V vertex)
private V
toV(java.lang.Integer i)
private void
unblock(V vertex)
-
-
-
Field Detail
-
graph
private DirectedGraph<V,E> graph
-
cycles
private java.util.List<java.util.List<V>> cycles
-
iToV
private V[] iToV
-
vToI
private java.util.Map<V,java.lang.Integer> vToI
-
blocked
private java.util.Set<V> blocked
-
stack
private java.util.ArrayDeque<V> stack
-
SCCs
private java.util.List<java.util.Set<V>> SCCs
-
index
private int index
-
vIndex
private java.util.Map<V,java.lang.Integer> vIndex
-
vLowlink
private java.util.Map<V,java.lang.Integer> vLowlink
-
path
private java.util.ArrayDeque<V> path
-
pathSet
private java.util.Set<V> pathSet
-
-
Constructor Detail
-
JohnsonSimpleCycles
public JohnsonSimpleCycles()
Create a simple cycle finder with an unspecified graph.
-
JohnsonSimpleCycles
public JohnsonSimpleCycles(DirectedGraph<V,E> graph)
Create a simple cycle finder for the specified graph.- Parameters:
graph
- - the DirectedGraph in which to find cycles.- Throws:
java.lang.IllegalArgumentException
- if the graph argument isnull
.
-
-
Method Detail
-
getGraph
public DirectedGraph<V,E> getGraph()
Returns the graph on which the simple cycle search algorithm is executed by this object.- Specified by:
getGraph
in interfaceDirectedSimpleCycles<V,E>
- Returns:
- The graph.
-
setGraph
public void setGraph(DirectedGraph<V,E> graph)
Sets the graph on which the simple cycle search algorithm is executed by this object.- Specified by:
setGraph
in interfaceDirectedSimpleCycles<V,E>
- Parameters:
graph
- the graph.
-
findSimpleCycles
public java.util.List<java.util.List<V>> findSimpleCycles()
Finds the simple cycles of the graph.
Note that the full algorithm is executed on every call since the graph may have changed between calls.- Specified by:
findSimpleCycles
in interfaceDirectedSimpleCycles<V,E>
- Returns:
- The list of all simple cycles. Possibly empty but never
null
.
-
findMinSCSG
private java.lang.Object[] findMinSCSG(int startIndex)
-
findSCCS
private java.util.List<java.util.Set<V>> findSCCS(int startIndex)
-
getSCCs
private void getSCCs(int startIndex, int vertexIndex)
-
findCyclesInSCG
private boolean findCyclesInSCG(int startIndex, int vertexIndex, DirectedGraph<V,E> scg)
-
unblock
private void unblock(V vertex)
-
initState
private void initState()
-
clearState
private void clearState()
-
initMinSCGState
private void initMinSCGState()
-
clearMinSCCState
private void clearMinSCCState()
-
toI
private java.lang.Integer toI(V vertex)
-
toV
private V toV(java.lang.Integer i)
-
-