20 |
20 |
21 #include <lemon/list_graph.h> |
21 #include <lemon/list_graph.h> |
22 #include <lemon/lgf_reader.h> |
22 #include <lemon/lgf_reader.h> |
23 #include <lemon/path.h> |
23 #include <lemon/path.h> |
24 #include <lemon/suurballe.h> |
24 #include <lemon/suurballe.h> |
|
25 #include <lemon/concepts/digraph.h> |
25 |
26 |
26 #include "test_tools.h" |
27 #include "test_tools.h" |
27 |
28 |
28 using namespace lemon; |
29 using namespace lemon; |
29 |
30 |
30 char test_lgf[] = |
31 char test_lgf[] = |
31 "@nodes\n" |
32 "@nodes\n" |
32 "label supply1 supply2 supply3\n" |
33 "label\n" |
33 "1 0 20 27\n" |
34 "1\n" |
34 "2 0 -4 0\n" |
35 "2\n" |
35 "3 0 0 0\n" |
36 "3\n" |
36 "4 0 0 0\n" |
37 "4\n" |
37 "5 0 9 0\n" |
38 "5\n" |
38 "6 0 -6 0\n" |
39 "6\n" |
39 "7 0 0 0\n" |
40 "7\n" |
40 "8 0 0 0\n" |
41 "8\n" |
41 "9 0 3 0\n" |
42 "9\n" |
42 "10 0 -2 0\n" |
43 "10\n" |
43 "11 0 0 0\n" |
44 "11\n" |
44 "12 0 -20 -27\n" |
45 "12\n" |
45 "@arcs\n" |
46 "@arcs\n" |
46 " cost capacity lower1 lower2\n" |
47 " length\n" |
47 " 1 2 70 11 0 8\n" |
48 " 1 2 70\n" |
48 " 1 3 150 3 0 1\n" |
49 " 1 3 150\n" |
49 " 1 4 80 15 0 2\n" |
50 " 1 4 80\n" |
50 " 2 8 80 12 0 0\n" |
51 " 2 8 80\n" |
51 " 3 5 140 5 0 3\n" |
52 " 3 5 140\n" |
52 " 4 6 60 10 0 1\n" |
53 " 4 6 60\n" |
53 " 4 7 80 2 0 0\n" |
54 " 4 7 80\n" |
54 " 4 8 110 3 0 0\n" |
55 " 4 8 110\n" |
55 " 5 7 60 14 0 0\n" |
56 " 5 7 60\n" |
56 " 5 11 120 12 0 0\n" |
57 " 5 11 120\n" |
57 " 6 3 0 3 0 0\n" |
58 " 6 3 0\n" |
58 " 6 9 140 4 0 0\n" |
59 " 6 9 140\n" |
59 " 6 10 90 8 0 0\n" |
60 " 6 10 90\n" |
60 " 7 1 30 5 0 0\n" |
61 " 7 1 30\n" |
61 " 8 12 60 16 0 4\n" |
62 " 8 12 60\n" |
62 " 9 12 50 6 0 0\n" |
63 " 9 12 50\n" |
63 "10 12 70 13 0 5\n" |
64 "10 12 70\n" |
64 "10 2 100 7 0 0\n" |
65 "10 2 100\n" |
65 "10 7 60 10 0 0\n" |
66 "10 7 60\n" |
66 "11 10 20 14 0 6\n" |
67 "11 10 20\n" |
67 "12 11 30 10 0 0\n" |
68 "12 11 30\n" |
68 "@attributes\n" |
69 "@attributes\n" |
69 "source 1\n" |
70 "source 1\n" |
70 "target 12\n" |
71 "target 12\n" |
71 "@end\n"; |
72 "@end\n"; |
|
73 |
|
74 // Check the interface of Suurballe |
|
75 void checkSuurballeCompile() |
|
76 { |
|
77 typedef int VType; |
|
78 typedef concepts::Digraph Digraph; |
|
79 |
|
80 typedef Digraph::Node Node; |
|
81 typedef Digraph::Arc Arc; |
|
82 typedef concepts::ReadMap<Arc, VType> LengthMap; |
|
83 |
|
84 typedef Suurballe<Digraph, LengthMap> SuurballeType; |
|
85 |
|
86 Digraph g; |
|
87 Node n; |
|
88 Arc e; |
|
89 LengthMap len; |
|
90 SuurballeType::FlowMap flow(g); |
|
91 SuurballeType::PotentialMap pi(g); |
|
92 |
|
93 SuurballeType suurb_test(g, len); |
|
94 const SuurballeType& const_suurb_test = suurb_test; |
|
95 |
|
96 suurb_test |
|
97 .flowMap(flow) |
|
98 .potentialMap(pi); |
|
99 |
|
100 int k; |
|
101 k = suurb_test.run(n, n); |
|
102 k = suurb_test.run(n, n, k); |
|
103 suurb_test.init(n); |
|
104 k = suurb_test.findFlow(n); |
|
105 k = suurb_test.findFlow(n, k); |
|
106 suurb_test.findPaths(); |
|
107 |
|
108 int f; |
|
109 VType c; |
|
110 c = const_suurb_test.totalLength(); |
|
111 f = const_suurb_test.flow(e); |
|
112 const SuurballeType::FlowMap& fm = |
|
113 const_suurb_test.flowMap(); |
|
114 c = const_suurb_test.potential(n); |
|
115 const SuurballeType::PotentialMap& pm = |
|
116 const_suurb_test.potentialMap(); |
|
117 k = const_suurb_test.pathNum(); |
|
118 Path<Digraph> p = const_suurb_test.path(k); |
|
119 |
|
120 ignore_unused_variable_warning(fm); |
|
121 ignore_unused_variable_warning(pm); |
|
122 } |
72 |
123 |
73 // Check the feasibility of the flow |
124 // Check the feasibility of the flow |
74 template <typename Digraph, typename FlowMap> |
125 template <typename Digraph, typename FlowMap> |
75 bool checkFlow( const Digraph& gr, const FlowMap& flow, |
126 bool checkFlow( const Digraph& gr, const FlowMap& flow, |
76 typename Digraph::Node s, typename Digraph::Node t, |
127 typename Digraph::Node s, typename Digraph::Node t, |
134 DIGRAPH_TYPEDEFS(ListDigraph); |
184 DIGRAPH_TYPEDEFS(ListDigraph); |
135 |
185 |
136 // Read the test digraph |
186 // Read the test digraph |
137 ListDigraph digraph; |
187 ListDigraph digraph; |
138 ListDigraph::ArcMap<int> length(digraph); |
188 ListDigraph::ArcMap<int> length(digraph); |
139 Node source, target; |
189 Node s, t; |
140 |
190 |
141 std::istringstream input(test_lgf); |
191 std::istringstream input(test_lgf); |
142 DigraphReader<ListDigraph>(digraph, input). |
192 DigraphReader<ListDigraph>(digraph, input). |
143 arcMap("cost", length). |
193 arcMap("length", length). |
144 node("source", source). |
194 node("source", s). |
145 node("target", target). |
195 node("target", t). |
146 run(); |
196 run(); |
147 |
197 |
148 // Find 2 paths |
198 // Find 2 paths |
149 { |
199 { |
150 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
200 Suurballe<ListDigraph> suurballe(digraph, length); |
151 check(suurballe.run(2) == 2, "Wrong number of paths"); |
201 check(suurballe.run(s, t) == 2, "Wrong number of paths"); |
152 check(checkFlow(digraph, suurballe.flowMap(), source, target, 2), |
202 check(checkFlow(digraph, suurballe.flowMap(), s, t, 2), |
153 "The flow is not feasible"); |
203 "The flow is not feasible"); |
154 check(suurballe.totalLength() == 510, "The flow is not optimal"); |
204 check(suurballe.totalLength() == 510, "The flow is not optimal"); |
155 check(checkOptimality(digraph, length, suurballe.flowMap(), |
205 check(checkOptimality(digraph, length, suurballe.flowMap(), |
156 suurballe.potentialMap()), |
206 suurballe.potentialMap()), |
157 "Wrong potentials"); |
207 "Wrong potentials"); |
158 for (int i = 0; i < suurballe.pathNum(); ++i) |
208 for (int i = 0; i < suurballe.pathNum(); ++i) |
159 check(checkPath(digraph, suurballe.path(i), source, target), |
209 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); |
160 "Wrong path"); |
|
161 } |
210 } |
162 |
211 |
163 // Find 3 paths |
212 // Find 3 paths |
164 { |
213 { |
165 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
214 Suurballe<ListDigraph> suurballe(digraph, length); |
166 check(suurballe.run(3) == 3, "Wrong number of paths"); |
215 check(suurballe.run(s, t, 3) == 3, "Wrong number of paths"); |
167 check(checkFlow(digraph, suurballe.flowMap(), source, target, 3), |
216 check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), |
168 "The flow is not feasible"); |
217 "The flow is not feasible"); |
169 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
218 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
170 check(checkOptimality(digraph, length, suurballe.flowMap(), |
219 check(checkOptimality(digraph, length, suurballe.flowMap(), |
171 suurballe.potentialMap()), |
220 suurballe.potentialMap()), |
172 "Wrong potentials"); |
221 "Wrong potentials"); |
173 for (int i = 0; i < suurballe.pathNum(); ++i) |
222 for (int i = 0; i < suurballe.pathNum(); ++i) |
174 check(checkPath(digraph, suurballe.path(i), source, target), |
223 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); |
175 "Wrong path"); |
|
176 } |
224 } |
177 |
225 |
178 // Find 5 paths (only 3 can be found) |
226 // Find 5 paths (only 3 can be found) |
179 { |
227 { |
180 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
228 Suurballe<ListDigraph> suurballe(digraph, length); |
181 check(suurballe.run(5) == 3, "Wrong number of paths"); |
229 check(suurballe.run(s, t, 5) == 3, "Wrong number of paths"); |
182 check(checkFlow(digraph, suurballe.flowMap(), source, target, 3), |
230 check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), |
183 "The flow is not feasible"); |
231 "The flow is not feasible"); |
184 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
232 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
185 check(checkOptimality(digraph, length, suurballe.flowMap(), |
233 check(checkOptimality(digraph, length, suurballe.flowMap(), |
186 suurballe.potentialMap()), |
234 suurballe.potentialMap()), |
187 "Wrong potentials"); |
235 "Wrong potentials"); |
188 for (int i = 0; i < suurballe.pathNum(); ++i) |
236 for (int i = 0; i < suurballe.pathNum(); ++i) |
189 check(checkPath(digraph, suurballe.path(i), source, target), |
237 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); |
190 "Wrong path"); |
|
191 } |
238 } |
192 |
239 |
193 return 0; |
240 return 0; |
194 } |
241 } |