Bug fix in CapacityScaling.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
24 #include <lemon/math.h>
27 #include <lemon/smart_graph.h>
28 #include <lemon/min_cost_arborescence.h>
30 #include <lemon/graph_utils.h>
31 #include <lemon/time_measure.h>
33 #include <lemon/tolerance.h>
35 #include "test_tools.h"
37 using namespace lemon;
45 int sources[EDGES] = {
46 1, 0, 2, 4, 4, 3, 9, 8, 9, 8,
47 4, 2, 0, 6, 4, 1, 7, 2, 8, 6,
51 int targets[EDGES] = {
52 8, 3, 1, 1, 4, 9, 8, 1, 8, 0,
53 3, 2, 1, 3, 1, 1, 2, 6, 3, 9,
57 double costs[EDGES] = {
58 107.444, 70.3069, 46.0496, 28.3962, 91.4325,
59 76.9443, 61.986, 39.3754, 74.9575, 39.3153,
60 45.7094, 34.6184, 100.156, 95.726, 22.3429,
61 31.587, 51.6972, 29.6773, 115.038, 32.4137,
68 typedef SmartGraph Graph;
69 GRAPH_TYPEDEFS(Graph);
71 typedef Graph::EdgeMap<double> CostMap;
77 for (int i = 0; i < NODES; ++i) {
78 nodes.push_back(graph.addNode());
81 for (int i = 0; i < EDGES; ++i) {
82 Edge edge = graph.addEdge(nodes[sources[i]], nodes[targets[i]]);
83 cost[edge] = costs[i];
86 Node source = nodes[sourceNode];
88 MinCostArborescence<Graph, CostMap> mca(graph, cost);
91 vector<pair<double, set<Node> > > dualSolution(mca.dualSize());
93 for (int i = 0; i < mca.dualSize(); ++i) {
94 dualSolution[i].first = mca.dualValue(i);
95 for (MinCostArborescence<Graph, CostMap>::DualIt it(mca, i);
96 it != INVALID; ++it) {
97 dualSolution[i].second.insert(it);
101 Tolerance<double> tolerance;
103 for (EdgeIt it(graph); it != INVALID; ++it) {
104 if (mca.reached(graph.source(it))) {
106 for (int i = 0; i < int(dualSolution.size()); ++i) {
107 if (dualSolution[i].second.find(graph.target(it))
108 != dualSolution[i].second.end() &&
109 dualSolution[i].second.find(graph.source(it))
110 == dualSolution[i].second.end()) {
111 sum += dualSolution[i].first;
114 if (mca.arborescence(it)) {
115 check(!tolerance.less(sum, cost[it]), "INVALID DUAL");
117 check(!tolerance.less(cost[it], sum), "INVALID DUAL");
122 check(!tolerance.different(mca.dualValue(), mca.arborescenceValue()),
126 check(mca.reached(source), "INVALID ARBORESCENCE");
127 for (EdgeIt it(graph); it != INVALID; ++it) {
128 check(!mca.reached(graph.source(it)) ||
129 mca.reached(graph.target(it)), "INVALID ARBORESCENCE");
132 for (NodeIt it(graph); it != INVALID; ++it) {
133 if (!mca.reached(it)) continue;
135 for (InEdgeIt jt(graph, it); jt != INVALID; ++jt) {
136 if (mca.arborescence(jt)) {
140 check((it == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");