1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2009
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
25 #include <lemon/max_matching.h>
26 #include <lemon/smart_graph.h>
27 #include <lemon/concepts/graph.h>
28 #include <lemon/concepts/maps.h>
29 #include <lemon/lgf_reader.h>
30 #include <lemon/math.h>
32 #include "test_tools.h"
35 using namespace lemon;
37 GRAPH_TYPEDEFS(SmartGraph);
41 const std::string lgf[lgfn] = {
115 void checkMaxMatchingCompile()
117 typedef concepts::Graph Graph;
118 typedef Graph::Node Node;
119 typedef Graph::Edge Edge;
120 typedef Graph::EdgeMap<bool> MatMap;
127 MaxMatching<Graph> mat_test(g);
128 const MaxMatching<Graph>&
129 const_mat_test = mat_test;
132 mat_test.greedyInit();
133 mat_test.matchingInit(mat);
134 mat_test.startSparse();
135 mat_test.startDense();
138 const_mat_test.matchingSize();
139 const_mat_test.matching(e);
140 const_mat_test.matching(n);
141 const_mat_test.mate(n);
143 MaxMatching<Graph>::Status stat =
144 const_mat_test.decomposition(n);
145 const_mat_test.barrier(n);
147 ignore_unused_variable_warning(stat);
150 void checkMaxWeightedMatchingCompile()
152 typedef concepts::Graph Graph;
153 typedef Graph::Node Node;
154 typedef Graph::Edge Edge;
155 typedef Graph::EdgeMap<int> WeightMap;
162 MaxWeightedMatching<Graph> mat_test(g, w);
163 const MaxWeightedMatching<Graph>&
164 const_mat_test = mat_test;
170 const_mat_test.matchingValue();
171 const_mat_test.matchingSize();
172 const_mat_test.matching(e);
173 const_mat_test.matching(n);
174 const_mat_test.mate(n);
177 const_mat_test.dualValue();
178 const_mat_test.nodeValue(n);
179 const_mat_test.blossomNum();
180 const_mat_test.blossomSize(k);
181 const_mat_test.blossomValue(k);
184 void checkMaxWeightedPerfectMatchingCompile()
186 typedef concepts::Graph Graph;
187 typedef Graph::Node Node;
188 typedef Graph::Edge Edge;
189 typedef Graph::EdgeMap<int> WeightMap;
196 MaxWeightedPerfectMatching<Graph> mat_test(g, w);
197 const MaxWeightedPerfectMatching<Graph>&
198 const_mat_test = mat_test;
204 const_mat_test.matchingValue();
205 const_mat_test.matching(e);
206 const_mat_test.matching(n);
207 const_mat_test.mate(n);
210 const_mat_test.dualValue();
211 const_mat_test.nodeValue(n);
212 const_mat_test.blossomNum();
213 const_mat_test.blossomSize(k);
214 const_mat_test.blossomValue(k);
217 void checkMatching(const SmartGraph& graph,
218 const MaxMatching<SmartGraph>& mm) {
221 IntNodeMap comp_index(graph);
222 UnionFind<IntNodeMap> comp(comp_index);
226 for (NodeIt n(graph); n != INVALID; ++n) {
227 check(mm.decomposition(n) == MaxMatching<SmartGraph>::EVEN ||
228 mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition");
229 if (mm.decomposition(n) == MaxMatching<SmartGraph>::ODD) {
236 for (EdgeIt e(graph); e != INVALID; ++e) {
237 if (mm.matching(e)) {
238 check(e == mm.matching(graph.u(e)), "Wrong matching");
239 check(e == mm.matching(graph.v(e)), "Wrong matching");
242 check(mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::EVEN ||
243 mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED,
244 "Wrong Gallai-Edmonds decomposition");
246 check(mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::EVEN ||
247 mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED,
248 "Wrong Gallai-Edmonds decomposition");
250 if (mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::ODD &&
251 mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {
252 comp.join(graph.u(e), graph.v(e));
256 std::set<int> comp_root;
257 int odd_comp_num = 0;
258 for (NodeIt n(graph); n != INVALID; ++n) {
259 if (mm.decomposition(n) != MaxMatching<SmartGraph>::ODD) {
260 int root = comp.find(n);
261 if (comp_root.find(root) == comp_root.end()) {
262 comp_root.insert(root);
263 if (comp.size(n) % 2 == 1) {
270 check(mm.matchingSize() == num, "Wrong matching");
271 check(2 * num == countNodes(graph) - (odd_comp_num - barrier_num),
276 void checkWeightedMatching(const SmartGraph& graph,
277 const SmartGraph::EdgeMap<int>& weight,
278 const MaxWeightedMatching<SmartGraph>& mwm) {
279 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
280 if (graph.u(e) == graph.v(e)) continue;
281 int rw = mwm.nodeValue(graph.u(e)) + mwm.nodeValue(graph.v(e));
283 for (int i = 0; i < mwm.blossomNum(); ++i) {
284 bool s = false, t = false;
285 for (MaxWeightedMatching<SmartGraph>::BlossomIt n(mwm, i);
287 if (graph.u(e) == n) s = true;
288 if (graph.v(e) == n) t = true;
290 if (s == true && t == true) {
291 rw += mwm.blossomValue(i);
294 rw -= weight[e] * mwm.dualScale;
296 check(rw >= 0, "Negative reduced weight");
297 check(rw == 0 || !mwm.matching(e),
298 "Non-zero reduced weight on matching edge");
302 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
303 if (mwm.matching(n) != INVALID) {
304 check(mwm.nodeValue(n) >= 0, "Invalid node value");
305 pv += weight[mwm.matching(n)];
306 SmartGraph::Node o = graph.target(mwm.matching(n));
307 check(mwm.mate(n) == o, "Invalid matching");
308 check(mwm.matching(n) == graph.oppositeArc(mwm.matching(o)),
311 check(mwm.mate(n) == INVALID, "Invalid matching");
312 check(mwm.nodeValue(n) == 0, "Invalid matching");
317 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
318 dv += mwm.nodeValue(n);
321 for (int i = 0; i < mwm.blossomNum(); ++i) {
322 check(mwm.blossomValue(i) >= 0, "Invalid blossom value");
323 check(mwm.blossomSize(i) % 2 == 1, "Even blossom size");
324 dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2);
327 check(pv * mwm.dualScale == dv * 2, "Wrong duality");
332 void checkWeightedPerfectMatching(const SmartGraph& graph,
333 const SmartGraph::EdgeMap<int>& weight,
334 const MaxWeightedPerfectMatching<SmartGraph>& mwpm) {
335 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
336 if (graph.u(e) == graph.v(e)) continue;
337 int rw = mwpm.nodeValue(graph.u(e)) + mwpm.nodeValue(graph.v(e));
339 for (int i = 0; i < mwpm.blossomNum(); ++i) {
340 bool s = false, t = false;
341 for (MaxWeightedPerfectMatching<SmartGraph>::BlossomIt n(mwpm, i);
343 if (graph.u(e) == n) s = true;
344 if (graph.v(e) == n) t = true;
346 if (s == true && t == true) {
347 rw += mwpm.blossomValue(i);
350 rw -= weight[e] * mwpm.dualScale;
352 check(rw >= 0, "Negative reduced weight");
353 check(rw == 0 || !mwpm.matching(e),
354 "Non-zero reduced weight on matching edge");
358 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
359 check(mwpm.matching(n) != INVALID, "Non perfect");
360 pv += weight[mwpm.matching(n)];
361 SmartGraph::Node o = graph.target(mwpm.matching(n));
362 check(mwpm.mate(n) == o, "Invalid matching");
363 check(mwpm.matching(n) == graph.oppositeArc(mwpm.matching(o)),
368 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
369 dv += mwpm.nodeValue(n);
372 for (int i = 0; i < mwpm.blossomNum(); ++i) {
373 check(mwpm.blossomValue(i) >= 0, "Invalid blossom value");
374 check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size");
375 dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2);
378 check(pv * mwpm.dualScale == dv * 2, "Wrong duality");
386 for (int i = 0; i < lgfn; ++i) {
388 SmartGraph::EdgeMap<int> weight(graph);
390 istringstream lgfs(lgf[i]);
391 graphReader(graph, lgfs).
392 edgeMap("weight", weight).run();
394 MaxMatching<SmartGraph> mm(graph);
396 checkMatching(graph, mm);
398 MaxWeightedMatching<SmartGraph> mwm(graph, weight);
400 checkWeightedMatching(graph, weight, mwm);
402 MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
403 bool perfect = mwpm.run();
405 check(perfect == (mm.matchingSize() * 2 == countNodes(graph)),
406 "Perfect matching found");
409 checkWeightedPerfectMatching(graph, weight, mwpm);