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