# source:lemon-0.x/test/bipartite_matching_test.cc@2111:ea1fa1bc3f6d

Last change on this file since 2111:ea1fa1bc3f6d was 2058:0b1fc1566fdb, checked in by Balazs Dezso, 15 years ago

Refinements in bipartite matching algorithms

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