COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/bipartite_matching_test.cc @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 12 years ago

Happy New Year to all source files!

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