deba@501: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@501: * deba@501: * This file is a part of LEMON, a generic C++ optimization library. deba@501: * deba@501: * Copyright (C) 2003-2008 deba@501: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@501: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@501: * deba@501: * Permission to use, modify and distribute this software is granted deba@501: * provided that this copyright notice appears in all copies. For deba@501: * precise terms see the accompanying LICENSE file. deba@501: * deba@501: * This software is provided "AS IS" with no warranty of any kind, deba@501: * express or implied, and with no claim as to its suitability for any deba@501: * purpose. deba@501: * deba@501: */ deba@501: deba@501: #include deba@501: #include deba@501: #include deba@501: #include deba@501: deba@501: #include deba@501: #include deba@501: #include kpeter@625: #include deba@501: deba@501: #include "test_tools.h" deba@501: deba@501: using namespace lemon; deba@501: using namespace std; deba@501: deba@501: const char test_lgf[] = deba@501: "@nodes\n" deba@501: "label\n" deba@501: "0\n" deba@501: "1\n" deba@501: "2\n" deba@501: "3\n" deba@501: "4\n" deba@501: "5\n" deba@501: "6\n" deba@501: "7\n" deba@501: "8\n" deba@501: "9\n" deba@501: "@arcs\n" deba@501: " label cost\n" deba@501: "1 8 0 107\n" deba@501: "0 3 1 70\n" deba@501: "2 1 2 46\n" deba@501: "4 1 3 28\n" deba@501: "4 4 4 91\n" deba@501: "3 9 5 76\n" deba@501: "9 8 6 61\n" deba@501: "8 1 7 39\n" deba@501: "9 8 8 74\n" deba@501: "8 0 9 39\n" deba@501: "4 3 10 45\n" deba@501: "2 2 11 34\n" deba@501: "0 1 12 100\n" deba@501: "6 3 13 95\n" deba@501: "4 1 14 22\n" deba@501: "1 1 15 31\n" deba@501: "7 2 16 51\n" deba@501: "2 6 17 29\n" deba@501: "8 3 18 115\n" deba@501: "6 9 19 32\n" deba@501: "1 1 20 60\n" deba@501: "0 3 21 40\n" deba@501: "@attributes\n" deba@501: "source 0\n"; deba@501: kpeter@625: kpeter@625: void checkMinCostArborescenceCompile() kpeter@625: { kpeter@625: typedef double VType; kpeter@625: typedef concepts::Digraph Digraph; kpeter@625: typedef concepts::ReadMap CostMap; kpeter@625: typedef Digraph::Node Node; kpeter@625: typedef Digraph::Arc Arc; kpeter@625: typedef concepts::WriteMap ArbMap; kpeter@625: typedef concepts::ReadWriteMap PredMap; kpeter@625: kpeter@625: typedef MinCostArborescence:: kpeter@625: SetArborescenceMap:: kpeter@625: SetPredMap::Create MinCostArbType; kpeter@625: kpeter@625: Digraph g; kpeter@625: Node s, n; kpeter@625: Arc e; kpeter@625: VType c; kpeter@625: bool b; alpar@1083: ::lemon::ignore_unused_variable_warning(c,b); kpeter@625: int i; kpeter@625: CostMap cost; kpeter@625: ArbMap arb; kpeter@625: PredMap pred; kpeter@625: kpeter@625: MinCostArbType mcarb_test(g, cost); kpeter@625: const MinCostArbType& const_mcarb_test = mcarb_test; kpeter@625: kpeter@625: mcarb_test kpeter@625: .arborescenceMap(arb) kpeter@625: .predMap(pred) kpeter@625: .run(s); kpeter@625: kpeter@625: mcarb_test.init(); kpeter@625: mcarb_test.addSource(s); kpeter@625: mcarb_test.start(); kpeter@625: n = mcarb_test.processNextNode(); kpeter@625: b = const_mcarb_test.emptyQueue(); kpeter@625: i = const_mcarb_test.queueSize(); kpeter@625: kpeter@625: c = const_mcarb_test.arborescenceCost(); kpeter@625: b = const_mcarb_test.arborescence(e); kpeter@625: e = const_mcarb_test.pred(n); kpeter@625: const MinCostArbType::ArborescenceMap &am = kpeter@625: const_mcarb_test.arborescenceMap(); kpeter@625: const MinCostArbType::PredMap &pm = kpeter@625: const_mcarb_test.predMap(); kpeter@625: b = const_mcarb_test.reached(n); kpeter@625: b = const_mcarb_test.processed(n); kpeter@625: kpeter@625: i = const_mcarb_test.dualNum(); kpeter@625: c = const_mcarb_test.dualValue(); kpeter@625: i = const_mcarb_test.dualSize(i); kpeter@625: c = const_mcarb_test.dualValue(i); kpeter@625: alpar@1083: ::lemon::ignore_unused_variable_warning(am); alpar@1083: ::lemon::ignore_unused_variable_warning(pm); kpeter@625: } kpeter@625: deba@501: int main() { deba@501: typedef SmartDigraph Digraph; deba@501: DIGRAPH_TYPEDEFS(Digraph); deba@501: deba@501: typedef Digraph::ArcMap CostMap; deba@501: deba@501: Digraph digraph; deba@501: CostMap cost(digraph); deba@501: Node source; deba@501: deba@501: std::istringstream is(test_lgf); deba@501: digraphReader(digraph, is). deba@501: arcMap("cost", cost). deba@501: node("source", source).run(); deba@501: deba@501: MinCostArborescence mca(digraph, cost); deba@501: mca.run(source); deba@501: deba@501: vector > > dualSolution(mca.dualNum()); deba@501: deba@501: for (int i = 0; i < mca.dualNum(); ++i) { deba@501: dualSolution[i].first = mca.dualValue(i); deba@501: for (MinCostArborescence::DualIt it(mca, i); deba@501: it != INVALID; ++it) { deba@501: dualSolution[i].second.insert(it); deba@501: } deba@501: } deba@501: deba@501: for (ArcIt it(digraph); it != INVALID; ++it) { deba@501: if (mca.reached(digraph.source(it))) { deba@501: double sum = 0.0; deba@501: for (int i = 0; i < int(dualSolution.size()); ++i) { deba@501: if (dualSolution[i].second.find(digraph.target(it)) deba@501: != dualSolution[i].second.end() && deba@501: dualSolution[i].second.find(digraph.source(it)) deba@501: == dualSolution[i].second.end()) { deba@501: sum += dualSolution[i].first; deba@501: } deba@501: } deba@501: if (mca.arborescence(it)) { kpeter@625: check(sum == cost[it], "Invalid dual solution"); deba@501: } kpeter@625: check(sum <= cost[it], "Invalid dual solution"); deba@501: } deba@501: } deba@501: deba@501: kpeter@625: check(mca.dualValue() == mca.arborescenceCost(), "Invalid dual solution"); deba@501: kpeter@625: check(mca.reached(source), "Invalid arborescence"); deba@501: for (ArcIt a(digraph); a != INVALID; ++a) { deba@501: check(!mca.reached(digraph.source(a)) || kpeter@625: mca.reached(digraph.target(a)), "Invalid arborescence"); deba@501: } deba@501: deba@501: for (NodeIt n(digraph); n != INVALID; ++n) { deba@501: if (!mca.reached(n)) continue; deba@501: int cnt = 0; deba@501: for (InArcIt a(digraph, n); a != INVALID; ++a) { deba@501: if (mca.arborescence(a)) { kpeter@625: check(mca.pred(n) == a, "Invalid arborescence"); deba@501: ++cnt; deba@501: } deba@501: } kpeter@625: check((n == source ? cnt == 0 : cnt == 1), "Invalid arborescence"); deba@501: } deba@501: deba@501: Digraph::ArcMap arborescence(digraph); kpeter@625: check(mca.arborescenceCost() == deba@501: minCostArborescence(digraph, cost, source, arborescence), kpeter@625: "Wrong result of the function interface"); deba@501: deba@501: return 0; deba@501: }