diff -r 6dbd5184c6a9 -r 64ad48007fb2 test/max_weighted_matching_test.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/max_weighted_matching_test.cc Mon Oct 13 13:56:00 2008 +0200 @@ -0,0 +1,250 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2008 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#include +#include +#include +#include +#include +#include + +#include "test_tools.h" +#include +#include +#include + +using namespace std; +using namespace lemon; + +GRAPH_TYPEDEFS(SmartGraph); + +const int lgfn = 3; +const std::string lgf[lgfn] = { + "@nodes\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "6\n" + "7\n" + "@edges\n" + "label weight\n" + "7 4 0 984\n" + "0 7 1 73\n" + "7 1 2 204\n" + "2 3 3 583\n" + "2 7 4 565\n" + "2 1 5 582\n" + "0 4 6 551\n" + "2 5 7 385\n" + "1 5 8 561\n" + "5 3 9 484\n" + "7 5 10 904\n" + "3 6 11 47\n" + "7 6 12 888\n" + "3 0 13 747\n" + "6 1 14 310\n", + + "@nodes\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "6\n" + "7\n" + "@edges\n" + "label weight\n" + "2 5 0 710\n" + "0 5 1 241\n" + "2 4 2 856\n" + "2 6 3 762\n" + "4 1 4 747\n" + "6 1 5 962\n" + "4 7 6 723\n" + "1 7 7 661\n" + "2 3 8 376\n" + "1 0 9 416\n" + "6 7 10 391\n", + + "@nodes\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "6\n" + "7\n" + "@edges\n" + "label weight\n" + "6 2 0 553\n" + "0 7 1 653\n" + "6 3 2 22\n" + "4 7 3 846\n" + "7 2 4 981\n" + "7 6 5 250\n" + "5 2 6 539\n" +}; + +void checkMatching(const SmartGraph& graph, + const SmartGraph::EdgeMap& weight, + const MaxWeightedMatching& mwm) { + for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { + if (graph.u(e) == graph.v(e)) continue; + int rw = + mwm.nodeValue(graph.u(e)) + mwm.nodeValue(graph.v(e)); + + for (int i = 0; i < mwm.blossomNum(); ++i) { + bool s = false, t = false; + for (MaxWeightedMatching::BlossomIt n(mwm, i); + n != INVALID; ++n) { + if (graph.u(e) == n) s = true; + if (graph.v(e) == n) t = true; + } + if (s == true && t == true) { + rw += mwm.blossomValue(i); + } + } + rw -= weight[e] * mwm.dualScale; + + check(rw >= 0, "Negative reduced weight"); + check(rw == 0 || !mwm.matching(e), + "Non-zero reduced weight on matching arc"); + } + + int pv = 0; + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { + if (mwm.matching(n) != INVALID) { + check(mwm.nodeValue(n) >= 0, "Invalid node value"); + pv += weight[mwm.matching(n)]; + SmartGraph::Node o = graph.target(mwm.matching(n)); + check(mwm.mate(n) == o, "Invalid matching"); + check(mwm.matching(n) == graph.oppositeArc(mwm.matching(o)), + "Invalid matching"); + } else { + check(mwm.mate(n) == INVALID, "Invalid matching"); + check(mwm.nodeValue(n) == 0, "Invalid matching"); + } + } + + int dv = 0; + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { + dv += mwm.nodeValue(n); + } + + for (int i = 0; i < mwm.blossomNum(); ++i) { + check(mwm.blossomValue(i) >= 0, "Invalid blossom value"); + check(mwm.blossomSize(i) % 2 == 1, "Even blossom size"); + dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2); + } + + check(pv * mwm.dualScale == dv * 2, "Wrong duality"); + + return; +} + +void checkPerfectMatching(const SmartGraph& graph, + const SmartGraph::EdgeMap& weight, + const MaxWeightedPerfectMatching& mwpm) { + for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { + if (graph.u(e) == graph.v(e)) continue; + int rw = + mwpm.nodeValue(graph.u(e)) + mwpm.nodeValue(graph.v(e)); + + for (int i = 0; i < mwpm.blossomNum(); ++i) { + bool s = false, t = false; + for (MaxWeightedPerfectMatching::BlossomIt n(mwpm, i); + n != INVALID; ++n) { + if (graph.u(e) == n) s = true; + if (graph.v(e) == n) t = true; + } + if (s == true && t == true) { + rw += mwpm.blossomValue(i); + } + } + rw -= weight[e] * mwpm.dualScale; + + check(rw >= 0, "Negative reduced weight"); + check(rw == 0 || !mwpm.matching(e), + "Non-zero reduced weight on matching arc"); + } + + int pv = 0; + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { + check(mwpm.matching(n) != INVALID, "Non perfect"); + pv += weight[mwpm.matching(n)]; + SmartGraph::Node o = graph.target(mwpm.matching(n)); + check(mwpm.mate(n) == o, "Invalid matching"); + check(mwpm.matching(n) == graph.oppositeArc(mwpm.matching(o)), + "Invalid matching"); + } + + int dv = 0; + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { + dv += mwpm.nodeValue(n); + } + + for (int i = 0; i < mwpm.blossomNum(); ++i) { + check(mwpm.blossomValue(i) >= 0, "Invalid blossom value"); + check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size"); + dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2); + } + + check(pv * mwpm.dualScale == dv * 2, "Wrong duality"); + + return; +} + + +int main() { + + for (int i = 0; i < lgfn; ++i) { + SmartGraph graph; + SmartGraph::EdgeMap weight(graph); + + istringstream lgfs(lgf[i]); + graphReader(graph, lgfs). + edgeMap("weight", weight).run(); + + MaxWeightedMatching mwm(graph, weight); + mwm.run(); + checkMatching(graph, weight, mwm); + + MaxMatching mm(graph); + mm.run(); + + MaxWeightedPerfectMatching mwpm(graph, weight); + bool perfect = mwpm.run(); + + check(perfect == (mm.size() * 2 == countNodes(graph)), + "Perfect matching found"); + + if (perfect) { + checkPerfectMatching(graph, weight, mwpm); + } + } + + return 0; +}