Package org.jgrapht.alg.cycle
Class HawickJamesSimpleCycles<V,E>
- java.lang.Object
-
- org.jgrapht.alg.cycle.HawickJamesSimpleCycles<V,E>
-
- Type Parameters:
V
- the vertex type.E
- the edge type.
- All Implemented Interfaces:
DirectedSimpleCycles<V,E>
public class HawickJamesSimpleCycles<V,E> extends java.lang.Object implements DirectedSimpleCycles<V,E>
Find all simple cycles of a directed graph using the algorithm described by Hawick and James.See:
K. A. Hawick, H. A. James. Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs. Computational Science Technical Note CSTN-013, 2008
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
HawickJamesSimpleCycles.Operation
-
Field Summary
Fields Modifier and Type Field Description private java.util.List<java.lang.Integer>[]
Ak
private java.util.List<java.lang.Integer>[]
B
private boolean[]
blocked
private java.util.List<java.util.List<V>>
cycles
private DirectedGraph<V,E>
graph
private V[]
iToV
private long
nCycles
private int
nVertices
private java.util.ArrayDeque<java.lang.Integer>
stack
private java.lang.Integer
start
private java.util.Map<V,java.lang.Integer>
vToI
-
Constructor Summary
Constructors Constructor Description HawickJamesSimpleCycles()
Create a simple cycle finder with an unspecified graph.HawickJamesSimpleCycles(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 java.util.List<java.lang.Integer>[]
buildAdjacencyList()
private boolean
circuit(java.lang.Integer v, HawickJamesSimpleCycles.Operation o)
private void
clearState()
long
countSimpleCycles()
Count the number of simple cycles.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.DirectedGraph<V,E>
getGraph()
Returns the graph on which the simple cycle search algorithm is executed by this object.private void
initState(HawickJamesSimpleCycles.Operation o)
void
printSimpleCycles()
Print to the standard output all simple cycles without building a list to keep them, thus avoiding high memory consumption when investigating large and much connected graphs.private int
removeFromList(java.util.List<java.lang.Integer> list, java.lang.Integer u)
Remove all occurrences of a value from the list.void
setGraph(DirectedGraph<V,E> graph)
Sets the graph on which the simple cycle search algorithm is executed by this object.private void
unblock(java.lang.Integer u)
-
-
-
Field Detail
-
graph
private DirectedGraph<V,E> graph
-
nVertices
private int nVertices
-
nCycles
private long nCycles
-
cycles
private java.util.List<java.util.List<V>> cycles
-
start
private java.lang.Integer start
-
Ak
private java.util.List<java.lang.Integer>[] Ak
-
B
private java.util.List<java.lang.Integer>[] B
-
blocked
private boolean[] blocked
-
stack
private java.util.ArrayDeque<java.lang.Integer> stack
-
iToV
private V[] iToV
-
vToI
private java.util.Map<V,java.lang.Integer> vToI
-
-
Constructor Detail
-
HawickJamesSimpleCycles
public HawickJamesSimpleCycles()
Create a simple cycle finder with an unspecified graph.
-
HawickJamesSimpleCycles
public HawickJamesSimpleCycles(DirectedGraph<V,E> graph) throws java.lang.IllegalArgumentException
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
-
initState
private void initState(HawickJamesSimpleCycles.Operation o)
-
buildAdjacencyList
private java.util.List<java.lang.Integer>[] buildAdjacencyList()
-
clearState
private void clearState()
-
circuit
private boolean circuit(java.lang.Integer v, HawickJamesSimpleCycles.Operation o)
-
unblock
private void unblock(java.lang.Integer u)
-
removeFromList
private int removeFromList(java.util.List<java.lang.Integer> list, java.lang.Integer u)
Remove all occurrences of a value from the list.- Parameters:
u
- the Integer to be removed.list
- the list from which all the occurrences of u must be removed.
-
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) throws java.lang.IllegalArgumentException
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.- Throws:
java.lang.IllegalArgumentException
- if the argument isnull
.
-
findSimpleCycles
public java.util.List<java.util.List<V>> findSimpleCycles() throws java.lang.IllegalArgumentException
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
. - Throws:
java.lang.IllegalArgumentException
- if the current graph is null.
-
printSimpleCycles
public void printSimpleCycles()
Print to the standard output all simple cycles without building a list to keep them, thus avoiding high memory consumption when investigating large and much connected graphs.
-
countSimpleCycles
public long countSimpleCycles()
Count the number of simple cycles. It can count up to Long.MAX cycles in a graph.- Returns:
- the number of simple cycles
-
-