- Type Parameters:
V
- the vertex typeE
- the edge type
- All Implemented Interfaces:
CycleBasisAlgorithm<V,E>
- Direct Known Subclasses:
QueueBFSFundamentalCycleBasis
,StackBFSFundamentalCycleBasis
public abstract class AbstractFundamentalCycleBasis<V,E> extends java.lang.Object implements CycleBasisAlgorithm<V,E>
For information on algorithms and heuristics for the computation of fundamental cycle bases see the following paper: Narsingh Deo, G. Prabhu, and M. S. Krishnamoorthy. Algorithms for Generating Fundamental Cycles in a Graph. ACM Trans. Math. Softw. 8, 1, 26-42, 1982.
The implementation returns a fundamental cycle basis as an undirected cycle basis. For a discussion of different kinds of cycle bases in graphs see the following paper: Christian Liebchen, and Romeo Rizzi. Classes of Cycle Bases. Discrete Applied Mathematics, 155(3), 337-355, 2007.
- Author:
- Dimitrios Michail
-
Nested Class Summary
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.CycleBasisAlgorithm
CycleBasisAlgorithm.CycleBasis<V,E>, CycleBasisAlgorithm.CycleBasisImpl<V,E>
-
Field Summary
-
Constructor Summary
Constructors Constructor Description AbstractFundamentalCycleBasis(Graph<V,E> graph)
Constructor -
Method Summary
Modifier and Type Method Description protected abstract java.util.Map<V,E>
computeSpanningForest()
Compute a spanning forest of the graph.CycleBasisAlgorithm.CycleBasis<V,E>
getCycleBasis()
Return a list of cycles forming an undirected cycle basis of a graph.
-
Field Details
-
Constructor Details
-
AbstractFundamentalCycleBasis
Constructor- Parameters:
graph
- the input graph
-
-
Method Details
-
getCycleBasis
Return a list of cycles forming an undirected cycle basis of a graph.- Specified by:
getCycleBasis
in interfaceCycleBasisAlgorithm<V,E>
- Returns:
- an undirected cycle basis
-
computeSpanningForest
Compute a spanning forest of the graph.The representation assumes that the map contains the predecessor edge of each vertex in the forest. The predecessor edge is the forest edge that was used to discover the vertex. If no such edge was used (the vertex is a leaf in the forest) then the corresponding entry must be null.
- Returns:
- a map representation of a spanning forest.
-