Package com.jgalgo.alg.cycle

Class ChinesePostmanImpl

java.lang.Object
com.jgalgo.alg.cycle.ChinesePostmanAbstract
com.jgalgo.alg.cycle.ChinesePostmanImpl
All Implemented Interfaces:
ChinesePostman
public class ChinesePostmanImpl extends ChinesePostmanAbstract
An algorithm for the chinese postman problem using minimum weighted perfect matching and Eulerian tour.

The chinese postman problem is to find a closed path that visits all edges in the graph at least once, with minimum weight sum with respect to a given edge weight function. The algorithm uses the following steps:

  1. Find all vertices with odd degree. If all vertices have even degree, an Eulerian tour should exists (if the graph is connected).
  2. Create a complete graph of the odd vertices, with edges weighted by the shortest paths between each pair.
  3. Compute a minimum weighted perfect matching between the odd vertices.
  4. Create a graph with the original vertices and edges, and for each edge resulted from the perfect matching, add an edge between the two vertices in the original graph.
  5. Compute an Eulerian tour in the new graph.
  6. Construct the full result path by replacing each artificial edge connecting two odd vertices with the shortest path between them.

The running time and space are dominated by the shortest path all pairs and minimum perfect matching algorithms. Other than that, the algorithm use linear time and space.

Author:
Barak Ugav

  • Constructor Details

    • ChinesePostmanImpl

      public ChinesePostmanImpl()
      Create a new instance of the Chinese postman algorithm.

      Please prefer using ChinesePostman.newInstance() to get a default implementation for the ChinesePostman interface.