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: * alpar@877: * Copyright (C) 2003-2010 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@327: #include deba@326: #include deba@326: #include deba@326: #include deba@326: kpeter@594: #include deba@327: #include kpeter@590: #include kpeter@590: #include deba@327: #include kpeter@590: #include deba@327: deba@326: #include "test_tools.h" deba@326: deba@326: using namespace std; deba@326: using namespace lemon; deba@326: deba@327: GRAPH_TYPEDEFS(SmartGraph); deba@327: deba@327: deba@327: const int lgfn = 3; deba@327: const std::string lgf[lgfn] = { deba@327: "@nodes\n" deba@327: "label\n" deba@327: "0\n" deba@327: "1\n" deba@327: "2\n" deba@327: "3\n" deba@327: "4\n" deba@327: "5\n" deba@327: "6\n" deba@327: "7\n" deba@327: "@edges\n" deba@327: " label weight\n" deba@327: "7 4 0 984\n" deba@327: "0 7 1 73\n" deba@327: "7 1 2 204\n" deba@327: "2 3 3 583\n" deba@327: "2 7 4 565\n" deba@327: "2 1 5 582\n" deba@327: "0 4 6 551\n" deba@327: "2 5 7 385\n" deba@327: "1 5 8 561\n" deba@327: "5 3 9 484\n" deba@327: "7 5 10 904\n" deba@327: "3 6 11 47\n" deba@327: "7 6 12 888\n" deba@327: "3 0 13 747\n" deba@327: "6 1 14 310\n", deba@327: deba@327: "@nodes\n" deba@327: "label\n" deba@327: "0\n" deba@327: "1\n" deba@327: "2\n" deba@327: "3\n" deba@327: "4\n" deba@327: "5\n" deba@327: "6\n" deba@327: "7\n" deba@327: "@edges\n" deba@327: " label weight\n" deba@327: "2 5 0 710\n" deba@327: "0 5 1 241\n" deba@327: "2 4 2 856\n" deba@327: "2 6 3 762\n" deba@327: "4 1 4 747\n" deba@327: "6 1 5 962\n" deba@327: "4 7 6 723\n" deba@327: "1 7 7 661\n" deba@327: "2 3 8 376\n" deba@327: "1 0 9 416\n" deba@327: "6 7 10 391\n", deba@327: deba@327: "@nodes\n" deba@327: "label\n" deba@327: "0\n" deba@327: "1\n" deba@327: "2\n" deba@327: "3\n" deba@327: "4\n" deba@327: "5\n" deba@327: "6\n" deba@327: "7\n" deba@327: "@edges\n" deba@327: " label weight\n" deba@327: "6 2 0 553\n" deba@327: "0 7 1 653\n" deba@327: "6 3 2 22\n" deba@327: "4 7 3 846\n" deba@327: "7 2 4 981\n" deba@327: "7 6 5 250\n" deba@327: "5 2 6 539\n", deba@327: }; deba@327: kpeter@590: void checkMaxMatchingCompile() kpeter@590: { kpeter@590: typedef concepts::Graph Graph; kpeter@590: typedef Graph::Node Node; kpeter@590: typedef Graph::Edge Edge; kpeter@590: typedef Graph::EdgeMap MatMap; kpeter@590: kpeter@590: Graph g; kpeter@590: Node n; kpeter@590: Edge e; kpeter@590: MatMap mat(g); kpeter@590: kpeter@590: MaxMatching mat_test(g); kpeter@590: const MaxMatching& kpeter@590: const_mat_test = mat_test; kpeter@590: kpeter@590: mat_test.init(); kpeter@590: mat_test.greedyInit(); kpeter@590: mat_test.matchingInit(mat); kpeter@590: mat_test.startSparse(); kpeter@590: mat_test.startDense(); kpeter@590: mat_test.run(); alpar@877: kpeter@590: const_mat_test.matchingSize(); kpeter@590: const_mat_test.matching(e); kpeter@590: const_mat_test.matching(n); kpeter@593: const MaxMatching::MatchingMap& mmap = kpeter@593: const_mat_test.matchingMap(); kpeter@593: e = mmap[n]; kpeter@590: const_mat_test.mate(n); kpeter@590: alpar@877: MaxMatching::Status stat = kpeter@593: const_mat_test.status(n); kpeter@593: const MaxMatching::StatusMap& smap = kpeter@593: const_mat_test.statusMap(); kpeter@593: stat = smap[n]; kpeter@590: const_mat_test.barrier(n); kpeter@590: } kpeter@590: kpeter@590: void checkMaxWeightedMatchingCompile() kpeter@590: { kpeter@590: typedef concepts::Graph Graph; kpeter@590: typedef Graph::Node Node; kpeter@590: typedef Graph::Edge Edge; kpeter@590: typedef Graph::EdgeMap WeightMap; kpeter@590: kpeter@590: Graph g; kpeter@590: Node n; kpeter@590: Edge e; kpeter@590: WeightMap w(g); kpeter@590: kpeter@590: MaxWeightedMatching mat_test(g, w); kpeter@590: const MaxWeightedMatching& kpeter@590: const_mat_test = mat_test; kpeter@590: kpeter@590: mat_test.init(); kpeter@590: mat_test.start(); kpeter@590: mat_test.run(); alpar@877: kpeter@593: const_mat_test.matchingWeight(); kpeter@590: const_mat_test.matchingSize(); kpeter@590: const_mat_test.matching(e); kpeter@590: const_mat_test.matching(n); kpeter@593: const MaxWeightedMatching::MatchingMap& mmap = kpeter@593: const_mat_test.matchingMap(); kpeter@593: e = mmap[n]; kpeter@590: const_mat_test.mate(n); alpar@877: kpeter@590: int k = 0; kpeter@590: const_mat_test.dualValue(); kpeter@590: const_mat_test.nodeValue(n); kpeter@590: const_mat_test.blossomNum(); kpeter@590: const_mat_test.blossomSize(k); kpeter@590: const_mat_test.blossomValue(k); kpeter@590: } kpeter@590: kpeter@590: void checkMaxWeightedPerfectMatchingCompile() kpeter@590: { kpeter@590: typedef concepts::Graph Graph; kpeter@590: typedef Graph::Node Node; kpeter@590: typedef Graph::Edge Edge; kpeter@590: typedef Graph::EdgeMap WeightMap; kpeter@590: kpeter@590: Graph g; kpeter@590: Node n; kpeter@590: Edge e; kpeter@590: WeightMap w(g); kpeter@590: kpeter@590: MaxWeightedPerfectMatching mat_test(g, w); kpeter@590: const MaxWeightedPerfectMatching& kpeter@590: const_mat_test = mat_test; kpeter@590: kpeter@590: mat_test.init(); kpeter@590: mat_test.start(); kpeter@590: mat_test.run(); alpar@877: kpeter@593: const_mat_test.matchingWeight(); kpeter@590: const_mat_test.matching(e); kpeter@590: const_mat_test.matching(n); kpeter@593: const MaxWeightedPerfectMatching::MatchingMap& mmap = kpeter@593: const_mat_test.matchingMap(); kpeter@593: e = mmap[n]; kpeter@590: const_mat_test.mate(n); alpar@877: kpeter@590: int k = 0; kpeter@590: const_mat_test.dualValue(); kpeter@590: const_mat_test.nodeValue(n); kpeter@590: const_mat_test.blossomNum(); kpeter@590: const_mat_test.blossomSize(k); kpeter@590: const_mat_test.blossomValue(k); kpeter@590: } kpeter@590: deba@327: void checkMatching(const SmartGraph& graph, deba@327: const MaxMatching& mm) { deba@327: int num = 0; deba@327: deba@327: IntNodeMap comp_index(graph); deba@327: UnionFind comp(comp_index); deba@327: deba@327: int barrier_num = 0; deba@327: deba@327: for (NodeIt n(graph); n != INVALID; ++n) { kpeter@593: check(mm.status(n) == MaxMatching::EVEN || deba@327: mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition"); kpeter@593: if (mm.status(n) == MaxMatching::ODD) { deba@327: ++barrier_num; deba@327: } else { deba@327: comp.insert(n); deba@327: } deba@327: } deba@327: deba@327: for (EdgeIt e(graph); e != INVALID; ++e) { deba@327: if (mm.matching(e)) { deba@327: check(e == mm.matching(graph.u(e)), "Wrong matching"); deba@327: check(e == mm.matching(graph.v(e)), "Wrong matching"); deba@327: ++num; deba@327: } kpeter@593: check(mm.status(graph.u(e)) != MaxMatching::EVEN || kpeter@593: mm.status(graph.v(e)) != MaxMatching::MATCHED, deba@327: "Wrong Gallai-Edmonds decomposition"); deba@327: kpeter@593: check(mm.status(graph.v(e)) != MaxMatching::EVEN || kpeter@593: mm.status(graph.u(e)) != MaxMatching::MATCHED, deba@327: "Wrong Gallai-Edmonds decomposition"); deba@327: kpeter@593: if (mm.status(graph.u(e)) != MaxMatching::ODD && kpeter@593: mm.status(graph.v(e)) != MaxMatching::ODD) { deba@327: comp.join(graph.u(e), graph.v(e)); deba@327: } deba@327: } deba@327: deba@327: std::set comp_root; deba@327: int odd_comp_num = 0; deba@327: for (NodeIt n(graph); n != INVALID; ++n) { kpeter@593: if (mm.status(n) != MaxMatching::ODD) { deba@327: int root = comp.find(n); deba@327: if (comp_root.find(root) == comp_root.end()) { deba@327: comp_root.insert(root); deba@327: if (comp.size(n) % 2 == 1) { deba@327: ++odd_comp_num; deba@327: } deba@327: } deba@327: } deba@327: } deba@327: deba@327: check(mm.matchingSize() == num, "Wrong matching"); deba@327: check(2 * num == countNodes(graph) - (odd_comp_num - barrier_num), deba@327: "Wrong matching"); deba@327: return; deba@327: } deba@327: deba@327: void checkWeightedMatching(const SmartGraph& graph, deba@327: const SmartGraph::EdgeMap& weight, deba@327: const MaxWeightedMatching& mwm) { deba@327: for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { deba@327: if (graph.u(e) == graph.v(e)) continue; deba@327: int rw = mwm.nodeValue(graph.u(e)) + mwm.nodeValue(graph.v(e)); deba@327: deba@327: for (int i = 0; i < mwm.blossomNum(); ++i) { deba@327: bool s = false, t = false; deba@327: for (MaxWeightedMatching::BlossomIt n(mwm, i); deba@327: n != INVALID; ++n) { deba@327: if (graph.u(e) == n) s = true; deba@327: if (graph.v(e) == n) t = true; deba@327: } deba@327: if (s == true && t == true) { deba@327: rw += mwm.blossomValue(i); deba@327: } deba@327: } deba@327: rw -= weight[e] * mwm.dualScale; deba@327: deba@327: check(rw >= 0, "Negative reduced weight"); deba@327: check(rw == 0 || !mwm.matching(e), deba@327: "Non-zero reduced weight on matching edge"); deba@327: } deba@327: deba@327: int pv = 0; deba@327: for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { deba@327: if (mwm.matching(n) != INVALID) { deba@327: check(mwm.nodeValue(n) >= 0, "Invalid node value"); deba@327: pv += weight[mwm.matching(n)]; deba@327: SmartGraph::Node o = graph.target(mwm.matching(n)); deba@327: check(mwm.mate(n) == o, "Invalid matching"); deba@327: check(mwm.matching(n) == graph.oppositeArc(mwm.matching(o)), deba@327: "Invalid matching"); deba@327: } else { deba@327: check(mwm.mate(n) == INVALID, "Invalid matching"); deba@327: check(mwm.nodeValue(n) == 0, "Invalid matching"); deba@327: } deba@327: } deba@327: deba@327: int dv = 0; deba@327: for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { deba@327: dv += mwm.nodeValue(n); deba@327: } deba@327: deba@327: for (int i = 0; i < mwm.blossomNum(); ++i) { deba@327: check(mwm.blossomValue(i) >= 0, "Invalid blossom value"); deba@327: check(mwm.blossomSize(i) % 2 == 1, "Even blossom size"); deba@327: dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2); deba@327: } deba@327: deba@327: check(pv * mwm.dualScale == dv * 2, "Wrong duality"); deba@327: deba@327: return; deba@327: } deba@327: deba@327: void checkWeightedPerfectMatching(const SmartGraph& graph, deba@327: const SmartGraph::EdgeMap& weight, deba@327: const MaxWeightedPerfectMatching& mwpm) { deba@327: for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { deba@327: if (graph.u(e) == graph.v(e)) continue; deba@327: int rw = mwpm.nodeValue(graph.u(e)) + mwpm.nodeValue(graph.v(e)); deba@327: deba@327: for (int i = 0; i < mwpm.blossomNum(); ++i) { deba@327: bool s = false, t = false; deba@327: for (MaxWeightedPerfectMatching::BlossomIt n(mwpm, i); deba@327: n != INVALID; ++n) { deba@327: if (graph.u(e) == n) s = true; deba@327: if (graph.v(e) == n) t = true; deba@327: } deba@327: if (s == true && t == true) { deba@327: rw += mwpm.blossomValue(i); deba@327: } deba@327: } deba@327: rw -= weight[e] * mwpm.dualScale; deba@327: deba@327: check(rw >= 0, "Negative reduced weight"); deba@327: check(rw == 0 || !mwpm.matching(e), deba@327: "Non-zero reduced weight on matching edge"); deba@327: } deba@327: deba@327: int pv = 0; deba@327: for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { deba@327: check(mwpm.matching(n) != INVALID, "Non perfect"); deba@327: pv += weight[mwpm.matching(n)]; deba@327: SmartGraph::Node o = graph.target(mwpm.matching(n)); deba@327: check(mwpm.mate(n) == o, "Invalid matching"); deba@327: check(mwpm.matching(n) == graph.oppositeArc(mwpm.matching(o)), deba@327: "Invalid matching"); deba@327: } deba@327: deba@327: int dv = 0; deba@327: for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { deba@327: dv += mwpm.nodeValue(n); deba@327: } deba@327: deba@327: for (int i = 0; i < mwpm.blossomNum(); ++i) { deba@327: check(mwpm.blossomValue(i) >= 0, "Invalid blossom value"); deba@327: check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size"); deba@327: dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2); deba@327: } deba@327: deba@327: check(pv * mwpm.dualScale == dv * 2, "Wrong duality"); deba@327: deba@327: return; deba@327: } deba@327: deba@327: deba@326: int main() { deba@326: deba@327: for (int i = 0; i < lgfn; ++i) { deba@327: SmartGraph graph; deba@327: SmartGraph::EdgeMap weight(graph); deba@326: deba@327: istringstream lgfs(lgf[i]); deba@327: graphReader(graph, lgfs). deba@327: edgeMap("weight", weight).run(); deba@326: deba@870: bool perfect; deba@870: { deba@870: MaxMatching mm(graph); deba@870: mm.run(); deba@870: checkMatching(graph, mm); deba@870: perfect = 2 * mm.matchingSize() == countNodes(graph); deba@870: } deba@326: deba@870: { deba@870: MaxWeightedMatching mwm(graph, weight); deba@870: mwm.run(); deba@870: checkWeightedMatching(graph, weight, mwm); deba@870: } deba@326: deba@870: { deba@870: MaxWeightedMatching mwm(graph, weight); deba@870: mwm.init(); deba@870: mwm.start(); deba@870: checkWeightedMatching(graph, weight, mwm); deba@870: } deba@326: deba@870: { deba@870: MaxWeightedPerfectMatching mwpm(graph, weight); deba@870: bool result = mwpm.run(); alpar@877: deba@870: check(result == perfect, "Perfect matching found"); deba@870: if (perfect) { deba@870: checkWeightedPerfectMatching(graph, weight, mwpm); deba@870: } deba@870: } deba@326: deba@870: { deba@870: MaxWeightedPerfectMatching mwpm(graph, weight); deba@870: mwpm.init(); deba@870: bool result = mwpm.start(); alpar@877: deba@870: check(result == perfect, "Perfect matching found"); deba@870: if (perfect) { deba@870: checkWeightedPerfectMatching(graph, weight, mwpm); deba@870: } deba@326: } deba@326: } deba@326: deba@326: return 0; deba@326: }