Package org.jgrapht.alg.cycle

Algorithms related to graph cycles.

See: Description

Interface Summary

Interface	Description
DirectedSimpleCycles<V,E>	A common interface for classes implementing algorithms for enumeration of the simple cycles of a directed graph.

Class Summary

Class	Description
AbstractFundamentalCycleBasis<V,E>	A base implementation for the computation of a fundamental cycle basis of a graph.
AhujaOrlinSharmaCyclicExchangeLocalAugmentation<V,E>	Implementation of an algorithm for the local augmentation problem for the cyclic exchange neighborhood, i.e.
BergeGraphInspector<V,E>	Tests whether a graph is perfect.
ChinesePostman<V,E>	This class solves the Chinese Postman Problem (CPP), also known as the Route Inspection Problem.
ChordalGraphMinimalVertexSeparatorFinder<V,E>	Allows obtaining a mapping of all minimal vertex separators of a graph to their multiplicities
ChordalityInspector<V,E>	Tests whether a graph is chordal.
CycleDetector<V,E>	Performs cycle detection on a graph.
Cycles	Collection of helper methods related to cycles.
HawickJamesSimpleCycles<V,E>	Find all simple cycles of a directed graph using the algorithm described by Hawick and James.
HierholzerEulerianCycle<V,E>	An implementation of Hierholzer's algorithm for finding an Eulerian cycle in Eulerian graphs.
JohnsonSimpleCycles<V,E>	Find all simple cycles of a directed graph using the Johnson's algorithm.
PatonCycleBase<V,E>	Find a cycle basis of an undirected graph using a variant of Paton's algorithm.
QueueBFSFundamentalCycleBasis<V,E>	Generate a set of fundamental cycles by building a spanning tree (forest) using a straightforward implementation of BFS using a FIFO queue.
StackBFSFundamentalCycleBasis<V,E>	Generate a set of fundamental cycles by building a spanning tree (forest) using an implementation of BFS using a LIFO Stack.
SzwarcfiterLauerSimpleCycles<V,E>	Find all simple cycles of a directed graph using the Schwarcfiter and Lauer's algorithm.
TarjanSimpleCycles<V,E>	Find all simple cycles of a directed graph using the Tarjan's algorithm.
TiernanSimpleCycles<V,E>	Find all simple cycles of a directed graph using the Tiernan's algorithm.
WeakChordalityInspector<V,E>	Tests whether a graph is weakly chordal.

Enum Summary

Enum	Description
ChordalityInspector.IterationOrder	Specifies internal iterator type.

Package org.jgrapht.alg.cycle Description

Algorithms related to graph cycles.

Algorithms for enumeration of simple cycles in graphs

Contains four different algorithms for the enumeration of simple cycles in directed graphs. The worst case time complexity of the algorithms is:

1. Szwarcfiter and Lauer - $O(V + EC)$
2. Tarjan - $O(VEC)$
3. Johnson - $O(((V+E)C)$
4. Tiernan - $O(V.const^V)$

where $V$ is the number of vertices, $E$ is the number of edges and $C$ is the number of the simple cycles in the graph. All the above implementations work correctly with loops but not with multiple edges. Space complexity for all cases is $O(V+E)$.

The worst case performance is achieved for graphs with special structure, so on practical workloads an algorithm with higher worst case complexity may outperform an algorithm with lower worst case complexity. Note also that "administrative costs" of algorithms with better worst case performance are higher. Also higher is their memory cost.

See the following papers for details of the above algorithms:

1. J.C.Tiernan An Efficient Search Algorithm Find the Elementary Circuits of a Graph., Communications of the ACM, V13, 12, (1970), pp. 722 - 726.
2. R.Tarjan, Depth-first search and linear graph algorithms., SIAM J. Comput. 1 (1972), pp. 146-160.
3. R. Tarjan, Enumeration of the elementary circuits of a directed graph, SIAM J. Comput., 2 (1973), pp. 211-216.
4. D. B. Johnson, Finding all the elementary circuits of a directed graph, SIAM J. Comput., 4 (1975), pp. 77-84.
5. J. L. Szwarcfiter and P. E. Lauer, Finding the elementary cycles of a directed graph in O(n + m) per cycle, Technical Report Series, #60, May 1974, Univ. of Newcastle upon Tyne, Newcastle upon Tyne, England.
6. L. G. Bezem and J. van Leeuwen, Enumeration in graphs., Technical report RUU-CS-87-7, University of Utrecht, The Netherlands, 1987.

Algorithms for the computation of undirected cycle basis

1. A variant of Paton's algorithm PatonCycleBase, performing a BFS using a stack which returns a weakly fundamental cycle basis. Supports graphs with self-loops but not multiple (parallel) edges.
2. A variant of Paton's algorithm StackBFSFundamentalCycleBasis, which returns a fundamental cycle basis. This is a more generic implementation which supports self-loops and multiple (parallel) edges.
3. An algorithm QueueBFSFundamentalCycleBasis which constructs a fundamental cycle basis using a straightforward implementation of BFS using a queue. The implementation supports graphs with self-loops and multiple (parallel) edges.

The worst case time complexity of all above algorithms is $O(|V|^3)$ since the length of the cycle basis can be that large.

See the following papers for details of the above algorithms:

1. K. Paton, An algorithm for finding a fundamental set of cycles for an undirected linear graph, Comm. ACM 12 (1969), pp. 514-518.
2. 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.

Algorithms for the computation of Eulerian cycles

1. An implementation of Hierholzer's algorithm for finding an Eulerian cycle in Eulerian graphs.