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: * alpar@463: * Copyright (C) 2003-2009 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: kpeter@641: #include deba@339: #include kpeter@637: #include kpeter@637: #include deba@339: #include kpeter@637: #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: kpeter@637: void checkMaxMatchingCompile() kpeter@637: { kpeter@637: typedef concepts::Graph Graph; kpeter@637: typedef Graph::Node Node; kpeter@637: typedef Graph::Edge Edge; kpeter@637: typedef Graph::EdgeMap MatMap; kpeter@637: kpeter@637: Graph g; kpeter@637: Node n; kpeter@637: Edge e; kpeter@637: MatMap mat(g); kpeter@637: kpeter@637: MaxMatching mat_test(g); kpeter@637: const MaxMatching& kpeter@637: const_mat_test = mat_test; kpeter@637: kpeter@637: mat_test.init(); kpeter@637: mat_test.greedyInit(); kpeter@637: mat_test.matchingInit(mat); kpeter@637: mat_test.startSparse(); kpeter@637: mat_test.startDense(); kpeter@637: mat_test.run(); kpeter@637: kpeter@637: const_mat_test.matchingSize(); kpeter@637: const_mat_test.matching(e); kpeter@637: const_mat_test.matching(n); kpeter@640: const MaxMatching::MatchingMap& mmap = kpeter@640: const_mat_test.matchingMap(); kpeter@640: e = mmap[n]; kpeter@637: const_mat_test.mate(n); kpeter@637: kpeter@637: MaxMatching::Status stat = kpeter@640: const_mat_test.status(n); alpar@1171: ignore_unused_variable_warning(stat); kpeter@640: const MaxMatching::StatusMap& smap = kpeter@640: const_mat_test.statusMap(); kpeter@640: stat = smap[n]; kpeter@637: const_mat_test.barrier(n); kpeter@637: } kpeter@637: kpeter@637: void checkMaxWeightedMatchingCompile() kpeter@637: { kpeter@637: typedef concepts::Graph Graph; kpeter@637: typedef Graph::Node Node; kpeter@637: typedef Graph::Edge Edge; kpeter@637: typedef Graph::EdgeMap WeightMap; kpeter@637: kpeter@637: Graph g; kpeter@637: Node n; kpeter@637: Edge e; kpeter@637: WeightMap w(g); kpeter@637: kpeter@637: MaxWeightedMatching mat_test(g, w); kpeter@637: const MaxWeightedMatching& kpeter@637: const_mat_test = mat_test; kpeter@637: kpeter@637: mat_test.init(); kpeter@637: mat_test.start(); kpeter@637: mat_test.run(); kpeter@637: kpeter@640: const_mat_test.matchingWeight(); kpeter@637: const_mat_test.matchingSize(); kpeter@637: const_mat_test.matching(e); kpeter@637: const_mat_test.matching(n); kpeter@640: const MaxWeightedMatching::MatchingMap& mmap = kpeter@640: const_mat_test.matchingMap(); kpeter@640: e = mmap[n]; kpeter@637: const_mat_test.mate(n); kpeter@637: kpeter@637: int k = 0; kpeter@637: const_mat_test.dualValue(); kpeter@637: const_mat_test.nodeValue(n); kpeter@637: const_mat_test.blossomNum(); kpeter@637: const_mat_test.blossomSize(k); kpeter@637: const_mat_test.blossomValue(k); kpeter@637: } kpeter@637: kpeter@637: void checkMaxWeightedPerfectMatchingCompile() kpeter@637: { kpeter@637: typedef concepts::Graph Graph; kpeter@637: typedef Graph::Node Node; kpeter@637: typedef Graph::Edge Edge; kpeter@637: typedef Graph::EdgeMap WeightMap; kpeter@637: kpeter@637: Graph g; kpeter@637: Node n; kpeter@637: Edge e; kpeter@637: WeightMap w(g); kpeter@637: kpeter@637: MaxWeightedPerfectMatching mat_test(g, w); kpeter@637: const MaxWeightedPerfectMatching& kpeter@637: const_mat_test = mat_test; kpeter@637: kpeter@637: mat_test.init(); kpeter@637: mat_test.start(); kpeter@637: mat_test.run(); kpeter@637: kpeter@640: const_mat_test.matchingWeight(); kpeter@637: const_mat_test.matching(e); kpeter@637: const_mat_test.matching(n); kpeter@640: const MaxWeightedPerfectMatching::MatchingMap& mmap = kpeter@640: const_mat_test.matchingMap(); kpeter@640: e = mmap[n]; kpeter@637: const_mat_test.mate(n); kpeter@637: kpeter@637: int k = 0; kpeter@637: const_mat_test.dualValue(); kpeter@637: const_mat_test.nodeValue(n); kpeter@637: const_mat_test.blossomNum(); kpeter@637: const_mat_test.blossomSize(k); kpeter@637: const_mat_test.blossomValue(k); kpeter@637: } kpeter@637: 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) { kpeter@640: check(mm.status(n) == MaxMatching::EVEN || deba@339: mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition"); kpeter@640: if (mm.status(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: } kpeter@640: check(mm.status(graph.u(e)) != MaxMatching::EVEN || kpeter@640: mm.status(graph.v(e)) != MaxMatching::MATCHED, deba@339: "Wrong Gallai-Edmonds decomposition"); deba@339: kpeter@640: check(mm.status(graph.v(e)) != MaxMatching::EVEN || kpeter@640: mm.status(graph.u(e)) != MaxMatching::MATCHED, deba@339: "Wrong Gallai-Edmonds decomposition"); deba@339: kpeter@640: if (mm.status(graph.u(e)) != MaxMatching::ODD && kpeter@640: mm.status(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) { kpeter@640: if (mm.status(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: }