1

When solving the Chinese postman problem (route inspection problem), how can we find the pairings (between odd vertices) such that the sum of the weights is minimized?

This is the most crucial step in the algorithm that successfully solves the Chinese Postman Problem for a non-Eulerian Graph. Though it is easy to implement on paper, but I am facing difficulty in implementing in Java.

I was thinking about ways to find all possible pairs but if one runs the first loop over all the odd vertices and the next loop for all the other possible pairs. This will only give one pair, to find all other pairs you would need another two loops and so on. This is rather strange as one will be 'looping over loops' in a crude sense. Is there a better way to resolve this problem.

I have read about the Edmonds-Jonhson algorithm, but I don't understand the motivation behind constructing a bipartite graph. And I have also read Chinese Postman Problem: finding best connections between odd-degree nodes, but the author does not explain how to implement a brute-force algorithm. Also the following question: How should I generate the partitions / pairs for the Chinese Postman problem? has been asked previously by a user of Stack overflow., but a reply to the post gives a python implementation of the code. I am not familiar with python and I would request any community member to rewrite the code in Java or if possible explain the algorithm.

Thank You.

Manu
  • 1,474
  • 1
  • 12
  • 18
Student
  • 119
  • 1
  • 1
  • 12
  • You should at least link to the previous post. And is your problem maybe just the assignment problem? – Niklas B. Dec 04 '15 at 11:12
  • you have some elements yet: algorithms, code in python (if not evident, you can see the logic inside ?), and your capabilities in java. Can you try to write some code ? – guillaume girod-vitouchkina Dec 04 '15 at 11:25
  • Learning isn't just about understanding study material, but mostly about asking the good question. You'd rather start [here](http://stackoverflow.com/help/how-to-ask) about how to ask a good question considering your question being too broad, unclear and lacks of quality. – eliasah Dec 04 '15 at 12:37

2 Answers2

0

Economical recursion

These tuples normally are called edges, aren't they?

You need a recursion. 

0. Create main stack of edge lists.
1. take all edges into a current edge list. Null the found edge stack.
2. take a next current edge for the current edge list and add it in the found edge stack.
3. Create the next edge list from the current edge list. push the current edge list into the main stack. Make next edge list current.
4. Clean current edge list from all adjacent to current edge and from current edge.
5. If the current edge list is not empty, loop to 2.
6. Remember the current state of found edge stack - it is the next result set of edges that you need.
7. Pop the the found edge stack into current edge. Pop the main stack into current edge list. If stacks are empty, return. Repeat until current edge has a next edge after it. 
8. loop to 2.

As a result, you have all possible sets of edges and you never need to check "if I had seen the same set in the different order?"

Gangnus
  • 24,044
  • 16
  • 90
  • 149
  • I implemented the algorithm that you have written, it works. But the Chinese Postman problem requires one to consider k/2 tuples of vertices that are not adjacent to one another. How should I generate all the possible combinations of non-adjacent edges? – Student Dec 04 '15 at 13:59
  • In continuation to the previous comment---For example, {A,B,C,D} Gives the possible edges as {AB,AC,AD,BC,BD,CD}. But when we choose AB we are forced to choose CD, similarly when we chose AC, we have to choose BD, thus we get the following groups-{{AB, CD}, {AC, BD}, {AD, BC}}. In this case, it is evident that the extreme ends of the edge array yield the desired tuples. But if the number of vertices increases(will always be even) then is there any general way to generate such groups? – Student Dec 04 '15 at 14:10
  • 1
    You have several questions in one post. It is not acceptable. – Gangnus Dec 04 '15 at 14:27
  • Please, remove all questions except the main one. If you need them, do not formulate them as questions. Change tuples to edges. – Gangnus Dec 04 '15 at 15:45
0

It's actually fairly simple when you wrap your head around it. I'm just sharing some code here in the hope it will help the next person!

The function below returns all the valid odd vertex combinations that one then needs to check for the shortest one.

private static ObjectArrayList<ObjectArrayList<IntArrayList>> getOddVertexCombinations(IntArrayList oddVertices,
                                                                                       ObjectArrayList<IntArrayList> buffer){
    ObjectArrayList<ObjectArrayList<IntArrayList>> toReturn = new ObjectArrayList<>();
    if (oddVertices.isEmpty()) {
        toReturn.add(buffer.clone());
    } else {
        int first = oddVertices.removeInt(0);
        for (int c = 0; c < oddVertices.size(); c++) {
            int second = oddVertices.removeInt(c);
            buffer.add(new IntArrayList(new int[]{first, second}));
            toReturn.addAll(getOddVertexCombinations(oddVertices, buffer));
            buffer.pop();
            oddVertices.add(c, second);
        }
        oddVertices.add(0, first);
    }
    return toReturn;
}
vincent
  • 1,953
  • 3
  • 18
  • 24