Java Program to Implement the Traditional Chinese Postman Problem

This is a java program to implement chinese Postman Problem. In graph theory, a branch of mathematics, the Chinese postman problem (CPP), postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of a (connected) undirected graph. When the graph has an Eulerian circuit (a closed walk that covers every edge once), that circuit is an optimal solution. Otherwise, the optimization problem is to find the fewest number of edges to add to the graph so that the resulting multigraph does have an Eulerian circuit.

Here is the source code of the Java Program to Give an Implementation of the Traditional Chinese Postman Problem. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1.  
  2. package com.sanfoundry.graph;
  3.  
  4. import java.util.Vector;
  5.  
  6. public class ChinesePostmanProblem
  7. {
  8.     int            N;                // number of vertices
  9.     int            delta[];          // deltas of vertices
  10.     int            neg[], pos[];     // unbalanced vertices
  11.     int            arcs[][];         // adjacency matrix, counts arcs between
  12.                                       // vertices
  13.     Vector<String> label[][];        // vectors of labels of arcs (for each
  14.                                       // vertex
  15.     // pair)
  16.     int            f[][];            // repeated arcs in CPT
  17.     float          c[][];            // costs of cheapest arcs or paths
  18.     String         cheapestLabel[][]; // labels of cheapest arcs
  19.     boolean        defined[][];      // whether path cost is defined between
  20.                                       // vertices
  21.     int            path[][];         // spanning tree of the graph
  22.     float          basicCost;        // total cost of traversing each arc once
  23.  
  24.     void solve()
  25.     {
  26.         leastCostPaths();
  27.         checkValid();
  28.         findUnbalanced();
  29.         findFeasible();
  30.         while (improvements())
  31.             ;
  32.     }
  33.  
  34.     // allocate array memory, and instantiate graph object
  35.     @SuppressWarnings("unchecked")
  36.     ChinesePostmanProblem(int vertices)
  37.     {
  38.         if ((N = vertices) <= 0)
  39.             throw new Error("Graph is empty");
  40.         delta = new int[N];
  41.         defined = new boolean[N][N];
  42.         label = new Vector[N][N];
  43.         c = new float[N][N];
  44.         f = new int[N][N];
  45.         arcs = new int[N][N];
  46.         cheapestLabel = new String[N][N];
  47.         path = new int[N][N];
  48.         basicCost = 0;
  49.     }
  50.  
  51.     ChinesePostmanProblem addArc(String lab, int u, int v, float cost)
  52.     {
  53.         if (!defined[u][v])
  54.             label[u][v] = new Vector<String>();
  55.         label[u][v].addElement(lab);
  56.         basicCost += cost;
  57.         if (!defined[u][v] || c[u][v] > cost)
  58.         {
  59.             c[u][v] = cost;
  60.             cheapestLabel[u][v] = lab;
  61.             defined[u][v] = true;
  62.             path[u][v] = v;
  63.         }
  64.         arcs[u][v]++;
  65.         delta[u]++;
  66.         delta[v]--;
  67.         return this;
  68.     }
  69.  
  70.     void leastCostPaths()
  71.     {
  72.         for (int k = 0; k < N; k++)
  73.             for (int i = 0; i < N; i++)
  74.                 if (defined[i][k])
  75.                     for (int j = 0; j < N; j++)
  76.                         if (defined[k][j]
  77.                                 && (!defined[i][j] || c[i][j] > c[i][k]
  78.                                         + c[k][j]))
  79.                         {
  80.                             path[i][j] = path[i][k];
  81.                             c[i][j] = c[i][k] + c[k][j];
  82.                             defined[i][j] = true;
  83.                             if (i == j && c[i][j] < 0)
  84.                                 return; // stop on negative cycle
  85.                         }
  86.     }
  87.  
  88.     void checkValid()
  89.     {
  90.         for (int i = 0; i < N; i++)
  91.         {
  92.             for (int j = 0; j < N; j++)
  93.                 if (!defined[i][j])
  94.                     throw new Error("Graph is not strongly connected");
  95.             if (c[i][i] < 0)
  96.                 throw new Error("Graph has a negative cycle");
  97.         }
  98.     }
  99.  
  100.     float cost()
  101.     {
  102.         return basicCost + phi();
  103.     }
  104.  
  105.     float phi()
  106.     {
  107.         float phi = 0;
  108.         for (int i = 0; i < N; i++)
  109.             for (int j = 0; j < N; j++)
  110.                 phi += c[i][j] * f[i][j];
  111.         return phi;
  112.     }
  113.  
  114.     void findUnbalanced()
  115.     {
  116.         int nn = 0, np = 0; // number of vertices of negative/positive delta
  117.         for (int i = 0; i < N; i++)
  118.             if (delta[i] < 0)
  119.                 nn++;
  120.             else if (delta[i] > 0)
  121.                 np++;
  122.         neg = new int[nn];
  123.         pos = new int[np];
  124.         nn = np = 0;
  125.         for (int i = 0; i < N; i++)
  126.             // initialise sets
  127.             if (delta[i] < 0)
  128.                 neg[nn++] = i;
  129.             else if (delta[i] > 0)
  130.                 pos[np++] = i;
  131.     }
  132.  
  133.     void findFeasible()
  134.     {   // delete next 3 lines to be faster, but non-reentrant
  135.         int delta[] = new int[N];
  136.         for (int i = 0; i < N; i++)
  137.             delta[i] = this.delta[i];
  138.         for (int u = 0; u < neg.length; u++)
  139.         {
  140.             int i = neg[u];
  141.             for (int v = 0; v < pos.length; v++)
  142.             {
  143.                 int j = pos[v];
  144.                 f[i][j] = -delta[i] < delta[j] ? -delta[i] : delta[j];
  145.                 delta[i] += f[i][j];
  146.                 delta[j] -= f[i][j];
  147.             }
  148.         }
  149.     }
  150.  
  151.     boolean improvements()
  152.     {
  153.         ChinesePostmanProblem residual = new ChinesePostmanProblem(N);
  154.         for (int u = 0; u < neg.length; u++)
  155.         {
  156.             int i = neg[u];
  157.             for (int v = 0; v < pos.length; v++)
  158.             {
  159.                 int j = pos[v];
  160.                 residual.addArc(null, i, j, c[i][j]);
  161.                 if (f[i][j] != 0)
  162.                     residual.addArc(null, j, i, -c[i][j]);
  163.             }
  164.         }
  165.         residual.leastCostPaths(); // find a negative cycle
  166.         for (int i = 0; i < N; i++)
  167.             if (residual.c[i][i] < 0) // cancel the cycle (if any)
  168.             {
  169.                 int k = 0, u, v;
  170.                 boolean kunset = true;
  171.                 u = i;
  172.                 do // find k to cancel
  173.                 {
  174.                     v = residual.path[u][i];
  175.                     if (residual.c[u][v] < 0 && (kunset || k > f[v][u]))
  176.                     {
  177.                         k = f[v][u];
  178.                         kunset = false;
  179.                     }
  180.                 }
  181.                 while ((u = v) != i);
  182.                 u = i;
  183.                 do // cancel k along the cycle
  184.                 {
  185.                     v = residual.path[u][i];
  186.                     if (residual.c[u][v] < 0)
  187.                         f[v][u] -= k;
  188.                     else
  189.                         f[u][v] += k;
  190.                 }
  191.                 while ((u = v) != i);
  192.                 return true; // have another go
  193.             }
  194.         return false; // no improvements found
  195.     }
  196.  
  197.     static final int NONE = -1; // anything < 0
  198.  
  199.     int findPath(int from, int f[][]) // find a path between unbalanced vertices
  200.     {
  201.         for (int i = 0; i < N; i++)
  202.             if (f[from][i] > 0)
  203.                 return i;
  204.         return NONE;
  205.     }
  206.  
  207.     void printCPT(int startVertex)
  208.     {
  209.         int v = startVertex;
  210.         // delete next 7 lines to be faster, but non-reentrant
  211.         int arcs[][] = new int[N][N];
  212.         int f[][] = new int[N][N];
  213.         for (int i = 0; i < N; i++)
  214.             for (int j = 0; j < N; j++)
  215.             {
  216.                 arcs[i][j] = this.arcs[i][j];
  217.                 f[i][j] = this.f[i][j];
  218.             }
  219.         while (true)
  220.         {
  221.             int u = v;
  222.             if ((v = findPath(u, f)) != NONE)
  223.             {
  224.                 f[u][v]--; // remove path
  225.                 for (int p; u != v; u = p) // break down path into its arcs
  226.                 {
  227.                     p = path[u][v];
  228.                     System.out.println("Take arc " + cheapestLabel[u][p]
  229.                             + " from " + u + " to " + p);
  230.                 }
  231.             }
  232.             else
  233.             {
  234.                 int bridgeVertex = path[u][startVertex];
  235.                 if (arcs[u][bridgeVertex] == 0)
  236.                     break; // finished if bridge already used
  237.                 v = bridgeVertex;
  238.                 for (int i = 0; i < N; i++)
  239.                     // find an unused arc, using bridge last
  240.                     if (i != bridgeVertex && arcs[u][i] > 0)
  241.                     {
  242.                         v = i;
  243.                         break;
  244.                     }
  245.                 arcs[u][v]--; // decrement count of parallel arcs
  246.                 System.out.println("Take arc "
  247.                         + label[u][v].elementAt(arcs[u][v]) + " from " + u
  248.                         + " to " + v); // use each arc label in turn
  249.             }
  250.         }
  251.     }
  252.  
  253.     static public void main(String args[])
  254.     {
  255.         // create a graph of four vertices
  256.         ChinesePostmanProblem G = new ChinesePostmanProblem(4);
  257.         // add the arcs for the example graph
  258.         G.addArc("a", 0, 1, 1).addArc("b", 0, 2, 1).addArc("c", 1, 2, 1)
  259.                 .addArc("d", 1, 3, 1).addArc("e", 2, 3, 1).addArc("f", 3, 0, 1);
  260.         G.solve(); // find the CPT
  261.         G.printCPT(0); // print it, starting from vertex 0
  262.         System.out.println("Cost = " + G.cost());
  263.         OpenCPP.test();
  264.     }
  265.  
  266.     // Print arcs and f
  267.     void debugarcf()
  268.     {
  269.         for (int i = 0; i < N; i++)
  270.         {
  271.             System.out.print("f[" + i + "]= ");
  272.             for (int j = 0; j < N; j++)
  273.                 System.out.print(f[i][j] + " ");
  274.             System.out.print("  arcs[" + i + "]= ");
  275.             for (int j = 0; j < N; j++)
  276.                 System.out.print(arcs[i][j] + " ");
  277.             System.out.println();
  278.         }
  279.     }
  280.  
  281.     // Print out most of the matrices: defined, path and f
  282.     void debug()
  283.     {
  284.         for (int i = 0; i < N; i++)
  285.         {
  286.             System.out.print(i + " ");
  287.             for (int j = 0; j < N; j++)
  288.                 System.out
  289.                         .print(j + ":" + (defined[i][j] ? "T" : "F") + " "
  290.                                 + c[i][j] + " p=" + path[i][j] + " f="
  291.                                 + f[i][j] + "; ");
  292.             System.out.println();
  293.         }
  294.     }
  295.  
  296.     // Print out non zero f elements, and phi
  297.     void debugf()
  298.     {
  299.         float sum = 0;
  300.         for (int i = 0; i < N; i++)
  301.         {
  302.             boolean any = false;
  303.             for (int j = 0; j < N; j++)
  304.                 if (f[i][j] != 0)
  305.                 {
  306.                     any = true;
  307.                     System.out.print("f(" + i + "," + j + ":" + label[i][j]
  308.                             + ")=" + f[i][j] + "@" + c[i][j] + "  ");
  309.                     sum += f[i][j] * c[i][j];
  310.                 }
  311.             if (any)
  312.                 System.out.println();
  313.         }
  314.         System.out.println("-->phi=" + sum);
  315.     }
  316.  
  317.     // Print out cost matrix.
  318.     void debugc()
  319.     {
  320.         for (int i = 0; i < N; i++)
  321.         {
  322.             boolean any = false;
  323.             for (int j = 0; j < N; j++)
  324.                 if (c[i][j] != 0)
  325.                 {
  326.                     any = true;
  327.                     System.out.print("c(" + i + "," + j + ":" + label[i][j]
  328.                             + ")=" + c[i][j] + "  ");
  329.                 }
  330.             if (any)
  331.                 System.out.println();
  332.         }
  333.     }
  334. }
  335.  
  336. class OpenCPP
  337. {
  338.     class Arc
  339.     {
  340.         String lab;
  341.         int    u, v;
  342.         float  cost;
  343.  
  344.         Arc(String lab, int u, int v, float cost)
  345.         {
  346.             this.lab = lab;
  347.             this.u = u;
  348.             this.v = v;
  349.             this.cost = cost;
  350.         }
  351.     }
  352.  
  353.     Vector<Arc> arcs = new Vector<Arc>();
  354.     int         N;
  355.  
  356.     OpenCPP(int vertices)
  357.     {
  358.         N = vertices;
  359.     }
  360.  
  361.     OpenCPP addArc(String lab, int u, int v, float cost)
  362.     {
  363.         if (cost < 0)
  364.             throw new Error("Graph has negative costs");
  365.         arcs.addElement(new Arc(lab, u, v, cost));
  366.         return this;
  367.     }
  368.  
  369.     float printCPT(int startVertex)
  370.     {
  371.         ChinesePostmanProblem bestGraph = null, g;
  372.         float bestCost = 0, cost;
  373.         int i = 0;
  374.         do
  375.         {
  376.             g = new ChinesePostmanProblem(N + 1);
  377.             for (int j = 0; j < arcs.size(); j++)
  378.             {
  379.                 Arc it = arcs.elementAt(j);
  380.                 g.addArc(it.lab, it.u, it.v, it.cost);
  381.             }
  382.             cost = g.basicCost;
  383.             g.findUnbalanced(); // initialise g.neg on original graph
  384.             g.addArc("'virtual start'", N, startVertex, cost);
  385.             g.addArc("'virtual end'",
  386.             // graph is Eulerian if neg.length=0
  387.                     g.neg.length == 0 ? startVertex : g.neg[i], N, cost);
  388.             g.solve();
  389.             if (bestGraph == null || bestCost > g.cost())
  390.             {
  391.                 bestCost = g.cost();
  392.                 bestGraph = g;
  393.             }
  394.         }
  395.         while (++i < g.neg.length);
  396.         System.out.println("Open CPT from " + startVertex
  397.                 + " (ignore virtual arcs)");
  398.         bestGraph.printCPT(N);
  399.         return cost + bestGraph.phi();
  400.     }
  401.  
  402.     static void test()
  403.     {
  404.         OpenCPP G = new OpenCPP(4); // create a graph of four vertices
  405.         // add the arcs for the example graph
  406.         G.addArc("a", 0, 1, 1).addArc("b", 0, 2, 1).addArc("c", 1, 2, 1)
  407.                 .addArc("d", 1, 3, 1).addArc("e", 2, 3, 1).addArc("f", 3, 0, 1);
  408.         int besti = 0;
  409.         float bestCost = 0;
  410.         for (int i = 0; i < 4; i++)
  411.         {
  412.             System.out.println("Solve from " + i);
  413.             float c = G.printCPT(i);
  414.             System.out.println("Cost = " + c);
  415.             if (i == 0 || c < bestCost)
  416.             {
  417.                 bestCost = c;
  418.                 besti = i;
  419.             }
  420.         }
  421.         G.printCPT(besti);
  422.         System.out.println("Cost = " + bestCost);
  423.     }
  424. }

