Cycles

Algorithms

The following algorithms are available:

jgrapht.algorithms.cycles.chinese_postman(graph)

Run Edmonds-Johnson algorithm to solve the chinese postman problem (CPP).

The CPP problem asks for the minimum length (weight) closed-walk 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 closed-walk of minimum weight which visits every edge at least once

jgrapht.algorithms.cycles.enumerate_simple_cycles_hawick_james(graph)

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 self-loops 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 Self-Arcs and Multiple-Arcs.” 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)

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 self-loops 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. 77-84.

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)

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 self-loops 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)

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 self-loops 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. 211-216.

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)

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 self-loops 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)

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)

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 fundamental-cycles set. It supports graphs with self-loops 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, 26-42, 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)

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 fundamental-cycles set. It supports graphs with self-loops 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. 514-518.

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)

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 self-loops 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. 514-518.

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

Interface for a graph path.

abstract edges()

Edges of the path.

Return type

collections.abc.Iterable

abstract end_vertex()

Ending vertex of the path.

abstract graph()

The graph that this graph path refers to.

Return type

jgrapht.types.Graph

abstract start_vertex()

Starting vertex of the path.

property vertices

Vertices of the path.

abstract weight()

Weight of the path.

Return type

Double