[Lemon-user] Trouble with MaxWeightedPerfectMatching

[Waldron, Philip]

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.

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.  

The graph structure and driver code follow below.  I'd appreciate any advice.

Thanks,
Philip Waldron

---------------------------------------

@nodeset 
label	
0	
1	
2	
3	
4	
5	
6	
7	
8	
9	
10	
11	
12	
13	
14	
15	
16	
17	
18	
19	
20	
21	
22	
23	
24	
25	
26	
27	
28	
29	
30	
31	
32	
33	
34	
35	
36	
37	
38	
39	
40	
41	
42	
43	
44	
45	
46	
47	
@uedgeset 
		label	weight	
0	43	0	2999995	
0	45	1	2080001	
0	46	2	550001	
0	47	3	1	
1	44	4	3840001	
1	45	5	3430001	
1	46	6	2080001	
1	47	7	1590001	
2	40	8	4600000	
2	44	9	4230000	
2	46	10	2550000	
2	47	11	2080000	
3	40	12	4600001	
3	44	13	4230001	
3	46	14	2550001	
3	47	15	2080001	
4	41	16	5279997	
4	43	17	5279991	
4	44	18	4950000	
4	45	19	4600000	
5	39	20	5589999	
5	41	21	5279999	
5	42	22	5279997	
5	43	23	5279995	
6	34	24	6400001	
6	37	25	6399995	
6	39	26	6149999	
6	42	27	5879997	
7	31	28	6839997	
7	32	29	6839991	
7	33	30	6839985	
7	37	31	6629979	
8	32	32	6839993	
8	35	33	6629993	
8	40	34	6149998	
8	41	35	6149993	
9	36	36	6629991	
9	40	37	6149999	
9	41	38	6149995	
9	42	39	6149991	
10	34	40	6630000	
10	39	41	6399997	
10	43	42	6149991	
10	45	43	5590000	
11	32	44	6839999	
11	34	45	6630001	
11	38	46	6400001	
11	42	47	6149997	
12	30	48	7200000	
12	31	49	7030000	
12	36	50	6839994	
12	37	51	6839991	
13	30	52	7200001	
13	32	53	7029999	
13	33	54	7029997	
13	36	55	6839997	
14	20	56	7799995	
14	27	57	7679999	
14	38	58	6839999	
14	39	59	6839995	
15	31	60	7200000	
15	33	61	7199994	
15	35	62	7029997	
15	36	63	7029994	
16	19	64	7800001	
16	23	65	7749999	
16	28	66	7679999	
16	37	67	7029995	
17	20	68	7829997	
17	27	69	7750000	
17	29	70	7590000	
17	38	71	7030000	
18	27	72	7750001	
18	30	73	7480001	
18	34	74	7200001	
18	38	75	7030001	
19	22	76	7829999	
19	23	77	7829995	
19	28	78	7799995	
20	22	79	7830000	
20	25	80	7829991	
21	23	81	7829999	
21	26	82	7829993	
21	27	83	7800001	
21	31	84	7480001	
22	23	85	7845002	
22	24	86	7845003	
24	29	87	7749999	
24	30	88	7679999	
24	35	89	7479995	
25	26	90	7845002	
25	29	91	7750000	
25	35	92	7479997	
26	28	93	7829999	
26	29	94	7750001	
28	33	95	7679997	
@end

--------------------------------------------------------

#include <iostream>
#include <limits>
#include <lemon/list_graph.h>
#include <lemon/max_matching.h>
#include <lemon/graph_reader.h>

typedef lemon::ListUGraph Graph;
typedef Graph::Node Node;
typedef Graph::UEdge UEdge;
typedef Graph::NodeIt NodeIt;
typedef Graph::NodeMap<long long> NodeMap;
typedef Graph::UEdgeMap<long long> LengthMap;

int main(int argc, char **argv) {
	Graph g;
	LengthMap weight(g);
	
	lemon::UGraphReader<Graph> reader(std::cin, g);
	reader.readUEdgeMap("weight", weight);
	reader.run();

	std::cout << "Starting match" << std::endl;

	lemon::MaxWeightedPerfectMatching<Graph, LengthMap> mwm(g, weight);
	mwm.run();

	return 0;
}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20081219/fbdd5686/attachment.html>