diff -r a3ba22ebccc6 -r 88b81ec599ed test/max_weighted_matching_test.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/max_weighted_matching_test.cc Sat Dec 29 15:11:41 2007 +0000 @@ -0,0 +1,253 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * 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 + +UGRAPH_TYPEDEFS(SmartUGraph); + +using namespace std; +using namespace lemon; + +const int lgfn = 3; +const std::string lgf[lgfn] = { + "@nodeset\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "6\n" + "7\n" + "@uedgeset\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" + "@end\n", + + "@nodeset\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "6\n" + "7\n" + "@uedgeset\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" + "@end\n", + + "@nodeset\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "6\n" + "7\n" + "@uedgeset\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" + "@end\n" +}; + +void checkMatching(const SmartUGraph& ugraph, + const SmartUGraph::UEdgeMap& weight, + const MaxWeightedMatching& mwm) { + for (SmartUGraph::UEdgeIt e(ugraph); e != INVALID; ++e) { + if (ugraph.source(e) == ugraph.target(e)) continue; + int rw = + mwm.nodeValue(ugraph.source(e)) + mwm.nodeValue(ugraph.target(e)); + + for (int i = 0; i < mwm.blossomNum(); ++i) { + bool s = false, t = false; + for (MaxWeightedMatching::BlossomIt n(mwm, i); + n != INVALID; ++n) { + if (ugraph.source(e) == n) s = true; + if (ugraph.target(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 edge"); + } + + int pv = 0; + for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) { + if (mwm.matching(n) != INVALID) { + check(mwm.nodeValue(n) >= 0, "Invalid node value"); + pv += weight[mwm.matching(n)]; + SmartUGraph::Node o = ugraph.target(mwm.matching(n)); + check(mwm.mate(n) == o, "Invalid matching"); + check(mwm.matching(n) == ugraph.oppositeEdge(mwm.matching(o)), + "Invalid matching"); + } else { + check(mwm.mate(n) == INVALID, "Invalid matching"); + check(mwm.nodeValue(n) == 0, "Invalid matching"); + } + } + + int dv = 0; + for (SmartUGraph::NodeIt n(ugraph); 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 SmartUGraph& ugraph, + const SmartUGraph::UEdgeMap& weight, + const MaxWeightedPerfectMatching& mwpm) { + for (SmartUGraph::UEdgeIt e(ugraph); e != INVALID; ++e) { + if (ugraph.source(e) == ugraph.target(e)) continue; + int rw = + mwpm.nodeValue(ugraph.source(e)) + mwpm.nodeValue(ugraph.target(e)); + + for (int i = 0; i < mwpm.blossomNum(); ++i) { + bool s = false, t = false; + for (MaxWeightedPerfectMatching::BlossomIt n(mwpm, i); + n != INVALID; ++n) { + if (ugraph.source(e) == n) s = true; + if (ugraph.target(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 edge"); + } + + int pv = 0; + for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) { + check(mwpm.matching(n) != INVALID, "Non perfect"); + pv += weight[mwpm.matching(n)]; + SmartUGraph::Node o = ugraph.target(mwpm.matching(n)); + check(mwpm.mate(n) == o, "Invalid matching"); + check(mwpm.matching(n) == ugraph.oppositeEdge(mwpm.matching(o)), + "Invalid matching"); + } + + int dv = 0; + for (SmartUGraph::NodeIt n(ugraph); 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) { + SmartUGraph ugraph; + SmartUGraph::UEdgeMap weight(ugraph); + + istringstream lgfs(lgf[i]); + UGraphReader(lgfs, ugraph). + readUEdgeMap("weight", weight).run(); + + MaxWeightedMatching mwm(ugraph, weight); + mwm.run(); + checkMatching(ugraph, weight, mwm); + + MaxMatching mm(ugraph); + mm.run(); + + MaxWeightedPerfectMatching mwpm(ugraph, weight); + bool perfect = mwpm.run(); + + check(perfect == (mm.size() * 2 == countNodes(ugraph)), + "Perfect matching found"); + + if (perfect) { + checkPerfectMatching(ugraph, weight, mwpm); + } + } + + return 0; +}