Changeset 2051:08652c1763f6 in lemon-0.x for test/bipartite_matching_test.cc
- Timestamp:
- 04/14/06 20:07:33 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2694
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/bipartite_matching_test.cc
r2040 r2051 9 9 10 10 #include <lemon/graph_utils.h> 11 12 #include <lemon/maps.h> 11 13 12 14 #include "test_tools.h" … … 25 27 int m = argc > 2 ? atoi(argv[2]) : 100; 26 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; 27 36 28 37 for (int i = 0; i < n; ++i) { … … 37 46 Node aNode = aNodes[urandom(n)]; 38 47 Node bNode = bNodes[urandom(m)]; 39 graph.addEdge(aNode, bNode); 48 UEdge uedge = graph.addEdge(aNode, bNode); 49 weight[uedge] = urandom(c); 40 50 } 41 51 … … 58 68 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { 59 69 if (mm[jt]) ++num; 60 } 61 check(num <= 1, "INVALID PRIMAL"); 62 } 70 } 71 check(num <= 1, "INVALID PRIMAL"); 72 } 73 max_cardinality = bpmatch.matchingSize(); 63 74 } 64 75 … … 112 123 113 124 { 114 SwapBpUGraphAdaptor<Graph> swapgraph(graph); 115 MaxBipartiteMatching<SwapBpUGraphAdaptor<Graph> > bpmatch(swapgraph); 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); 116 163 117 164 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 } 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 135 262 } 136 263
Note: See TracChangeset
for help on using the changeset viewer.