COIN-OR::LEMON - Graph Library

source: lemon-main/test/max_weighted_matching_test.cc @ 326:64ad48007fb2

Last change on this file since 326:64ad48007fb2 was 326:64ad48007fb2, checked in by Balazs Dezso <deba@…>, 16 years ago

Port maximum matching algorithms from svn 3498 (ticket #48)

File size: 6.5 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2008
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>
20#include <sstream>
21#include <vector>
22#include <queue>
23#include <lemon/math.h>
24#include <cstdlib>
25
26#include "test_tools.h"
27#include <lemon/smart_graph.h>
28#include <lemon/max_matching.h>
29#include <lemon/lgf_reader.h>
30
31using namespace std;
32using namespace lemon;
33
34GRAPH_TYPEDEFS(SmartGraph);
35
36const int lgfn = 3;
37const std::string lgf[lgfn] = {
38  "@nodes\n"
39  "label\n"
40  "0\n"
41  "1\n"
42  "2\n"
43  "3\n"
44  "4\n"
45  "5\n"
46  "6\n"
47  "7\n"
48  "@edges\n"
49  "label        weight\n"
50  "7    4       0       984\n"
51  "0    7       1       73\n"
52  "7    1       2       204\n"
53  "2    3       3       583\n"
54  "2    7       4       565\n"
55  "2    1       5       582\n"
56  "0    4       6       551\n"
57  "2    5       7       385\n"
58  "1    5       8       561\n"
59  "5    3       9       484\n"
60  "7    5       10      904\n"
61  "3    6       11      47\n"
62  "7    6       12      888\n"
63  "3    0       13      747\n"
64  "6    1       14      310\n",
65
66  "@nodes\n"
67  "label\n"
68  "0\n"
69  "1\n"
70  "2\n"
71  "3\n"
72  "4\n"
73  "5\n"
74  "6\n"
75  "7\n"
76  "@edges\n"
77  "label        weight\n"
78  "2    5       0       710\n"
79  "0    5       1       241\n"
80  "2    4       2       856\n"
81  "2    6       3       762\n"
82  "4    1       4       747\n"
83  "6    1       5       962\n"
84  "4    7       6       723\n"
85  "1    7       7       661\n"
86  "2    3       8       376\n"
87  "1    0       9       416\n"
88  "6    7       10      391\n",
89
90  "@nodes\n"
91  "label\n"
92  "0\n"
93  "1\n"
94  "2\n"
95  "3\n"
96  "4\n"
97  "5\n"
98  "6\n"
99  "7\n"
100  "@edges\n"
101  "label        weight\n"
102  "6    2       0       553\n"
103  "0    7       1       653\n"
104  "6    3       2       22\n"
105  "4    7       3       846\n"
106  "7    2       4       981\n"
107  "7    6       5       250\n"
108  "5    2       6       539\n"
109};
110
111void checkMatching(const SmartGraph& graph,
112                   const SmartGraph::EdgeMap<int>& weight,
113                   const MaxWeightedMatching<SmartGraph>& mwm) {
114  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
115    if (graph.u(e) == graph.v(e)) continue;
116    int rw =
117      mwm.nodeValue(graph.u(e)) + mwm.nodeValue(graph.v(e));
118
119    for (int i = 0; i < mwm.blossomNum(); ++i) {
120      bool s = false, t = false;
121      for (MaxWeightedMatching<SmartGraph>::BlossomIt n(mwm, i);
122           n != INVALID; ++n) {
123        if (graph.u(e) == n) s = true;
124        if (graph.v(e) == n) t = true;
125      }
126      if (s == true && t == true) {
127        rw += mwm.blossomValue(i);
128      }
129    }
130    rw -= weight[e] * mwm.dualScale;
131
132    check(rw >= 0, "Negative reduced weight");
133    check(rw == 0 || !mwm.matching(e),
134          "Non-zero reduced weight on matching arc");
135  }
136
137  int pv = 0;
138  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
139    if (mwm.matching(n) != INVALID) {
140      check(mwm.nodeValue(n) >= 0, "Invalid node value");
141      pv += weight[mwm.matching(n)];
142      SmartGraph::Node o = graph.target(mwm.matching(n));
143      check(mwm.mate(n) == o, "Invalid matching");
144      check(mwm.matching(n) == graph.oppositeArc(mwm.matching(o)),
145            "Invalid matching");
146    } else {
147      check(mwm.mate(n) == INVALID, "Invalid matching");
148      check(mwm.nodeValue(n) == 0, "Invalid matching");
149    }
150  }
151
152  int dv = 0;
153  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
154    dv += mwm.nodeValue(n);
155  }
156
157  for (int i = 0; i < mwm.blossomNum(); ++i) {
158    check(mwm.blossomValue(i) >= 0, "Invalid blossom value");
159    check(mwm.blossomSize(i) % 2 == 1, "Even blossom size");
160    dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2);
161  }
162
163  check(pv * mwm.dualScale == dv * 2, "Wrong duality");
164
165  return;
166}
167
168void checkPerfectMatching(const SmartGraph& graph,
169                          const SmartGraph::EdgeMap<int>& weight,
170                          const MaxWeightedPerfectMatching<SmartGraph>& mwpm) {
171  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
172    if (graph.u(e) == graph.v(e)) continue;
173    int rw =
174      mwpm.nodeValue(graph.u(e)) + mwpm.nodeValue(graph.v(e));
175
176    for (int i = 0; i < mwpm.blossomNum(); ++i) {
177      bool s = false, t = false;
178      for (MaxWeightedPerfectMatching<SmartGraph>::BlossomIt n(mwpm, i);
179           n != INVALID; ++n) {
180        if (graph.u(e) == n) s = true;
181        if (graph.v(e) == n) t = true;
182      }
183      if (s == true && t == true) {
184        rw += mwpm.blossomValue(i);
185      }
186    }
187    rw -= weight[e] * mwpm.dualScale;
188
189    check(rw >= 0, "Negative reduced weight");
190    check(rw == 0 || !mwpm.matching(e),
191          "Non-zero reduced weight on matching arc");
192  }
193
194  int pv = 0;
195  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
196    check(mwpm.matching(n) != INVALID, "Non perfect");
197    pv += weight[mwpm.matching(n)];
198    SmartGraph::Node o = graph.target(mwpm.matching(n));
199    check(mwpm.mate(n) == o, "Invalid matching");
200    check(mwpm.matching(n) == graph.oppositeArc(mwpm.matching(o)),
201          "Invalid matching");
202  }
203
204  int dv = 0;
205  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
206    dv += mwpm.nodeValue(n);
207  }
208
209  for (int i = 0; i < mwpm.blossomNum(); ++i) {
210    check(mwpm.blossomValue(i) >= 0, "Invalid blossom value");
211    check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size");
212    dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2);
213  }
214
215  check(pv * mwpm.dualScale == dv * 2, "Wrong duality");
216
217  return;
218}
219
220
221int main() {
222
223  for (int i = 0; i < lgfn; ++i) {
224    SmartGraph graph;
225    SmartGraph::EdgeMap<int> weight(graph);
226
227    istringstream lgfs(lgf[i]);
228    graphReader(graph, lgfs).
229      edgeMap("weight", weight).run();
230
231    MaxWeightedMatching<SmartGraph> mwm(graph, weight);
232    mwm.run();
233    checkMatching(graph, weight, mwm);
234
235    MaxMatching<SmartGraph> mm(graph);
236    mm.run();
237
238    MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
239    bool perfect = mwpm.run();
240
241    check(perfect == (mm.size() * 2 == countNodes(graph)),
242          "Perfect matching found");
243
244    if (perfect) {
245      checkPerfectMatching(graph, weight, mwpm);
246    }
247  }
248
249  return 0;
250}
Note: See TracBrowser for help on using the repository browser.