COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/max_weighted_matching_test.cc @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 6.5 KB
Line 
1/* -*- C++ -*-
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 <cmath>
24#include <cstdlib>
25
26#include "test_tools.h"
27#include <lemon/smart_graph.h>
28#include <lemon/max_matching.h>
29#include <lemon/graph_reader.h>
30
31UGRAPH_TYPEDEFS(SmartUGraph);
32
33using namespace std;
34using namespace lemon;
35
36const int lgfn = 3;
37const std::string lgf[lgfn] = {   
38  "@nodeset\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  "@uedgeset\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  "@end\n",
66
67  "@nodeset\n"
68  "label\n"
69  "0\n"
70  "1\n"
71  "2\n"
72  "3\n"
73  "4\n"
74  "5\n"
75  "6\n"
76  "7\n"
77  "@uedgeset\n"
78  "label        weight\n"
79  "2    5       0       710\n"
80  "0    5       1       241\n"
81  "2    4       2       856\n"
82  "2    6       3       762\n"
83  "4    1       4       747\n"
84  "6    1       5       962\n"
85  "4    7       6       723\n"
86  "1    7       7       661\n"
87  "2    3       8       376\n"
88  "1    0       9       416\n"
89  "6    7       10      391\n"
90  "@end\n",
91
92  "@nodeset\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  "@uedgeset\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  "@end\n"
112};
113
114void checkMatching(const SmartUGraph& ugraph,
115                   const SmartUGraph::UEdgeMap<int>& weight,
116                   const MaxWeightedMatching<SmartUGraph>& mwm) {
117  for (SmartUGraph::UEdgeIt e(ugraph); e != INVALID; ++e) {
118    if (ugraph.source(e) == ugraph.target(e)) continue;
119    int rw =
120      mwm.nodeValue(ugraph.source(e)) + mwm.nodeValue(ugraph.target(e));
121
122    for (int i = 0; i < mwm.blossomNum(); ++i) {
123      bool s = false, t = false;
124      for (MaxWeightedMatching<SmartUGraph>::BlossomIt n(mwm, i);
125           n != INVALID; ++n) {
126        if (ugraph.source(e) == n) s = true;
127        if (ugraph.target(e) == n) t = true;
128      }
129      if (s == true && t == true) {
130        rw += mwm.blossomValue(i);
131      }
132    }
133    rw -= weight[e] * mwm.dualScale;
134
135    check(rw >= 0, "Negative reduced weight");
136    check(rw == 0 || !mwm.matching(e),
137          "Non-zero reduced weight on matching edge");
138  }
139
140  int pv = 0;
141  for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) {
142    if (mwm.matching(n) != INVALID) {
143      check(mwm.nodeValue(n) >= 0, "Invalid node value");
144      pv += weight[mwm.matching(n)];
145      SmartUGraph::Node o = ugraph.target(mwm.matching(n));
146      check(mwm.mate(n) == o, "Invalid matching");
147      check(mwm.matching(n) == ugraph.oppositeEdge(mwm.matching(o)),
148            "Invalid matching");
149    } else {
150      check(mwm.mate(n) == INVALID, "Invalid matching");
151      check(mwm.nodeValue(n) == 0, "Invalid matching");
152    }
153  }
154
155  int dv = 0;
156  for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) {
157    dv += mwm.nodeValue(n);
158  }
159
160  for (int i = 0; i < mwm.blossomNum(); ++i) {
161    check(mwm.blossomValue(i) >= 0, "Invalid blossom value");
162    check(mwm.blossomSize(i) % 2 == 1, "Even blossom size");
163    dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2);
164  }
165
166  check(pv * mwm.dualScale == dv * 2, "Wrong duality");
167
168  return;
169}
170
171void checkPerfectMatching(const SmartUGraph& ugraph,
172                          const SmartUGraph::UEdgeMap<int>& weight,
173                          const MaxWeightedPerfectMatching<SmartUGraph>& mwpm) {
174  for (SmartUGraph::UEdgeIt e(ugraph); e != INVALID; ++e) {
175    if (ugraph.source(e) == ugraph.target(e)) continue;
176    int rw =
177      mwpm.nodeValue(ugraph.source(e)) + mwpm.nodeValue(ugraph.target(e));
178
179    for (int i = 0; i < mwpm.blossomNum(); ++i) {
180      bool s = false, t = false;
181      for (MaxWeightedPerfectMatching<SmartUGraph>::BlossomIt n(mwpm, i);
182           n != INVALID; ++n) {
183        if (ugraph.source(e) == n) s = true;
184        if (ugraph.target(e) == n) t = true;
185      }
186      if (s == true && t == true) {
187        rw += mwpm.blossomValue(i);
188      }
189    }
190    rw -= weight[e] * mwpm.dualScale;
191
192    check(rw >= 0, "Negative reduced weight");
193    check(rw == 0 || !mwpm.matching(e),
194          "Non-zero reduced weight on matching edge");
195  }
196
197  int pv = 0;
198  for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) {
199    check(mwpm.matching(n) != INVALID, "Non perfect");
200    pv += weight[mwpm.matching(n)];
201    SmartUGraph::Node o = ugraph.target(mwpm.matching(n));
202    check(mwpm.mate(n) == o, "Invalid matching");
203    check(mwpm.matching(n) == ugraph.oppositeEdge(mwpm.matching(o)),
204          "Invalid matching");
205  }
206
207  int dv = 0;
208  for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) {
209    dv += mwpm.nodeValue(n);
210  }
211
212  for (int i = 0; i < mwpm.blossomNum(); ++i) {
213    check(mwpm.blossomValue(i) >= 0, "Invalid blossom value");
214    check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size");
215    dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2);
216  }
217
218  check(pv * mwpm.dualScale == dv * 2, "Wrong duality");
219
220  return;
221}
222
223
224int main() {
225
226  for (int i = 0; i < lgfn; ++i) {
227    SmartUGraph ugraph;
228    SmartUGraph::UEdgeMap<int> weight(ugraph);
229   
230    istringstream lgfs(lgf[i]);
231    UGraphReader<SmartUGraph>(lgfs, ugraph).
232      readUEdgeMap("weight", weight).run();
233
234    MaxWeightedMatching<SmartUGraph> mwm(ugraph, weight);
235    mwm.run();
236    checkMatching(ugraph, weight, mwm);
237
238    MaxMatching<SmartUGraph> mm(ugraph);
239    mm.run();
240
241    MaxWeightedPerfectMatching<SmartUGraph> mwpm(ugraph, weight);
242    bool perfect = mwpm.run();
243
244    check(perfect == (mm.size() * 2 == countNodes(ugraph)),
245          "Perfect matching found");
246
247    if (perfect) {
248      checkPerfectMatching(ugraph, weight, mwpm);
249    }
250  }
251 
252  return 0;
253}
Note: See TracBrowser for help on using the repository browser.