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 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

Author:

Luiz Kill

Constructor Summary

Constructors

Constructor and 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

Modifier and Type	Method and Description
long	countSimpleCycles() Count the number of simple cycles.
List<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.
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.
void	setGraph(DirectedGraph<V,E> graph) Sets the graph on which the simple cycle search algorithm is executed by this object.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

HawickJamesSimpleCycles

public HawickJamesSimpleCycles()

Create a simple cycle finder with an unspecified graph.

HawickJamesSimpleCycles

public HawickJamesSimpleCycles(DirectedGraph<V,E> graph)
                        throws IllegalArgumentException

Create a simple cycle finder for the specified graph.

Parameters:

graph - the DirectedGraph in which to find cycles.

Throws:

IllegalArgumentException - if the graph argument is null.

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 interface DirectedSimpleCycles<V,E>

Returns:

The graph.

setGraph

public void setGraph(DirectedGraph<V,E> graph)
              throws IllegalArgumentException

Sets the graph on which the simple cycle search algorithm is executed by this object.

Specified by:

setGraph in interface DirectedSimpleCycles<V,E>

Parameters:

graph - the graph.

Throws:

IllegalArgumentException - if the argument is null.

findSimpleCycles

public List<List<V>> findSimpleCycles()
                               throws 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 interface DirectedSimpleCycles<V,E>

Returns:

The list of all simple cycles. Possibly empty but never null.

Throws:

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