COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/bipartite_matching_test.cc @ 2462:7a096a6bf53a

Last change on this file since 2462:7a096a6bf53a was 2462:7a096a6bf53a, checked in by Balazs Dezso, 12 years ago

Common interface for bipartite matchings
Some useful query function for push-relabel based matching

The naming should be rethink for these classes
for example: pr-ap prefix for push-relabel and augmenting path
algorithms

File size: 10.1 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#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::UEdgeMap<bool> mm(graph);
140
141    check(max_cardinality == maxBipartiteMatching(graph, mm),
142          "WRONG MATCHING");
143   
144    for (ANodeIt it(graph); it != INVALID; ++it) {
145      int num = 0;
146      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
147        if (mm[jt]) ++num;
148      }
149      check(num <= 1, "INVALID PRIMAL");
150    }
151  }
152
153  {
154    MaxBipartiteMatching<Graph> bpmatch(graph);
155
156    bpmatch.greedyInit();
157    bpmatch.start();
158
159    Graph::UEdgeMap<bool> mm(graph);
160    Graph::NodeMap<bool> cs(graph);
161
162    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
163   
164    for (UEdgeIt it(graph); it != INVALID; ++it) {
165      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
166    }
167   
168    for (ANodeIt it(graph); it != INVALID; ++it) {
169      int num = 0;
170      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
171        if (mm[jt]) ++num;
172    }
173      check(num <= 1, "INVALID PRIMAL");
174    }
175  }
176
177  {
178    MaxBipartiteMatching<Graph> bpmatch(graph);
179
180    bpmatch.greedyInit();
181    while (bpmatch.simpleAugment());
182   
183    Graph::UEdgeMap<bool> mm(graph);
184    Graph::NodeMap<bool> cs(graph);
185   
186    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
187   
188    for (UEdgeIt it(graph); it != INVALID; ++it) {
189      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
190    }
191   
192    for (ANodeIt it(graph); it != INVALID; ++it) {
193      int num = 0;
194      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
195        if (mm[jt]) ++num;
196    }
197      check(num <= 1, "INVALID PRIMAL");
198    }
199  }
200
201  {
202    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
203
204    bpmatch.init();
205
206    max_weight = 0;
207    while (bpmatch.augment(true)) {
208   
209      Graph::UEdgeMap<bool> mm(graph);
210      Graph::NodeMap<int> pm(graph);
211     
212      bpmatch.matching(mm);
213      bpmatch.potential(pm);
214     
215      for (UEdgeIt it(graph); it != INVALID; ++it) {
216        if (mm[it]) {
217          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
218                "INVALID DUAL");
219        } else {
220          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
221                "INVALID DUAL");
222        }
223      }
224
225      for (ANodeIt it(graph); it != INVALID; ++it) {
226        int num = 0;
227        for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
228          if (mm[jt]) ++num;
229        }
230        check(num <= 1, "INVALID PRIMAL");
231      }
232      if (bpmatch.matchingValue() > max_weight) {
233        max_weight = bpmatch.matchingValue();
234      }
235    }
236  }
237
238  {
239    Graph::UEdgeMap<bool> mm(graph);
240
241    check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),
242          "WRONG MATCHING");
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  }
252
253  {
254    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
255
256    bpmatch.run();
257   
258    Graph::UEdgeMap<bool> mm(graph);
259    Graph::NodeMap<int> pm(graph);
260
261    bpmatch.matching(mm);
262    bpmatch.potential(pm);
263   
264    for (UEdgeIt it(graph); it != INVALID; ++it) {
265      if (mm[it]) {
266        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
267              "INVALID DUAL");
268      } else {
269        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
270              "INVALID DUAL");
271      }
272    }
273
274    for (ANodeIt it(graph); it != INVALID; ++it) {
275      int num = 0;
276      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
277        if (mm[jt]) ++num;
278    }
279      check(num <= 1, "INVALID PRIMAL");
280    }
281    check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");
282  }
283
284  {
285    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
286
287    bpmatch.run(true);
288   
289    Graph::UEdgeMap<bool> mm(graph);
290    Graph::NodeMap<int> pm(graph);
291
292    bpmatch.matching(mm);
293    bpmatch.potential(pm);
294   
295    for (UEdgeIt it(graph); it != INVALID; ++it) {
296      if (mm[it]) {
297        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
298              "INVALID DUAL");
299      } else {
300        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
301              "INVALID DUAL");
302      }
303    }
304
305    for (ANodeIt it(graph); it != INVALID; ++it) {
306      int num = 0;
307      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
308        if (mm[jt]) ++num;
309    }
310      check(num <= 1, "INVALID PRIMAL");
311    }
312    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
313    max_cardinality_max_weight = bpmatch.matchingValue();
314
315  }
316
317  {
318    Graph::UEdgeMap<bool> mm(graph);
319
320    check(max_cardinality_max_weight ==
321          maxWeightedMaxBipartiteMatching(graph, weight, mm),
322          "WRONG MATCHING");
323   
324    for (ANodeIt it(graph); it != INVALID; ++it) {
325      int num = 0;
326      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
327        if (mm[jt]) ++num;
328      }
329      check(num <= 1, "INVALID PRIMAL");
330    }
331  }
332
333  Graph::UEdgeMap<int> cost(graph);
334  cost = subMap(constMap<UEdge>(C), weight);
335  {
336
337    MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
338
339    bpmatch.run();
340   
341    Graph::UEdgeMap<bool> mm(graph);
342    Graph::NodeMap<int> pm(graph);
343
344    bpmatch.matching(mm);
345    bpmatch.potential(pm);
346   
347    min_cost_matching = bpmatch.matchingCost();
348    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
349    check(max_cardinality * C - max_cardinality_max_weight
350          == bpmatch.matchingCost(), "WRONG SIZE");
351
352    for (UEdgeIt it(graph); it != INVALID; ++it) {
353      if (mm[it]) {
354        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
355              "INVALID DUAL");
356      } else {
357        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
358              "INVALID DUAL");
359      }
360    }
361
362    for (ANodeIt it(graph); it != INVALID; ++it) {
363      int num = 0;
364      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
365        if (mm[jt]) ++num;
366    }
367      check(num <= 1, "INVALID PRIMAL");
368    }
369
370    min_cost_matching = bpmatch.matchingCost();
371    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
372    check(max_cardinality * C - max_cardinality_max_weight
373          == bpmatch.matchingCost(), "WRONG SIZE");
374
375  }
376
377  {
378    Graph::UEdgeMap<bool> mm(graph);
379
380    check(min_cost_matching ==
381          minCostMaxBipartiteMatching(graph, cost, mm),
382          "WRONG MATCHING");
383   
384    for (ANodeIt it(graph); it != INVALID; ++it) {
385      int num = 0;
386      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
387        if (mm[jt]) ++num;
388      }
389      check(num <= 1, "INVALID PRIMAL");
390    }
391  }
392
393  return 0;
394}
Note: See TracBrowser for help on using the repository browser.