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