COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/bipartite_matching_test.cc @ 2196:09af6d2b683b

Last change on this file since 2196:09af6d2b683b was 2137:54043fa66bce, checked in by Balazs Dezso, 18 years ago

Using fixed bipartite graph

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