1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/min_cost_arborescence_test.cc Thu Nov 05 15:50:01 2009 +0100
1.3 @@ -0,0 +1,206 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#include <iostream>
1.23 +#include <set>
1.24 +#include <vector>
1.25 +#include <iterator>
1.26 +
1.27 +#include <lemon/smart_graph.h>
1.28 +#include <lemon/min_cost_arborescence.h>
1.29 +#include <lemon/lgf_reader.h>
1.30 +#include <lemon/concepts/digraph.h>
1.31 +
1.32 +#include "test_tools.h"
1.33 +
1.34 +using namespace lemon;
1.35 +using namespace std;
1.36 +
1.37 +const char test_lgf[] =
1.38 + "@nodes\n"
1.39 + "label\n"
1.40 + "0\n"
1.41 + "1\n"
1.42 + "2\n"
1.43 + "3\n"
1.44 + "4\n"
1.45 + "5\n"
1.46 + "6\n"
1.47 + "7\n"
1.48 + "8\n"
1.49 + "9\n"
1.50 + "@arcs\n"
1.51 + " label cost\n"
1.52 + "1 8 0 107\n"
1.53 + "0 3 1 70\n"
1.54 + "2 1 2 46\n"
1.55 + "4 1 3 28\n"
1.56 + "4 4 4 91\n"
1.57 + "3 9 5 76\n"
1.58 + "9 8 6 61\n"
1.59 + "8 1 7 39\n"
1.60 + "9 8 8 74\n"
1.61 + "8 0 9 39\n"
1.62 + "4 3 10 45\n"
1.63 + "2 2 11 34\n"
1.64 + "0 1 12 100\n"
1.65 + "6 3 13 95\n"
1.66 + "4 1 14 22\n"
1.67 + "1 1 15 31\n"
1.68 + "7 2 16 51\n"
1.69 + "2 6 17 29\n"
1.70 + "8 3 18 115\n"
1.71 + "6 9 19 32\n"
1.72 + "1 1 20 60\n"
1.73 + "0 3 21 40\n"
1.74 + "@attributes\n"
1.75 + "source 0\n";
1.76 +
1.77 +
1.78 +void checkMinCostArborescenceCompile()
1.79 +{
1.80 + typedef double VType;
1.81 + typedef concepts::Digraph Digraph;
1.82 + typedef concepts::ReadMap<Digraph::Arc, VType> CostMap;
1.83 + typedef Digraph::Node Node;
1.84 + typedef Digraph::Arc Arc;
1.85 + typedef concepts::WriteMap<Digraph::Arc, bool> ArbMap;
1.86 + typedef concepts::ReadWriteMap<Digraph::Node, Digraph::Arc> PredMap;
1.87 +
1.88 + typedef MinCostArborescence<Digraph, CostMap>::
1.89 + SetArborescenceMap<ArbMap>::
1.90 + SetPredMap<PredMap>::Create MinCostArbType;
1.91 +
1.92 + Digraph g;
1.93 + Node s, n;
1.94 + Arc e;
1.95 + VType c;
1.96 + bool b;
1.97 + int i;
1.98 + CostMap cost;
1.99 + ArbMap arb;
1.100 + PredMap pred;
1.101 +
1.102 + MinCostArbType mcarb_test(g, cost);
1.103 + const MinCostArbType& const_mcarb_test = mcarb_test;
1.104 +
1.105 + mcarb_test
1.106 + .arborescenceMap(arb)
1.107 + .predMap(pred)
1.108 + .run(s);
1.109 +
1.110 + mcarb_test.init();
1.111 + mcarb_test.addSource(s);
1.112 + mcarb_test.start();
1.113 + n = mcarb_test.processNextNode();
1.114 + b = const_mcarb_test.emptyQueue();
1.115 + i = const_mcarb_test.queueSize();
1.116 +
1.117 + c = const_mcarb_test.arborescenceCost();
1.118 + b = const_mcarb_test.arborescence(e);
1.119 + e = const_mcarb_test.pred(n);
1.120 + const MinCostArbType::ArborescenceMap &am =
1.121 + const_mcarb_test.arborescenceMap();
1.122 + const MinCostArbType::PredMap &pm =
1.123 + const_mcarb_test.predMap();
1.124 + b = const_mcarb_test.reached(n);
1.125 + b = const_mcarb_test.processed(n);
1.126 +
1.127 + i = const_mcarb_test.dualNum();
1.128 + c = const_mcarb_test.dualValue();
1.129 + i = const_mcarb_test.dualSize(i);
1.130 + c = const_mcarb_test.dualValue(i);
1.131 +
1.132 + ignore_unused_variable_warning(am);
1.133 + ignore_unused_variable_warning(pm);
1.134 +}
1.135 +
1.136 +int main() {
1.137 + typedef SmartDigraph Digraph;
1.138 + DIGRAPH_TYPEDEFS(Digraph);
1.139 +
1.140 + typedef Digraph::ArcMap<double> CostMap;
1.141 +
1.142 + Digraph digraph;
1.143 + CostMap cost(digraph);
1.144 + Node source;
1.145 +
1.146 + std::istringstream is(test_lgf);
1.147 + digraphReader(digraph, is).
1.148 + arcMap("cost", cost).
1.149 + node("source", source).run();
1.150 +
1.151 + MinCostArborescence<Digraph, CostMap> mca(digraph, cost);
1.152 + mca.run(source);
1.153 +
1.154 + vector<pair<double, set<Node> > > dualSolution(mca.dualNum());
1.155 +
1.156 + for (int i = 0; i < mca.dualNum(); ++i) {
1.157 + dualSolution[i].first = mca.dualValue(i);
1.158 + for (MinCostArborescence<Digraph, CostMap>::DualIt it(mca, i);
1.159 + it != INVALID; ++it) {
1.160 + dualSolution[i].second.insert(it);
1.161 + }
1.162 + }
1.163 +
1.164 + for (ArcIt it(digraph); it != INVALID; ++it) {
1.165 + if (mca.reached(digraph.source(it))) {
1.166 + double sum = 0.0;
1.167 + for (int i = 0; i < int(dualSolution.size()); ++i) {
1.168 + if (dualSolution[i].second.find(digraph.target(it))
1.169 + != dualSolution[i].second.end() &&
1.170 + dualSolution[i].second.find(digraph.source(it))
1.171 + == dualSolution[i].second.end()) {
1.172 + sum += dualSolution[i].first;
1.173 + }
1.174 + }
1.175 + if (mca.arborescence(it)) {
1.176 + check(sum == cost[it], "Invalid dual solution");
1.177 + }
1.178 + check(sum <= cost[it], "Invalid dual solution");
1.179 + }
1.180 + }
1.181 +
1.182 +
1.183 + check(mca.dualValue() == mca.arborescenceCost(), "Invalid dual solution");
1.184 +
1.185 + check(mca.reached(source), "Invalid arborescence");
1.186 + for (ArcIt a(digraph); a != INVALID; ++a) {
1.187 + check(!mca.reached(digraph.source(a)) ||
1.188 + mca.reached(digraph.target(a)), "Invalid arborescence");
1.189 + }
1.190 +
1.191 + for (NodeIt n(digraph); n != INVALID; ++n) {
1.192 + if (!mca.reached(n)) continue;
1.193 + int cnt = 0;
1.194 + for (InArcIt a(digraph, n); a != INVALID; ++a) {
1.195 + if (mca.arborescence(a)) {
1.196 + check(mca.pred(n) == a, "Invalid arborescence");
1.197 + ++cnt;
1.198 + }
1.199 + }
1.200 + check((n == source ? cnt == 0 : cnt == 1), "Invalid arborescence");
1.201 + }
1.202 +
1.203 + Digraph::ArcMap<bool> arborescence(digraph);
1.204 + check(mca.arborescenceCost() ==
1.205 + minCostArborescence(digraph, cost, source, arborescence),
1.206 + "Wrong result of the function interface");
1.207 +
1.208 + return 0;
1.209 +}