COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/arborescence_test.cc @ 2242:16523135943d

Last change on this file since 2242:16523135943d was 2242:16523135943d, checked in by Balazs Dezso, 14 years ago

New random interface
Switching to the new interface

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  typedef SmartGraph Graph;
51  GRAPH_TYPEDEFS(Graph);
52
53  typedef Graph::EdgeMap<double> CostMap;
54
55  Graph graph;
56  CostMap cost(graph);
57  vector<Node> nodes;
58 
59  for (int i = 0; i < n; ++i) {
60    nodes.push_back(graph.addNode());
61  }
62
63  for (int i = 0; i < e; ++i) {
64    Edge edge = graph.addEdge(nodes[sources[i]], nodes[targets[i]]);
65    cost[edge] = costs[i];
66  }
67
68  Node source = nodes[sourceNode];
69
70  MinCostArborescence<Graph, CostMap> mca(graph, cost);
71  mca.run(source);
72
73  vector<pair<double, set<Node> > > dualSolution(mca.dualSize());
74
75  for (int i = 0; i < mca.dualSize(); ++i) {
76    dualSolution[i].first = mca.dualValue(i);
77    for (MinCostArborescence<Graph, CostMap>::DualIt it(mca, i);
78         it != INVALID; ++it) {
79      dualSolution[i].second.insert(it);
80    }
81  }
82
83  Tolerance<double> tolerance;
84
85  for (EdgeIt it(graph); it != INVALID; ++it) {
86    if (mca.reached(graph.source(it))) {
87      double sum = 0.0;
88      for (int i = 0; i < (int)dualSolution.size(); ++i) {
89        if (dualSolution[i].second.find(graph.target(it))
90            != dualSolution[i].second.end() &&
91            dualSolution[i].second.find(graph.source(it))
92            == dualSolution[i].second.end()) {
93          sum += dualSolution[i].first;
94        }
95      }
96      if (mca.arborescence(it)) {
97        check(!tolerance.less(sum, cost[it]), "INVALID DUAL");
98      }
99      check(!tolerance.less(cost[it], sum), "INVALID DUAL");
100    }
101  }
102
103
104  check(!tolerance.different(mca.dualValue(), mca.arborescenceValue()),
105               "INVALID DUAL");
106
107
108  check(mca.reached(source), "INVALID ARBORESCENCE");
109  for (EdgeIt it(graph); it != INVALID; ++it) {
110    check(!mca.reached(graph.source(it)) ||
111                 mca.reached(graph.target(it)), "INVALID ARBORESCENCE");
112  }
113
114  for (NodeIt it(graph); it != INVALID; ++it) {
115    if (!mca.reached(it)) continue;
116    int cnt = 0;
117    for (InEdgeIt jt(graph, it); jt != INVALID; ++jt) {
118      if (mca.arborescence(jt)) {
119        ++cnt;
120      }
121    }
122    check((it == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
123  }
124 
125  return 0;
126}
Note: See TracBrowser for help on using the repository browser.