COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/arborescence_test.cc @ 2230:67af33b34394

Last change on this file since 2230:67af33b34394 was 2180:d5544c9409e4, checked in by Balazs Dezso, 18 years ago

Omit warning
Using check instead of the LEMON_ASSERT
Using fixed graph

File size: 2.9 KB
Line 
1#include <iostream>
2#include <set>
3#include <vector>
4#include <iterator>
5
6#include <cmath>
7#include <cstdlib>
8
9#include <lemon/smart_graph.h>
10#include <lemon/min_cost_arborescence.h>
11
12#include <lemon/graph_utils.h>
13#include <lemon/time_measure.h>
14
15#include <lemon/tolerance.h>
16
17#include "test_tools.h"
18
19using namespace lemon;
20using namespace std;
21
22const int n = 10;
23const int e = 22;
24
25int sourceNode = 0;
26
27int sources[e] = {
28  1, 0, 2, 4, 4, 3, 9, 8, 9, 8,
29  4, 2, 0, 6, 4, 1, 7, 2, 8, 6,
30  1, 0
31};
32
33int targets[e] = {
34  8, 3, 1, 1, 4, 9, 8, 1, 8, 0,
35  3, 2, 1, 3, 1, 1, 2, 6, 3, 9,
36  1, 3
37};
38
39double costs[e] = {
40  107.444, 70.3069, 46.0496, 28.3962, 91.4325,
41  76.9443, 61.986, 39.3754, 74.9575, 39.3153,
42  45.7094, 34.6184, 100.156, 95.726, 22.3429,
43  31.587, 51.6972, 29.6773, 115.038, 32.4137,
44  60.0038, 40.1237
45};
46
47
48
49int main() {
50  srand(time(0));
51  typedef SmartGraph Graph;
52  GRAPH_TYPEDEFS(Graph);
53
54  typedef Graph::EdgeMap<double> CostMap;
55
56  Graph graph;
57  CostMap cost(graph);
58  vector<Node> nodes;
59 
60  for (int i = 0; i < n; ++i) {
61    nodes.push_back(graph.addNode());
62  }
63
64  for (int i = 0; i < e; ++i) {
65    Edge edge = graph.addEdge(nodes[sources[i]], nodes[targets[i]]);
66    cost[edge] = costs[i];
67  }
68
69  Node source = nodes[sourceNode];
70
71  MinCostArborescence<Graph, CostMap> mca(graph, cost);
72  mca.run(source);
73
74  vector<pair<double, set<Node> > > dualSolution(mca.dualSize());
75
76  for (int i = 0; i < mca.dualSize(); ++i) {
77    dualSolution[i].first = mca.dualValue(i);
78    for (MinCostArborescence<Graph, CostMap>::DualIt it(mca, i);
79         it != INVALID; ++it) {
80      dualSolution[i].second.insert(it);
81    }
82  }
83
84  Tolerance<double> tolerance;
85
86  for (EdgeIt it(graph); it != INVALID; ++it) {
87    if (mca.reached(graph.source(it))) {
88      double sum = 0.0;
89      for (int i = 0; i < (int)dualSolution.size(); ++i) {
90        if (dualSolution[i].second.find(graph.target(it))
91            != dualSolution[i].second.end() &&
92            dualSolution[i].second.find(graph.source(it))
93            == dualSolution[i].second.end()) {
94          sum += dualSolution[i].first;
95        }
96      }
97      if (mca.arborescence(it)) {
98        check(!tolerance.less(sum, cost[it]), "INVALID DUAL");
99      }
100      check(!tolerance.less(cost[it], sum), "INVALID DUAL");
101    }
102  }
103
104
105  check(!tolerance.different(mca.dualValue(), mca.arborescenceValue()),
106               "INVALID DUAL");
107
108
109  check(mca.reached(source), "INVALID ARBORESCENCE");
110  for (EdgeIt it(graph); it != INVALID; ++it) {
111    check(!mca.reached(graph.source(it)) ||
112                 mca.reached(graph.target(it)), "INVALID ARBORESCENCE");
113  }
114
115  for (NodeIt it(graph); it != INVALID; ++it) {
116    if (!mca.reached(it)) continue;
117    int cnt = 0;
118    for (InEdgeIt jt(graph, it); jt != INVALID; ++jt) {
119      if (mca.arborescence(jt)) {
120        ++cnt;
121      }
122    }
123    check((it == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
124  }
125 
126  return 0;
127}
Note: See TracBrowser for help on using the repository browser.