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 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	Description
HawickJamesSimpleCycles()	Create a simple cycle finder with an unspecified graph.
HawickJamesSimpleCycles(Graph<V,E> graph)	Create a simple cycle finder for the specified graph.

Method Summary

Modifier and Type	Method	Description
void	clearPathLimit()	This is the default behaviour of the algorithm.
long	countSimpleCycles()	Count the number of simple cycles.
List<List<V>>	findSimpleCycles()	Find the simple cycles of the graph.
Graph<V,E>	getGraph()	Get the graph
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(Graph<V,E> graph)	Set the graph
void	setPathLimit(int pathLimit)	Limits the maximum number of edges in a cycle.

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(Graph<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 Graph<V,E> getGraph()

Get the graph

Returns:

graph

setGraph

public void setGraph(Graph<V,E> graph)

Set the graph

Parameters:

graph - graph

findSimpleCycles

public List<List<V>> findSimpleCycles()
                               throws IllegalArgumentException

Find the simple cycles of the graph.

Specified by:

findSimpleCycles in interface DirectedSimpleCycles<V,E>

Returns:

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

Throws:

IllegalArgumentException

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

setPathLimit

public void setPathLimit(int pathLimit)

Limits the maximum number of edges in a cycle.

Parameters:

pathLimit - maximum paths.

clearPathLimit

public void clearPathLimit()

This is the default behaviour of the algorithm. It will keep looking as long as there are paths available.