COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/bipartite_matching_test.cc @ 2051:08652c1763f6

Last change on this file since 2051:08652c1763f6 was 2051:08652c1763f6, checked in by Balazs Dezso, 13 years ago

MaxWeightedBipartiteMatching?
MinCostMaxBipartiteMatching?

Both algorithms are based on successive shortest
path algorithm with dijkstra shortest path
finding

File size: 6.6 KB
Line 
1#include <cstdlib>
2#include <iostream>
3#include <sstream>
4
5#include <lemon/list_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 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]) : 100;
27  int m = argc > 2 ? atoi(argv[2]) : 100;
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
37  for (int i = 0; i < n; ++i) {
38    Node node = graph.addANode();
39    aNodes.push_back(node);
40  }
41  for (int i = 0; i < m; ++i) {
42    Node node = graph.addBNode();
43    bNodes.push_back(node);
44  }
45  for (int i = 0; i < e; ++i) {
46    Node aNode = aNodes[urandom(n)];
47    Node bNode = bNodes[urandom(m)];
48    UEdge uedge = graph.addEdge(aNode, bNode);
49    weight[uedge] = urandom(c);
50  }
51
52  {
53    MaxBipartiteMatching<Graph> bpmatch(graph);
54
55    bpmatch.run();
56
57    Graph::UEdgeMap<bool> mm(graph);
58    Graph::NodeMap<bool> cs(graph);
59   
60    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
61   
62    for (UEdgeIt it(graph); it != INVALID; ++it) {
63      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
64    }
65   
66    for (ANodeIt it(graph); it != INVALID; ++it) {
67      int num = 0;
68      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
69        if (mm[jt]) ++num;
70      }
71      check(num <= 1, "INVALID PRIMAL");
72    }
73    max_cardinality = bpmatch.matchingSize();
74  }
75
76  {
77    MaxBipartiteMatching<Graph> bpmatch(graph);
78
79    bpmatch.greedyInit();
80    bpmatch.start();
81
82    Graph::UEdgeMap<bool> mm(graph);
83    Graph::NodeMap<bool> cs(graph);
84
85    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
86   
87    for (UEdgeIt it(graph); it != INVALID; ++it) {
88      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
89    }
90   
91    for (ANodeIt it(graph); it != INVALID; ++it) {
92      int num = 0;
93      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
94        if (mm[jt]) ++num;
95    }
96      check(num <= 1, "INVALID PRIMAL");
97    }
98  }
99
100  {
101    MaxBipartiteMatching<Graph> bpmatch(graph);
102
103    bpmatch.greedyInit();
104    while (bpmatch.simpleAugment());
105   
106    Graph::UEdgeMap<bool> mm(graph);
107    Graph::NodeMap<bool> cs(graph);
108   
109    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
110   
111    for (UEdgeIt it(graph); it != INVALID; ++it) {
112      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
113    }
114   
115    for (ANodeIt it(graph); it != INVALID; ++it) {
116      int num = 0;
117      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
118        if (mm[jt]) ++num;
119    }
120      check(num <= 1, "INVALID PRIMAL");
121    }
122  }
123
124  {
125    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
126
127    bpmatch.init();
128
129    max_weight = 0;
130    while (bpmatch.augment(true)) {
131   
132      Graph::UEdgeMap<bool> mm(graph);
133      Graph::NodeMap<int> pm(graph);
134     
135      bpmatch.matching(mm);
136      bpmatch.potential(pm);
137     
138      for (UEdgeIt it(graph); it != INVALID; ++it) {
139        if (mm[it]) {
140          check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
141                "INVALID DUAL");
142        } else {
143          check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
144                "INVALID DUAL");
145        }
146      }
147
148      for (ANodeIt it(graph); it != INVALID; ++it) {
149        int num = 0;
150        for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
151          if (mm[jt]) ++num;
152        }
153        check(num <= 1, "INVALID PRIMAL");
154      }
155      if (bpmatch.matchingValue() > max_weight) {
156        max_weight = bpmatch.matchingValue();
157      }
158    }
159  }
160
161  {
162    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
163
164    bpmatch.run();
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)] - weight[it] - pm[graph.bNode(it)] == 0,
175              "INVALID DUAL");
176      } else {
177        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(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    check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");
190  }
191
192  {
193    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
194
195    bpmatch.run(true);
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)] - weight[it] - pm[graph.bNode(it)] == 0,
206              "INVALID DUAL");
207      } else {
208        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(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_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
221    max_cardinality_max_weight = bpmatch.matchingValue();
222
223  }
224
225  {
226    Graph::UEdgeMap<int> cost(graph);
227
228    cost = subMap(constMap<UEdge>(c), weight);
229
230    MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
231
232    bpmatch.run();
233   
234    Graph::UEdgeMap<bool> mm(graph);
235    Graph::NodeMap<int> pm(graph);
236
237    bpmatch.matching(mm);
238    bpmatch.potential(pm);
239   
240    for (UEdgeIt it(graph); it != INVALID; ++it) {
241      if (mm[it]) {
242        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
243              "INVALID DUAL");
244      } else {
245        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
246              "INVALID DUAL");
247      }
248    }
249
250    for (ANodeIt it(graph); it != INVALID; ++it) {
251      int num = 0;
252      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
253        if (mm[jt]) ++num;
254    }
255      check(num <= 1, "INVALID PRIMAL");
256    }
257
258    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
259    check(max_cardinality * c - max_cardinality_max_weight
260          == bpmatch.matchingCost(), "WRONG SIZE");
261
262  }
263
264  return 0;
265}
Note: See TracBrowser for help on using the repository browser.