Chinese Postman in Python
Detailed Implementation & Explanation, with special emphasis on unique approach to generate Odd Vertex Pairings using Recursion
Today, I’m going to explain and implement the popular ‘Chinese Postman’ Algorithm.
The article is divided in the following sections, for the convenience of the reader, and it is advised to go through all sections in order.
- A. Motivation
- B. Algorithm, Pre-Requisites & Presumptions
- C. Implementation
- D. Why this works?
- E. Final Code and References
Motivation
The Chinese Postman Problem was first investigated by the Chinese mathematician Kwan Mei-Ko in the early 1960’s. He posed the question, that what if a Postman (in his case a Chinese Postman, hence the name :D) wishes to travel along all the streets in a city, deliver letters and come back to his post office, with the least possible distance.
Since we live in the age of Internet, where e-mails and instant messaging have taken over the traditional letters, I will revamp the problem to suit this generation 😃
Let’s imagine you are on an amazing vacation, in an ancient beautiful city. We’ll have to imagine this, given the current scenario, and wait until the Covid-19 pandemic blows away to try this out.
You seek a tour of this city, and being a passionate tourist, and let’s say a photographer; starting from your hotel, you wish to visit every street in this city at least once, and come back to your hotel. (Street Photography is your hobby :D)
However, you have a big backpack to carry, camera equipment, rations, etc. This puts a physical limit on how much you can walk. Moreover, you don’t have all the time in the world to meander and keep wandering all day, seeking all streets one by one. (Though that sounds lovely!)
You wish to know what the minimum possible distance to accomplish this tour is, and how to do so?
Well, after reading this article, you will be able to implement a python program, which would return you the minimum distance required to make your tour, if you feed in the map of the city as a Graph!
Algorithm, Pre-Requisites and Presumptions
Speaking in terms of Graph Theory, the problem is to simply find the Path Distance of the Euler’s Circuit in a graph. However, a graph can only have an Euler’s Circuit (or also known as Euler’s Cycle), if all the degrees of its vertices are even.
So if we have a graph with all even vertices, the Euler’s Circuit in that graph would traverse each edge exactly once.
This covers one of the cases of our Algorithm: If our graph has all even vertices, we simply need to return the sum of all weights of edges in that graph.
But the world isn’t a perfect place now, is it? The possibility of finding graph of a city with all even vertices is very unlikely. In fact, one doesn’t even find such graphs in their exam question papers, leave alone ancient cities (I’m a student too :D)
So what happens in case of a graph having some odd vertices? This is where the Chinese Postman Algorithm steps up.
- We find all the Odd Vertices in our Graph.
2. Determine all the possible pairings of odd vertices.
3. For each pairing, we find the edges that connect the odd vertices with the shortest possible path.
4. From the above combinations, we select the one with the shortest total length.
5. We compute the minimum distance for Chinese Postman by taking into account the new shortest extra edges added.
Before I dive into each of the steps, I will elaborate on what parts of the algorithm I’ll be explaining in detail, and the parts which are Pre-Requisites.
Pre-Requisites:
- We will be using the Dijkstra’s Algorithm to compute the shortest possible path between pairings. I will be implementing this in python; however I will not be explaining the algorithm itself in detail.
- Basic knowledge of python data structures and syntax, like lists, sets, loops, etc.
- Familiarity with the concept of Recursion.
- Familiarity with basic concepts of Graph Theory.
- Willingness to learn! :D
Steps covered in detail:
- Generating Odd Vertices Pairings: This is done by an Algorithm using Recursion, which I thought of when first solving this problem.
- From all combinations, selecting the appropriate one.
- All calculations leading to final minimum distance of a Chinese Postman tour.
Presumptions:
- I’m implementing this Algorithm considering a connected, undirected, weighted graph, with positive weights.
- Since the problem statement is often interpreted as finding the minimum distance with routes, I consider the assumption of undirected and positive weighted graph justified.
So now we are equipped with an Algorithm to get the minimum distance for the tour of the Ancient City. I will be demonstrating each step through python code blocks, and the entire code will be attached at the end. Please note that the implementations done by me are possibly not the most efficient of those existing out in the community, but, they reflect the ideas and approach required by an average student to code this algorithm :D
Implementation
The implementation of the Algorithm follows the following steps:
II. Implementing Dijkstra’s Algorithm as a function
III. Finding Odd Degree Vertices with a function
IV. Generating all Pairings of Odd Vertices with Recursion
V. Selecting Optimal Pairing with help of Dijkstra’s Function
VI. Implementing function to get sum of all edges
VII. Combining all Code Blocks together
VIII. Giving Chinese Postman Distance as Output for a Graph Input
I Defining Input as a Graph
We are taking an undirected, positive weighted graph as our input. We will store it in form of a list of lists, as shown in the code block.
Note: we can take user input to get graph in runtime, but since it would be cumbersome to enter the values one by one, we are taking pre-defined graphs to make our life easier 😄
As shown in the code block, we take 2 graphs as our input.
II Implementing Dijkstra’s Algorithm as a function
The objective of this algorithm is to find the shortest possible route, thus also distance, between given 2 nodes in a graph. It is of the category of a Greedy Algorithm, which tries to find the optimal path by seeking the nearest neighbors and adjusting itself. The only major drawback for Dijkstra’s is that it fails when weights are negative, where we use the Bellman Ford or other algorithms to find the shortest path.
The code block shows the approach taken to implement this algorithm, for a given set of source and destination vertexes of a graph. To find more details on implementation of this algorithm, see references.
III Finding Odd Degree Vertices
The decision to implement the steps for odd vertices depends on the very fact if odd vertices are present in our graph. If they aren’t, we can take a chill pill & just return the sum of all weights of edges😎 Otherwise we need to call in Chinese Postman for backup 👊
As our input graph is weighted and undirected, to find the degree of each vertex is not difficult. We just need to count number of non-zero entries for each node of the graph.
We do so by running a simple nested for loop, and keeping count for degrees of each vertex. Once we have degrees of each vertex, we use list comprehension to find the odd ones, and store the vertex number in another list called: odds, which we will need in future.
Keep in mind, the number of odd vertices in input graphs will always be even by the Handshaking Theorem.
IV Generating all Pairings of Odd Vertices
This step is often considered the most difficult part of this Algorithm to implement, and requires a lot of thought and effort. When I first solved this problem on my own, I spent almost 3–4 hours to come up with an algorithm to generate these pairings! However, the result was extremely satisfying and rewarding 🔥 I would encourage you to do the same, and give this step some thought. If you think and proceed logically, you might be able to solve this.
This Algorithm was made by me, but it might not be unique or original, in the sense that someone may have followed the same thought process and come up with a similar algorithm. However I am extremely proud to have thought this on my own, and this is one of the reasons for me to write this article, to share my approach, for the benefit of the community :)
Intuition and Logic
Our task is to get all possible pairings, which include all odd vertices. For example if the odd vertices are: A,B,C & D, the possible pairings are:-
§ (A,B) & (C,D)
§ (A,C) & (B,D)
§ (A,D) & (B, C)
This may look straightforward, but as the number of odd vertices increase, the numbers of such combinations increase exponentially. For example, for 10 odd vertices, there are 945 possible combinations!
Thus, to solve this problem, we must approach it rationally. If we observe how these pairs are being combined for a small number of vertices, we can generalize that for any number of vertices.
Refer the diagram given below. I have written down all unique pairs, for 6 odd vertices: A, B, C, D, E & F.
Each column contains the pairs, starting with each of A, B, C, D, E & F. Now any combination of pairings must include all of odd vertices, which are from A to F. So if we consider the first possible combination:
- We can combine AB,
- Then since B is taken -> go to C column
- Take CD
- Then since D is taken -> go to E column
- Take EF
So we got the first possible combination: (A,B) & (C,D) & (E,F)
For the second possible combination:
- Since E column has no more pairs remaining, we come back to C
- Now we take CE
- Now since D has NOT been taken -> go to D
- Since E is already been taken, take DF
So we got our second possible combination: (A,B) & (C,E) & (D,F)
We observe a pattern emerging here. If we are somehow able to keep track of vertices we have already used, then with recursion, we can easily get all possible combinations of pairings. Refer to the diagram below. Here I have visualized how we can get all combinations through each of the branches in a recursion like tree. We see that we will get 15 total combinations for 6 odd vertices.
Recursion Code
We first need a function which can give us all unique pairs, in the order as shown in Figure 1. We define a function ‘gen_pairs’, which uses a simple nested loop to fetch all the unique pairs. Since we want these pairs to be grouped by the columns starting with each letter, we make a list of lists -> ‘pairs’, where each column is a list. As shown in the code block, the function takes the odds list, which has all odd vertices, and returns pairs.
Now we come to our Recursion Function. To make a recursion function, we always need to think of 2 cases:-
§ The Base Case, where we return some output, or stop the recursion
§ The General Cases where we perform some computation and call our function again
We need two lists for input to the recursion function:
- ‘done’: This will keep track of the vertices we have already taken in our combination
- ‘final’: This will store all the combinations we want to generate
- Note: These need to be passed from one recursion call to another, without being overwritten. To counter this problem, I copied them without reference, using the slice operator. Example - val = done[:]
The recursion will be done in the ‘pairs’ list we previously generated, and the function will be called each time by slicing the list -> pairs[1:]
The recursion will only stop, when we finally get one combination. But since the ending pair of the combination can be from any of the columns, we check this condition by matching if the length of a combination list is equal to ‘Number of Vertices/ 2’. The reason for the condition is that since we will have pairs of 2, the total number of pairs will be ‘Number of Vertices’/2. Thus we pre-define a variable ‘l’, which is given the value: (len(pairs) + 1)//2
(Note: We use the pairs list to check this condition, as the logic is same. Feel free to use ‘odds’ to get this condition)
As shown in the code block, the code is short and sweet :D The cases just check if any of the letters in the pairs are in our done list, and if they aren’t, then we consider that pair for the combination.
I have also attached a Debugging version of this code, which I originally used while making this function. If you want to understand how the function is working at each recursion call, then it is recommended to remove some of my comments and run it.
V Selecting Optimal Pairing with help of Dijkstra’s
Firstly, if you’ve reached this far, then I commend you for your efforts, and I have some good news for you. All of the heavy work is done! 🎊
We now seek the pairing, where the total distance between the pairs is minimal. For example if we have odd vertices as: A, B, C & D
- We take each possible pairing, and calculate the total distance between each pair in that pairing, adding to the total distance for that pairing. This sounds very mumbo jumbo, but it is pretty easy to understand & implement
- For example, let’s take the pairing: (AB) & (CD):
· Using Dijkstra’s, let’s say minimum distance between A & B is: 20
· Using Dijkstra’s, let’s say minimum distance between C & D is: 10
· Then total distance for this pairing is: 20 + 10 = 30
- We repeat the process for (AC) & (BD) and (AD) & (BC)
- We choose the pairing with minimum distance out of all the 3 as our Optimal Pairing
This is also illustrated in the diagram shown below. (All values are considered randomly to demonstrate the process)
This is implemented in the code block below. We store the all distances in a list, and get the minimum of them as the extra distance needed to complete the Chinese Postman Distance
VI Function to get Sum of all Edges
The code block below uses simple nested loops to get sum of weights of all edges. We will need this to get sum of weights of input graph, which will be added with the extra distance computed by the minimum odd pairing.
VII Combining all Code Blocks
Congratulations! You made it to the very end 😃 All that remains is to call & use all the functions we wrote in one single function. Keep in mind, we need to account for both the cases for an input graph:
§ If all vertices are even: we return Chinese Postman distance as sum of all weights
§ If there are odd vertices: we compute odd pairings, get the minimum distance from the optimal one, and add it to the sum of all weights
VIII Final Chinese Postman Distance
The below code block has the final compiled function, which when called with a graph, will return the minimum distance required to traverse all edges of the graph at least once, and return to the starting vertex.
Why this works
Now, you will successfully be able to find the Chinese Postman distance from the above code. However, some doubts might linger in your mind, as to how this is actually working ❔
The below figure contains a simple graph with all even vertices. The Euler Circuit in this follows the arrows, which are from A -> B -> C -> D -> A. We see that the minimum distance we need to cover, to be able to visit all edges at least once, & come back to our starting vertex is same as sum of all weights of edges.
Now consider an addition to this graph as shown in the next figure. Now we have 2 odd vertices. Since the only pairing available here is AD, we get the minimum distance between them as the minimum pairing distance.
Now to visualize how we are completing the tour, let’s add a new edge along the shortest distance between the selected pairing AD
We see that this edge will make the graph have all even vertices. Now if we consider the Euler Circuit here, we will see that we need to traverse this new edge to reach back to our starting point. Thus, the total minimum distance for the Chinese Postman is the sum of all weights of the original graph, plus the weight of the added edge(s). That was precisely what our code was doing, without having to add an edge explicitly.
So the above diagrams convey the brilliance behind the Chinese Postman Algorithm!
Now you can visit any city in the world, make its map into a graph, feed it to your code, and get the minimum distance required for you to make the ‘Chinese Postman Tour’ :D
Final Code and References
Attached is the entire code for implementing the Chinese Postman Algorithm. If you also want the path for the minimum distance, then you can check out Fleury’s Algorithm, which can be used to display the Euler Circuit in the modified graph.
I’m very grateful to my University Graph Theory Professor Dr. Surabhi Narayan for teaching me these concepts and sparking my interest in this area :D
I hope you enjoyed this article, and are now well prepared to implement this algorithm on your own!
Below are some references to read more about the Chinese Postman Algorithm and Dijkstra’s Algorithm.
1. https://www.geeksforgeeks.org/chinese-postman-route-inspection-set-1-introduction/
2. https://en.wikipedia.org/wiki/Route_inspection_problem
3. https://www.youtube.com/watch?v=XB4MIexjvY0
4. https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/
