dilsonpereira / minimum-cost-perfect-matching Goto Github PK

Sometimes right, sometimes wrong.

The following is example of invalid matching:

#test file begin
34
42
0 1 10
1 2 6
2 3 10
3 4 6
4 5 10
5 6 6
6 7 10
8 0 10
9 8 10
7 10 10
11 12 10
12 9 10
13 14 6
14 11 10
15 16 10
17 18 10
18 19 6
19 13 10
20 21 6
21 22 10
10 23 4
23 20 10
22 24 6
24 15 6
16 25 4
25 17 10
5 0 10
12 26 10
26 27 6
28 29 6
29 11 10
28 27 10
27 23 6
28 24 4
30 25 6
9 31 10
31 10 6
32 29 6
30 13 10
30 32 10
33 7 6
33 8 10
#test file end

The invalid matching edges:
5 0
10 7
9 8
13 14
14 11
29 11
11 12
29 11
11 14
14 13
27 23
28 24
30 25
Solution cost: 440

How to fix it?

Sometimes returs invalid matching (compiled with : gcc version 7.3.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project))

./example.exe -f falsify.txt --minweight
Optimal matching cost: 6
Edges in the matching:
0 1
2 4
4 5

falsify.txt

removed unnecessary edges falsify.txt

Hey thanks for fixing the last issue. I ran into another problem. Sometimes your code crashes for me during Matching::Grow calls.
I attached a small python fuzzer that tries to match random graphs with 50 nodes. After a few seconds it crashes for me. Again compiled with gcc version 7.3.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project).

Minimum-Cost-Perfect-Matching.zip