AbstractFundamentalCycleBasis (JGraphT : a free Java graph library)

java.lang.Object
- org.jgrapht.alg.cycle.AbstractFundamentalCycleBasis<V,E>

Type Parameters:

V - the vertex type

E - 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>
```
A base implementation for the computation of a fundamental cycle basis of a graph. Subclasses should only provide a method for constructing a spanning forest of the graph. A cycle basis is fundamental if and only if each cycle in the basis contains at least one edge which is not contained in any other cycle in the basis.
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

Fields
Modifier and Type Field Description

protected Graph<V,E> graph

Constructor Summary

Constructors
Constructor Description

AbstractFundamentalCycleBasis(Graph<V,E> graph)
Constructor

Method Summary

All Methods Instance Methods Abstract Methods Concrete Methods
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.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - graph
```
protected Graph<V,E> graph
```
- Constructor Detail
  - AbstractFundamentalCycleBasis
```
public AbstractFundamentalCycleBasis(Graph<V,E> graph)
```
    Constructor
    
    Parameters:
    
    graph - the input graph
- Method Detail
  - getCycleBasis
```
public CycleBasisAlgorithm.CycleBasis<V,E> getCycleBasis()
```
    Return a list of cycles forming an undirected cycle basis of a graph.
    
    Specified by:
    
    getCycleBasis in interface CycleBasisAlgorithm<V,E>
    
    Returns:
    
    an undirected cycle basis
  - computeSpanningForest
```
protected abstract java.util.Map<V,E> 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.