V- the graph vertex type
E- the graph edge type
public class PatonCycleBase<V,E> extends Object implements CycleBasisAlgorithm<V,E>
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.
|Constructor and Description|
Create a cycle base finder for the specified graph.
|Modifier and Type||Method and Description|
Return an undirected cycle basis of a graph.
public PatonCycleBase(Graph<V,E> graph)
graph- the input graph
IllegalArgumentException- if the graph argument is
nullor the graph is not undirected
public CycleBasisAlgorithm.CycleBasis<V,E> getCycleBasis()
IllegalArgumentException- if the graph is not undirected
IllegalArgumentException- if the graph contains multiple edges between two vertices
Copyright © 2018. All rights reserved.