Module org.jgrapht.core
Package org.jgrapht.alg.cycle
package org.jgrapht.alg.cycle
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: Szwarcfiter and Lauer  $O(V + EC)$
 Tarjan  $O(VEC)$
 Johnson  $O(((V+E)C)$
 Tiernan  $O(V.const^V)$
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:
 J.C.Tiernan An Efficient Search Algorithm Find the Elementary Circuits of a Graph., Communications of the ACM, V13, 12, (1970), pp. 722  726.
 R.Tarjan, Depthfirst search and linear graph algorithms., SIAM J. Comput. 1 (1972), pp. 146160.
 R. Tarjan, Enumeration of the elementary circuits of a directed graph, SIAM J. Comput., 2 (1973), pp. 211216.
 D. B. Johnson, Finding all the elementary circuits of a directed graph, SIAM J. Comput., 4 (1975), pp. 7784.
 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.
 L. G. Bezem and J. van Leeuwen, Enumeration in graphs., Technical report RUUCS877, University of Utrecht, The Netherlands, 1987.
Algorithms for the computation of undirected cycle basis
 A variant of Paton's algorithm
PatonCycleBase
, performing a BFS using a stack which returns a weakly fundamental cycle basis. Supports graphs with selfloops but not multiple (parallel) edges.  A variant of Paton's algorithm
StackBFSFundamentalCycleBasis
, which returns a fundamental cycle basis. This is a more generic implementation which supports selfloops and multiple (parallel) edges.  An algorithm
QueueBFSFundamentalCycleBasis
which constructs a fundamental cycle basis using a straightforward implementation of BFS using a queue. The implementation supports graphs with selfloops and multiple (parallel) edges.
See the following papers for details of the above algorithms:
 K. Paton, An algorithm for finding a fundamental set of cycles for an undirected linear graph, Comm. ACM 12 (1969), pp. 514518.
 Narsingh Deo, G. Prabhu, and M. S. Krishnamoorthy. Algorithms for Generating Fundamental Cycles in a Graph. ACM Trans. Math. Softw. 8, 1, 2642, 1982.
Algorithms for the computation of Eulerian cycles
 An implementation of
Hierholzer
's algorithm for finding an Eulerian cycle in Eulerian graphs.

ClassDescriptionA base implementation for the computation of a fundamental cycle basis of a graph.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.Allows obtaining a mapping of all minimal vertex separators of a graph to their multiplicitiesChordalityInspector<V,E> Tests whether a graph is chordal.Specifies internal iterator type.CycleDetector<V,E> Performs cycle detection on a graph.Collection of helper methods related to cycles.DirectedSimpleCycles<V,E> A common interface for classes implementing algorithms for enumeration of the simple cycles of a directed graph.Find all simple cycles of a directed graph using the algorithm described by Hawick and James.An implementation of Hierholzer's algorithm for finding an Eulerian cycle in Eulerian graphs.Implementation of Howard`s algorithm for finding minimum cycle mean in a graph.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.Generate a set of fundamental cycles by building a spanning tree (forest) using a straightforward implementation of BFS using a FIFO queue.Generate a set of fundamental cycles by building a spanning tree (forest) using an implementation of BFS using a LIFO Stack.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.Tests whether a graph is weakly chordal.