15 * purpose. |
15 * purpose. |
16 * |
16 * |
17 */ |
17 */ |
18 |
18 |
19 #include <iostream> |
19 #include <iostream> |
|
20 #include <sstream> |
20 #include <vector> |
21 #include <vector> |
21 #include <queue> |
22 #include <queue> |
22 #include <lemon/math.h> |
23 #include <lemon/math.h> |
23 #include <cstdlib> |
24 #include <cstdlib> |
24 |
25 |
|
26 #include <lemon/max_matching.h> |
|
27 #include <lemon/smart_graph.h> |
|
28 #include <lemon/lgf_reader.h> |
|
29 |
25 #include "test_tools.h" |
30 #include "test_tools.h" |
26 #include <lemon/list_graph.h> |
|
27 #include <lemon/max_matching.h> |
|
28 |
31 |
29 using namespace std; |
32 using namespace std; |
30 using namespace lemon; |
33 using namespace lemon; |
31 |
34 |
|
35 GRAPH_TYPEDEFS(SmartGraph); |
|
36 |
|
37 |
|
38 const int lgfn = 3; |
|
39 const std::string lgf[lgfn] = { |
|
40 "@nodes\n" |
|
41 "label\n" |
|
42 "0\n" |
|
43 "1\n" |
|
44 "2\n" |
|
45 "3\n" |
|
46 "4\n" |
|
47 "5\n" |
|
48 "6\n" |
|
49 "7\n" |
|
50 "@edges\n" |
|
51 " label weight\n" |
|
52 "7 4 0 984\n" |
|
53 "0 7 1 73\n" |
|
54 "7 1 2 204\n" |
|
55 "2 3 3 583\n" |
|
56 "2 7 4 565\n" |
|
57 "2 1 5 582\n" |
|
58 "0 4 6 551\n" |
|
59 "2 5 7 385\n" |
|
60 "1 5 8 561\n" |
|
61 "5 3 9 484\n" |
|
62 "7 5 10 904\n" |
|
63 "3 6 11 47\n" |
|
64 "7 6 12 888\n" |
|
65 "3 0 13 747\n" |
|
66 "6 1 14 310\n", |
|
67 |
|
68 "@nodes\n" |
|
69 "label\n" |
|
70 "0\n" |
|
71 "1\n" |
|
72 "2\n" |
|
73 "3\n" |
|
74 "4\n" |
|
75 "5\n" |
|
76 "6\n" |
|
77 "7\n" |
|
78 "@edges\n" |
|
79 " label weight\n" |
|
80 "2 5 0 710\n" |
|
81 "0 5 1 241\n" |
|
82 "2 4 2 856\n" |
|
83 "2 6 3 762\n" |
|
84 "4 1 4 747\n" |
|
85 "6 1 5 962\n" |
|
86 "4 7 6 723\n" |
|
87 "1 7 7 661\n" |
|
88 "2 3 8 376\n" |
|
89 "1 0 9 416\n" |
|
90 "6 7 10 391\n", |
|
91 |
|
92 "@nodes\n" |
|
93 "label\n" |
|
94 "0\n" |
|
95 "1\n" |
|
96 "2\n" |
|
97 "3\n" |
|
98 "4\n" |
|
99 "5\n" |
|
100 "6\n" |
|
101 "7\n" |
|
102 "@edges\n" |
|
103 " label weight\n" |
|
104 "6 2 0 553\n" |
|
105 "0 7 1 653\n" |
|
106 "6 3 2 22\n" |
|
107 "4 7 3 846\n" |
|
108 "7 2 4 981\n" |
|
109 "7 6 5 250\n" |
|
110 "5 2 6 539\n", |
|
111 }; |
|
112 |
|
113 void checkMatching(const SmartGraph& graph, |
|
114 const MaxMatching<SmartGraph>& mm) { |
|
115 int num = 0; |
|
116 |
|
117 IntNodeMap comp_index(graph); |
|
118 UnionFind<IntNodeMap> comp(comp_index); |
|
119 |
|
120 int barrier_num = 0; |
|
121 |
|
122 for (NodeIt n(graph); n != INVALID; ++n) { |
|
123 check(mm.decomposition(n) == MaxMatching<SmartGraph>::EVEN || |
|
124 mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition"); |
|
125 if (mm.decomposition(n) == MaxMatching<SmartGraph>::ODD) { |
|
126 ++barrier_num; |
|
127 } else { |
|
128 comp.insert(n); |
|
129 } |
|
130 } |
|
131 |
|
132 for (EdgeIt e(graph); e != INVALID; ++e) { |
|
133 if (mm.matching(e)) { |
|
134 check(e == mm.matching(graph.u(e)), "Wrong matching"); |
|
135 check(e == mm.matching(graph.v(e)), "Wrong matching"); |
|
136 ++num; |
|
137 } |
|
138 check(mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::EVEN || |
|
139 mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED, |
|
140 "Wrong Gallai-Edmonds decomposition"); |
|
141 |
|
142 check(mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::EVEN || |
|
143 mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED, |
|
144 "Wrong Gallai-Edmonds decomposition"); |
|
145 |
|
146 if (mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::ODD && |
|
147 mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::ODD) { |
|
148 comp.join(graph.u(e), graph.v(e)); |
|
149 } |
|
150 } |
|
151 |
|
152 std::set<int> comp_root; |
|
153 int odd_comp_num = 0; |
|
154 for (NodeIt n(graph); n != INVALID; ++n) { |
|
155 if (mm.decomposition(n) != MaxMatching<SmartGraph>::ODD) { |
|
156 int root = comp.find(n); |
|
157 if (comp_root.find(root) == comp_root.end()) { |
|
158 comp_root.insert(root); |
|
159 if (comp.size(n) % 2 == 1) { |
|
160 ++odd_comp_num; |
|
161 } |
|
162 } |
|
163 } |
|
164 } |
|
165 |
|
166 check(mm.matchingSize() == num, "Wrong matching"); |
|
167 check(2 * num == countNodes(graph) - (odd_comp_num - barrier_num), |
|
168 "Wrong matching"); |
|
169 return; |
|
170 } |
|
171 |
|
172 void checkWeightedMatching(const SmartGraph& graph, |
|
173 const SmartGraph::EdgeMap<int>& weight, |
|
174 const MaxWeightedMatching<SmartGraph>& mwm) { |
|
175 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { |
|
176 if (graph.u(e) == graph.v(e)) continue; |
|
177 int rw = mwm.nodeValue(graph.u(e)) + mwm.nodeValue(graph.v(e)); |
|
178 |
|
179 for (int i = 0; i < mwm.blossomNum(); ++i) { |
|
180 bool s = false, t = false; |
|
181 for (MaxWeightedMatching<SmartGraph>::BlossomIt n(mwm, i); |
|
182 n != INVALID; ++n) { |
|
183 if (graph.u(e) == n) s = true; |
|
184 if (graph.v(e) == n) t = true; |
|
185 } |
|
186 if (s == true && t == true) { |
|
187 rw += mwm.blossomValue(i); |
|
188 } |
|
189 } |
|
190 rw -= weight[e] * mwm.dualScale; |
|
191 |
|
192 check(rw >= 0, "Negative reduced weight"); |
|
193 check(rw == 0 || !mwm.matching(e), |
|
194 "Non-zero reduced weight on matching edge"); |
|
195 } |
|
196 |
|
197 int pv = 0; |
|
198 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { |
|
199 if (mwm.matching(n) != INVALID) { |
|
200 check(mwm.nodeValue(n) >= 0, "Invalid node value"); |
|
201 pv += weight[mwm.matching(n)]; |
|
202 SmartGraph::Node o = graph.target(mwm.matching(n)); |
|
203 check(mwm.mate(n) == o, "Invalid matching"); |
|
204 check(mwm.matching(n) == graph.oppositeArc(mwm.matching(o)), |
|
205 "Invalid matching"); |
|
206 } else { |
|
207 check(mwm.mate(n) == INVALID, "Invalid matching"); |
|
208 check(mwm.nodeValue(n) == 0, "Invalid matching"); |
|
209 } |
|
210 } |
|
211 |
|
212 int dv = 0; |
|
213 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { |
|
214 dv += mwm.nodeValue(n); |
|
215 } |
|
216 |
|
217 for (int i = 0; i < mwm.blossomNum(); ++i) { |
|
218 check(mwm.blossomValue(i) >= 0, "Invalid blossom value"); |
|
219 check(mwm.blossomSize(i) % 2 == 1, "Even blossom size"); |
|
220 dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2); |
|
221 } |
|
222 |
|
223 check(pv * mwm.dualScale == dv * 2, "Wrong duality"); |
|
224 |
|
225 return; |
|
226 } |
|
227 |
|
228 void checkWeightedPerfectMatching(const SmartGraph& graph, |
|
229 const SmartGraph::EdgeMap<int>& weight, |
|
230 const MaxWeightedPerfectMatching<SmartGraph>& mwpm) { |
|
231 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { |
|
232 if (graph.u(e) == graph.v(e)) continue; |
|
233 int rw = mwpm.nodeValue(graph.u(e)) + mwpm.nodeValue(graph.v(e)); |
|
234 |
|
235 for (int i = 0; i < mwpm.blossomNum(); ++i) { |
|
236 bool s = false, t = false; |
|
237 for (MaxWeightedPerfectMatching<SmartGraph>::BlossomIt n(mwpm, i); |
|
238 n != INVALID; ++n) { |
|
239 if (graph.u(e) == n) s = true; |
|
240 if (graph.v(e) == n) t = true; |
|
241 } |
|
242 if (s == true && t == true) { |
|
243 rw += mwpm.blossomValue(i); |
|
244 } |
|
245 } |
|
246 rw -= weight[e] * mwpm.dualScale; |
|
247 |
|
248 check(rw >= 0, "Negative reduced weight"); |
|
249 check(rw == 0 || !mwpm.matching(e), |
|
250 "Non-zero reduced weight on matching edge"); |
|
251 } |
|
252 |
|
253 int pv = 0; |
|
254 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { |
|
255 check(mwpm.matching(n) != INVALID, "Non perfect"); |
|
256 pv += weight[mwpm.matching(n)]; |
|
257 SmartGraph::Node o = graph.target(mwpm.matching(n)); |
|
258 check(mwpm.mate(n) == o, "Invalid matching"); |
|
259 check(mwpm.matching(n) == graph.oppositeArc(mwpm.matching(o)), |
|
260 "Invalid matching"); |
|
261 } |
|
262 |
|
263 int dv = 0; |
|
264 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { |
|
265 dv += mwpm.nodeValue(n); |
|
266 } |
|
267 |
|
268 for (int i = 0; i < mwpm.blossomNum(); ++i) { |
|
269 check(mwpm.blossomValue(i) >= 0, "Invalid blossom value"); |
|
270 check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size"); |
|
271 dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2); |
|
272 } |
|
273 |
|
274 check(pv * mwpm.dualScale == dv * 2, "Wrong duality"); |
|
275 |
|
276 return; |
|
277 } |
|
278 |
|
279 |
32 int main() { |
280 int main() { |
33 |
281 |
34 typedef ListGraph Graph; |
282 for (int i = 0; i < lgfn; ++i) { |
35 |
283 SmartGraph graph; |
36 GRAPH_TYPEDEFS(Graph); |
284 SmartGraph::EdgeMap<int> weight(graph); |
37 |
285 |
38 Graph g; |
286 istringstream lgfs(lgf[i]); |
39 g.clear(); |
287 graphReader(graph, lgfs). |
40 |
288 edgeMap("weight", weight).run(); |
41 std::vector<Graph::Node> nodes; |
289 |
42 for (int i=0; i<13; ++i) |
290 MaxMatching<SmartGraph> mm(graph); |
43 nodes.push_back(g.addNode()); |
291 mm.run(); |
44 |
292 checkMatching(graph, mm); |
45 g.addEdge(nodes[0], nodes[0]); |
293 |
46 g.addEdge(nodes[6], nodes[10]); |
294 MaxWeightedMatching<SmartGraph> mwm(graph, weight); |
47 g.addEdge(nodes[5], nodes[10]); |
295 mwm.run(); |
48 g.addEdge(nodes[4], nodes[10]); |
296 checkWeightedMatching(graph, weight, mwm); |
49 g.addEdge(nodes[3], nodes[11]); |
297 |
50 g.addEdge(nodes[1], nodes[6]); |
298 MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight); |
51 g.addEdge(nodes[4], nodes[7]); |
299 bool perfect = mwpm.run(); |
52 g.addEdge(nodes[1], nodes[8]); |
300 |
53 g.addEdge(nodes[0], nodes[8]); |
301 check(perfect == (mm.matchingSize() * 2 == countNodes(graph)), |
54 g.addEdge(nodes[3], nodes[12]); |
302 "Perfect matching found"); |
55 g.addEdge(nodes[6], nodes[9]); |
303 |
56 g.addEdge(nodes[9], nodes[11]); |
304 if (perfect) { |
57 g.addEdge(nodes[2], nodes[10]); |
305 checkWeightedPerfectMatching(graph, weight, mwpm); |
58 g.addEdge(nodes[10], nodes[8]); |
306 } |
59 g.addEdge(nodes[5], nodes[8]); |
307 } |
60 g.addEdge(nodes[6], nodes[3]); |
|
61 g.addEdge(nodes[0], nodes[5]); |
|
62 g.addEdge(nodes[6], nodes[12]); |
|
63 |
|
64 MaxMatching<Graph> max_matching(g); |
|
65 max_matching.init(); |
|
66 max_matching.startDense(); |
|
67 |
|
68 int s=0; |
|
69 Graph::NodeMap<Node> mate(g,INVALID); |
|
70 max_matching.mateMap(mate); |
|
71 for(NodeIt v(g); v!=INVALID; ++v) { |
|
72 if ( mate[v]!=INVALID ) ++s; |
|
73 } |
|
74 int size=int(s/2); //size will be used as the size of a maxmatching |
|
75 |
|
76 for(NodeIt v(g); v!=INVALID; ++v) { |
|
77 max_matching.mate(v); |
|
78 } |
|
79 |
|
80 check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" ); |
|
81 |
|
82 Graph::NodeMap<MaxMatching<Graph>::DecompType> pos0(g); |
|
83 max_matching.decomposition(pos0); |
|
84 |
|
85 max_matching.init(); |
|
86 max_matching.startSparse(); |
|
87 s=0; |
|
88 max_matching.mateMap(mate); |
|
89 for(NodeIt v(g); v!=INVALID; ++v) { |
|
90 if ( mate[v]!=INVALID ) ++s; |
|
91 } |
|
92 check ( int(s/2) == size, "The size does not equal!" ); |
|
93 |
|
94 Graph::NodeMap<MaxMatching<Graph>::DecompType> pos1(g); |
|
95 max_matching.decomposition(pos1); |
|
96 |
|
97 max_matching.run(); |
|
98 s=0; |
|
99 max_matching.mateMap(mate); |
|
100 for(NodeIt v(g); v!=INVALID; ++v) { |
|
101 if ( mate[v]!=INVALID ) ++s; |
|
102 } |
|
103 check ( int(s/2) == size, "The size does not equal!" ); |
|
104 |
|
105 Graph::NodeMap<MaxMatching<Graph>::DecompType> pos2(g); |
|
106 max_matching.decomposition(pos2); |
|
107 |
|
108 max_matching.run(); |
|
109 s=0; |
|
110 max_matching.mateMap(mate); |
|
111 for(NodeIt v(g); v!=INVALID; ++v) { |
|
112 if ( mate[v]!=INVALID ) ++s; |
|
113 } |
|
114 check ( int(s/2) == size, "The size does not equal!" ); |
|
115 |
|
116 Graph::NodeMap<MaxMatching<Graph>::DecompType> pos(g); |
|
117 max_matching.decomposition(pos); |
|
118 |
|
119 bool ismatching=true; |
|
120 for(NodeIt v(g); v!=INVALID; ++v) { |
|
121 if ( mate[v]!=INVALID ) { |
|
122 Node u=mate[v]; |
|
123 if (mate[u]!=v) ismatching=false; |
|
124 } |
|
125 } |
|
126 check ( ismatching, "It is not a matching!" ); |
|
127 |
|
128 bool coincide=true; |
|
129 for(NodeIt v(g); v!=INVALID; ++v) { |
|
130 if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) { |
|
131 coincide=false; |
|
132 } |
|
133 } |
|
134 check ( coincide, "The decompositions do not coincide! " ); |
|
135 |
|
136 bool noarc=true; |
|
137 for(EdgeIt e(g); e!=INVALID; ++e) { |
|
138 if ( (pos[g.v(e)]==max_matching.C && |
|
139 pos[g.u(e)]==max_matching.D) || |
|
140 (pos[g.v(e)]==max_matching.D && |
|
141 pos[g.u(e)]==max_matching.C) ) |
|
142 noarc=false; |
|
143 } |
|
144 check ( noarc, "There are arcs between D and C!" ); |
|
145 |
|
146 bool oddcomp=true; |
|
147 Graph::NodeMap<bool> todo(g,true); |
|
148 int num_comp=0; |
|
149 for(NodeIt v(g); v!=INVALID; ++v) { |
|
150 if ( pos[v]==max_matching.D && todo[v] ) { |
|
151 int comp_size=1; |
|
152 ++num_comp; |
|
153 std::queue<Node> Q; |
|
154 Q.push(v); |
|
155 todo.set(v,false); |
|
156 while (!Q.empty()) { |
|
157 Node w=Q.front(); |
|
158 Q.pop(); |
|
159 for(IncEdgeIt e(g,w); e!=INVALID; ++e) { |
|
160 Node u=g.runningNode(e); |
|
161 if ( pos[u]==max_matching.D && todo[u] ) { |
|
162 ++comp_size; |
|
163 Q.push(u); |
|
164 todo.set(u,false); |
|
165 } |
|
166 } |
|
167 } |
|
168 if ( !(comp_size % 2) ) oddcomp=false; |
|
169 } |
|
170 } |
|
171 check ( oddcomp, "A component of g[D] is not odd." ); |
|
172 |
|
173 int barrier=0; |
|
174 for(NodeIt v(g); v!=INVALID; ++v) { |
|
175 if ( pos[v]==max_matching.A ) ++barrier; |
|
176 } |
|
177 int expected_size=int( countNodes(g)-num_comp+barrier)/2; |
|
178 check ( size==expected_size, "The size of the matching is wrong." ); |
|
179 |
308 |
180 return 0; |
309 return 0; |
181 } |
310 } |