V
 the graph vertex typeE
 the graph edge typepublic class ChinesePostman<V,E> extends Object
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 NPhard. 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:
Constructor and Description 

ChinesePostman() 
Modifier and Type  Method and Description 

GraphPath<V,E> 
getCPPSolution(Graph<V,E> graph)
Solves the Chinese Postman Problem on the given graph.

public GraphPath<V,E> getCPPSolution(Graph<V,E> graph)
KolmogorovWeightedPerfectMatching
matching algorithm;
for directed graphs, @KuhnMunkresMinimalWeightBipartitePerfectMatching
is used
instead. The input graph must be strongly connected. Otherwise the behavior of this class is
undefined.graph
 the input graph (must be a strongly connected graph)Copyright © 2019. All rights reserved.