1 | // Copyright Michael Drexl 2005, 2006. |
2 | // Distributed under the Boost Software License, Version 1.0. |
3 | // (See accompanying file LICENSE_1_0.txt or copy at |
4 | // http://boost.org/LICENSE_1_0.txt) |
5 | |
6 | #include <boost/config.hpp> |
7 | |
8 | #ifdef BOOST_MSVC |
9 | #pragma warning(disable : 4267) |
10 | #endif |
11 | |
12 | #include <boost/graph/adjacency_list.hpp> |
13 | //#include <boost/graph/dijkstra_shortest_paths.hpp> |
14 | |
15 | #include <boost/graph/r_c_shortest_paths.hpp> |
16 | #include <iostream> |
17 | #include <boost/core/lightweight_test.hpp> |
18 | |
19 | using namespace boost; |
20 | |
21 | struct SPPRC_Example_Graph_Vert_Prop |
22 | { |
23 | SPPRC_Example_Graph_Vert_Prop(int n = 0, int e = 0, int l = 0) |
24 | : num(n), eat(e), lat(l) |
25 | { |
26 | } |
27 | int num; |
28 | // earliest arrival time |
29 | int eat; |
30 | // latest arrival time |
31 | int lat; |
32 | }; |
33 | |
34 | struct SPPRC_Example_Graph_Arc_Prop |
35 | { |
36 | SPPRC_Example_Graph_Arc_Prop(int n = 0, int c = 0, int t = 0) |
37 | : num(n), cost(c), time(t) |
38 | { |
39 | } |
40 | int num; |
41 | // traversal cost |
42 | int cost; |
43 | // traversal time |
44 | int time; |
45 | }; |
46 | |
47 | typedef adjacency_list< vecS, vecS, directedS, SPPRC_Example_Graph_Vert_Prop, |
48 | SPPRC_Example_Graph_Arc_Prop > |
49 | SPPRC_Example_Graph; |
50 | |
51 | // data structures for spp without resource constraints: |
52 | // ResourceContainer model |
53 | struct spp_no_rc_res_cont |
54 | { |
55 | spp_no_rc_res_cont(int c = 0) : cost(c) {}; |
56 | spp_no_rc_res_cont& operator=(const spp_no_rc_res_cont& other) |
57 | { |
58 | if (this == &other) |
59 | return *this; |
60 | this->~spp_no_rc_res_cont(); |
61 | new (this) spp_no_rc_res_cont(other); |
62 | return *this; |
63 | } |
64 | int cost; |
65 | }; |
66 | |
67 | bool operator==( |
68 | const spp_no_rc_res_cont& res_cont_1, const spp_no_rc_res_cont& res_cont_2) |
69 | { |
70 | return (res_cont_1.cost == res_cont_2.cost); |
71 | } |
72 | |
73 | bool operator<( |
74 | const spp_no_rc_res_cont& res_cont_1, const spp_no_rc_res_cont& res_cont_2) |
75 | { |
76 | return (res_cont_1.cost < res_cont_2.cost); |
77 | } |
78 | |
79 | // ResourceExtensionFunction model |
80 | class ref_no_res_cont |
81 | { |
82 | public: |
83 | inline bool operator()(const SPPRC_Example_Graph& g, |
84 | spp_no_rc_res_cont& new_cont, const spp_no_rc_res_cont& old_cont, |
85 | graph_traits< SPPRC_Example_Graph >::edge_descriptor ed) const |
86 | { |
87 | new_cont.cost = old_cont.cost + g[ed].cost; |
88 | return true; |
89 | } |
90 | }; |
91 | |
92 | // DominanceFunction model |
93 | class dominance_no_res_cont |
94 | { |
95 | public: |
96 | inline bool operator()(const spp_no_rc_res_cont& res_cont_1, |
97 | const spp_no_rc_res_cont& res_cont_2) const |
98 | { |
99 | // must be "<=" here!!! |
100 | // must NOT be "<"!!! |
101 | return res_cont_1.cost <= res_cont_2.cost; |
102 | // this is not a contradiction to the documentation |
103 | // the documentation says: |
104 | // "A label $l_1$ dominates a label $l_2$ if and only if both are |
105 | // resident at the same vertex, and if, for each resource, the resource |
106 | // consumption of $l_1$ is less than or equal to the resource |
107 | // consumption of $l_2$, and if there is at least one resource where |
108 | // $l_1$ has a lower resource consumption than $l_2$." one can think of |
109 | // a new label with a resource consumption equal to that of an old label |
110 | // as being dominated by that old label, because the new one will have a |
111 | // higher number and is created at a later point in time, so one can |
112 | // implicitly use the number or the creation time as a resource for |
113 | // tie-breaking |
114 | } |
115 | }; |
116 | // end data structures for spp without resource constraints: |
117 | |
118 | // data structures for shortest path problem with time windows (spptw) |
119 | // ResourceContainer model |
120 | struct spp_spptw_res_cont |
121 | { |
122 | spp_spptw_res_cont(int c = 0, int t = 0) : cost(c), time(t) {} |
123 | spp_spptw_res_cont& operator=(const spp_spptw_res_cont& other) |
124 | { |
125 | if (this == &other) |
126 | return *this; |
127 | this->~spp_spptw_res_cont(); |
128 | new (this) spp_spptw_res_cont(other); |
129 | return *this; |
130 | } |
131 | int cost; |
132 | int time; |
133 | }; |
134 | |
135 | bool operator==( |
136 | const spp_spptw_res_cont& res_cont_1, const spp_spptw_res_cont& res_cont_2) |
137 | { |
138 | return (res_cont_1.cost == res_cont_2.cost |
139 | && res_cont_1.time == res_cont_2.time); |
140 | } |
141 | |
142 | bool operator<( |
143 | const spp_spptw_res_cont& res_cont_1, const spp_spptw_res_cont& res_cont_2) |
144 | { |
145 | if (res_cont_1.cost > res_cont_2.cost) |
146 | return false; |
147 | if (res_cont_1.cost == res_cont_2.cost) |
148 | return res_cont_1.time < res_cont_2.time; |
149 | return true; |
150 | } |
151 | |
152 | // ResourceExtensionFunction model |
153 | class ref_spptw |
154 | { |
155 | public: |
156 | inline bool operator()(const SPPRC_Example_Graph& g, |
157 | spp_spptw_res_cont& new_cont, const spp_spptw_res_cont& old_cont, |
158 | graph_traits< SPPRC_Example_Graph >::edge_descriptor ed) const |
159 | { |
160 | const SPPRC_Example_Graph_Arc_Prop& arc_prop = get(p: edge_bundle, g)[ed]; |
161 | const SPPRC_Example_Graph_Vert_Prop& vert_prop |
162 | = get(p: vertex_bundle, g)[target(e: ed, g)]; |
163 | new_cont.cost = old_cont.cost + arc_prop.cost; |
164 | int& i_time = new_cont.time; |
165 | i_time = old_cont.time + arc_prop.time; |
166 | i_time < vert_prop.eat ? i_time = vert_prop.eat : 0; |
167 | return i_time <= vert_prop.lat ? true : false; |
168 | } |
169 | }; |
170 | |
171 | // DominanceFunction model |
172 | class dominance_spptw |
173 | { |
174 | public: |
175 | inline bool operator()(const spp_spptw_res_cont& res_cont_1, |
176 | const spp_spptw_res_cont& res_cont_2) const |
177 | { |
178 | // must be "<=" here!!! |
179 | // must NOT be "<"!!! |
180 | return res_cont_1.cost <= res_cont_2.cost |
181 | && res_cont_1.time <= res_cont_2.time; |
182 | // this is not a contradiction to the documentation |
183 | // the documentation says: |
184 | // "A label $l_1$ dominates a label $l_2$ if and only if both are |
185 | // resident at the same vertex, and if, for each resource, the resource |
186 | // consumption of $l_1$ is less than or equal to the resource |
187 | // consumption of $l_2$, and if there is at least one resource where |
188 | // $l_1$ has a lower resource consumption than $l_2$." one can think of |
189 | // a new label with a resource consumption equal to that of an old label |
190 | // as being dominated by that old label, because the new one will have a |
191 | // higher number and is created at a later point in time, so one can |
192 | // implicitly use the number or the creation time as a resource for |
193 | // tie-breaking |
194 | } |
195 | }; |
196 | // end data structures for shortest path problem with time windows (spptw) |
197 | |
198 | struct spp_spptw_marked_res_cont |
199 | { |
200 | spp_spptw_marked_res_cont( |
201 | SPPRC_Example_Graph::vertex_descriptor v, int c = 0, int t = 0) |
202 | : cost(c), time(t), marked() |
203 | { |
204 | marked.insert(x: v); |
205 | } |
206 | spp_spptw_marked_res_cont& operator=(const spp_spptw_marked_res_cont& other) |
207 | { |
208 | if (this == &other) |
209 | return *this; |
210 | this->~spp_spptw_marked_res_cont(); |
211 | new (this) spp_spptw_marked_res_cont(other); |
212 | return *this; |
213 | } |
214 | int cost; |
215 | int time; |
216 | std::set< SPPRC_Example_Graph::vertex_descriptor > marked; |
217 | }; |
218 | |
219 | bool operator==(const spp_spptw_marked_res_cont& res_cont_1, |
220 | const spp_spptw_marked_res_cont& res_cont_2) |
221 | { |
222 | return res_cont_1.cost == res_cont_2.cost |
223 | && res_cont_1.time == res_cont_2.time |
224 | && res_cont_1.marked == res_cont_2.marked; |
225 | } |
226 | |
227 | bool operator<(const spp_spptw_marked_res_cont& res_cont_1, |
228 | const spp_spptw_marked_res_cont& res_cont_2) |
229 | { |
230 | if (res_cont_1.cost > res_cont_2.cost || res_cont_1.time > res_cont_2.time) |
231 | { |
232 | return false; |
233 | } |
234 | |
235 | if (!std::includes(first1: res_cont_2.marked.begin(), last1: res_cont_2.marked.end(), |
236 | first2: res_cont_1.marked.begin(), last2: res_cont_1.marked.end())) |
237 | { |
238 | return false; |
239 | } |
240 | |
241 | if (res_cont_1.cost == res_cont_2.cost) |
242 | { |
243 | return res_cont_1.time < res_cont_2.time; |
244 | } |
245 | return true; |
246 | } |
247 | |
248 | class ref_spptw_marked |
249 | { |
250 | public: |
251 | inline bool operator()(const SPPRC_Example_Graph& g, |
252 | spp_spptw_marked_res_cont& new_cont, |
253 | const spp_spptw_marked_res_cont& old_cont, |
254 | graph_traits< SPPRC_Example_Graph >::edge_descriptor ed) const |
255 | { |
256 | const graph_traits< SPPRC_Example_Graph >::vertex_descriptor dest |
257 | = target(e: ed, g); |
258 | |
259 | if (old_cont.marked.find(x: dest) != old_cont.marked.end()) |
260 | { |
261 | return false; |
262 | } |
263 | |
264 | const SPPRC_Example_Graph_Arc_Prop& arc_prop = get(p: edge_bundle, g)[ed]; |
265 | const SPPRC_Example_Graph_Vert_Prop& vert_prop |
266 | = get(p: vertex_bundle, g)[dest]; |
267 | new_cont.cost = old_cont.cost + arc_prop.cost; |
268 | new_cont.marked = old_cont.marked; |
269 | new_cont.marked.insert(x: dest); |
270 | int& i_time = new_cont.time; |
271 | i_time = old_cont.time + arc_prop.time; |
272 | i_time < vert_prop.eat ? i_time = vert_prop.eat : 0; |
273 | return i_time <= vert_prop.lat; |
274 | } |
275 | }; |
276 | |
277 | class dominance_spptw_marked |
278 | { |
279 | public: |
280 | inline bool operator()(const spp_spptw_marked_res_cont& res_cont_1, |
281 | const spp_spptw_marked_res_cont& res_cont_2) const |
282 | { |
283 | return res_cont_1.time <= res_cont_2.time |
284 | && res_cont_1.cost <= res_cont_2.cost |
285 | && std::includes(first1: res_cont_1.marked.begin(), last1: res_cont_1.marked.end(), |
286 | first2: res_cont_2.marked.begin(), last2: res_cont_2.marked.end()); |
287 | } |
288 | }; |
289 | |
290 | int main(int, char*[]) |
291 | { |
292 | SPPRC_Example_Graph g; |
293 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(0, 0, 1000000000), g_&: g); |
294 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(1, 56, 142), g_&: g); |
295 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(2, 0, 1000000000), g_&: g); |
296 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(3, 89, 178), g_&: g); |
297 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(4, 0, 1000000000), g_&: g); |
298 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(5, 49, 76), g_&: g); |
299 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(6, 0, 1000000000), g_&: g); |
300 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(7, 98, 160), g_&: g); |
301 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(8, 0, 1000000000), g_&: g); |
302 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(9, 90, 158), g_&: g); |
303 | add_edge(u: 0, v: 7, p: SPPRC_Example_Graph_Arc_Prop(6, 33, 2), g_&: g); |
304 | add_edge(u: 0, v: 6, p: SPPRC_Example_Graph_Arc_Prop(5, 31, 6), g_&: g); |
305 | add_edge(u: 0, v: 4, p: SPPRC_Example_Graph_Arc_Prop(3, 14, 4), g_&: g); |
306 | add_edge(u: 0, v: 1, p: SPPRC_Example_Graph_Arc_Prop(0, 43, 8), g_&: g); |
307 | add_edge(u: 0, v: 4, p: SPPRC_Example_Graph_Arc_Prop(4, 28, 10), g_&: g); |
308 | add_edge(u: 0, v: 3, p: SPPRC_Example_Graph_Arc_Prop(1, 31, 10), g_&: g); |
309 | add_edge(u: 0, v: 3, p: SPPRC_Example_Graph_Arc_Prop(2, 1, 7), g_&: g); |
310 | add_edge(u: 0, v: 9, p: SPPRC_Example_Graph_Arc_Prop(7, 25, 9), g_&: g); |
311 | add_edge(u: 1, v: 0, p: SPPRC_Example_Graph_Arc_Prop(8, 37, 4), g_&: g); |
312 | add_edge(u: 1, v: 6, p: SPPRC_Example_Graph_Arc_Prop(9, 7, 3), g_&: g); |
313 | add_edge(u: 2, v: 6, p: SPPRC_Example_Graph_Arc_Prop(12, 6, 7), g_&: g); |
314 | add_edge(u: 2, v: 3, p: SPPRC_Example_Graph_Arc_Prop(10, 13, 7), g_&: g); |
315 | add_edge(u: 2, v: 3, p: SPPRC_Example_Graph_Arc_Prop(11, 49, 9), g_&: g); |
316 | add_edge(u: 2, v: 8, p: SPPRC_Example_Graph_Arc_Prop(13, 47, 5), g_&: g); |
317 | add_edge(u: 3, v: 4, p: SPPRC_Example_Graph_Arc_Prop(17, 5, 10), g_&: g); |
318 | add_edge(u: 3, v: 1, p: SPPRC_Example_Graph_Arc_Prop(15, 47, 1), g_&: g); |
319 | add_edge(u: 3, v: 2, p: SPPRC_Example_Graph_Arc_Prop(16, 26, 9), g_&: g); |
320 | add_edge(u: 3, v: 9, p: SPPRC_Example_Graph_Arc_Prop(21, 24, 10), g_&: g); |
321 | add_edge(u: 3, v: 7, p: SPPRC_Example_Graph_Arc_Prop(20, 50, 10), g_&: g); |
322 | add_edge(u: 3, v: 0, p: SPPRC_Example_Graph_Arc_Prop(14, 41, 4), g_&: g); |
323 | add_edge(u: 3, v: 6, p: SPPRC_Example_Graph_Arc_Prop(19, 6, 1), g_&: g); |
324 | add_edge(u: 3, v: 4, p: SPPRC_Example_Graph_Arc_Prop(18, 8, 1), g_&: g); |
325 | add_edge(u: 4, v: 5, p: SPPRC_Example_Graph_Arc_Prop(26, 38, 4), g_&: g); |
326 | add_edge(u: 4, v: 9, p: SPPRC_Example_Graph_Arc_Prop(27, 32, 10), g_&: g); |
327 | add_edge(u: 4, v: 3, p: SPPRC_Example_Graph_Arc_Prop(24, 40, 3), g_&: g); |
328 | add_edge(u: 4, v: 0, p: SPPRC_Example_Graph_Arc_Prop(22, 7, 3), g_&: g); |
329 | add_edge(u: 4, v: 3, p: SPPRC_Example_Graph_Arc_Prop(25, 28, 9), g_&: g); |
330 | add_edge(u: 4, v: 2, p: SPPRC_Example_Graph_Arc_Prop(23, 39, 6), g_&: g); |
331 | add_edge(u: 5, v: 8, p: SPPRC_Example_Graph_Arc_Prop(32, 6, 2), g_&: g); |
332 | add_edge(u: 5, v: 2, p: SPPRC_Example_Graph_Arc_Prop(30, 26, 10), g_&: g); |
333 | add_edge(u: 5, v: 0, p: SPPRC_Example_Graph_Arc_Prop(28, 38, 9), g_&: g); |
334 | add_edge(u: 5, v: 2, p: SPPRC_Example_Graph_Arc_Prop(31, 48, 10), g_&: g); |
335 | add_edge(u: 5, v: 9, p: SPPRC_Example_Graph_Arc_Prop(33, 49, 2), g_&: g); |
336 | add_edge(u: 5, v: 1, p: SPPRC_Example_Graph_Arc_Prop(29, 22, 7), g_&: g); |
337 | add_edge(u: 6, v: 1, p: SPPRC_Example_Graph_Arc_Prop(34, 15, 7), g_&: g); |
338 | add_edge(u: 6, v: 7, p: SPPRC_Example_Graph_Arc_Prop(35, 20, 3), g_&: g); |
339 | add_edge(u: 7, v: 9, p: SPPRC_Example_Graph_Arc_Prop(40, 1, 3), g_&: g); |
340 | add_edge(u: 7, v: 0, p: SPPRC_Example_Graph_Arc_Prop(36, 23, 5), g_&: g); |
341 | add_edge(u: 7, v: 6, p: SPPRC_Example_Graph_Arc_Prop(38, 36, 2), g_&: g); |
342 | add_edge(u: 7, v: 6, p: SPPRC_Example_Graph_Arc_Prop(39, 18, 10), g_&: g); |
343 | add_edge(u: 7, v: 2, p: SPPRC_Example_Graph_Arc_Prop(37, 2, 1), g_&: g); |
344 | add_edge(u: 8, v: 5, p: SPPRC_Example_Graph_Arc_Prop(46, 36, 5), g_&: g); |
345 | add_edge(u: 8, v: 1, p: SPPRC_Example_Graph_Arc_Prop(42, 13, 10), g_&: g); |
346 | add_edge(u: 8, v: 0, p: SPPRC_Example_Graph_Arc_Prop(41, 40, 5), g_&: g); |
347 | add_edge(u: 8, v: 1, p: SPPRC_Example_Graph_Arc_Prop(43, 32, 8), g_&: g); |
348 | add_edge(u: 8, v: 6, p: SPPRC_Example_Graph_Arc_Prop(47, 25, 1), g_&: g); |
349 | add_edge(u: 8, v: 2, p: SPPRC_Example_Graph_Arc_Prop(44, 44, 3), g_&: g); |
350 | add_edge(u: 8, v: 3, p: SPPRC_Example_Graph_Arc_Prop(45, 11, 9), g_&: g); |
351 | add_edge(u: 9, v: 0, p: SPPRC_Example_Graph_Arc_Prop(48, 41, 5), g_&: g); |
352 | add_edge(u: 9, v: 1, p: SPPRC_Example_Graph_Arc_Prop(49, 44, 7), g_&: g); |
353 | |
354 | // spp without resource constraints |
355 | |
356 | std::vector< |
357 | std::vector< graph_traits< SPPRC_Example_Graph >::edge_descriptor > > |
358 | opt_solutions; |
359 | std::vector< spp_no_rc_res_cont > pareto_opt_rcs_no_rc; |
360 | std::vector< int > i_vec_opt_solutions_spp_no_rc; |
361 | // std::cout << "r_c_shortest_paths:" << std::endl; |
362 | for (int s = 0; s < 10; ++s) |
363 | { |
364 | for (int t = 0; t < 10; ++t) |
365 | { |
366 | r_c_shortest_paths(g, vertex_index_map: get(p: &SPPRC_Example_Graph_Vert_Prop::num, g), |
367 | edge_index_map: get(p: &SPPRC_Example_Graph_Arc_Prop::num, g), s, t, pareto_optimal_solutions&: opt_solutions, |
368 | pareto_optimal_resource_containers&: pareto_opt_rcs_no_rc, rc: spp_no_rc_res_cont(0), ref: ref_no_res_cont(), |
369 | dominance: dominance_no_res_cont(), |
370 | la: std::allocator< r_c_shortest_paths_label< SPPRC_Example_Graph, |
371 | spp_no_rc_res_cont > >(), |
372 | vis: default_r_c_shortest_paths_visitor()); |
373 | i_vec_opt_solutions_spp_no_rc.push_back( |
374 | x: pareto_opt_rcs_no_rc[0].cost); |
375 | // std::cout << "From " << s << " to " << t << ": "; |
376 | // std::cout << pareto_opt_rcs_no_rc[0].cost << std::endl; |
377 | } |
378 | } |
379 | |
380 | // std::vector<graph_traits<SPPRC_Example_Graph>::vertex_descriptor> |
381 | // p( num_vertices( g ) ); |
382 | // std::vector<int> d( num_vertices( g ) ); |
383 | // std::vector<int> i_vec_dijkstra_distances; |
384 | // std::cout << "Dijkstra:" << std::endl; |
385 | // for( int s = 0; s < 10; ++s ) |
386 | //{ |
387 | // dijkstra_shortest_paths( g, |
388 | // s, |
389 | // &p[0], |
390 | // &d[0], |
391 | // get( &SPPRC_Example_Graph_Arc_Prop::cost, g ), |
392 | // get( &SPPRC_Example_Graph_Vert_Prop::num, g ), |
393 | // std::less<int>(), |
394 | // closed_plus<int>(), |
395 | // (std::numeric_limits<int>::max)(), |
396 | // 0, |
397 | // default_dijkstra_visitor() ); |
398 | // for( int t = 0; t < 10; ++t ) |
399 | // { |
400 | // i_vec_dijkstra_distances.push_back( d[t] ); |
401 | // std::cout << "From " << s << " to " << t << ": " << d[t] << std::endl; |
402 | // } |
403 | //} |
404 | |
405 | std::vector< int > i_vec_correct_solutions; |
406 | i_vec_correct_solutions.push_back(x: 0); |
407 | i_vec_correct_solutions.push_back(x: 22); |
408 | i_vec_correct_solutions.push_back(x: 27); |
409 | i_vec_correct_solutions.push_back(x: 1); |
410 | i_vec_correct_solutions.push_back(x: 6); |
411 | i_vec_correct_solutions.push_back(x: 44); |
412 | i_vec_correct_solutions.push_back(x: 7); |
413 | i_vec_correct_solutions.push_back(x: 27); |
414 | i_vec_correct_solutions.push_back(x: 50); |
415 | i_vec_correct_solutions.push_back(x: 25); |
416 | i_vec_correct_solutions.push_back(x: 37); |
417 | i_vec_correct_solutions.push_back(x: 0); |
418 | i_vec_correct_solutions.push_back(x: 29); |
419 | i_vec_correct_solutions.push_back(x: 38); |
420 | i_vec_correct_solutions.push_back(x: 43); |
421 | i_vec_correct_solutions.push_back(x: 81); |
422 | i_vec_correct_solutions.push_back(x: 7); |
423 | i_vec_correct_solutions.push_back(x: 27); |
424 | i_vec_correct_solutions.push_back(x: 76); |
425 | i_vec_correct_solutions.push_back(x: 28); |
426 | i_vec_correct_solutions.push_back(x: 25); |
427 | i_vec_correct_solutions.push_back(x: 21); |
428 | i_vec_correct_solutions.push_back(x: 0); |
429 | i_vec_correct_solutions.push_back(x: 13); |
430 | i_vec_correct_solutions.push_back(x: 18); |
431 | i_vec_correct_solutions.push_back(x: 56); |
432 | i_vec_correct_solutions.push_back(x: 6); |
433 | i_vec_correct_solutions.push_back(x: 26); |
434 | i_vec_correct_solutions.push_back(x: 47); |
435 | i_vec_correct_solutions.push_back(x: 27); |
436 | i_vec_correct_solutions.push_back(x: 12); |
437 | i_vec_correct_solutions.push_back(x: 21); |
438 | i_vec_correct_solutions.push_back(x: 26); |
439 | i_vec_correct_solutions.push_back(x: 0); |
440 | i_vec_correct_solutions.push_back(x: 5); |
441 | i_vec_correct_solutions.push_back(x: 43); |
442 | i_vec_correct_solutions.push_back(x: 6); |
443 | i_vec_correct_solutions.push_back(x: 26); |
444 | i_vec_correct_solutions.push_back(x: 49); |
445 | i_vec_correct_solutions.push_back(x: 24); |
446 | i_vec_correct_solutions.push_back(x: 7); |
447 | i_vec_correct_solutions.push_back(x: 29); |
448 | i_vec_correct_solutions.push_back(x: 34); |
449 | i_vec_correct_solutions.push_back(x: 8); |
450 | i_vec_correct_solutions.push_back(x: 0); |
451 | i_vec_correct_solutions.push_back(x: 38); |
452 | i_vec_correct_solutions.push_back(x: 14); |
453 | i_vec_correct_solutions.push_back(x: 34); |
454 | i_vec_correct_solutions.push_back(x: 44); |
455 | i_vec_correct_solutions.push_back(x: 32); |
456 | i_vec_correct_solutions.push_back(x: 29); |
457 | i_vec_correct_solutions.push_back(x: 19); |
458 | i_vec_correct_solutions.push_back(x: 26); |
459 | i_vec_correct_solutions.push_back(x: 17); |
460 | i_vec_correct_solutions.push_back(x: 22); |
461 | i_vec_correct_solutions.push_back(x: 0); |
462 | i_vec_correct_solutions.push_back(x: 23); |
463 | i_vec_correct_solutions.push_back(x: 43); |
464 | i_vec_correct_solutions.push_back(x: 6); |
465 | i_vec_correct_solutions.push_back(x: 41); |
466 | i_vec_correct_solutions.push_back(x: 43); |
467 | i_vec_correct_solutions.push_back(x: 15); |
468 | i_vec_correct_solutions.push_back(x: 22); |
469 | i_vec_correct_solutions.push_back(x: 35); |
470 | i_vec_correct_solutions.push_back(x: 40); |
471 | i_vec_correct_solutions.push_back(x: 78); |
472 | i_vec_correct_solutions.push_back(x: 0); |
473 | i_vec_correct_solutions.push_back(x: 20); |
474 | i_vec_correct_solutions.push_back(x: 69); |
475 | i_vec_correct_solutions.push_back(x: 21); |
476 | i_vec_correct_solutions.push_back(x: 23); |
477 | i_vec_correct_solutions.push_back(x: 23); |
478 | i_vec_correct_solutions.push_back(x: 2); |
479 | i_vec_correct_solutions.push_back(x: 15); |
480 | i_vec_correct_solutions.push_back(x: 20); |
481 | i_vec_correct_solutions.push_back(x: 58); |
482 | i_vec_correct_solutions.push_back(x: 8); |
483 | i_vec_correct_solutions.push_back(x: 0); |
484 | i_vec_correct_solutions.push_back(x: 49); |
485 | i_vec_correct_solutions.push_back(x: 1); |
486 | i_vec_correct_solutions.push_back(x: 23); |
487 | i_vec_correct_solutions.push_back(x: 13); |
488 | i_vec_correct_solutions.push_back(x: 37); |
489 | i_vec_correct_solutions.push_back(x: 11); |
490 | i_vec_correct_solutions.push_back(x: 16); |
491 | i_vec_correct_solutions.push_back(x: 36); |
492 | i_vec_correct_solutions.push_back(x: 17); |
493 | i_vec_correct_solutions.push_back(x: 37); |
494 | i_vec_correct_solutions.push_back(x: 0); |
495 | i_vec_correct_solutions.push_back(x: 35); |
496 | i_vec_correct_solutions.push_back(x: 41); |
497 | i_vec_correct_solutions.push_back(x: 44); |
498 | i_vec_correct_solutions.push_back(x: 68); |
499 | i_vec_correct_solutions.push_back(x: 42); |
500 | i_vec_correct_solutions.push_back(x: 47); |
501 | i_vec_correct_solutions.push_back(x: 85); |
502 | i_vec_correct_solutions.push_back(x: 48); |
503 | i_vec_correct_solutions.push_back(x: 68); |
504 | i_vec_correct_solutions.push_back(x: 91); |
505 | i_vec_correct_solutions.push_back(x: 0); |
506 | BOOST_TEST( |
507 | i_vec_opt_solutions_spp_no_rc.size() == i_vec_correct_solutions.size()); |
508 | for (int i = 0; i < static_cast< int >(i_vec_correct_solutions.size()); ++i) |
509 | BOOST_TEST( |
510 | i_vec_opt_solutions_spp_no_rc[i] == i_vec_correct_solutions[i]); |
511 | |
512 | // spptw |
513 | std::vector< |
514 | std::vector< graph_traits< SPPRC_Example_Graph >::edge_descriptor > > |
515 | opt_solutions_spptw; |
516 | std::vector< spp_spptw_res_cont > pareto_opt_rcs_spptw; |
517 | std::vector< std::vector< std::vector< std::vector< |
518 | graph_traits< SPPRC_Example_Graph >::edge_descriptor > > > > |
519 | vec_vec_vec_vec_opt_solutions_spptw(10); |
520 | |
521 | for (int s = 0; s < 10; ++s) |
522 | { |
523 | for (int t = 0; t < 10; ++t) |
524 | { |
525 | r_c_shortest_paths(g, vertex_index_map: get(p: &SPPRC_Example_Graph_Vert_Prop::num, g), |
526 | edge_index_map: get(p: &SPPRC_Example_Graph_Arc_Prop::num, g), s, t, |
527 | pareto_optimal_solutions&: opt_solutions_spptw, pareto_optimal_resource_containers&: pareto_opt_rcs_spptw, |
528 | // be careful, do not simply take 0 as initial value for time |
529 | rc: spp_spptw_res_cont(0, g[s].eat), ref: ref_spptw(), dominance: dominance_spptw(), |
530 | la: std::allocator< r_c_shortest_paths_label< SPPRC_Example_Graph, |
531 | spp_spptw_res_cont > >(), |
532 | vis: default_r_c_shortest_paths_visitor()); |
533 | vec_vec_vec_vec_opt_solutions_spptw[s].push_back( |
534 | x: opt_solutions_spptw); |
535 | if (opt_solutions_spptw.size()) |
536 | { |
537 | bool b_is_a_path_at_all = false; |
538 | bool b_feasible = false; |
539 | bool b_correctly_extended = false; |
540 | spp_spptw_res_cont actual_final_resource_levels(0, 0); |
541 | graph_traits< SPPRC_Example_Graph >::edge_descriptor |
542 | ed_last_extended_arc; |
543 | check_r_c_path(g, ed_vec_path: opt_solutions_spptw[0], |
544 | initial_resource_levels: spp_spptw_res_cont(0, g[s].eat), b_result_must_be_equal_to_desired_final_resource_levels: true, |
545 | desired_final_resource_levels: pareto_opt_rcs_spptw[0], actual_final_resource_levels, |
546 | ref: ref_spptw(), b_is_a_path_at_all, b_feasible, |
547 | b_correctly_extended, ed_last_extended_arc); |
548 | BOOST_TEST( |
549 | b_is_a_path_at_all && b_feasible && b_correctly_extended); |
550 | b_is_a_path_at_all = false; |
551 | b_feasible = false; |
552 | b_correctly_extended = false; |
553 | spp_spptw_res_cont actual_final_resource_levels2(0, 0); |
554 | graph_traits< SPPRC_Example_Graph >::edge_descriptor |
555 | ed_last_extended_arc2; |
556 | check_r_c_path(g, ed_vec_path: opt_solutions_spptw[0], |
557 | initial_resource_levels: spp_spptw_res_cont(0, g[s].eat), b_result_must_be_equal_to_desired_final_resource_levels: false, |
558 | desired_final_resource_levels: pareto_opt_rcs_spptw[0], actual_final_resource_levels&: actual_final_resource_levels2, |
559 | ref: ref_spptw(), b_is_a_path_at_all, b_feasible, |
560 | b_correctly_extended, ed_last_extended_arc&: ed_last_extended_arc2); |
561 | BOOST_TEST( |
562 | b_is_a_path_at_all && b_feasible && b_correctly_extended); |
563 | } |
564 | } |
565 | } |
566 | |
567 | std::vector< int > i_vec_correct_num_solutions_spptw; |
568 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
569 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
570 | i_vec_correct_num_solutions_spptw.push_back(x: 3); |
571 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
572 | i_vec_correct_num_solutions_spptw.push_back(x: 3); |
573 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
574 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
575 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
576 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
577 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
578 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
579 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
580 | i_vec_correct_num_solutions_spptw.push_back(x: 4); |
581 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
582 | i_vec_correct_num_solutions_spptw.push_back(x: 3); |
583 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
584 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
585 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
586 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
587 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
588 | i_vec_correct_num_solutions_spptw.push_back(x: 4); |
589 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
590 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
591 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
592 | i_vec_correct_num_solutions_spptw.push_back(x: 4); |
593 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
594 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
595 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
596 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
597 | i_vec_correct_num_solutions_spptw.push_back(x: 3); |
598 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
599 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
600 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
601 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
602 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
603 | i_vec_correct_num_solutions_spptw.push_back(x: 0); |
604 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
605 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
606 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
607 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
608 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
609 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
610 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
611 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
612 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
613 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
614 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
615 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
616 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
617 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
618 | i_vec_correct_num_solutions_spptw.push_back(x: 4); |
619 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
620 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
621 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
622 | i_vec_correct_num_solutions_spptw.push_back(x: 4); |
623 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
624 | i_vec_correct_num_solutions_spptw.push_back(x: 4); |
625 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
626 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
627 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
628 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
629 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
630 | i_vec_correct_num_solutions_spptw.push_back(x: 4); |
631 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
632 | i_vec_correct_num_solutions_spptw.push_back(x: 5); |
633 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
634 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
635 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
636 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
637 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
638 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
639 | i_vec_correct_num_solutions_spptw.push_back(x: 3); |
640 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
641 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
642 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
643 | i_vec_correct_num_solutions_spptw.push_back(x: 0); |
644 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
645 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
646 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
647 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
648 | i_vec_correct_num_solutions_spptw.push_back(x: 3); |
649 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
650 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
651 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
652 | i_vec_correct_num_solutions_spptw.push_back(x: 3); |
653 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
654 | i_vec_correct_num_solutions_spptw.push_back(x: 3); |
655 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
656 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
657 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
658 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
659 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
660 | i_vec_correct_num_solutions_spptw.push_back(x: 4); |
661 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
662 | i_vec_correct_num_solutions_spptw.push_back(x: 3); |
663 | i_vec_correct_num_solutions_spptw.push_back(x: 0); |
664 | i_vec_correct_num_solutions_spptw.push_back(x: 2); |
665 | i_vec_correct_num_solutions_spptw.push_back(x: 3); |
666 | i_vec_correct_num_solutions_spptw.push_back(x: 4); |
667 | i_vec_correct_num_solutions_spptw.push_back(x: 1); |
668 | for (int s = 0; s < 10; ++s) |
669 | for (int t = 0; t < 10; ++t) |
670 | BOOST_TEST(static_cast< int >( |
671 | vec_vec_vec_vec_opt_solutions_spptw[s][t].size()) |
672 | == i_vec_correct_num_solutions_spptw[10 * s + t]); |
673 | |
674 | // one pareto-optimal solution |
675 | SPPRC_Example_Graph g2; |
676 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(0, 0, 1000000000), g_&: g2); |
677 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(1, 0, 1000000000), g_&: g2); |
678 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(2, 0, 1000000000), g_&: g2); |
679 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(3, 0, 1000000000), g_&: g2); |
680 | add_edge(u: 0, v: 1, p: SPPRC_Example_Graph_Arc_Prop(0, 1, 1), g_&: g2); |
681 | add_edge(u: 0, v: 2, p: SPPRC_Example_Graph_Arc_Prop(1, 2, 1), g_&: g2); |
682 | add_edge(u: 1, v: 3, p: SPPRC_Example_Graph_Arc_Prop(2, 3, 1), g_&: g2); |
683 | add_edge(u: 2, v: 3, p: SPPRC_Example_Graph_Arc_Prop(3, 1, 1), g_&: g2); |
684 | std::vector< graph_traits< SPPRC_Example_Graph >::edge_descriptor > |
685 | opt_solution; |
686 | spp_spptw_res_cont pareto_opt_rc; |
687 | r_c_shortest_paths(g: g2, vertex_index_map: get(p: &SPPRC_Example_Graph_Vert_Prop::num, g&: g2), |
688 | edge_index_map: get(p: &SPPRC_Example_Graph_Arc_Prop::num, g&: g2), s: 0, t: 3, pareto_optimal_solution&: opt_solution, |
689 | pareto_optimal_resource_container&: pareto_opt_rc, rc: spp_spptw_res_cont(0, 0), ref: ref_spptw(), dominance: dominance_spptw(), |
690 | la: std::allocator< r_c_shortest_paths_label< SPPRC_Example_Graph, |
691 | spp_spptw_res_cont > >(), |
692 | vis: default_r_c_shortest_paths_visitor()); |
693 | |
694 | BOOST_TEST(pareto_opt_rc.cost == 3); |
695 | |
696 | SPPRC_Example_Graph g3; |
697 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(0, 0, 1000), g_&: g3); |
698 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(1, 0, 1000), g_&: g3); |
699 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(2, 0, 974), g_&: g3); |
700 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(3, 0, 972), g_&: g3); |
701 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(4, 0, 967), g_&: g3); |
702 | add_vertex(p: SPPRC_Example_Graph_Vert_Prop(5, 678, 801), g_&: g3); |
703 | add_edge(u: 0, v: 2, p: SPPRC_Example_Graph_Arc_Prop(0, 0, 16), g_&: g3); |
704 | add_edge(u: 0, v: 3, p: SPPRC_Example_Graph_Arc_Prop(1, 0, 18), g_&: g3); |
705 | add_edge(u: 0, v: 4, p: SPPRC_Example_Graph_Arc_Prop(2, 0, 23), g_&: g3); |
706 | add_edge(u: 0, v: 5, p: SPPRC_Example_Graph_Arc_Prop(3, 0, 25), g_&: g3); |
707 | add_edge(u: 2, v: 3, p: SPPRC_Example_Graph_Arc_Prop(4, 0, 33), g_&: g3); |
708 | add_edge(u: 2, v: 4, p: SPPRC_Example_Graph_Arc_Prop(5, 0, 15), g_&: g3); |
709 | add_edge(u: 2, v: 5, p: SPPRC_Example_Graph_Arc_Prop(6, 0, 33), g_&: g3); |
710 | add_edge(u: 2, v: 1, p: SPPRC_Example_Graph_Arc_Prop(7, 0, 16), g_&: g3); |
711 | add_edge(u: 3, v: 2, p: SPPRC_Example_Graph_Arc_Prop(8, 0, 33), g_&: g3); |
712 | add_edge(u: 3, v: 4, p: SPPRC_Example_Graph_Arc_Prop(9, 0, 35), g_&: g3); |
713 | add_edge(u: 3, v: 5, p: SPPRC_Example_Graph_Arc_Prop(10, 0, 21), g_&: g3); |
714 | add_edge(u: 3, v: 1, p: SPPRC_Example_Graph_Arc_Prop(11, 0, 18), g_&: g3); |
715 | add_edge(u: 4, v: 2, p: SPPRC_Example_Graph_Arc_Prop(12, 0, 15), g_&: g3); |
716 | add_edge(u: 4, v: 3, p: SPPRC_Example_Graph_Arc_Prop(13, 0, 35), g_&: g3); |
717 | add_edge(u: 4, v: 5, p: SPPRC_Example_Graph_Arc_Prop(14, 0, 25), g_&: g3); |
718 | add_edge(u: 4, v: 1, p: SPPRC_Example_Graph_Arc_Prop(15, 0, 23), g_&: g3); |
719 | add_edge(u: 5, v: 2, p: SPPRC_Example_Graph_Arc_Prop(16, 0, 33), g_&: g3); |
720 | add_edge(u: 5, v: 3, p: SPPRC_Example_Graph_Arc_Prop(17, 0, 21), g_&: g3); |
721 | add_edge(u: 5, v: 4, p: SPPRC_Example_Graph_Arc_Prop(18, 0, 25), g_&: g3); |
722 | add_edge(u: 5, v: 1, p: SPPRC_Example_Graph_Arc_Prop(19, 0, 25), g_&: g3); |
723 | |
724 | std::vector< |
725 | std::vector< graph_traits< SPPRC_Example_Graph >::edge_descriptor > > |
726 | pareto_opt_marked_solutions; |
727 | std::vector< spp_spptw_marked_res_cont > |
728 | pareto_opt_marked_resource_containers; |
729 | |
730 | graph_traits< SPPRC_Example_Graph >::vertex_descriptor g3_source = 0, |
731 | g3_target = 1; |
732 | r_c_shortest_paths(g: g3, vertex_index_map: get(p: &SPPRC_Example_Graph_Vert_Prop::num, g&: g3), |
733 | edge_index_map: get(p: &SPPRC_Example_Graph_Arc_Prop::num, g&: g3), s: g3_source, t: g3_target, |
734 | pareto_optimal_solutions&: pareto_opt_marked_solutions, pareto_optimal_resource_containers&: pareto_opt_marked_resource_containers, |
735 | rc: spp_spptw_marked_res_cont(0, 0, 0), ref: ref_spptw_marked(), |
736 | dominance: dominance_spptw_marked(), |
737 | la: std::allocator< r_c_shortest_paths_label< SPPRC_Example_Graph, |
738 | spp_spptw_marked_res_cont > >(), |
739 | vis: default_r_c_shortest_paths_visitor()); |
740 | |
741 | BOOST_TEST(!pareto_opt_marked_solutions.empty()); |
742 | std::vector< std::vector< |
743 | graph_traits< SPPRC_Example_Graph >::edge_descriptor > >::const_iterator |
744 | path_it, |
745 | path_end_it; |
746 | for (path_it = pareto_opt_marked_solutions.begin(), |
747 | path_end_it = pareto_opt_marked_solutions.end(); |
748 | path_it != path_end_it; ++path_it) |
749 | { |
750 | const std::vector< |
751 | graph_traits< SPPRC_Example_Graph >::edge_descriptor >& path |
752 | = *path_it; |
753 | BOOST_TEST(!path.empty()); |
754 | |
755 | const graph_traits< SPPRC_Example_Graph >::edge_descriptor front |
756 | = path.front(); |
757 | BOOST_TEST(boost::target(front, g3) == g3_target); |
758 | |
759 | std::vector< graph_traits< SPPRC_Example_Graph >::edge_descriptor >:: |
760 | const_iterator edge_it, |
761 | edge_it_end; |
762 | graph_traits< SPPRC_Example_Graph >::edge_descriptor prev_edge = front; |
763 | |
764 | for (edge_it = path.begin() + 1, edge_it_end = path.end(); |
765 | edge_it != edge_it_end; ++edge_it) |
766 | { |
767 | graph_traits< SPPRC_Example_Graph >::edge_descriptor edge |
768 | = *edge_it; |
769 | |
770 | graph_traits< SPPRC_Example_Graph >::vertex_descriptor prev_end, |
771 | current_end; |
772 | prev_end = boost::source(e: prev_edge, g3); |
773 | current_end = boost::target(e: edge, g3); |
774 | BOOST_TEST(prev_end == current_end); |
775 | |
776 | prev_edge = edge; |
777 | } |
778 | |
779 | const graph_traits< SPPRC_Example_Graph >::edge_descriptor back |
780 | = path.back(); |
781 | BOOST_TEST(boost::source(back, g3) == g3_source); |
782 | } |
783 | |
784 | return boost::report_errors(); |
785 | } |
786 | |