12 #include <lemon/graph_utils.h> |
12 #include <lemon/graph_utils.h> |
13 #include <lemon/time_measure.h> |
13 #include <lemon/time_measure.h> |
14 |
14 |
15 #include <lemon/tolerance.h> |
15 #include <lemon/tolerance.h> |
16 |
16 |
|
17 #include "test_tools.h" |
|
18 |
17 using namespace lemon; |
19 using namespace lemon; |
18 using namespace std; |
20 using namespace std; |
19 |
21 |
20 int main(int argc, const char *argv[]) { |
22 const int n = 10; |
|
23 const int e = 22; |
|
24 |
|
25 int sourceNode = 0; |
|
26 |
|
27 int 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 |
|
33 int 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 |
|
39 double 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 |
|
49 int main() { |
21 srand(time(0)); |
50 srand(time(0)); |
22 typedef SmartGraph Graph; |
51 typedef SmartGraph Graph; |
23 GRAPH_TYPEDEFS(Graph); |
52 GRAPH_TYPEDEFS(Graph); |
24 |
53 |
25 typedef Graph::EdgeMap<double> CostMap; |
54 typedef Graph::EdgeMap<double> CostMap; |
26 |
|
27 const int n = argc > 1 ? atoi(argv[1]) : 100; |
|
28 const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log(n)); |
|
29 |
55 |
30 Graph graph; |
56 Graph graph; |
31 CostMap cost(graph); |
57 CostMap cost(graph); |
32 vector<Node> nodes; |
58 vector<Node> nodes; |
33 |
59 |
34 for (int i = 0; i < n; ++i) { |
60 for (int i = 0; i < n; ++i) { |
35 nodes.push_back(graph.addNode()); |
61 nodes.push_back(graph.addNode()); |
36 } |
62 } |
37 |
63 |
38 for (int i = 0; i < e; ++i) { |
64 for (int i = 0; i < e; ++i) { |
39 int s = (int)(n * (double)rand() / (RAND_MAX + 1.0)); |
65 Edge edge = graph.addEdge(nodes[sources[i]], nodes[targets[i]]); |
40 int t = (int)(n * (double)rand() / (RAND_MAX + 1.0)); |
66 cost[edge] = costs[i]; |
41 double c = rand() / (1.0 + RAND_MAX) * 100.0 + 20.0; |
|
42 Edge edge = graph.addEdge(nodes[s], nodes[t]); |
|
43 cost[edge] = c; |
|
44 } |
67 } |
45 |
68 |
46 Node source = nodes[(int)(n * (double)rand() / (RAND_MAX + 1.0))]; |
69 Node source = nodes[sourceNode]; |
47 |
70 |
48 MinCostArborescence<Graph, CostMap> mca(graph, cost); |
71 MinCostArborescence<Graph, CostMap> mca(graph, cost); |
49 mca.run(source); |
72 mca.run(source); |
50 |
73 |
51 vector<pair<double, set<Node> > > dualSolution(mca.dualSize()); |
74 vector<pair<double, set<Node> > > dualSolution(mca.dualSize()); |
70 == dualSolution[i].second.end()) { |
93 == dualSolution[i].second.end()) { |
71 sum += dualSolution[i].first; |
94 sum += dualSolution[i].first; |
72 } |
95 } |
73 } |
96 } |
74 if (mca.arborescence(it)) { |
97 if (mca.arborescence(it)) { |
75 LEMON_ASSERT(!tolerance.less(sum, cost[it]), "INVALID DUAL"); |
98 check(!tolerance.less(sum, cost[it]), "INVALID DUAL"); |
76 } |
99 } |
77 LEMON_ASSERT(!tolerance.less(cost[it], sum), "INVALID DUAL"); |
100 check(!tolerance.less(cost[it], sum), "INVALID DUAL"); |
78 } |
101 } |
79 } |
102 } |
80 |
103 |
81 |
104 |
82 LEMON_ASSERT(!tolerance.different(mca.dualValue(), mca.arborescenceValue()), |
105 check(!tolerance.different(mca.dualValue(), mca.arborescenceValue()), |
83 "INVALID DUAL"); |
106 "INVALID DUAL"); |
84 |
107 |
85 |
108 |
86 LEMON_ASSERT(mca.reached(source), "INVALID ARBORESCENCE"); |
109 check(mca.reached(source), "INVALID ARBORESCENCE"); |
87 for (EdgeIt it(graph); it != INVALID; ++it) { |
110 for (EdgeIt it(graph); it != INVALID; ++it) { |
88 LEMON_ASSERT(!mca.reached(graph.source(it)) || |
111 check(!mca.reached(graph.source(it)) || |
89 mca.reached(graph.target(it)), "INVALID ARBORESCENCE"); |
112 mca.reached(graph.target(it)), "INVALID ARBORESCENCE"); |
90 } |
113 } |
91 |
114 |
92 for (NodeIt it(graph); it != INVALID; ++it) { |
115 for (NodeIt it(graph); it != INVALID; ++it) { |
93 if (!mca.reached(it)) continue; |
116 if (!mca.reached(it)) continue; |