org.jgrapht.alg.cycle

Class StackBFSFundamentalCycleBasis<V,E>

java.lang.Object

org.jgrapht.alg.cycle.AbstractFundamentalCycleBasis<V,E>

org.jgrapht.alg.cycle.StackBFSFundamentalCycleBasis<V,E>

Type Parameters:

V - the vertex type

E - the edge type

All Implemented Interfaces:

CycleBasisAlgorithm<V,E>

public class StackBFSFundamentalCycleBasis<V,E>
extends AbstractFundamentalCycleBasis<V,E>

Generate a set of fundamental cycles by building a spanning tree (forest) using an implementation of BFS using a LIFO Stack. The implementation first constructs the spanning forest and then builds the fundamental-cycles set. It supports graphs with self-loops and/or graphs with multiple (parallel) edges.

The algorithm constructs the same fundamental cycle basis as the algorithm in the following paper: K. Paton, An algorithm for finding a fundamental set of cycles for an undirected linear graph, Comm. ACM 12 (1969), pp. 514-518.

The total length of the fundamental-cycle 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

Constructors

Constructor and Description
StackBFSFundamentalCycleBasis(Graph<V,E> graph) Constructor

Method Summary

Modifier and Type	Method and Description
protected Map<V,E>	computeSpanningForest() Compute a spanning forest of the graph using a stack (LIFO) based BFS implementation.

Methods inherited from class org.jgrapht.alg.cycle.AbstractFundamentalCycleBasis

getCycleBasis

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

StackBFSFundamentalCycleBasis

public StackBFSFundamentalCycleBasis(Graph<V,E> graph)

Constructor

Parameters:

graph - the input graph

Method Detail

computeSpanningForest

protected Map<V,E> computeSpanningForest()

Compute a spanning forest of the graph using a stack (LIFO) based 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 class AbstractFundamentalCycleBasis<V,E>

Returns:

a map representation of a spanning forest.