COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/bipartite_matching_test.cc @ 2570:c62964ff0d53

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

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

File size: 10.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 <cstdlib>
20#include <iostream>
21#include <sstream>
22
23#include <lemon/smart_graph.h>
24
25#include <lemon/bpugraph_adaptor.h>
26#include <lemon/bipartite_matching.h>
27#include <lemon/pr_bipartite_matching.h>
28
29#include <lemon/graph_utils.h>
30
31#include <lemon/maps.h>
32
33#include "test_tools.h"
34
35using namespace std;
36using namespace lemon;
37
38typedef SmartBpUGraph Graph;
39BPUGRAPH_TYPEDEFS(Graph);
40
41const int N = 10;
42const int M = 10;
43const int E = 52;
44const int C = 100;
45
46const int sa[E] = { 6, 5, 6, 4, 1, 0, 9, 5, 2, 4, 4, 3, 5,
47                    2, 3, 8, 3, 4, 9, 6, 9, 4, 3, 1, 5, 8,
48                    4, 8, 9, 2, 2, 3, 0, 5, 2, 3, 6, 3, 8,
49                    8, 4, 0, 9, 9, 6, 2, 1, 2, 7, 1, 9, 4};
50
51const int ta[E] = { 2, 7, 4, 8, 6, 3, 4, 1, 7, 7, 0, 1, 6,
52                    3, 2, 6, 8, 3, 5, 6, 3, 1, 8, 7, 2, 0,
53                    6, 9, 6, 7, 8, 3, 3, 4, 5, 8, 6, 4, 1,
54                    4, 3, 3, 8, 7, 7, 3, 7, 7, 3, 5, 1, 6};
55
56const int wa[E] = { 3, 99, 85, 16, 79, 52, 83, 99, 62, 6, 42, 6, 95,
57                    13, 34, 9, 5, 38, 39, 75, 99, 12, 73, 35, 93, 43,
58                    54, 91, 45, 26, 77, 47, 11, 22, 50, 74, 37, 64, 91,
59                    60, 6, 92, 29, 46, 34, 84, 67, 34, 45, 0, 39, 47};
60
61
62int main() {
63  Graph graph;
64  vector<Node> aNodes;
65  vector<Node> bNodes;
66
67  Graph::UEdgeMap<int> weight(graph);
68
69  int max_cardinality;
70  int max_weight;
71  int max_cardinality_max_weight;
72  int min_cost_matching;
73
74  for (int i = 0; i < N; ++i) {
75    Node node = graph.addANode();
76    aNodes.push_back(node);
77  }
78  for (int i = 0; i < M; ++i) {
79    Node node = graph.addBNode();
80    bNodes.push_back(node);
81  }
82  for (int i = 0; i < E; ++i) {
83    Node aNode = aNodes[sa[i]];
84    Node bNode = bNodes[ta[i]];
85    UEdge uedge = graph.addEdge(aNode, bNode);
86    weight[uedge] = wa[i];
87  }
88
89
90  {
91    MaxBipartiteMatching<Graph> bpmatch(graph);
92
93    bpmatch.run();
94
95    Graph::UEdgeMap<bool> mm(graph);
96    Graph::NodeMap<bool> cs(graph);
97   
98    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
99   
100    for (UEdgeIt it(graph); it != INVALID; ++it) {
101      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
102    }
103   
104    for (ANodeIt it(graph); it != INVALID; ++it) {
105      int num = 0;
106      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
107        if (mm[jt]) ++num;
108      }
109      check(num <= 1, "INVALID PRIMAL");
110    }
111    max_cardinality = bpmatch.matchingSize();
112  }
113
114  {
115    PrBipartiteMatching<Graph> bpmatch(graph);
116
117    bpmatch.run();
118
119    Graph::UEdgeMap<bool> mm(graph);
120    Graph::NodeMap<bool> cs(graph);
121   
122    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
123   
124    for (UEdgeIt it(graph); it != INVALID; ++it) {
125      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
126    }
127   
128    for (ANodeIt it(graph); it != INVALID; ++it) {
129      int num = 0;
130      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
131        if (mm[jt]) ++num;
132      }
133      check(num <= 1, "INVALID PRIMAL");
134    }
135    max_cardinality = bpmatch.matchingSize();
136  }
137
138  {
139    Graph::ANodeMap<UEdge> mm(graph);
140
141    check(max_cardinality == maxBipartiteMatching(graph, mm),
142          "WRONG MATCHING");
143   
144    for (BNodeIt it(graph); it != INVALID; ++it) {
145      int num = 0;
146     
147      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
148        if (mm[graph.aNode(jt)] == jt) ++num;
149      }
150      check(num <= 1, "INVALID PRIMAL");
151    }
152  }
153
154  {
155    Graph::ANodeMap<UEdge> mm(graph);
156
157    check(max_cardinality == prBipartiteMatching(graph, mm),
158          "WRONG MATCHING");
159   
160    for (BNodeIt it(graph); it != INVALID; ++it) {
161      int num = 0;
162     
163      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
164        if (mm[graph.aNode(jt)] == jt) ++num;
165      }
166      check(num <= 1, "INVALID PRIMAL");
167    }
168  }
169
170  {
171    MaxBipartiteMatching<Graph> bpmatch(graph);
172
173    bpmatch.greedyInit();
174    bpmatch.start();
175
176    Graph::UEdgeMap<bool> mm(graph);
177    Graph::NodeMap<bool> cs(graph);
178
179    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
180   
181    for (UEdgeIt it(graph); it != INVALID; ++it) {
182      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
183    }
184   
185    for (ANodeIt it(graph); it != INVALID; ++it) {
186      int num = 0;
187      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
188        if (mm[jt]) ++num;
189    }
190      check(num <= 1, "INVALID PRIMAL");
191    }
192  }
193
194  {
195    MaxBipartiteMatching<Graph> bpmatch(graph);
196
197    bpmatch.greedyInit();
198    while (bpmatch.simpleAugment());
199   
200    Graph::UEdgeMap<bool> mm(graph);
201    Graph::NodeMap<bool> cs(graph);
202   
203    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
204   
205    for (UEdgeIt it(graph); it != INVALID; ++it) {
206      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
207    }
208   
209    for (ANodeIt it(graph); it != INVALID; ++it) {
210      int num = 0;
211      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
212        if (mm[jt]) ++num;
213    }
214      check(num <= 1, "INVALID PRIMAL");
215    }
216  }
217
218  {
219    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
220
221    bpmatch.init();
222
223    max_weight = 0;
224    while (bpmatch.augment(true)) {
225   
226      Graph::UEdgeMap<bool> mm(graph);
227      Graph::NodeMap<int> pm(graph);
228     
229      bpmatch.matching(mm);
230      bpmatch.potential(pm);
231     
232      for (UEdgeIt it(graph); it != INVALID; ++it) {
233        if (mm[it]) {
234          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
235                "INVALID DUAL");
236        } else {
237          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
238                "INVALID DUAL");
239        }
240      }
241
242      for (ANodeIt it(graph); it != INVALID; ++it) {
243        int num = 0;
244        for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
245          if (mm[jt]) ++num;
246        }
247        check(num <= 1, "INVALID PRIMAL");
248      }
249      if (bpmatch.matchingValue() > max_weight) {
250        max_weight = bpmatch.matchingValue();
251      }
252    }
253  }
254
255  {
256    Graph::UEdgeMap<bool> mm(graph);
257
258    check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),
259          "WRONG MATCHING");
260   
261    for (ANodeIt it(graph); it != INVALID; ++it) {
262      int num = 0;
263      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
264        if (mm[jt]) ++num;
265      }
266      check(num <= 1, "INVALID PRIMAL");
267    }
268  }
269
270  {
271    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
272
273    bpmatch.run();
274   
275    Graph::UEdgeMap<bool> mm(graph);
276    Graph::NodeMap<int> pm(graph);
277
278    bpmatch.matching(mm);
279    bpmatch.potential(pm);
280   
281    for (UEdgeIt it(graph); it != INVALID; ++it) {
282      if (mm[it]) {
283        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
284              "INVALID DUAL");
285      } else {
286        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
287              "INVALID DUAL");
288      }
289    }
290
291    for (ANodeIt it(graph); it != INVALID; ++it) {
292      int num = 0;
293      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
294        if (mm[jt]) ++num;
295    }
296      check(num <= 1, "INVALID PRIMAL");
297    }
298    check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");
299  }
300
301  {
302    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
303
304    bpmatch.run(true);
305   
306    Graph::UEdgeMap<bool> mm(graph);
307    Graph::NodeMap<int> pm(graph);
308
309    bpmatch.matching(mm);
310    bpmatch.potential(pm);
311   
312    for (UEdgeIt it(graph); it != INVALID; ++it) {
313      if (mm[it]) {
314        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
315              "INVALID DUAL");
316      } else {
317        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
318              "INVALID DUAL");
319      }
320    }
321
322    for (ANodeIt it(graph); it != INVALID; ++it) {
323      int num = 0;
324      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
325        if (mm[jt]) ++num;
326    }
327      check(num <= 1, "INVALID PRIMAL");
328    }
329    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
330    max_cardinality_max_weight = bpmatch.matchingValue();
331
332  }
333
334  {
335    Graph::UEdgeMap<bool> mm(graph);
336
337    check(max_cardinality_max_weight ==
338          maxWeightedMaxBipartiteMatching(graph, weight, mm),
339          "WRONG MATCHING");
340   
341    for (ANodeIt it(graph); it != INVALID; ++it) {
342      int num = 0;
343      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
344        if (mm[jt]) ++num;
345      }
346      check(num <= 1, "INVALID PRIMAL");
347    }
348  }
349
350  Graph::UEdgeMap<int> cost(graph);
351  cost = subMap(constMap<UEdge>(C), weight);
352  {
353
354    MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
355
356    bpmatch.run();
357   
358    Graph::UEdgeMap<bool> mm(graph);
359    Graph::NodeMap<int> pm(graph);
360
361    bpmatch.matching(mm);
362    bpmatch.potential(pm);
363   
364    min_cost_matching = bpmatch.matchingCost();
365    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
366    check(max_cardinality * C - max_cardinality_max_weight
367          == bpmatch.matchingCost(), "WRONG SIZE");
368
369    for (UEdgeIt it(graph); it != INVALID; ++it) {
370      if (mm[it]) {
371        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
372              "INVALID DUAL");
373      } else {
374        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
375              "INVALID DUAL");
376      }
377    }
378
379    for (ANodeIt it(graph); it != INVALID; ++it) {
380      int num = 0;
381      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
382        if (mm[jt]) ++num;
383    }
384      check(num <= 1, "INVALID PRIMAL");
385    }
386
387    min_cost_matching = bpmatch.matchingCost();
388    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
389    check(max_cardinality * C - max_cardinality_max_weight
390          == bpmatch.matchingCost(), "WRONG SIZE");
391
392  }
393
394  {
395    Graph::UEdgeMap<bool> mm(graph);
396
397    check(min_cost_matching ==
398          minCostMaxBipartiteMatching(graph, cost, mm),
399          "WRONG MATCHING");
400   
401    for (ANodeIt it(graph); it != INVALID; ++it) {
402      int num = 0;
403      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
404        if (mm[jt]) ++num;
405      }
406      check(num <= 1, "INVALID PRIMAL");
407    }
408  }
409
410  return 0;
411}
Note: See TracBrowser for help on using the repository browser.