graph.algorithm.cycles

Class JohnsonSimpleCycles<V extends Vertex,E extends Edge<V>>

java.lang.Object

graph.algorithm.cycles.JohnsonSimpleCycles<V,E>

Type Parameters:

V - The vertex type.

E - The edge type.

public class JohnsonSimpleCycles<V extends Vertex,E extends Edge<V>>
extends java.lang.Object

Find all simple cycles of a directed graph using the Johnson's algorithm. D.B.Johnson, Finding all the elementary circuits of a directed graph, SIAM J. Comput., 4 (1975), pp. 77-84. Ports the implementation of the following author:

Author:

Nikolay Ognyanov

Constructor Summary

Constructors

Constructor and Description
JohnsonSimpleCycles() Create a simple cycle finder with an unspecified graph.
JohnsonSimpleCycles(Graph<V,E> graph)
JohnsonSimpleCycles(Graph<V,E> graph, boolean stopWhenOneFound) Create a simple cycle finder for the specified graph.

Method Summary

Modifier and Type	Method and Description
java.util.List<java.util.List<V>>	findSimpleCycles()

Methods inherited from class java.lang.Object

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

Constructor Detail

JohnsonSimpleCycles

public JohnsonSimpleCycles()

Create a simple cycle finder with an unspecified graph.

JohnsonSimpleCycles

public JohnsonSimpleCycles(Graph<V,E> graph,
                           boolean stopWhenOneFound)

Create a simple cycle finder for the specified graph.

Parameters:

stopWhenOneFound - Indicator if the algorithm should stop when as soon as one cycle is detected

graph - A directed graph in which to find cycles.

Throws:

java.lang.IllegalArgumentException - if the graph argument is null.

JohnsonSimpleCycles

public JohnsonSimpleCycles(Graph<V,E> graph)

Method Detail

findSimpleCycles

public java.util.List<java.util.List<V>> findSimpleCycles()

Returns:

A list simple cycles, where each cycle is represented as a list of vertices it contains