Module org.jgrapht.core
Package org.jgrapht.alg.cycle

Class QueueBFSFundamentalCycleBasis<V,E>

java.lang.Object
org.jgrapht.alg.cycle.AbstractFundamentalCycleBasis<V,E>
org.jgrapht.alg.cycle.QueueBFSFundamentalCycleBasis<V,E>
Type Parameters:
V - the vertex type
E - the edge type
All Implemented Interfaces:
CycleBasisAlgorithm<V,E>
public class QueueBFSFundamentalCycleBasis<V,E> extends AbstractFundamentalCycleBasis<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 fundamental-cycles set. It supports graphs with self-loops 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, 26-42, 1982.

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

  • Constructor Details

    • QueueBFSFundamentalCycleBasis

      public QueueBFSFundamentalCycleBasis(Graph<V,E> graph)
      Constructor
      Parameters:
      graph - the input graph

  • Method Details

    • computeSpanningForest

      protected Map<V,E> 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 class AbstractFundamentalCycleBasis<V,E>
      Returns:
      a map representation of a spanning forest.