1.1 --- a/test/max_matching_test.cc Mon Oct 13 13:56:00 2008 +0200
1.2 +++ b/test/max_matching_test.cc Mon Oct 13 14:00:11 2008 +0200
1.3 @@ -17,165 +17,294 @@
1.4 */
1.5
1.6 #include <iostream>
1.7 +#include <sstream>
1.8 #include <vector>
1.9 #include <queue>
1.10 #include <lemon/math.h>
1.11 #include <cstdlib>
1.12
1.13 +#include <lemon/max_matching.h>
1.14 +#include <lemon/smart_graph.h>
1.15 +#include <lemon/lgf_reader.h>
1.16 +
1.17 #include "test_tools.h"
1.18 -#include <lemon/list_graph.h>
1.19 -#include <lemon/max_matching.h>
1.20
1.21 using namespace std;
1.22 using namespace lemon;
1.23
1.24 +GRAPH_TYPEDEFS(SmartGraph);
1.25 +
1.26 +
1.27 +const int lgfn = 3;
1.28 +const std::string lgf[lgfn] = {
1.29 + "@nodes\n"
1.30 + "label\n"
1.31 + "0\n"
1.32 + "1\n"
1.33 + "2\n"
1.34 + "3\n"
1.35 + "4\n"
1.36 + "5\n"
1.37 + "6\n"
1.38 + "7\n"
1.39 + "@edges\n"
1.40 + " label weight\n"
1.41 + "7 4 0 984\n"
1.42 + "0 7 1 73\n"
1.43 + "7 1 2 204\n"
1.44 + "2 3 3 583\n"
1.45 + "2 7 4 565\n"
1.46 + "2 1 5 582\n"
1.47 + "0 4 6 551\n"
1.48 + "2 5 7 385\n"
1.49 + "1 5 8 561\n"
1.50 + "5 3 9 484\n"
1.51 + "7 5 10 904\n"
1.52 + "3 6 11 47\n"
1.53 + "7 6 12 888\n"
1.54 + "3 0 13 747\n"
1.55 + "6 1 14 310\n",
1.56 +
1.57 + "@nodes\n"
1.58 + "label\n"
1.59 + "0\n"
1.60 + "1\n"
1.61 + "2\n"
1.62 + "3\n"
1.63 + "4\n"
1.64 + "5\n"
1.65 + "6\n"
1.66 + "7\n"
1.67 + "@edges\n"
1.68 + " label weight\n"
1.69 + "2 5 0 710\n"
1.70 + "0 5 1 241\n"
1.71 + "2 4 2 856\n"
1.72 + "2 6 3 762\n"
1.73 + "4 1 4 747\n"
1.74 + "6 1 5 962\n"
1.75 + "4 7 6 723\n"
1.76 + "1 7 7 661\n"
1.77 + "2 3 8 376\n"
1.78 + "1 0 9 416\n"
1.79 + "6 7 10 391\n",
1.80 +
1.81 + "@nodes\n"
1.82 + "label\n"
1.83 + "0\n"
1.84 + "1\n"
1.85 + "2\n"
1.86 + "3\n"
1.87 + "4\n"
1.88 + "5\n"
1.89 + "6\n"
1.90 + "7\n"
1.91 + "@edges\n"
1.92 + " label weight\n"
1.93 + "6 2 0 553\n"
1.94 + "0 7 1 653\n"
1.95 + "6 3 2 22\n"
1.96 + "4 7 3 846\n"
1.97 + "7 2 4 981\n"
1.98 + "7 6 5 250\n"
1.99 + "5 2 6 539\n",
1.100 +};
1.101 +
1.102 +void checkMatching(const SmartGraph& graph,
1.103 + const MaxMatching<SmartGraph>& mm) {
1.104 + int num = 0;
1.105 +
1.106 + IntNodeMap comp_index(graph);
1.107 + UnionFind<IntNodeMap> comp(comp_index);
1.108 +
1.109 + int barrier_num = 0;
1.110 +
1.111 + for (NodeIt n(graph); n != INVALID; ++n) {
1.112 + check(mm.decomposition(n) == MaxMatching<SmartGraph>::EVEN ||
1.113 + mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition");
1.114 + if (mm.decomposition(n) == MaxMatching<SmartGraph>::ODD) {
1.115 + ++barrier_num;
1.116 + } else {
1.117 + comp.insert(n);
1.118 + }
1.119 + }
1.120 +
1.121 + for (EdgeIt e(graph); e != INVALID; ++e) {
1.122 + if (mm.matching(e)) {
1.123 + check(e == mm.matching(graph.u(e)), "Wrong matching");
1.124 + check(e == mm.matching(graph.v(e)), "Wrong matching");
1.125 + ++num;
1.126 + }
1.127 + check(mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::EVEN ||
1.128 + mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED,
1.129 + "Wrong Gallai-Edmonds decomposition");
1.130 +
1.131 + check(mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::EVEN ||
1.132 + mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED,
1.133 + "Wrong Gallai-Edmonds decomposition");
1.134 +
1.135 + if (mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::ODD &&
1.136 + mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {
1.137 + comp.join(graph.u(e), graph.v(e));
1.138 + }
1.139 + }
1.140 +
1.141 + std::set<int> comp_root;
1.142 + int odd_comp_num = 0;
1.143 + for (NodeIt n(graph); n != INVALID; ++n) {
1.144 + if (mm.decomposition(n) != MaxMatching<SmartGraph>::ODD) {
1.145 + int root = comp.find(n);
1.146 + if (comp_root.find(root) == comp_root.end()) {
1.147 + comp_root.insert(root);
1.148 + if (comp.size(n) % 2 == 1) {
1.149 + ++odd_comp_num;
1.150 + }
1.151 + }
1.152 + }
1.153 + }
1.154 +
1.155 + check(mm.matchingSize() == num, "Wrong matching");
1.156 + check(2 * num == countNodes(graph) - (odd_comp_num - barrier_num),
1.157 + "Wrong matching");
1.158 + return;
1.159 +}
1.160 +
1.161 +void checkWeightedMatching(const SmartGraph& graph,
1.162 + const SmartGraph::EdgeMap<int>& weight,
1.163 + const MaxWeightedMatching<SmartGraph>& mwm) {
1.164 + for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
1.165 + if (graph.u(e) == graph.v(e)) continue;
1.166 + int rw = mwm.nodeValue(graph.u(e)) + mwm.nodeValue(graph.v(e));
1.167 +
1.168 + for (int i = 0; i < mwm.blossomNum(); ++i) {
1.169 + bool s = false, t = false;
1.170 + for (MaxWeightedMatching<SmartGraph>::BlossomIt n(mwm, i);
1.171 + n != INVALID; ++n) {
1.172 + if (graph.u(e) == n) s = true;
1.173 + if (graph.v(e) == n) t = true;
1.174 + }
1.175 + if (s == true && t == true) {
1.176 + rw += mwm.blossomValue(i);
1.177 + }
1.178 + }
1.179 + rw -= weight[e] * mwm.dualScale;
1.180 +
1.181 + check(rw >= 0, "Negative reduced weight");
1.182 + check(rw == 0 || !mwm.matching(e),
1.183 + "Non-zero reduced weight on matching edge");
1.184 + }
1.185 +
1.186 + int pv = 0;
1.187 + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
1.188 + if (mwm.matching(n) != INVALID) {
1.189 + check(mwm.nodeValue(n) >= 0, "Invalid node value");
1.190 + pv += weight[mwm.matching(n)];
1.191 + SmartGraph::Node o = graph.target(mwm.matching(n));
1.192 + check(mwm.mate(n) == o, "Invalid matching");
1.193 + check(mwm.matching(n) == graph.oppositeArc(mwm.matching(o)),
1.194 + "Invalid matching");
1.195 + } else {
1.196 + check(mwm.mate(n) == INVALID, "Invalid matching");
1.197 + check(mwm.nodeValue(n) == 0, "Invalid matching");
1.198 + }
1.199 + }
1.200 +
1.201 + int dv = 0;
1.202 + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
1.203 + dv += mwm.nodeValue(n);
1.204 + }
1.205 +
1.206 + for (int i = 0; i < mwm.blossomNum(); ++i) {
1.207 + check(mwm.blossomValue(i) >= 0, "Invalid blossom value");
1.208 + check(mwm.blossomSize(i) % 2 == 1, "Even blossom size");
1.209 + dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2);
1.210 + }
1.211 +
1.212 + check(pv * mwm.dualScale == dv * 2, "Wrong duality");
1.213 +
1.214 + return;
1.215 +}
1.216 +
1.217 +void checkWeightedPerfectMatching(const SmartGraph& graph,
1.218 + const SmartGraph::EdgeMap<int>& weight,
1.219 + const MaxWeightedPerfectMatching<SmartGraph>& mwpm) {
1.220 + for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
1.221 + if (graph.u(e) == graph.v(e)) continue;
1.222 + int rw = mwpm.nodeValue(graph.u(e)) + mwpm.nodeValue(graph.v(e));
1.223 +
1.224 + for (int i = 0; i < mwpm.blossomNum(); ++i) {
1.225 + bool s = false, t = false;
1.226 + for (MaxWeightedPerfectMatching<SmartGraph>::BlossomIt n(mwpm, i);
1.227 + n != INVALID; ++n) {
1.228 + if (graph.u(e) == n) s = true;
1.229 + if (graph.v(e) == n) t = true;
1.230 + }
1.231 + if (s == true && t == true) {
1.232 + rw += mwpm.blossomValue(i);
1.233 + }
1.234 + }
1.235 + rw -= weight[e] * mwpm.dualScale;
1.236 +
1.237 + check(rw >= 0, "Negative reduced weight");
1.238 + check(rw == 0 || !mwpm.matching(e),
1.239 + "Non-zero reduced weight on matching edge");
1.240 + }
1.241 +
1.242 + int pv = 0;
1.243 + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
1.244 + check(mwpm.matching(n) != INVALID, "Non perfect");
1.245 + pv += weight[mwpm.matching(n)];
1.246 + SmartGraph::Node o = graph.target(mwpm.matching(n));
1.247 + check(mwpm.mate(n) == o, "Invalid matching");
1.248 + check(mwpm.matching(n) == graph.oppositeArc(mwpm.matching(o)),
1.249 + "Invalid matching");
1.250 + }
1.251 +
1.252 + int dv = 0;
1.253 + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
1.254 + dv += mwpm.nodeValue(n);
1.255 + }
1.256 +
1.257 + for (int i = 0; i < mwpm.blossomNum(); ++i) {
1.258 + check(mwpm.blossomValue(i) >= 0, "Invalid blossom value");
1.259 + check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size");
1.260 + dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2);
1.261 + }
1.262 +
1.263 + check(pv * mwpm.dualScale == dv * 2, "Wrong duality");
1.264 +
1.265 + return;
1.266 +}
1.267 +
1.268 +
1.269 int main() {
1.270
1.271 - typedef ListGraph Graph;
1.272 + for (int i = 0; i < lgfn; ++i) {
1.273 + SmartGraph graph;
1.274 + SmartGraph::EdgeMap<int> weight(graph);
1.275
1.276 - GRAPH_TYPEDEFS(Graph);
1.277 + istringstream lgfs(lgf[i]);
1.278 + graphReader(graph, lgfs).
1.279 + edgeMap("weight", weight).run();
1.280
1.281 - Graph g;
1.282 - g.clear();
1.283 + MaxMatching<SmartGraph> mm(graph);
1.284 + mm.run();
1.285 + checkMatching(graph, mm);
1.286
1.287 - std::vector<Graph::Node> nodes;
1.288 - for (int i=0; i<13; ++i)
1.289 - nodes.push_back(g.addNode());
1.290 + MaxWeightedMatching<SmartGraph> mwm(graph, weight);
1.291 + mwm.run();
1.292 + checkWeightedMatching(graph, weight, mwm);
1.293
1.294 - g.addEdge(nodes[0], nodes[0]);
1.295 - g.addEdge(nodes[6], nodes[10]);
1.296 - g.addEdge(nodes[5], nodes[10]);
1.297 - g.addEdge(nodes[4], nodes[10]);
1.298 - g.addEdge(nodes[3], nodes[11]);
1.299 - g.addEdge(nodes[1], nodes[6]);
1.300 - g.addEdge(nodes[4], nodes[7]);
1.301 - g.addEdge(nodes[1], nodes[8]);
1.302 - g.addEdge(nodes[0], nodes[8]);
1.303 - g.addEdge(nodes[3], nodes[12]);
1.304 - g.addEdge(nodes[6], nodes[9]);
1.305 - g.addEdge(nodes[9], nodes[11]);
1.306 - g.addEdge(nodes[2], nodes[10]);
1.307 - g.addEdge(nodes[10], nodes[8]);
1.308 - g.addEdge(nodes[5], nodes[8]);
1.309 - g.addEdge(nodes[6], nodes[3]);
1.310 - g.addEdge(nodes[0], nodes[5]);
1.311 - g.addEdge(nodes[6], nodes[12]);
1.312 + MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
1.313 + bool perfect = mwpm.run();
1.314
1.315 - MaxMatching<Graph> max_matching(g);
1.316 - max_matching.init();
1.317 - max_matching.startDense();
1.318 + check(perfect == (mm.matchingSize() * 2 == countNodes(graph)),
1.319 + "Perfect matching found");
1.320
1.321 - int s=0;
1.322 - Graph::NodeMap<Node> mate(g,INVALID);
1.323 - max_matching.mateMap(mate);
1.324 - for(NodeIt v(g); v!=INVALID; ++v) {
1.325 - if ( mate[v]!=INVALID ) ++s;
1.326 - }
1.327 - int size=int(s/2); //size will be used as the size of a maxmatching
1.328 -
1.329 - for(NodeIt v(g); v!=INVALID; ++v) {
1.330 - max_matching.mate(v);
1.331 - }
1.332 -
1.333 - check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" );
1.334 -
1.335 - Graph::NodeMap<MaxMatching<Graph>::DecompType> pos0(g);
1.336 - max_matching.decomposition(pos0);
1.337 -
1.338 - max_matching.init();
1.339 - max_matching.startSparse();
1.340 - s=0;
1.341 - max_matching.mateMap(mate);
1.342 - for(NodeIt v(g); v!=INVALID; ++v) {
1.343 - if ( mate[v]!=INVALID ) ++s;
1.344 - }
1.345 - check ( int(s/2) == size, "The size does not equal!" );
1.346 -
1.347 - Graph::NodeMap<MaxMatching<Graph>::DecompType> pos1(g);
1.348 - max_matching.decomposition(pos1);
1.349 -
1.350 - max_matching.run();
1.351 - s=0;
1.352 - max_matching.mateMap(mate);
1.353 - for(NodeIt v(g); v!=INVALID; ++v) {
1.354 - if ( mate[v]!=INVALID ) ++s;
1.355 - }
1.356 - check ( int(s/2) == size, "The size does not equal!" );
1.357 -
1.358 - Graph::NodeMap<MaxMatching<Graph>::DecompType> pos2(g);
1.359 - max_matching.decomposition(pos2);
1.360 -
1.361 - max_matching.run();
1.362 - s=0;
1.363 - max_matching.mateMap(mate);
1.364 - for(NodeIt v(g); v!=INVALID; ++v) {
1.365 - if ( mate[v]!=INVALID ) ++s;
1.366 - }
1.367 - check ( int(s/2) == size, "The size does not equal!" );
1.368 -
1.369 - Graph::NodeMap<MaxMatching<Graph>::DecompType> pos(g);
1.370 - max_matching.decomposition(pos);
1.371 -
1.372 - bool ismatching=true;
1.373 - for(NodeIt v(g); v!=INVALID; ++v) {
1.374 - if ( mate[v]!=INVALID ) {
1.375 - Node u=mate[v];
1.376 - if (mate[u]!=v) ismatching=false;
1.377 + if (perfect) {
1.378 + checkWeightedPerfectMatching(graph, weight, mwpm);
1.379 }
1.380 }
1.381 - check ( ismatching, "It is not a matching!" );
1.382 -
1.383 - bool coincide=true;
1.384 - for(NodeIt v(g); v!=INVALID; ++v) {
1.385 - if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) {
1.386 - coincide=false;
1.387 - }
1.388 - }
1.389 - check ( coincide, "The decompositions do not coincide! " );
1.390 -
1.391 - bool noarc=true;
1.392 - for(EdgeIt e(g); e!=INVALID; ++e) {
1.393 - if ( (pos[g.v(e)]==max_matching.C &&
1.394 - pos[g.u(e)]==max_matching.D) ||
1.395 - (pos[g.v(e)]==max_matching.D &&
1.396 - pos[g.u(e)]==max_matching.C) )
1.397 - noarc=false;
1.398 - }
1.399 - check ( noarc, "There are arcs between D and C!" );
1.400 -
1.401 - bool oddcomp=true;
1.402 - Graph::NodeMap<bool> todo(g,true);
1.403 - int num_comp=0;
1.404 - for(NodeIt v(g); v!=INVALID; ++v) {
1.405 - if ( pos[v]==max_matching.D && todo[v] ) {
1.406 - int comp_size=1;
1.407 - ++num_comp;
1.408 - std::queue<Node> Q;
1.409 - Q.push(v);
1.410 - todo.set(v,false);
1.411 - while (!Q.empty()) {
1.412 - Node w=Q.front();
1.413 - Q.pop();
1.414 - for(IncEdgeIt e(g,w); e!=INVALID; ++e) {
1.415 - Node u=g.runningNode(e);
1.416 - if ( pos[u]==max_matching.D && todo[u] ) {
1.417 - ++comp_size;
1.418 - Q.push(u);
1.419 - todo.set(u,false);
1.420 - }
1.421 - }
1.422 - }
1.423 - if ( !(comp_size % 2) ) oddcomp=false;
1.424 - }
1.425 - }
1.426 - check ( oddcomp, "A component of g[D] is not odd." );
1.427 -
1.428 - int barrier=0;
1.429 - for(NodeIt v(g); v!=INVALID; ++v) {
1.430 - if ( pos[v]==max_matching.A ) ++barrier;
1.431 - }
1.432 - int expected_size=int( countNodes(g)-num_comp+barrier)/2;
1.433 - check ( size==expected_size, "The size of the matching is wrong." );
1.434
1.435 return 0;
1.436 }