1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/fractional_matching_test.cc Sun Aug 11 15:28:12 2013 +0200
1.3 @@ -0,0 +1,527 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2010
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#include <iostream>
1.23 +#include <sstream>
1.24 +#include <vector>
1.25 +#include <queue>
1.26 +#include <cstdlib>
1.27 +
1.28 +#include <lemon/fractional_matching.h>
1.29 +#include <lemon/smart_graph.h>
1.30 +#include <lemon/concepts/graph.h>
1.31 +#include <lemon/concepts/maps.h>
1.32 +#include <lemon/lgf_reader.h>
1.33 +#include <lemon/math.h>
1.34 +
1.35 +#include "test_tools.h"
1.36 +
1.37 +using namespace std;
1.38 +using namespace lemon;
1.39 +
1.40 +GRAPH_TYPEDEFS(SmartGraph);
1.41 +
1.42 +
1.43 +const int lgfn = 4;
1.44 +const std::string lgf[lgfn] = {
1.45 + "@nodes\n"
1.46 + "label\n"
1.47 + "0\n"
1.48 + "1\n"
1.49 + "2\n"
1.50 + "3\n"
1.51 + "4\n"
1.52 + "5\n"
1.53 + "6\n"
1.54 + "7\n"
1.55 + "@edges\n"
1.56 + " label weight\n"
1.57 + "7 4 0 984\n"
1.58 + "0 7 1 73\n"
1.59 + "7 1 2 204\n"
1.60 + "2 3 3 583\n"
1.61 + "2 7 4 565\n"
1.62 + "2 1 5 582\n"
1.63 + "0 4 6 551\n"
1.64 + "2 5 7 385\n"
1.65 + "1 5 8 561\n"
1.66 + "5 3 9 484\n"
1.67 + "7 5 10 904\n"
1.68 + "3 6 11 47\n"
1.69 + "7 6 12 888\n"
1.70 + "3 0 13 747\n"
1.71 + "6 1 14 310\n",
1.72 +
1.73 + "@nodes\n"
1.74 + "label\n"
1.75 + "0\n"
1.76 + "1\n"
1.77 + "2\n"
1.78 + "3\n"
1.79 + "4\n"
1.80 + "5\n"
1.81 + "6\n"
1.82 + "7\n"
1.83 + "@edges\n"
1.84 + " label weight\n"
1.85 + "2 5 0 710\n"
1.86 + "0 5 1 241\n"
1.87 + "2 4 2 856\n"
1.88 + "2 6 3 762\n"
1.89 + "4 1 4 747\n"
1.90 + "6 1 5 962\n"
1.91 + "4 7 6 723\n"
1.92 + "1 7 7 661\n"
1.93 + "2 3 8 376\n"
1.94 + "1 0 9 416\n"
1.95 + "6 7 10 391\n",
1.96 +
1.97 + "@nodes\n"
1.98 + "label\n"
1.99 + "0\n"
1.100 + "1\n"
1.101 + "2\n"
1.102 + "3\n"
1.103 + "4\n"
1.104 + "5\n"
1.105 + "6\n"
1.106 + "7\n"
1.107 + "@edges\n"
1.108 + " label weight\n"
1.109 + "6 2 0 553\n"
1.110 + "0 7 1 653\n"
1.111 + "6 3 2 22\n"
1.112 + "4 7 3 846\n"
1.113 + "7 2 4 981\n"
1.114 + "7 6 5 250\n"
1.115 + "5 2 6 539\n",
1.116 +
1.117 + "@nodes\n"
1.118 + "label\n"
1.119 + "0\n"
1.120 + "@edges\n"
1.121 + " label weight\n"
1.122 + "0 0 0 100\n"
1.123 +};
1.124 +
1.125 +void checkMaxFractionalMatchingCompile()
1.126 +{
1.127 + typedef concepts::Graph Graph;
1.128 + typedef Graph::Node Node;
1.129 + typedef Graph::Edge Edge;
1.130 +
1.131 + Graph g;
1.132 + Node n;
1.133 + Edge e;
1.134 +
1.135 + MaxFractionalMatching<Graph> mat_test(g);
1.136 + const MaxFractionalMatching<Graph>&
1.137 + const_mat_test = mat_test;
1.138 +
1.139 + mat_test.init();
1.140 + mat_test.start();
1.141 + mat_test.start(true);
1.142 + mat_test.startPerfect();
1.143 + mat_test.startPerfect(true);
1.144 + mat_test.run();
1.145 + mat_test.run(true);
1.146 + mat_test.runPerfect();
1.147 + mat_test.runPerfect(true);
1.148 +
1.149 + const_mat_test.matchingSize();
1.150 + const_mat_test.matching(e);
1.151 + const_mat_test.matching(n);
1.152 + const MaxFractionalMatching<Graph>::MatchingMap& mmap =
1.153 + const_mat_test.matchingMap();
1.154 + e = mmap[n];
1.155 +
1.156 + const_mat_test.barrier(n);
1.157 +}
1.158 +
1.159 +void checkMaxWeightedFractionalMatchingCompile()
1.160 +{
1.161 + typedef concepts::Graph Graph;
1.162 + typedef Graph::Node Node;
1.163 + typedef Graph::Edge Edge;
1.164 + typedef Graph::EdgeMap<int> WeightMap;
1.165 +
1.166 + Graph g;
1.167 + Node n;
1.168 + Edge e;
1.169 + WeightMap w(g);
1.170 +
1.171 + MaxWeightedFractionalMatching<Graph> mat_test(g, w);
1.172 + const MaxWeightedFractionalMatching<Graph>&
1.173 + const_mat_test = mat_test;
1.174 +
1.175 + mat_test.init();
1.176 + mat_test.start();
1.177 + mat_test.run();
1.178 +
1.179 + const_mat_test.matchingWeight();
1.180 + const_mat_test.matchingSize();
1.181 + const_mat_test.matching(e);
1.182 + const_mat_test.matching(n);
1.183 + const MaxWeightedFractionalMatching<Graph>::MatchingMap& mmap =
1.184 + const_mat_test.matchingMap();
1.185 + e = mmap[n];
1.186 +
1.187 + const_mat_test.dualValue();
1.188 + const_mat_test.nodeValue(n);
1.189 +}
1.190 +
1.191 +void checkMaxWeightedPerfectFractionalMatchingCompile()
1.192 +{
1.193 + typedef concepts::Graph Graph;
1.194 + typedef Graph::Node Node;
1.195 + typedef Graph::Edge Edge;
1.196 + typedef Graph::EdgeMap<int> WeightMap;
1.197 +
1.198 + Graph g;
1.199 + Node n;
1.200 + Edge e;
1.201 + WeightMap w(g);
1.202 +
1.203 + MaxWeightedPerfectFractionalMatching<Graph> mat_test(g, w);
1.204 + const MaxWeightedPerfectFractionalMatching<Graph>&
1.205 + const_mat_test = mat_test;
1.206 +
1.207 + mat_test.init();
1.208 + mat_test.start();
1.209 + mat_test.run();
1.210 +
1.211 + const_mat_test.matchingWeight();
1.212 + const_mat_test.matching(e);
1.213 + const_mat_test.matching(n);
1.214 + const MaxWeightedPerfectFractionalMatching<Graph>::MatchingMap& mmap =
1.215 + const_mat_test.matchingMap();
1.216 + e = mmap[n];
1.217 +
1.218 + const_mat_test.dualValue();
1.219 + const_mat_test.nodeValue(n);
1.220 +}
1.221 +
1.222 +void checkFractionalMatching(const SmartGraph& graph,
1.223 + const MaxFractionalMatching<SmartGraph>& mfm,
1.224 + bool allow_loops = true) {
1.225 + int pv = 0;
1.226 + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
1.227 + int indeg = 0;
1.228 + for (InArcIt a(graph, n); a != INVALID; ++a) {
1.229 + if (mfm.matching(graph.source(a)) == a) {
1.230 + ++indeg;
1.231 + }
1.232 + }
1.233 + if (mfm.matching(n) != INVALID) {
1.234 + check(indeg == 1, "Invalid matching");
1.235 + ++pv;
1.236 + } else {
1.237 + check(indeg == 0, "Invalid matching");
1.238 + }
1.239 + }
1.240 + check(pv == mfm.matchingSize(), "Wrong matching size");
1.241 +
1.242 + for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
1.243 + check((e == mfm.matching(graph.u(e)) ? 1 : 0) +
1.244 + (e == mfm.matching(graph.v(e)) ? 1 : 0) ==
1.245 + mfm.matching(e), "Invalid matching");
1.246 + }
1.247 +
1.248 + SmartGraph::NodeMap<bool> processed(graph, false);
1.249 + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
1.250 + if (processed[n]) continue;
1.251 + processed[n] = true;
1.252 + if (mfm.matching(n) == INVALID) continue;
1.253 + int num = 1;
1.254 + Node v = graph.target(mfm.matching(n));
1.255 + while (v != n) {
1.256 + processed[v] = true;
1.257 + ++num;
1.258 + v = graph.target(mfm.matching(v));
1.259 + }
1.260 + check(num == 2 || num % 2 == 1, "Wrong cycle size");
1.261 + check(allow_loops || num != 1, "Wrong cycle size");
1.262 + }
1.263 +
1.264 + int anum = 0, bnum = 0;
1.265 + SmartGraph::NodeMap<bool> neighbours(graph, false);
1.266 + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
1.267 + if (!mfm.barrier(n)) continue;
1.268 + ++anum;
1.269 + for (SmartGraph::InArcIt a(graph, n); a != INVALID; ++a) {
1.270 + Node u = graph.source(a);
1.271 + if (!allow_loops && u == n) continue;
1.272 + if (!neighbours[u]) {
1.273 + neighbours[u] = true;
1.274 + ++bnum;
1.275 + }
1.276 + }
1.277 + }
1.278 + check(anum - bnum + mfm.matchingSize() == countNodes(graph),
1.279 + "Wrong barrier");
1.280 +}
1.281 +
1.282 +void checkPerfectFractionalMatching(const SmartGraph& graph,
1.283 + const MaxFractionalMatching<SmartGraph>& mfm,
1.284 + bool perfect, bool allow_loops = true) {
1.285 + if (perfect) {
1.286 + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
1.287 + int indeg = 0;
1.288 + for (InArcIt a(graph, n); a != INVALID; ++a) {
1.289 + if (mfm.matching(graph.source(a)) == a) {
1.290 + ++indeg;
1.291 + }
1.292 + }
1.293 + check(mfm.matching(n) != INVALID, "Invalid matching");
1.294 + check(indeg == 1, "Invalid matching");
1.295 + }
1.296 + for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
1.297 + check((e == mfm.matching(graph.u(e)) ? 1 : 0) +
1.298 + (e == mfm.matching(graph.v(e)) ? 1 : 0) ==
1.299 + mfm.matching(e), "Invalid matching");
1.300 + }
1.301 + } else {
1.302 + int anum = 0, bnum = 0;
1.303 + SmartGraph::NodeMap<bool> neighbours(graph, false);
1.304 + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
1.305 + if (!mfm.barrier(n)) continue;
1.306 + ++anum;
1.307 + for (SmartGraph::InArcIt a(graph, n); a != INVALID; ++a) {
1.308 + Node u = graph.source(a);
1.309 + if (!allow_loops && u == n) continue;
1.310 + if (!neighbours[u]) {
1.311 + neighbours[u] = true;
1.312 + ++bnum;
1.313 + }
1.314 + }
1.315 + }
1.316 + check(anum - bnum > 0, "Wrong barrier");
1.317 + }
1.318 +}
1.319 +
1.320 +void checkWeightedFractionalMatching(const SmartGraph& graph,
1.321 + const SmartGraph::EdgeMap<int>& weight,
1.322 + const MaxWeightedFractionalMatching<SmartGraph>& mwfm,
1.323 + bool allow_loops = true) {
1.324 + for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
1.325 + if (graph.u(e) == graph.v(e) && !allow_loops) continue;
1.326 + int rw = mwfm.nodeValue(graph.u(e)) + mwfm.nodeValue(graph.v(e))
1.327 + - weight[e] * mwfm.dualScale;
1.328 +
1.329 + check(rw >= 0, "Negative reduced weight");
1.330 + check(rw == 0 || !mwfm.matching(e),
1.331 + "Non-zero reduced weight on matching edge");
1.332 + }
1.333 +
1.334 + int pv = 0;
1.335 + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
1.336 + int indeg = 0;
1.337 + for (InArcIt a(graph, n); a != INVALID; ++a) {
1.338 + if (mwfm.matching(graph.source(a)) == a) {
1.339 + ++indeg;
1.340 + }
1.341 + }
1.342 + check(indeg <= 1, "Invalid matching");
1.343 + if (mwfm.matching(n) != INVALID) {
1.344 + check(mwfm.nodeValue(n) >= 0, "Invalid node value");
1.345 + check(indeg == 1, "Invalid matching");
1.346 + pv += weight[mwfm.matching(n)];
1.347 + SmartGraph::Node o = graph.target(mwfm.matching(n));
1.348 + ::lemon::ignore_unused_variable_warning(o);
1.349 + } else {
1.350 + check(mwfm.nodeValue(n) == 0, "Invalid matching");
1.351 + check(indeg == 0, "Invalid matching");
1.352 + }
1.353 + }
1.354 +
1.355 + for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
1.356 + check((e == mwfm.matching(graph.u(e)) ? 1 : 0) +
1.357 + (e == mwfm.matching(graph.v(e)) ? 1 : 0) ==
1.358 + mwfm.matching(e), "Invalid matching");
1.359 + }
1.360 +
1.361 + int dv = 0;
1.362 + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
1.363 + dv += mwfm.nodeValue(n);
1.364 + }
1.365 +
1.366 + check(pv * mwfm.dualScale == dv * 2, "Wrong duality");
1.367 +
1.368 + SmartGraph::NodeMap<bool> processed(graph, false);
1.369 + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
1.370 + if (processed[n]) continue;
1.371 + processed[n] = true;
1.372 + if (mwfm.matching(n) == INVALID) continue;
1.373 + int num = 1;
1.374 + Node v = graph.target(mwfm.matching(n));
1.375 + while (v != n) {
1.376 + processed[v] = true;
1.377 + ++num;
1.378 + v = graph.target(mwfm.matching(v));
1.379 + }
1.380 + check(num == 2 || num % 2 == 1, "Wrong cycle size");
1.381 + check(allow_loops || num != 1, "Wrong cycle size");
1.382 + }
1.383 +
1.384 + return;
1.385 +}
1.386 +
1.387 +void checkWeightedPerfectFractionalMatching(const SmartGraph& graph,
1.388 + const SmartGraph::EdgeMap<int>& weight,
1.389 + const MaxWeightedPerfectFractionalMatching<SmartGraph>& mwpfm,
1.390 + bool allow_loops = true) {
1.391 + for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
1.392 + if (graph.u(e) == graph.v(e) && !allow_loops) continue;
1.393 + int rw = mwpfm.nodeValue(graph.u(e)) + mwpfm.nodeValue(graph.v(e))
1.394 + - weight[e] * mwpfm.dualScale;
1.395 +
1.396 + check(rw >= 0, "Negative reduced weight");
1.397 + check(rw == 0 || !mwpfm.matching(e),
1.398 + "Non-zero reduced weight on matching edge");
1.399 + }
1.400 +
1.401 + int pv = 0;
1.402 + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
1.403 + int indeg = 0;
1.404 + for (InArcIt a(graph, n); a != INVALID; ++a) {
1.405 + if (mwpfm.matching(graph.source(a)) == a) {
1.406 + ++indeg;
1.407 + }
1.408 + }
1.409 + check(mwpfm.matching(n) != INVALID, "Invalid perfect matching");
1.410 + check(indeg == 1, "Invalid perfect matching");
1.411 + pv += weight[mwpfm.matching(n)];
1.412 + SmartGraph::Node o = graph.target(mwpfm.matching(n));
1.413 + ::lemon::ignore_unused_variable_warning(o);
1.414 + }
1.415 +
1.416 + for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
1.417 + check((e == mwpfm.matching(graph.u(e)) ? 1 : 0) +
1.418 + (e == mwpfm.matching(graph.v(e)) ? 1 : 0) ==
1.419 + mwpfm.matching(e), "Invalid matching");
1.420 + }
1.421 +
1.422 + int dv = 0;
1.423 + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
1.424 + dv += mwpfm.nodeValue(n);
1.425 + }
1.426 +
1.427 + check(pv * mwpfm.dualScale == dv * 2, "Wrong duality");
1.428 +
1.429 + SmartGraph::NodeMap<bool> processed(graph, false);
1.430 + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
1.431 + if (processed[n]) continue;
1.432 + processed[n] = true;
1.433 + if (mwpfm.matching(n) == INVALID) continue;
1.434 + int num = 1;
1.435 + Node v = graph.target(mwpfm.matching(n));
1.436 + while (v != n) {
1.437 + processed[v] = true;
1.438 + ++num;
1.439 + v = graph.target(mwpfm.matching(v));
1.440 + }
1.441 + check(num == 2 || num % 2 == 1, "Wrong cycle size");
1.442 + check(allow_loops || num != 1, "Wrong cycle size");
1.443 + }
1.444 +
1.445 + return;
1.446 +}
1.447 +
1.448 +
1.449 +int main() {
1.450 +
1.451 + for (int i = 0; i < lgfn; ++i) {
1.452 + SmartGraph graph;
1.453 + SmartGraph::EdgeMap<int> weight(graph);
1.454 +
1.455 + istringstream lgfs(lgf[i]);
1.456 + graphReader(graph, lgfs).
1.457 + edgeMap("weight", weight).run();
1.458 +
1.459 + bool perfect_with_loops;
1.460 + {
1.461 + MaxFractionalMatching<SmartGraph> mfm(graph, true);
1.462 + mfm.run();
1.463 + checkFractionalMatching(graph, mfm, true);
1.464 + perfect_with_loops = mfm.matchingSize() == countNodes(graph);
1.465 + }
1.466 +
1.467 + bool perfect_without_loops;
1.468 + {
1.469 + MaxFractionalMatching<SmartGraph> mfm(graph, false);
1.470 + mfm.run();
1.471 + checkFractionalMatching(graph, mfm, false);
1.472 + perfect_without_loops = mfm.matchingSize() == countNodes(graph);
1.473 + }
1.474 +
1.475 + {
1.476 + MaxFractionalMatching<SmartGraph> mfm(graph, true);
1.477 + bool result = mfm.runPerfect();
1.478 + checkPerfectFractionalMatching(graph, mfm, result, true);
1.479 + check(result == perfect_with_loops, "Wrong perfect matching");
1.480 + }
1.481 +
1.482 + {
1.483 + MaxFractionalMatching<SmartGraph> mfm(graph, false);
1.484 + bool result = mfm.runPerfect();
1.485 + checkPerfectFractionalMatching(graph, mfm, result, false);
1.486 + check(result == perfect_without_loops, "Wrong perfect matching");
1.487 + }
1.488 +
1.489 + {
1.490 + MaxWeightedFractionalMatching<SmartGraph> mwfm(graph, weight, true);
1.491 + mwfm.run();
1.492 + checkWeightedFractionalMatching(graph, weight, mwfm, true);
1.493 + }
1.494 +
1.495 + {
1.496 + MaxWeightedFractionalMatching<SmartGraph> mwfm(graph, weight, false);
1.497 + mwfm.run();
1.498 + checkWeightedFractionalMatching(graph, weight, mwfm, false);
1.499 + }
1.500 +
1.501 + {
1.502 + MaxWeightedPerfectFractionalMatching<SmartGraph> mwpfm(graph, weight,
1.503 + true);
1.504 + bool perfect = mwpfm.run();
1.505 + check(perfect == (mwpfm.matchingSize() == countNodes(graph)),
1.506 + "Perfect matching found");
1.507 + check(perfect == perfect_with_loops, "Wrong perfect matching");
1.508 +
1.509 + if (perfect) {
1.510 + checkWeightedPerfectFractionalMatching(graph, weight, mwpfm, true);
1.511 + }
1.512 + }
1.513 +
1.514 + {
1.515 + MaxWeightedPerfectFractionalMatching<SmartGraph> mwpfm(graph, weight,
1.516 + false);
1.517 + bool perfect = mwpfm.run();
1.518 + check(perfect == (mwpfm.matchingSize() == countNodes(graph)),
1.519 + "Perfect matching found");
1.520 + check(perfect == perfect_without_loops, "Wrong perfect matching");
1.521 +
1.522 + if (perfect) {
1.523 + checkWeightedPerfectFractionalMatching(graph, weight, mwpfm, false);
1.524 + }
1.525 + }
1.526 +
1.527 + }
1.528 +
1.529 + return 0;
1.530 +}