java.lang.Object
org.jgrapht.alg.cycle.AbstractFundamentalCycleBasis<V,E>
org.jgrapht.alg.cycle.QueueBFSFundamentalCycleBasis<V,E>
 Type Parameters:
V
 the vertex typeE
 the edge type
 All Implemented Interfaces:
CycleBasisAlgorithm<V,
E>
Generate a set of fundamental cycles by building a spanning tree (forest) using a straightforward
implementation of BFS using a FIFO queue. The implementation first constructs the spanning forest
and then builds the fundamentalcycles set. It supports graphs with selfloops and/or graphs with
multiple (parallel) edges.
For information on algorithms computing 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, 2642, 1982.
The total length of the fundamentalcycle set can be as large as $O(n^3)$ where $n$ is the number of vertices of the graph.
 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 inherited from class org.jgrapht.alg.cycle.AbstractFundamentalCycleBasis
graph

Constructor Summary

Method Summary
Modifier and TypeMethodDescriptionCompute a spanning forest of the graph using a straightforward BFS implementation.Methods inherited from class org.jgrapht.alg.cycle.AbstractFundamentalCycleBasis
getCycleBasis

Constructor Details

QueueBFSFundamentalCycleBasis
Constructor Parameters:
graph
 the input graph


Method Details

computeSpanningForest
Compute a spanning forest of the graph using a straightforward BFS implementation.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.
 Specified by:
computeSpanningForest
in classAbstractFundamentalCycleBasis<V,
E>  Returns:
 a map representation of a spanning forest.
