COIN-OR::LEMON - Graph Library

source: lemon/test/matching_test.cc

Last change on this file was 1423:8c567e298d7f, checked in by Balazs Dezso <deba@…>, 5 years ago

Paremeter to stop matching calculation when only single node is unmatched

File size: 12.8 KB
RevLine 
[338]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
[1270]5 * Copyright (C) 2003-2013
[338]6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19#include <iostream>
[339]20#include <sstream>
[338]21#include <vector>
22#include <queue>
23#include <cstdlib>
24
[641]25#include <lemon/matching.h>
[339]26#include <lemon/smart_graph.h>
[637]27#include <lemon/concepts/graph.h>
28#include <lemon/concepts/maps.h>
[339]29#include <lemon/lgf_reader.h>
[637]30#include <lemon/math.h>
[339]31
[338]32#include "test_tools.h"
33
34using namespace std;
35using namespace lemon;
36
[339]37GRAPH_TYPEDEFS(SmartGraph);
38
39
40const int lgfn = 3;
41const std::string lgf[lgfn] = {
42  "@nodes\n"
43  "label\n"
44  "0\n"
45  "1\n"
46  "2\n"
47  "3\n"
48  "4\n"
49  "5\n"
50  "6\n"
51  "7\n"
52  "@edges\n"
53  "     label  weight\n"
54  "7 4  0      984\n"
55  "0 7  1      73\n"
56  "7 1  2      204\n"
57  "2 3  3      583\n"
58  "2 7  4      565\n"
59  "2 1  5      582\n"
60  "0 4  6      551\n"
61  "2 5  7      385\n"
62  "1 5  8      561\n"
63  "5 3  9      484\n"
64  "7 5  10     904\n"
65  "3 6  11     47\n"
66  "7 6  12     888\n"
67  "3 0  13     747\n"
68  "6 1  14     310\n",
69
70  "@nodes\n"
71  "label\n"
72  "0\n"
73  "1\n"
74  "2\n"
75  "3\n"
76  "4\n"
77  "5\n"
78  "6\n"
79  "7\n"
80  "@edges\n"
81  "     label  weight\n"
82  "2 5  0      710\n"
83  "0 5  1      241\n"
84  "2 4  2      856\n"
85  "2 6  3      762\n"
86  "4 1  4      747\n"
87  "6 1  5      962\n"
88  "4 7  6      723\n"
89  "1 7  7      661\n"
90  "2 3  8      376\n"
91  "1 0  9      416\n"
92  "6 7  10     391\n",
93
94  "@nodes\n"
95  "label\n"
96  "0\n"
97  "1\n"
98  "2\n"
99  "3\n"
100  "4\n"
101  "5\n"
102  "6\n"
103  "7\n"
104  "@edges\n"
105  "     label  weight\n"
106  "6 2  0      553\n"
107  "0 7  1      653\n"
108  "6 3  2      22\n"
109  "4 7  3      846\n"
110  "7 2  4      981\n"
111  "7 6  5      250\n"
112  "5 2  6      539\n",
113};
114
[637]115void checkMaxMatchingCompile()
116{
117  typedef concepts::Graph Graph;
118  typedef Graph::Node Node;
119  typedef Graph::Edge Edge;
120  typedef Graph::EdgeMap<bool> MatMap;
121
122  Graph g;
123  Node n;
124  Edge e;
125  MatMap mat(g);
126
127  MaxMatching<Graph> mat_test(g);
128  const MaxMatching<Graph>&
129    const_mat_test = mat_test;
130
131  mat_test.init();
132  mat_test.greedyInit();
133  mat_test.matchingInit(mat);
134  mat_test.startSparse();
135  mat_test.startDense();
136  mat_test.run();
[1423]137  mat_test.startSparse(false);
138  mat_test.startDense(false);
139  mat_test.run(false);
[956]140
[637]141  const_mat_test.matchingSize();
142  const_mat_test.matching(e);
143  const_mat_test.matching(n);
[640]144  const MaxMatching<Graph>::MatchingMap& mmap =
145    const_mat_test.matchingMap();
146  e = mmap[n];
[637]147  const_mat_test.mate(n);
148
[956]149  MaxMatching<Graph>::Status stat =
[640]150    const_mat_test.status(n);
[1257]151  ::lemon::ignore_unused_variable_warning(stat);
[640]152  const MaxMatching<Graph>::StatusMap& smap =
153    const_mat_test.statusMap();
154  stat = smap[n];
[637]155  const_mat_test.barrier(n);
156}
157
158void checkMaxWeightedMatchingCompile()
159{
160  typedef concepts::Graph Graph;
161  typedef Graph::Node Node;
162  typedef Graph::Edge Edge;
163  typedef Graph::EdgeMap<int> WeightMap;
164
165  Graph g;
166  Node n;
167  Edge e;
168  WeightMap w(g);
169
170  MaxWeightedMatching<Graph> mat_test(g, w);
171  const MaxWeightedMatching<Graph>&
172    const_mat_test = mat_test;
173
174  mat_test.init();
175  mat_test.start();
176  mat_test.run();
[956]177
[640]178  const_mat_test.matchingWeight();
[637]179  const_mat_test.matchingSize();
180  const_mat_test.matching(e);
181  const_mat_test.matching(n);
[640]182  const MaxWeightedMatching<Graph>::MatchingMap& mmap =
183    const_mat_test.matchingMap();
184  e = mmap[n];
[637]185  const_mat_test.mate(n);
[956]186
[637]187  int k = 0;
188  const_mat_test.dualValue();
189  const_mat_test.nodeValue(n);
190  const_mat_test.blossomNum();
191  const_mat_test.blossomSize(k);
192  const_mat_test.blossomValue(k);
193}
194
195void checkMaxWeightedPerfectMatchingCompile()
196{
197  typedef concepts::Graph Graph;
198  typedef Graph::Node Node;
199  typedef Graph::Edge Edge;
200  typedef Graph::EdgeMap<int> WeightMap;
201
202  Graph g;
203  Node n;
204  Edge e;
205  WeightMap w(g);
206
207  MaxWeightedPerfectMatching<Graph> mat_test(g, w);
208  const MaxWeightedPerfectMatching<Graph>&
209    const_mat_test = mat_test;
210
211  mat_test.init();
212  mat_test.start();
213  mat_test.run();
[956]214
[640]215  const_mat_test.matchingWeight();
[637]216  const_mat_test.matching(e);
217  const_mat_test.matching(n);
[640]218  const MaxWeightedPerfectMatching<Graph>::MatchingMap& mmap =
219    const_mat_test.matchingMap();
220  e = mmap[n];
[637]221  const_mat_test.mate(n);
[956]222
[637]223  int k = 0;
224  const_mat_test.dualValue();
225  const_mat_test.nodeValue(n);
226  const_mat_test.blossomNum();
227  const_mat_test.blossomSize(k);
228  const_mat_test.blossomValue(k);
229}
230
[339]231void checkMatching(const SmartGraph& graph,
232                   const MaxMatching<SmartGraph>& mm) {
233  int num = 0;
234
235  IntNodeMap comp_index(graph);
236  UnionFind<IntNodeMap> comp(comp_index);
237
238  int barrier_num = 0;
239
240  for (NodeIt n(graph); n != INVALID; ++n) {
[640]241    check(mm.status(n) == MaxMatching<SmartGraph>::EVEN ||
[339]242          mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition");
[640]243    if (mm.status(n) == MaxMatching<SmartGraph>::ODD) {
[339]244      ++barrier_num;
245    } else {
246      comp.insert(n);
247    }
248  }
249
250  for (EdgeIt e(graph); e != INVALID; ++e) {
251    if (mm.matching(e)) {
252      check(e == mm.matching(graph.u(e)), "Wrong matching");
253      check(e == mm.matching(graph.v(e)), "Wrong matching");
254      ++num;
255    }
[640]256    check(mm.status(graph.u(e)) != MaxMatching<SmartGraph>::EVEN ||
257          mm.status(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED,
[339]258          "Wrong Gallai-Edmonds decomposition");
259
[640]260    check(mm.status(graph.v(e)) != MaxMatching<SmartGraph>::EVEN ||
261          mm.status(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED,
[339]262          "Wrong Gallai-Edmonds decomposition");
263
[640]264    if (mm.status(graph.u(e)) != MaxMatching<SmartGraph>::ODD &&
265        mm.status(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {
[339]266      comp.join(graph.u(e), graph.v(e));
267    }
268  }
269
270  std::set<int> comp_root;
271  int odd_comp_num = 0;
272  for (NodeIt n(graph); n != INVALID; ++n) {
[640]273    if (mm.status(n) != MaxMatching<SmartGraph>::ODD) {
[339]274      int root = comp.find(n);
275      if (comp_root.find(root) == comp_root.end()) {
276        comp_root.insert(root);
277        if (comp.size(n) % 2 == 1) {
278          ++odd_comp_num;
279        }
280      }
281    }
282  }
283
284  check(mm.matchingSize() == num, "Wrong matching");
285  check(2 * num == countNodes(graph) - (odd_comp_num - barrier_num),
286         "Wrong matching");
287  return;
288}
289
290void checkWeightedMatching(const SmartGraph& graph,
291                   const SmartGraph::EdgeMap<int>& weight,
292                   const MaxWeightedMatching<SmartGraph>& mwm) {
293  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
294    if (graph.u(e) == graph.v(e)) continue;
295    int rw = mwm.nodeValue(graph.u(e)) + mwm.nodeValue(graph.v(e));
296
297    for (int i = 0; i < mwm.blossomNum(); ++i) {
298      bool s = false, t = false;
299      for (MaxWeightedMatching<SmartGraph>::BlossomIt n(mwm, i);
300           n != INVALID; ++n) {
301        if (graph.u(e) == n) s = true;
302        if (graph.v(e) == n) t = true;
303      }
304      if (s == true && t == true) {
305        rw += mwm.blossomValue(i);
306      }
307    }
308    rw -= weight[e] * mwm.dualScale;
309
310    check(rw >= 0, "Negative reduced weight");
311    check(rw == 0 || !mwm.matching(e),
312          "Non-zero reduced weight on matching edge");
313  }
314
315  int pv = 0;
316  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
317    if (mwm.matching(n) != INVALID) {
318      check(mwm.nodeValue(n) >= 0, "Invalid node value");
319      pv += weight[mwm.matching(n)];
320      SmartGraph::Node o = graph.target(mwm.matching(n));
321      check(mwm.mate(n) == o, "Invalid matching");
322      check(mwm.matching(n) == graph.oppositeArc(mwm.matching(o)),
323            "Invalid matching");
324    } else {
325      check(mwm.mate(n) == INVALID, "Invalid matching");
326      check(mwm.nodeValue(n) == 0, "Invalid matching");
327    }
328  }
329
330  int dv = 0;
331  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
332    dv += mwm.nodeValue(n);
333  }
334
335  for (int i = 0; i < mwm.blossomNum(); ++i) {
336    check(mwm.blossomValue(i) >= 0, "Invalid blossom value");
337    check(mwm.blossomSize(i) % 2 == 1, "Even blossom size");
338    dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2);
339  }
340
341  check(pv * mwm.dualScale == dv * 2, "Wrong duality");
342
343  return;
344}
345
346void checkWeightedPerfectMatching(const SmartGraph& graph,
347                          const SmartGraph::EdgeMap<int>& weight,
348                          const MaxWeightedPerfectMatching<SmartGraph>& mwpm) {
349  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
350    if (graph.u(e) == graph.v(e)) continue;
351    int rw = mwpm.nodeValue(graph.u(e)) + mwpm.nodeValue(graph.v(e));
352
353    for (int i = 0; i < mwpm.blossomNum(); ++i) {
354      bool s = false, t = false;
355      for (MaxWeightedPerfectMatching<SmartGraph>::BlossomIt n(mwpm, i);
356           n != INVALID; ++n) {
357        if (graph.u(e) == n) s = true;
358        if (graph.v(e) == n) t = true;
359      }
360      if (s == true && t == true) {
361        rw += mwpm.blossomValue(i);
362      }
363    }
364    rw -= weight[e] * mwpm.dualScale;
365
366    check(rw >= 0, "Negative reduced weight");
367    check(rw == 0 || !mwpm.matching(e),
368          "Non-zero reduced weight on matching edge");
369  }
370
371  int pv = 0;
372  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
373    check(mwpm.matching(n) != INVALID, "Non perfect");
374    pv += weight[mwpm.matching(n)];
375    SmartGraph::Node o = graph.target(mwpm.matching(n));
376    check(mwpm.mate(n) == o, "Invalid matching");
377    check(mwpm.matching(n) == graph.oppositeArc(mwpm.matching(o)),
378          "Invalid matching");
379  }
380
381  int dv = 0;
382  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
383    dv += mwpm.nodeValue(n);
384  }
385
386  for (int i = 0; i < mwpm.blossomNum(); ++i) {
387    check(mwpm.blossomValue(i) >= 0, "Invalid blossom value");
388    check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size");
389    dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2);
390  }
391
392  check(pv * mwpm.dualScale == dv * 2, "Wrong duality");
393
394  return;
395}
396
397
[338]398int main() {
399
[339]400  for (int i = 0; i < lgfn; ++i) {
401    SmartGraph graph;
402    SmartGraph::EdgeMap<int> weight(graph);
[338]403
[339]404    istringstream lgfs(lgf[i]);
405    graphReader(graph, lgfs).
406      edgeMap("weight", weight).run();
[338]407
[1423]408    int size;
[949]409    bool perfect;
410    {
411      MaxMatching<SmartGraph> mm(graph);
412      mm.run();
413      checkMatching(graph, mm);
[1423]414      size = mm.matchingSize();
[949]415      perfect = 2 * mm.matchingSize() == countNodes(graph);
416    }
[338]417
[949]418    {
[1423]419      MaxMatching<SmartGraph> mm(graph);
420      mm.init();
421      mm.startSparse();
422      checkMatching(graph, mm);
423      check(size == mm.matchingSize(), "Inconsistent matching size");
424    }
425
426    {
427      MaxMatching<SmartGraph> mm(graph);
428      mm.init();
429      mm.startDense();
430      checkMatching(graph, mm);
431      check(size == mm.matchingSize(), "Inconsistent matching size");
432    }
433
434    {
435      MaxMatching<SmartGraph> mm(graph);
436      mm.greedyInit();
437      mm.startSparse();
438      checkMatching(graph, mm);
439      check(size == mm.matchingSize(), "Inconsistent matching size");
440    }
441
442    {
443      MaxMatching<SmartGraph> mm(graph);
444      mm.greedyInit();
445      mm.startDense();
446      checkMatching(graph, mm);
447      check(size == mm.matchingSize(), "Inconsistent matching size");
448    }
449
450    {
451      MaxMatching<SmartGraph> mm(graph);
452      mm.run(false);
453      check(size == mm.matchingSize(), "Inconsistent max cardinality matching");
454    }
455
456    {
457      MaxMatching<SmartGraph> mm(graph);
458      mm.init();
459      mm.startSparse(false);
460      check(size == mm.matchingSize(), "Inconsistent matching size");
461    }
462
463    {
464      MaxMatching<SmartGraph> mm(graph);
465      mm.init();
466      mm.startDense(false);
467      check(size == mm.matchingSize(), "Inconsistent matching size");
468    }
469
470    {
471      MaxMatching<SmartGraph> mm(graph);
472      mm.greedyInit();
473      mm.startSparse(false);
474      check(size == mm.matchingSize(), "Inconsistent matching size");
475    }
476
477    {
478      MaxMatching<SmartGraph> mm(graph);
479      mm.greedyInit();
480      mm.startDense(false);
481      check(size == mm.matchingSize(), "Inconsistent matching size");
482    }
483
484    {
[949]485      MaxWeightedMatching<SmartGraph> mwm(graph, weight);
486      mwm.run();
487      checkWeightedMatching(graph, weight, mwm);
488    }
[338]489
[949]490    {
491      MaxWeightedMatching<SmartGraph> mwm(graph, weight);
492      mwm.init();
493      mwm.start();
494      checkWeightedMatching(graph, weight, mwm);
495    }
[338]496
[949]497    {
498      MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
499      bool result = mwpm.run();
[338]500
[949]501      check(result == perfect, "Perfect matching found");
502      if (perfect) {
503        checkWeightedPerfectMatching(graph, weight, mwpm);
504      }
505    }
[641]506
[949]507    {
508      MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
509      mwpm.init();
510      bool result = mwpm.start();
[956]511
[949]512      check(result == perfect, "Perfect matching found");
513      if (perfect) {
514        checkWeightedPerfectMatching(graph, weight, mwpm);
515      }
[338]516    }
517  }
518
519  return 0;
520}
Note: See TracBrowser for help on using the repository browser.