graph.algorithm.cycles

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

java.lang.Object

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

Type Parameters:

V - The vertex type.

E - The edge type.

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

Find a cycle basis of an undirected graph using the Paton's algorithm. See: K. Paton, An algorithm for finding a fundamental set of cycles for an undirected linear graph, Comm. ACM 12 (1969), pp. 514-518. Ports the implementation of the following author:

Author:

Nikolay Ognyanov

Constructor Summary

Constructors

Constructor and Description
PatonSimpleCycles(Graph<V,E> graph) Create a cycle basis 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

PatonSimpleCycles

public PatonSimpleCycles(Graph<V,E> graph)

Create a cycle basis finder for the specified graph.

Parameters:

graph - An undirected graph in which to find cycles.

Throws:

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

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