# 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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!