org.jgrapht.alg.cycle

Class ChinesePostman<V,E>

java.lang.Object

org.jgrapht.alg.cycle.ChinesePostman<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

public class ChinesePostman<V,E>
extends Object

This class solves the Chinese Postman Problem (CPP), also known as the Route Inspection Problem. The CPP asks to find a closed walk of minimum length that visits every edge of the graph at least once. In weighted graphs, the length of the closed walk is defined as the sum of its edge weights; in unweighted graphs, a closed walk with the least number of edges is returned (the same result can be obtained for weighted graphs with uniform edge weights).

The algorithm works with directed and undirected graphs which may contain loops and/or multiple edges. The runtime complexity is O(N^3) where N is the number of vertices in the graph. Mixed graphs are currently not supported, as solving the CPP for mixed graphs is NP-hard. The graph on which this algorithm is invoked must be strongly connected; invoking this algorithm on a graph which is not strongly connected may result in undefined behavior. In case of weighted graphs, all edge weights must be positive. If the input graph is Eulerian (see GraphTests.isEulerian(Graph) for details) use HierholzerEulerianCycle instead.

The implementation is based on the following paper:
Edmonds, J., Johnson, E.L. Matching, Euler tours and the Chinese postman, Mathematical Programming (1973) 5: 88. doi:10.1007/BF01580113
More concise descriptions of the algorithms can be found here:

• CPP for Undirected graphs
• CPP for Directed graphs

Author:

Joris Kinable

Constructor Summary

Constructors

Constructor and Description
ChinesePostman()

Method Summary

Modifier and Type	Method and Description
GraphPath<V,E>	getCPPSolution(Graph<V,E> graph) Solves the Chinese Postman Problem on the given graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ChinesePostman

public ChinesePostman()

Method Detail

getCPPSolution

public GraphPath<V,E> getCPPSolution(Graph<V,E> graph)

Solves the Chinese Postman Problem on the given graph. For Undirected graph, this implementation uses the @KolmogorovMinimumWeightPerfectMatching matching algorithm; for directed graphs, @KuhnMunkresMinimalWeightBipartitePerfectMatching is used instead. The input graph must be strongly connected. Otherwise the behavior of this class is undefined.

Parameters:

graph - the input graph (must be a strongly connected graph)

Returns:

Eulerian circuit of minimum weight.