deba@2549: /* -*- C++ -*- deba@2549: * deba@2549: * This file is a part of LEMON, a generic C++ optimization library deba@2549: * alpar@2553: * Copyright (C) 2003-2008 deba@2549: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@2549: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@2549: * deba@2549: * Permission to use, modify and distribute this software is granted deba@2549: * provided that this copyright notice appears in all copies. For deba@2549: * precise terms see the accompanying LICENSE file. deba@2549: * deba@2549: * This software is provided "AS IS" with no warranty of any kind, deba@2549: * express or implied, and with no claim as to its suitability for any deba@2549: * purpose. deba@2549: * deba@2549: */ deba@2549: deba@2549: #include deba@2549: #include deba@2549: #include deba@2549: #include deba@2549: #include deba@2549: #include deba@2549: deba@2549: #include "test_tools.h" deba@2549: #include deba@2549: #include deba@2549: #include deba@2549: deba@2549: UGRAPH_TYPEDEFS(SmartUGraph); deba@2549: deba@2549: using namespace std; deba@2549: using namespace lemon; deba@2549: deba@2549: const int lgfn = 3; deba@2549: const std::string lgf[lgfn] = { deba@2549: "@nodeset\n" deba@2549: "label\n" deba@2549: "0\n" deba@2549: "1\n" deba@2549: "2\n" deba@2549: "3\n" deba@2549: "4\n" deba@2549: "5\n" deba@2549: "6\n" deba@2549: "7\n" deba@2549: "@uedgeset\n" deba@2549: "label weight\n" deba@2549: "7 4 0 984\n" deba@2549: "0 7 1 73\n" deba@2549: "7 1 2 204\n" deba@2549: "2 3 3 583\n" deba@2549: "2 7 4 565\n" deba@2549: "2 1 5 582\n" deba@2549: "0 4 6 551\n" deba@2549: "2 5 7 385\n" deba@2549: "1 5 8 561\n" deba@2549: "5 3 9 484\n" deba@2549: "7 5 10 904\n" deba@2549: "3 6 11 47\n" deba@2549: "7 6 12 888\n" deba@2549: "3 0 13 747\n" deba@2549: "6 1 14 310\n" deba@2549: "@end\n", deba@2549: deba@2549: "@nodeset\n" deba@2549: "label\n" deba@2549: "0\n" deba@2549: "1\n" deba@2549: "2\n" deba@2549: "3\n" deba@2549: "4\n" deba@2549: "5\n" deba@2549: "6\n" deba@2549: "7\n" deba@2549: "@uedgeset\n" deba@2549: "label weight\n" deba@2549: "2 5 0 710\n" deba@2549: "0 5 1 241\n" deba@2549: "2 4 2 856\n" deba@2549: "2 6 3 762\n" deba@2549: "4 1 4 747\n" deba@2549: "6 1 5 962\n" deba@2549: "4 7 6 723\n" deba@2549: "1 7 7 661\n" deba@2549: "2 3 8 376\n" deba@2549: "1 0 9 416\n" deba@2549: "6 7 10 391\n" deba@2549: "@end\n", deba@2549: deba@2549: "@nodeset\n" deba@2549: "label\n" deba@2549: "0\n" deba@2549: "1\n" deba@2549: "2\n" deba@2549: "3\n" deba@2549: "4\n" deba@2549: "5\n" deba@2549: "6\n" deba@2549: "7\n" deba@2549: "@uedgeset\n" deba@2549: "label weight\n" deba@2549: "6 2 0 553\n" deba@2549: "0 7 1 653\n" deba@2549: "6 3 2 22\n" deba@2549: "4 7 3 846\n" deba@2549: "7 2 4 981\n" deba@2549: "7 6 5 250\n" deba@2549: "5 2 6 539\n" deba@2549: "@end\n" deba@2549: }; deba@2549: deba@2549: void checkMatching(const SmartUGraph& ugraph, deba@2549: const SmartUGraph::UEdgeMap& weight, deba@2549: const MaxWeightedMatching& mwm) { deba@2549: for (SmartUGraph::UEdgeIt e(ugraph); e != INVALID; ++e) { deba@2549: if (ugraph.source(e) == ugraph.target(e)) continue; deba@2549: int rw = deba@2549: mwm.nodeValue(ugraph.source(e)) + mwm.nodeValue(ugraph.target(e)); deba@2549: deba@2549: for (int i = 0; i < mwm.blossomNum(); ++i) { deba@2549: bool s = false, t = false; deba@2549: for (MaxWeightedMatching::BlossomIt n(mwm, i); deba@2549: n != INVALID; ++n) { deba@2549: if (ugraph.source(e) == n) s = true; deba@2549: if (ugraph.target(e) == n) t = true; deba@2549: } deba@2549: if (s == true && t == true) { deba@2549: rw += mwm.blossomValue(i); deba@2549: } deba@2549: } deba@2549: rw -= weight[e] * mwm.dualScale; deba@2549: deba@2549: check(rw >= 0, "Negative reduced weight"); deba@2549: check(rw == 0 || !mwm.matching(e), deba@2549: "Non-zero reduced weight on matching edge"); deba@2549: } deba@2549: deba@2549: int pv = 0; deba@2549: for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) { deba@2549: if (mwm.matching(n) != INVALID) { deba@2549: check(mwm.nodeValue(n) >= 0, "Invalid node value"); deba@2549: pv += weight[mwm.matching(n)]; deba@2549: SmartUGraph::Node o = ugraph.target(mwm.matching(n)); deba@2549: check(mwm.mate(n) == o, "Invalid matching"); deba@2549: check(mwm.matching(n) == ugraph.oppositeEdge(mwm.matching(o)), deba@2549: "Invalid matching"); deba@2549: } else { deba@2549: check(mwm.mate(n) == INVALID, "Invalid matching"); deba@2549: check(mwm.nodeValue(n) == 0, "Invalid matching"); deba@2549: } deba@2549: } deba@2549: deba@2549: int dv = 0; deba@2549: for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) { deba@2549: dv += mwm.nodeValue(n); deba@2549: } deba@2549: deba@2549: for (int i = 0; i < mwm.blossomNum(); ++i) { deba@2549: check(mwm.blossomValue(i) >= 0, "Invalid blossom value"); deba@2549: check(mwm.blossomSize(i) % 2 == 1, "Even blossom size"); deba@2549: dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2); deba@2549: } deba@2549: deba@2549: check(pv * mwm.dualScale == dv * 2, "Wrong duality"); deba@2549: deba@2549: return; deba@2549: } deba@2549: deba@2549: void checkPerfectMatching(const SmartUGraph& ugraph, deba@2549: const SmartUGraph::UEdgeMap& weight, deba@2549: const MaxWeightedPerfectMatching& mwpm) { deba@2549: for (SmartUGraph::UEdgeIt e(ugraph); e != INVALID; ++e) { deba@2549: if (ugraph.source(e) == ugraph.target(e)) continue; deba@2549: int rw = deba@2549: mwpm.nodeValue(ugraph.source(e)) + mwpm.nodeValue(ugraph.target(e)); deba@2549: deba@2549: for (int i = 0; i < mwpm.blossomNum(); ++i) { deba@2549: bool s = false, t = false; deba@2549: for (MaxWeightedPerfectMatching::BlossomIt n(mwpm, i); deba@2549: n != INVALID; ++n) { deba@2549: if (ugraph.source(e) == n) s = true; deba@2549: if (ugraph.target(e) == n) t = true; deba@2549: } deba@2549: if (s == true && t == true) { deba@2549: rw += mwpm.blossomValue(i); deba@2549: } deba@2549: } deba@2549: rw -= weight[e] * mwpm.dualScale; deba@2549: deba@2549: check(rw >= 0, "Negative reduced weight"); deba@2549: check(rw == 0 || !mwpm.matching(e), deba@2549: "Non-zero reduced weight on matching edge"); deba@2549: } deba@2549: deba@2549: int pv = 0; deba@2549: for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) { deba@2549: check(mwpm.matching(n) != INVALID, "Non perfect"); deba@2549: pv += weight[mwpm.matching(n)]; deba@2549: SmartUGraph::Node o = ugraph.target(mwpm.matching(n)); deba@2549: check(mwpm.mate(n) == o, "Invalid matching"); deba@2549: check(mwpm.matching(n) == ugraph.oppositeEdge(mwpm.matching(o)), deba@2549: "Invalid matching"); deba@2549: } deba@2549: deba@2549: int dv = 0; deba@2549: for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) { deba@2549: dv += mwpm.nodeValue(n); deba@2549: } deba@2549: deba@2549: for (int i = 0; i < mwpm.blossomNum(); ++i) { deba@2549: check(mwpm.blossomValue(i) >= 0, "Invalid blossom value"); deba@2549: check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size"); deba@2549: dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2); deba@2549: } deba@2549: deba@2549: check(pv * mwpm.dualScale == dv * 2, "Wrong duality"); deba@2549: deba@2549: return; deba@2549: } deba@2549: deba@2549: deba@2549: int main() { deba@2549: deba@2549: for (int i = 0; i < lgfn; ++i) { deba@2549: SmartUGraph ugraph; deba@2549: SmartUGraph::UEdgeMap weight(ugraph); deba@2549: deba@2549: istringstream lgfs(lgf[i]); deba@2549: UGraphReader(lgfs, ugraph). deba@2549: readUEdgeMap("weight", weight).run(); deba@2549: deba@2549: MaxWeightedMatching mwm(ugraph, weight); deba@2549: mwm.run(); deba@2549: checkMatching(ugraph, weight, mwm); deba@2549: deba@2549: MaxMatching mm(ugraph); deba@2549: mm.run(); deba@2549: deba@2549: MaxWeightedPerfectMatching mwpm(ugraph, weight); deba@2549: bool perfect = mwpm.run(); deba@2549: deba@2549: check(perfect == (mm.size() * 2 == countNodes(ugraph)), deba@2549: "Perfect matching found"); deba@2549: deba@2549: if (perfect) { deba@2549: checkPerfectMatching(ugraph, weight, mwpm); deba@2549: } deba@2549: } deba@2549: deba@2549: return 0; deba@2549: }