<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Generator" CONTENT="MS Exchange Server version 6.5.7653.38">
<TITLE>Trouble with MaxWeightedPerfectMatching</TITLE>
</HEAD>
<BODY>
<!-- Converted from text/plain format -->
<P><FONT SIZE=2>I am having trouble with the maximum weighted perfect matching algorithm for a particular graph. The code seems to initialize properly and runs on my other graphs, but for this structure the program enters the MaxWeightedPerfectMatching.run() function and never returns. The graph is 48 nodes, 192 edges, so it shouldn't be large enough to present a serious computing challenge. I've tried loading the graph dump back into a simple solver module (code below) to see if it was a memory corruption in the original program, but that doesn't seem to be the case. Even the driver program seems to sit in a loop.<BR>
<BR>
I've run the graph through another weighted matching program (the Rothberg code) and verified that a matching exists, but LEMON doesn't seem to be able to find it. I'm running the LEMON 0.7 branch with gcc 4.3.2. <BR>
<BR>
The graph structure and driver code follow below. I'd appreciate any advice.<BR>
<BR>
Thanks,<BR>
Philip Waldron<BR>
<BR>
---------------------------------------<BR>
<BR>
@nodeset<BR>
label <BR>
0 <BR>
1 <BR>
2 <BR>
3 <BR>
4 <BR>
5 <BR>
6 <BR>
7 <BR>
8 <BR>
9 <BR>
10 <BR>
11 <BR>
12 <BR>
13 <BR>
14 <BR>
15 <BR>
16 <BR>
17 <BR>
18 <BR>
19 <BR>
20 <BR>
21 <BR>
22 <BR>
23 <BR>
24 <BR>
25 <BR>
26 <BR>
27 <BR>
28 <BR>
29 <BR>
30 <BR>
31 <BR>
32 <BR>
33 <BR>
34 <BR>
35 <BR>
36 <BR>
37 <BR>
38 <BR>
39 <BR>
40 <BR>
41 <BR>
42 <BR>
43 <BR>
44 <BR>
45 <BR>
46 <BR>
47 <BR>
@uedgeset<BR>
label weight <BR>
0 43 0 2999995<BR>
0 45 1 2080001<BR>
0 46 2 550001 <BR>
0 47 3 1 <BR>
1 44 4 3840001<BR>
1 45 5 3430001<BR>
1 46 6 2080001<BR>
1 47 7 1590001<BR>
2 40 8 4600000<BR>
2 44 9 4230000<BR>
2 46 10 2550000<BR>
2 47 11 2080000<BR>
3 40 12 4600001<BR>
3 44 13 4230001<BR>
3 46 14 2550001<BR>
3 47 15 2080001<BR>
4 41 16 5279997<BR>
4 43 17 5279991<BR>
4 44 18 4950000<BR>
4 45 19 4600000<BR>
5 39 20 5589999<BR>
5 41 21 5279999<BR>
5 42 22 5279997<BR>
5 43 23 5279995<BR>
6 34 24 6400001<BR>
6 37 25 6399995<BR>
6 39 26 6149999<BR>
6 42 27 5879997<BR>
7 31 28 6839997<BR>
7 32 29 6839991<BR>
7 33 30 6839985<BR>
7 37 31 6629979<BR>
8 32 32 6839993<BR>
8 35 33 6629993<BR>
8 40 34 6149998<BR>
8 41 35 6149993<BR>
9 36 36 6629991<BR>
9 40 37 6149999<BR>
9 41 38 6149995<BR>
9 42 39 6149991<BR>
10 34 40 6630000<BR>
10 39 41 6399997<BR>
10 43 42 6149991<BR>
10 45 43 5590000<BR>
11 32 44 6839999<BR>
11 34 45 6630001<BR>
11 38 46 6400001<BR>
11 42 47 6149997<BR>
12 30 48 7200000<BR>
12 31 49 7030000<BR>
12 36 50 6839994<BR>
12 37 51 6839991<BR>
13 30 52 7200001<BR>
13 32 53 7029999<BR>
13 33 54 7029997<BR>
13 36 55 6839997<BR>
14 20 56 7799995<BR>
14 27 57 7679999<BR>
14 38 58 6839999<BR>
14 39 59 6839995<BR>
15 31 60 7200000<BR>
15 33 61 7199994<BR>
15 35 62 7029997<BR>
15 36 63 7029994<BR>
16 19 64 7800001<BR>
16 23 65 7749999<BR>
16 28 66 7679999<BR>
16 37 67 7029995<BR>
17 20 68 7829997<BR>
17 27 69 7750000<BR>
17 29 70 7590000<BR>
17 38 71 7030000<BR>
18 27 72 7750001<BR>
18 30 73 7480001<BR>
18 34 74 7200001<BR>
18 38 75 7030001<BR>
19 22 76 7829999<BR>
19 23 77 7829995<BR>
19 28 78 7799995<BR>
20 22 79 7830000<BR>
20 25 80 7829991<BR>
21 23 81 7829999<BR>
21 26 82 7829993<BR>
21 27 83 7800001<BR>
21 31 84 7480001<BR>
22 23 85 7845002<BR>
22 24 86 7845003<BR>
24 29 87 7749999<BR>
24 30 88 7679999<BR>
24 35 89 7479995<BR>
25 26 90 7845002<BR>
25 29 91 7750000<BR>
25 35 92 7479997<BR>
26 28 93 7829999<BR>
26 29 94 7750001<BR>
28 33 95 7679997<BR>
@end<BR>
<BR>
--------------------------------------------------------<BR>
<BR>
#include <iostream><BR>
#include <limits><BR>
#include <lemon/list_graph.h><BR>
#include <lemon/max_matching.h><BR>
#include <lemon/graph_reader.h><BR>
<BR>
typedef lemon::ListUGraph Graph;<BR>
typedef Graph::Node Node;<BR>
typedef Graph::UEdge UEdge;<BR>
typedef Graph::NodeIt NodeIt;<BR>
typedef Graph::NodeMap<long long> NodeMap;<BR>
typedef Graph::UEdgeMap<long long> LengthMap;<BR>
<BR>
int main(int argc, char **argv) {<BR>
Graph g;<BR>
LengthMap weight(g);<BR>
<BR>
lemon::UGraphReader<Graph> reader(std::cin, g);<BR>
reader.readUEdgeMap("weight", weight);<BR>
reader.run();<BR>
<BR>
std::cout << "Starting match" << std::endl;<BR>
<BR>
lemon::MaxWeightedPerfectMatching<Graph, LengthMap> mwm(g, weight);<BR>
mwm.run();<BR>
<BR>
return 0;<BR>
}<BR>
</FONT>
</P>
</BODY>
</HTML>