V- the vertex type
E- the edge type
public class StackBFSFundamentalCycleBasis<V,E> extends AbstractFundamentalCycleBasis<V,E>
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.
|Constructor and Description|
|Modifier and Type||Method and Description|
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.
Copyright © 2020. All rights reserved.