Output:

$ javac ChinesePostmanProblem.java
$ java ChinesePostmanProblem
 
Take arc b from 0 to 2
Take arc e from 2 to 3
Take arc f from 3 to 0
Take arc a from 0 to 1
Take arc c from 1 to 2
Take arc e from 2 to 3
Take arc f from 3 to 0
Take arc a from 0 to 1
Take arc d from 1 to 3
Take arc f from 3 to 0
Cost = 10.0
Solve from 0
Open CPT from 0 (ignore virtual arcs)
Take arc 'virtual start' from 4 to 0
Take arc a from 0 to 1
Take arc d from 1 to 3
Take arc f from 3 to 0
Take arc a from 0 to 1
Take arc c from 1 to 2
Take arc e from 2 to 3
Take arc f from 3 to 0
Take arc b from 0 to 2
Take arc 'virtual end' from 2 to 4
Cost = 8.0
Solve from 1
Open CPT from 1 (ignore virtual arcs)
Take arc 'virtual start' from 4 to 1
Take arc d from 1 to 3
Take arc f from 3 to 0
Take arc a from 0 to 1
Take arc c from 1 to 2
Take arc e from 2 to 3
Take arc f from 3 to 0
Take arc b from 0 to 2
Take arc 'virtual end' from 2 to 4
Cost = 7.0
Solve from 2
Open CPT from 2 (ignore virtual arcs)
Take arc 'virtual start' from 4 to 2
Take arc e from 2 to 3
Take arc f from 3 to 0
Take arc a from 0 to 1
Take arc d from 1 to 3
Take arc f from 3 to 0
Take arc a from 0 to 1
Take arc c from 1 to 2
Take arc e from 2 to 3
Take arc f from 3 to 0
Take arc b from 0 to 2
Take arc 'virtual end' from 2 to 4
Cost = 10.0
Solve from 3
Open CPT from 3 (ignore virtual arcs)
Take arc 'virtual start' from 4 to 3
Take arc f from 3 to 0
Take arc a from 0 to 1
Take arc d from 1 to 3
Take arc f from 3 to 0
Take arc a from 0 to 1
Take arc c from 1 to 2
Take arc e from 2 to 3
Take arc f from 3 to 0
Take arc b from 0 to 2
Take arc 'virtual end' from 2 to 4
Cost = 9.0
Open CPT from 1 (ignore virtual arcs)
Take arc 'virtual start' from 4 to 1
Take arc d from 1 to 3
Take arc f from 3 to 0
Take arc a from 0 to 1
Take arc c from 1 to 2
Take arc e from 2 to 3
Take arc f from 3 to 0
Take arc b from 0 to 2
Take arc 'virtual end' from 2 to 4
Cost = 7.0

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.