Cycles¶
Algorithms¶
The following algorithms are available:

jgrapht.algorithms.cycles.
chinese_postman
(graph)[source]¶ Run EdmondsJohnson algorithm to solve the chinese postman problem (CPP).
The CPP problem asks for the minimum length (weight) closedwalk that visits every edge of the graph at least once.
Note
This implementation assumes that the graph is strongly connected, otherwise the behavior is undefined.
Running time \(\mathcal{O}(n^3)\) where \(n\) is the number of vertices.
See the following paper:
Edmonds, J., Johnson, E.L. Matching, Euler tours and the Chinese postman, Mathematical Programming (1973) 5: 88. doi:10.1007/BF01580113
 Parameters
graph – the input graph. It must be strongly connected
 Returns
a closedwalk of minimum weight which visits every edge at least once

jgrapht.algorithms.cycles.
enumerate_simple_cycles_hawick_james
(graph)[source]¶ Enumerate all simple cycles in a directed graph.
Running time \(\mathcal{O}((n+m)C)\) where \(n\) is the number of vertices, \(m\) the number of edges and \(C\) the number of simple cycles in the graph. This algorithm is a variant of Johnson’ algorithm.
Note
The algorithm supports selfloops but not multiple edges.
Note
The algorithm returns cycles as sets of vertices.
See the paper:
Hawick, Kenneth A., and Heath A. James. “Enumerating Circuits and Loops in Graphs with SelfArcs and MultipleArcs.” FCS. 2008.
 Parameters
graph – the graph. Must be directed and without multiple edges
 Returns
an iterator over the cycles. Cycles are returned as vertex sets.

jgrapht.algorithms.cycles.
enumerate_simple_cycles_johnson
(graph)[source]¶ Enumerate all simple cycles in a directed graph.
Running time \(\mathcal{O}((n + m)C)\) where \(n\) is the number of vertices, \(m\) the number of edges and \(C\) the number of simple cycles in the graph.
Note
The algorithm supports selfloops but not multiple edges.
Note
The algorithm returns cycles as sets of vertices.
See the paper:
D. B. Johnson, Finding all the elementary circuits of a directed graph, SIAM J. Comput., 4 (1975), pp. 7784.
 Parameters
graph – the graph. Must be directed and without multiple edges
 Returns
an iterator over the cycles. Cycles are returned as vertex sets.

jgrapht.algorithms.cycles.
enumerate_simple_cycles_szwarcfiter_lauer
(graph)[source]¶ Enumerate all simple cycles in a directed graph.
Running time \(\mathcal{O}((n+m)C)\) where \(n\) is the number of vertices, \(m\) the number of edges and \(C\) the number of simple cycles in the graph.
Note
The algorithm supports selfloops but not multiple edges.
Note
The algorithm returns cycles as sets of vertices.
See the paper:
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.
 Parameters
graph – the graph. Must be directed and without multiple edges
 Returns
an iterator over the cycles. Cycles are returned as vertex sets.

jgrapht.algorithms.cycles.
enumerate_simple_cycles_tarjan
(graph)[source]¶ Enumerate all simple cycles in a directed graph.
Running time \(\mathcal{O}(n m C)\) where \(n\) is the number of vertices, \(m\) the number of edges and \(C\) the number of simple cycles in the graph.
Note
The algorithm supports selfloops but not multiple edges.
Note
The algorithm returns cycles as sets of vertices.
See the paper:
R. Tarjan, Enumeration of the elementary circuits of a directed graph, SIAM J. Comput., 2 (1973), pp. 211216.
 Parameters
graph – the graph. Must be directed and without multiple edges
 Returns
an iterator over the cycles. Cycles are returned as vertex sets.

jgrapht.algorithms.cycles.
enumerate_simple_cycles_tiernan
(graph)[source]¶ Enumerate all simple cycles in a directed graph.
Running time \(\mathcal{O}(n d^n)\) where \(n\) is the number of vertices, \(m\) the number of edges and \(d\) is a constant.
Note
The algorithm supports selfloops but not multiple edges.
Note
The algorithm returns cycles as sets of vertices.
See the paper:
J.C.Tiernan An Efficient Search Algorithm Find the Elementary Circuits of a Graph., Communications of the ACM, V13, 12, (1970), pp. 722  726.
 Parameters
graph – the graph. Must be directed and without multiple edges
 Returns
an iterator over the cycles. Cycles are returned as vertex sets.

jgrapht.algorithms.cycles.
eulerian_cycle
(graph)[source]¶ Run Hierholzer’s algorithm to check if a graph is Eulerian and if yes construst an Eulerian cycle.
The algorithm works with directed and undirected graphs which may contain loops and/or multiple edges. The running time is linear, i.e. \(\mathcal{O}(m)\) where \(m\) is the cardinality of the edge set of the graph.
See the wikipedia article for details and references about Eulerian cycles and a short description of Hierholzer’s algorithm for the construction of an Eulerian cycle. The original presentation of the algorithm dates back to 1873 and the following paper:
Carl Hierholzer: Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen 6(1), 30–32, 1873.
 Parameters
graph – The input graph
 Returns
An Eulerian cycle as a
GraphPath
or None if the graph is not Eulerian

jgrapht.algorithms.cycles.
fundamental_cycle_basis_bfs_with_queue
(graph)[source]¶ Compute a fundamental cycle basis.
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 fundamentalcycles set. It supports graphs with selfloops and/or graphs with multiple 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, 2642, 1982.
Running time \(\mathcal{O}(n^3)\).
 Parameters
graph – the graph. It must be undirected
 Returns
a tuple (weight, cycle iterator). Each cycle is returned as a
GraphPath
instance

jgrapht.algorithms.cycles.
fundamental_cycle_basis_bfs_with_stack
(graph)[source]¶ Compute a fundamental cycle basis.
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 fundamentalcycles set. It supports graphs with selfloops and/or graphs with multiple 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. 514518.
Running time \(\mathcal{O}(n^3)\).
 Parameters
graph – the graph. It must be undirected
 Returns
a tuple (weight, cycle iterator). Each cycle is returned as a
GraphPath
instance

jgrapht.algorithms.cycles.
fundamental_cycle_basis_paton
(graph)[source]¶ Compute a fundamental cycle basis.
This is a variant of Paton’s algorithm, performing a BFS using a stack which returns a weakly fundamental cycle basis. It supports graphs with selfloops but not multiple edges.
Running time \(\mathcal{O}(n^3)\).
 See:
K. Paton, An algorithm for finding a fundamental set of cycles for an undirected linear graph, Comm. ACM 12 (1969), pp. 514518.
 Parameters
graph – the graph. It must be undirected
 Returns
a tuple (weight, cycle iterator). Each cycle is returned as a
GraphPath
instance
Types¶
Cycles are usually represented with instances of GraphPath
.

class
jgrapht.types.
GraphPath
[source] Interface for a graph path.

abstract
edges
()[source] Edges of the path.
 Return type
collections.abc.Iterable

abstract
end_vertex
()[source] Ending vertex of the path.

abstract
graph
()[source] The graph that this graph path refers to.
 Return type

abstract
start_vertex
()[source] Starting vertex of the path.

property
vertices
Vertices of the path.

abstract
weight
()[source] Weight of the path.
 Return type
Double

abstract