invalid matching about minimum-cost-perfect-matching HOT 5 CLOSED

Hi. I ran the code with your input and it gives me the following output, which seems to be correct:
Optimal matching cost: 124
Edges in the matching:
1 2
3 4
5 6
8 0
11 12
13 14
15 16
18 19
20 21
10 23
22 24
25 17
26 27
28 29
9 31
30 32
33 7

from minimum-cost-perfect-matching.

Hi. I ran the code with your input and it gives me the following output, which seems to be correct:
Optimal matching cost: 124
Edges in the matching:
1 2
3 4
5 6
8 0
11 12
13 14
15 16
18 19
20 21
10 23
22 24
25 17
26 27
28 29
9 31
30 32
33 7

I am sorry that I misled you due to a problem in my presentation. Actually, this is the result of the Chinese Postman Problem.

I used your algorithm to solve the Chinese Postman Problem and found that it was a mistake in the perfect matching algorithm that led to the wrong solution. So I'm posting the problem here.
The above text is the result of insert print code in line 98 of ChinesePostman.h to display the added edge.

                    while (w != -1)
		{
			A[w].push_back(v);
			A[v].push_back(w);
			printf("\n%d  %d", v, w);  //display added edge, line 98 of ChinesePostman.h
			v = w;
			w = shortestPath[u][v];
		}

See the red line segment in the image. Obviously, three of the new edges( 29->11, 11->14, 14->13 ) are redundant, causing the odd point to remain an odd point ( point: 29, 11, 13 ), So the solution fails.

There are some cases where your program works well and gets a very perfect result. Thank you for all your hard work. I am very much looking forward to the fix of this issue. I can provide more error cases if necessary.

from minimum-cost-perfect-matching.

Can you please update your copy of the chinese postman code and check if the problem is solved?

from minimum-cost-perfect-matching.

Can you please update your copy of the chinese postman code and check if the problem is solved?

The bug has been fixed!
Thank you for helping me, I really appreciate it.

from minimum-cost-perfect-matching.

Great. I fixed a bug in the matching code a while ago and I thought it would be automatically broadcast to the repos that depended on it. I was wrong and manually updating the chinese postman code with the current matching code seems to have fixed the bug you were experiencing.

from minimum-cost-perfect-matching.