org.jgrapht.alg.cycle

## Class PatonCycleBase<V,E>

• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
UndirectedCycleBase<V,E>, CycleBasisAlgorithm<V,E>

public class PatonCycleBase<V,E>
extends Object
implements UndirectedCycleBase<V,E>, CycleBasisAlgorithm<V,E>
Find a cycle basis of an undirected graph using a variant of 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.

Note that Paton's algorithm produces a fundamental cycle basis while this implementation produces a weakly fundamental cycle basis. A cycle basis is called weakly fundamental if there exists a linear ordering of the cycles in a cycle basis such that each cycle includes at least one edge that is not part of any previous cycle. Every fundamental cycle basis is weakly fundamental (for all linear orderings) but not necessarily vice versa.

Author:
Nikolay Ognyanov

• ### Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.CycleBasisAlgorithm

CycleBasisAlgorithm.CycleBasis<V,E>, CycleBasisAlgorithm.CycleBasisImpl<V,E>
• ### Constructor Summary

Constructors
Constructor and Description
PatonCycleBase()
Deprecated.
PatonCycleBase(Graph<V,E> graph)
Create a cycle base finder for the specified graph.
• ### Method Summary

All Methods
Modifier and Type Method and Description
List<List<V>> findCycleBase()
Deprecated.
CycleBasisAlgorithm.CycleBasis<V,E> getCycleBasis()
Return an undirected cycle basis of a graph.
Graph<V,E> getGraph()
Deprecated.
void setGraph(Graph<V,E> graph)
Deprecated.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Constructor Detail

• #### PatonCycleBase

@Deprecated
public PatonCycleBase()
Deprecated. Use PatonCycleBase(Graph) instead.
Construct a new instance of the cycle basis algorithm.
• #### PatonCycleBase

public PatonCycleBase(Graph<V,E> graph)
Create a cycle base finder for the specified graph.
Parameters:
graph - the input graph
Throws:
IllegalArgumentException - if the graph argument is null or the graph is not undirected
• ### Method Detail

• #### getGraph

@Deprecated
public Graph<V,E> getGraph()
Deprecated. in favor of CycleBasisAlgorithm
Returns the graph on which the cycle base search algorithm is executed by this object.
Specified by:
getGraph in interface UndirectedCycleBase<V,E>
Returns:
The graph.
• #### setGraph

@Deprecated
public void setGraph(Graph<V,E> graph)
Deprecated. in favor of CycleBasisAlgorithm
Sets the graph on which the cycle base search algorithm is executed by this object.
Specified by:
setGraph in interface UndirectedCycleBase<V,E>
Parameters:
graph - the graph.
• #### findCycleBase

@Deprecated
public List<List<V>> findCycleBase()
Deprecated. in favor of getCycleBasis()
Finds a cycle base of the graph.
Note that the full algorithm is executed on every call since the graph may have changed between calls.
Specified by:
findCycleBase in interface UndirectedCycleBase<V,E>
Returns:
A list of cycles constituting a cycle base for the graph. Possibly empty but never null.
Throws:
IllegalArgumentException - if the graph contains multiple edges between two vertices
• #### getCycleBasis

public CycleBasisAlgorithm.CycleBasis<V,E> getCycleBasis()
Return an undirected cycle basis of a graph. Works only for undirected graphs which do not have multiple (parallel) edges.
Specified by:
getCycleBasis in interface CycleBasisAlgorithm<V,E>
Returns:
an undirected cycle basis
Throws:
IllegalArgumentException - if the graph is not undirected
IllegalArgumentException - if the graph contains multiple edges between two vertices