1 | // r_c_shortest_paths.hpp header file |
2 | |
3 | // Copyright Michael Drexl 2005, 2006. |
4 | // Distributed under the Boost Software License, Version 1.0. |
5 | // (See accompanying file LICENSE_1_0.txt or copy at |
6 | // http://boost.org/LICENSE_1_0.txt) |
7 | |
8 | #ifndef BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP |
9 | #define BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP |
10 | |
11 | #include <map> |
12 | #include <queue> |
13 | #include <vector> |
14 | |
15 | #include <boost/graph/graph_traits.hpp> |
16 | #include <boost/graph/iteration_macros.hpp> |
17 | #include <boost/property_map/property_map.hpp> |
18 | |
19 | namespace boost { |
20 | |
21 | // r_c_shortest_paths_label struct |
22 | template<class Graph, class Resource_Container> |
23 | struct r_c_shortest_paths_label |
24 | { |
25 | r_c_shortest_paths_label |
26 | ( const unsigned long n, |
27 | const Resource_Container& rc = Resource_Container(), |
28 | const r_c_shortest_paths_label* const pl = 0, |
29 | const typename graph_traits<Graph>::edge_descriptor& ed = |
30 | graph_traits<Graph>::edge_descriptor(), |
31 | const typename graph_traits<Graph>::vertex_descriptor& vd = |
32 | graph_traits<Graph>::vertex_descriptor() ) |
33 | : num( n ), |
34 | cumulated_resource_consumption( rc ), |
35 | p_pred_label( pl ), |
36 | pred_edge( ed ), |
37 | resident_vertex( vd ), |
38 | b_is_dominated( false ), |
39 | b_is_processed( false ), |
40 | b_is_valid( true ) |
41 | {} |
42 | r_c_shortest_paths_label& operator=( const r_c_shortest_paths_label& other ) |
43 | { |
44 | if( this == &other ) |
45 | return *this; |
46 | this->~r_c_shortest_paths_label(); |
47 | new( this ) r_c_shortest_paths_label( other ); |
48 | return *this; |
49 | } |
50 | const unsigned long num; |
51 | Resource_Container cumulated_resource_consumption; |
52 | const r_c_shortest_paths_label* const p_pred_label; |
53 | const typename graph_traits<Graph>::edge_descriptor pred_edge; |
54 | const typename graph_traits<Graph>::vertex_descriptor resident_vertex; |
55 | bool b_is_dominated; |
56 | bool b_is_processed; |
57 | bool b_is_valid; |
58 | }; // r_c_shortest_paths_label |
59 | |
60 | template<class Graph, class Resource_Container> |
61 | inline bool operator== |
62 | ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, |
63 | const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) |
64 | { |
65 | assert (l1.b_is_valid && l2.b_is_valid); |
66 | return |
67 | l1.cumulated_resource_consumption == l2.cumulated_resource_consumption; |
68 | } |
69 | |
70 | template<class Graph, class Resource_Container> |
71 | inline bool operator!= |
72 | ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, |
73 | const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) |
74 | { |
75 | assert (l1.b_is_valid && l2.b_is_valid); |
76 | return |
77 | !( l1 == l2 ); |
78 | } |
79 | |
80 | template<class Graph, class Resource_Container> |
81 | inline bool operator< |
82 | ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, |
83 | const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) |
84 | { |
85 | assert (l1.b_is_valid && l2.b_is_valid); |
86 | return |
87 | l1.cumulated_resource_consumption < l2.cumulated_resource_consumption; |
88 | } |
89 | |
90 | template<class Graph, class Resource_Container> |
91 | inline bool operator> |
92 | ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, |
93 | const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) |
94 | { |
95 | assert (l1.b_is_valid && l2.b_is_valid); |
96 | return |
97 | l2.cumulated_resource_consumption < l1.cumulated_resource_consumption; |
98 | } |
99 | |
100 | template<class Graph, class Resource_Container> |
101 | inline bool operator<= |
102 | ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, |
103 | const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) |
104 | { |
105 | assert (l1.b_is_valid && l2.b_is_valid); |
106 | return |
107 | l1 < l2 || l1 == l2; |
108 | } |
109 | |
110 | template<class Graph, class Resource_Container> |
111 | inline bool operator>= |
112 | ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, |
113 | const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) |
114 | { |
115 | assert (l1.b_is_valid && l2.b_is_valid); |
116 | return l2 < l1 || l1 == l2; |
117 | } |
118 | |
119 | namespace detail { |
120 | |
121 | // ks_smart_pointer class |
122 | // from: |
123 | // Kuhlins, S.; Schader, M. (1999): |
124 | // Die C++-Standardbibliothek |
125 | // Springer, Berlin |
126 | // p. 333 f. |
127 | template<class T> |
128 | class ks_smart_pointer |
129 | { |
130 | public: |
131 | ks_smart_pointer( T* ptt = 0 ) : pt( ptt ) {} |
132 | ks_smart_pointer( const ks_smart_pointer& other ) : pt( other.pt ) {} |
133 | ks_smart_pointer& operator=( const ks_smart_pointer& other ) |
134 | { pt = other.pt; return *this; } |
135 | ~ks_smart_pointer() {} |
136 | T& operator*() const { return *pt; } |
137 | T* operator->() const { return pt; } |
138 | T* get() const { return pt; } |
139 | operator T*() const { return pt; } |
140 | friend bool operator==( const ks_smart_pointer& t, |
141 | const ks_smart_pointer& u ) |
142 | { return *t.pt == *u.pt; } |
143 | friend bool operator!=( const ks_smart_pointer& t, |
144 | const ks_smart_pointer& u ) |
145 | { return *t.pt != *u.pt; } |
146 | friend bool operator<( const ks_smart_pointer& t, |
147 | const ks_smart_pointer& u ) |
148 | { return *t.pt < *u.pt; } |
149 | friend bool operator>( const ks_smart_pointer& t, |
150 | const ks_smart_pointer& u ) |
151 | { return *t.pt > *u.pt; } |
152 | friend bool operator<=( const ks_smart_pointer& t, |
153 | const ks_smart_pointer& u ) |
154 | { return *t.pt <= *u.pt; } |
155 | friend bool operator>=( const ks_smart_pointer& t, |
156 | const ks_smart_pointer& u ) |
157 | { return *t.pt >= *u.pt; } |
158 | private: |
159 | T* pt; |
160 | }; // ks_smart_pointer |
161 | |
162 | |
163 | // r_c_shortest_paths_dispatch function (body/implementation) |
164 | template<class Graph, |
165 | class VertexIndexMap, |
166 | class EdgeIndexMap, |
167 | class Resource_Container, |
168 | class Resource_Extension_Function, |
169 | class Dominance_Function, |
170 | class Label_Allocator, |
171 | class Visitor> |
172 | void r_c_shortest_paths_dispatch |
173 | ( const Graph& g, |
174 | const VertexIndexMap& vertex_index_map, |
175 | const EdgeIndexMap& /*edge_index_map*/, |
176 | typename graph_traits<Graph>::vertex_descriptor s, |
177 | typename graph_traits<Graph>::vertex_descriptor t, |
178 | // each inner vector corresponds to a pareto-optimal path |
179 | std::vector |
180 | <std::vector |
181 | <typename graph_traits |
182 | <Graph>::edge_descriptor> >& pareto_optimal_solutions, |
183 | std::vector |
184 | <Resource_Container>& pareto_optimal_resource_containers, |
185 | bool b_all_pareto_optimal_solutions, |
186 | // to initialize the first label/resource container |
187 | // and to carry the type information |
188 | const Resource_Container& rc, |
189 | Resource_Extension_Function& ref, |
190 | Dominance_Function& dominance, |
191 | // to specify the memory management strategy for the labels |
192 | Label_Allocator /*la*/, |
193 | Visitor vis ) |
194 | { |
195 | pareto_optimal_resource_containers.clear(); |
196 | pareto_optimal_solutions.clear(); |
197 | |
198 | size_t i_label_num = 0; |
199 | typedef |
200 | typename |
201 | Label_Allocator::template rebind |
202 | <r_c_shortest_paths_label |
203 | <Graph, Resource_Container> >::other LAlloc; |
204 | LAlloc l_alloc; |
205 | typedef |
206 | ks_smart_pointer |
207 | <r_c_shortest_paths_label<Graph, Resource_Container> > Splabel; |
208 | std::priority_queue<Splabel, std::vector<Splabel>, std::greater<Splabel> > |
209 | unprocessed_labels; |
210 | |
211 | bool b_feasible = true; |
212 | r_c_shortest_paths_label<Graph, Resource_Container>* first_label = |
213 | l_alloc.allocate( 1 ); |
214 | l_alloc.construct |
215 | ( first_label, |
216 | r_c_shortest_paths_label |
217 | <Graph, Resource_Container>( i_label_num++, |
218 | rc, |
219 | 0, |
220 | typename graph_traits<Graph>:: |
221 | edge_descriptor(), |
222 | s ) ); |
223 | |
224 | Splabel splabel_first_label = Splabel( first_label ); |
225 | unprocessed_labels.push( splabel_first_label ); |
226 | std::vector<std::list<Splabel> > vec_vertex_labels_data( num_vertices( g ) ); |
227 | iterator_property_map<typename std::vector<std::list<Splabel> >::iterator, |
228 | VertexIndexMap> |
229 | vec_vertex_labels(vec_vertex_labels_data.begin(), vertex_index_map); |
230 | vec_vertex_labels[s].push_back( splabel_first_label ); |
231 | typedef |
232 | std::vector<typename std::list<Splabel>::iterator> |
233 | vec_last_valid_positions_for_dominance_data_type; |
234 | vec_last_valid_positions_for_dominance_data_type |
235 | vec_last_valid_positions_for_dominance_data( num_vertices( g ) ); |
236 | iterator_property_map< |
237 | typename vec_last_valid_positions_for_dominance_data_type::iterator, |
238 | VertexIndexMap> |
239 | vec_last_valid_positions_for_dominance |
240 | (vec_last_valid_positions_for_dominance_data.begin(), |
241 | vertex_index_map); |
242 | BGL_FORALL_VERTICES_T(v, g, Graph) { |
243 | put(vec_last_valid_positions_for_dominance, v, vec_vertex_labels[v].begin()); |
244 | } |
245 | std::vector<size_t> vec_last_valid_index_for_dominance_data( num_vertices( g ), 0 ); |
246 | iterator_property_map<std::vector<size_t>::iterator, VertexIndexMap> |
247 | vec_last_valid_index_for_dominance |
248 | (vec_last_valid_index_for_dominance_data.begin(), vertex_index_map); |
249 | std::vector<bool> |
250 | b_vec_vertex_already_checked_for_dominance_data( num_vertices( g ), false ); |
251 | iterator_property_map<std::vector<bool>::iterator, VertexIndexMap> |
252 | b_vec_vertex_already_checked_for_dominance |
253 | (b_vec_vertex_already_checked_for_dominance_data.begin(), |
254 | vertex_index_map); |
255 | |
256 | while( !unprocessed_labels.empty() && vis.on_enter_loop(unprocessed_labels, g) ) |
257 | { |
258 | Splabel cur_label = unprocessed_labels.top(); |
259 | assert (cur_label->b_is_valid); |
260 | unprocessed_labels.pop(); |
261 | vis.on_label_popped( *cur_label, g ); |
262 | // an Splabel object in unprocessed_labels and the respective Splabel |
263 | // object in the respective list<Splabel> of vec_vertex_labels share their |
264 | // embedded r_c_shortest_paths_label object |
265 | // to avoid memory leaks, dominated |
266 | // r_c_shortest_paths_label objects are marked and deleted when popped |
267 | // from unprocessed_labels, as they can no longer be deleted at the end of |
268 | // the function; only the Splabel object in unprocessed_labels still |
269 | // references the r_c_shortest_paths_label object |
270 | // this is also for efficiency, because the else branch is executed only |
271 | // if there is a chance that extending the |
272 | // label leads to new undominated labels, which in turn is possible only |
273 | // if the label to be extended is undominated |
274 | assert (cur_label->b_is_valid); |
275 | if( !cur_label->b_is_dominated ) |
276 | { |
277 | typename boost::graph_traits<Graph>::vertex_descriptor |
278 | i_cur_resident_vertex = cur_label->resident_vertex; |
279 | std::list<Splabel>& list_labels_cur_vertex = |
280 | get(vec_vertex_labels, i_cur_resident_vertex); |
281 | if( list_labels_cur_vertex.size() >= 2 |
282 | && vec_last_valid_index_for_dominance[i_cur_resident_vertex] |
283 | < list_labels_cur_vertex.size() ) |
284 | { |
285 | typename std::list<Splabel>::iterator outer_iter = |
286 | list_labels_cur_vertex.begin(); |
287 | bool b_outer_iter_at_or_beyond_last_valid_pos_for_dominance = false; |
288 | while( outer_iter != list_labels_cur_vertex.end() ) |
289 | { |
290 | Splabel cur_outer_splabel = *outer_iter; |
291 | assert (cur_outer_splabel->b_is_valid); |
292 | typename std::list<Splabel>::iterator inner_iter = outer_iter; |
293 | if( !b_outer_iter_at_or_beyond_last_valid_pos_for_dominance |
294 | && outer_iter == |
295 | get(vec_last_valid_positions_for_dominance, |
296 | i_cur_resident_vertex) ) |
297 | b_outer_iter_at_or_beyond_last_valid_pos_for_dominance = true; |
298 | if( !get(b_vec_vertex_already_checked_for_dominance, i_cur_resident_vertex) |
299 | || b_outer_iter_at_or_beyond_last_valid_pos_for_dominance ) |
300 | { |
301 | ++inner_iter; |
302 | } |
303 | else |
304 | { |
305 | inner_iter = |
306 | get(vec_last_valid_positions_for_dominance, |
307 | i_cur_resident_vertex); |
308 | ++inner_iter; |
309 | } |
310 | bool b_outer_iter_erased = false; |
311 | while( inner_iter != list_labels_cur_vertex.end() ) |
312 | { |
313 | Splabel cur_inner_splabel = *inner_iter; |
314 | assert (cur_inner_splabel->b_is_valid); |
315 | if( dominance( cur_outer_splabel-> |
316 | cumulated_resource_consumption, |
317 | cur_inner_splabel-> |
318 | cumulated_resource_consumption ) ) |
319 | { |
320 | typename std::list<Splabel>::iterator buf = inner_iter; |
321 | ++inner_iter; |
322 | list_labels_cur_vertex.erase( buf ); |
323 | if( cur_inner_splabel->b_is_processed ) |
324 | { |
325 | cur_inner_splabel->b_is_valid = false; |
326 | l_alloc.destroy( cur_inner_splabel.get() ); |
327 | l_alloc.deallocate( cur_inner_splabel.get(), 1 ); |
328 | } |
329 | else |
330 | cur_inner_splabel->b_is_dominated = true; |
331 | continue; |
332 | } |
333 | else |
334 | ++inner_iter; |
335 | if( dominance( cur_inner_splabel-> |
336 | cumulated_resource_consumption, |
337 | cur_outer_splabel-> |
338 | cumulated_resource_consumption ) ) |
339 | { |
340 | typename std::list<Splabel>::iterator buf = outer_iter; |
341 | ++outer_iter; |
342 | list_labels_cur_vertex.erase( buf ); |
343 | b_outer_iter_erased = true; |
344 | assert (cur_outer_splabel->b_is_valid); |
345 | if( cur_outer_splabel->b_is_processed ) |
346 | { |
347 | cur_outer_splabel->b_is_valid = false; |
348 | l_alloc.destroy( cur_outer_splabel.get() ); |
349 | l_alloc.deallocate( cur_outer_splabel.get(), 1 ); |
350 | } |
351 | else |
352 | cur_outer_splabel->b_is_dominated = true; |
353 | break; |
354 | } |
355 | } |
356 | if( !b_outer_iter_erased ) |
357 | ++outer_iter; |
358 | } |
359 | if( list_labels_cur_vertex.size() > 1 ) |
360 | put(vec_last_valid_positions_for_dominance, i_cur_resident_vertex, |
361 | (--(list_labels_cur_vertex.end()))); |
362 | else |
363 | put(vec_last_valid_positions_for_dominance, i_cur_resident_vertex, |
364 | list_labels_cur_vertex.begin()); |
365 | put(b_vec_vertex_already_checked_for_dominance, |
366 | i_cur_resident_vertex, true); |
367 | put(vec_last_valid_index_for_dominance, i_cur_resident_vertex, |
368 | list_labels_cur_vertex.size() - 1); |
369 | } |
370 | } |
371 | assert (b_all_pareto_optimal_solutions || cur_label->b_is_valid); |
372 | if( !b_all_pareto_optimal_solutions && cur_label->resident_vertex == t ) |
373 | { |
374 | // the devil don't sleep |
375 | if( cur_label->b_is_dominated ) |
376 | { |
377 | cur_label->b_is_valid = false; |
378 | l_alloc.destroy( cur_label.get() ); |
379 | l_alloc.deallocate( cur_label.get(), 1 ); |
380 | } |
381 | while( unprocessed_labels.size() ) |
382 | { |
383 | Splabel l = unprocessed_labels.top(); |
384 | assert (l->b_is_valid); |
385 | unprocessed_labels.pop(); |
386 | // delete only dominated labels, because nondominated labels are |
387 | // deleted at the end of the function |
388 | if( l->b_is_dominated ) |
389 | { |
390 | l->b_is_valid = false; |
391 | l_alloc.destroy( l.get() ); |
392 | l_alloc.deallocate( l.get(), 1 ); |
393 | } |
394 | } |
395 | break; |
396 | } |
397 | if( !cur_label->b_is_dominated ) |
398 | { |
399 | cur_label->b_is_processed = true; |
400 | vis.on_label_not_dominated( *cur_label, g ); |
401 | typename graph_traits<Graph>::vertex_descriptor cur_vertex = |
402 | cur_label->resident_vertex; |
403 | typename graph_traits<Graph>::out_edge_iterator oei, oei_end; |
404 | for( boost::tie( oei, oei_end ) = out_edges( cur_vertex, g ); |
405 | oei != oei_end; |
406 | ++oei ) |
407 | { |
408 | b_feasible = true; |
409 | r_c_shortest_paths_label<Graph, Resource_Container>* new_label = |
410 | l_alloc.allocate( 1 ); |
411 | l_alloc.construct( new_label, |
412 | r_c_shortest_paths_label |
413 | <Graph, Resource_Container> |
414 | ( i_label_num++, |
415 | cur_label->cumulated_resource_consumption, |
416 | cur_label.get(), |
417 | *oei, |
418 | target( *oei, g ) ) ); |
419 | b_feasible = |
420 | ref( g, |
421 | new_label->cumulated_resource_consumption, |
422 | new_label->p_pred_label->cumulated_resource_consumption, |
423 | new_label->pred_edge ); |
424 | |
425 | if( !b_feasible ) |
426 | { |
427 | vis.on_label_not_feasible( *new_label, g ); |
428 | new_label->b_is_valid = false; |
429 | l_alloc.destroy( new_label ); |
430 | l_alloc.deallocate( new_label, 1 ); |
431 | } |
432 | else |
433 | { |
434 | const r_c_shortest_paths_label<Graph, Resource_Container>& |
435 | ref_new_label = *new_label; |
436 | vis.on_label_feasible( ref_new_label, g ); |
437 | Splabel new_sp_label( new_label ); |
438 | vec_vertex_labels[new_sp_label->resident_vertex]. |
439 | push_back( new_sp_label ); |
440 | unprocessed_labels.push( new_sp_label ); |
441 | } |
442 | } |
443 | } |
444 | else |
445 | { |
446 | assert (cur_label->b_is_valid); |
447 | vis.on_label_dominated( *cur_label, g ); |
448 | cur_label->b_is_valid = false; |
449 | l_alloc.destroy( cur_label.get() ); |
450 | l_alloc.deallocate( cur_label.get(), 1 ); |
451 | } |
452 | } |
453 | std::list<Splabel> dsplabels = get(vec_vertex_labels, t); |
454 | typename std::list<Splabel>::const_iterator csi = dsplabels.begin(); |
455 | typename std::list<Splabel>::const_iterator csi_end = dsplabels.end(); |
456 | // if d could be reached from o |
457 | if( !dsplabels.empty() ) |
458 | { |
459 | for( ; csi != csi_end; ++csi ) |
460 | { |
461 | std::vector<typename graph_traits<Graph>::edge_descriptor> |
462 | cur_pareto_optimal_path; |
463 | const r_c_shortest_paths_label<Graph, Resource_Container>* p_cur_label = |
464 | (*csi).get(); |
465 | assert (p_cur_label->b_is_valid); |
466 | pareto_optimal_resource_containers. |
467 | push_back( p_cur_label->cumulated_resource_consumption ); |
468 | while( p_cur_label->num != 0 ) |
469 | { |
470 | cur_pareto_optimal_path.push_back( p_cur_label->pred_edge ); |
471 | p_cur_label = p_cur_label->p_pred_label; |
472 | assert (p_cur_label->b_is_valid); |
473 | } |
474 | pareto_optimal_solutions.push_back( cur_pareto_optimal_path ); |
475 | if( !b_all_pareto_optimal_solutions ) |
476 | break; |
477 | } |
478 | } |
479 | |
480 | BGL_FORALL_VERTICES_T(i, g, Graph) { |
481 | const std::list<Splabel>& list_labels_cur_vertex = vec_vertex_labels[i]; |
482 | csi_end = list_labels_cur_vertex.end(); |
483 | for( csi = list_labels_cur_vertex.begin(); csi != csi_end; ++csi ) |
484 | { |
485 | assert ((*csi)->b_is_valid); |
486 | (*csi)->b_is_valid = false; |
487 | l_alloc.destroy( (*csi).get() ); |
488 | l_alloc.deallocate( (*csi).get(), 1 ); |
489 | } |
490 | } |
491 | } // r_c_shortest_paths_dispatch |
492 | |
493 | } // detail |
494 | |
495 | // default_r_c_shortest_paths_visitor struct |
496 | struct default_r_c_shortest_paths_visitor |
497 | { |
498 | template<class Label, class Graph> |
499 | void on_label_popped( const Label&, const Graph& ) {} |
500 | template<class Label, class Graph> |
501 | void on_label_feasible( const Label&, const Graph& ) {} |
502 | template<class Label, class Graph> |
503 | void on_label_not_feasible( const Label&, const Graph& ) {} |
504 | template<class Label, class Graph> |
505 | void on_label_dominated( const Label&, const Graph& ) {} |
506 | template<class Label, class Graph> |
507 | void on_label_not_dominated( const Label&, const Graph& ) {} |
508 | template<class Queue, class Graph> |
509 | bool on_enter_loop(const Queue& queue, const Graph& graph) {return true;} |
510 | }; // default_r_c_shortest_paths_visitor |
511 | |
512 | |
513 | // default_r_c_shortest_paths_allocator |
514 | typedef |
515 | std::allocator<int> default_r_c_shortest_paths_allocator; |
516 | // default_r_c_shortest_paths_allocator |
517 | |
518 | |
519 | // r_c_shortest_paths functions (handle/interface) |
520 | // first overload: |
521 | // - return all pareto-optimal solutions |
522 | // - specify Label_Allocator and Visitor arguments |
523 | template<class Graph, |
524 | class VertexIndexMap, |
525 | class EdgeIndexMap, |
526 | class Resource_Container, |
527 | class Resource_Extension_Function, |
528 | class Dominance_Function, |
529 | class Label_Allocator, |
530 | class Visitor> |
531 | void r_c_shortest_paths |
532 | ( const Graph& g, |
533 | const VertexIndexMap& vertex_index_map, |
534 | const EdgeIndexMap& edge_index_map, |
535 | typename graph_traits<Graph>::vertex_descriptor s, |
536 | typename graph_traits<Graph>::vertex_descriptor t, |
537 | // each inner vector corresponds to a pareto-optimal path |
538 | std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >& |
539 | pareto_optimal_solutions, |
540 | std::vector<Resource_Container>& pareto_optimal_resource_containers, |
541 | // to initialize the first label/resource container |
542 | // and to carry the type information |
543 | const Resource_Container& rc, |
544 | const Resource_Extension_Function& ref, |
545 | const Dominance_Function& dominance, |
546 | // to specify the memory management strategy for the labels |
547 | Label_Allocator la, |
548 | Visitor vis ) |
549 | { |
550 | r_c_shortest_paths_dispatch( g, |
551 | vertex_index_map, |
552 | edge_index_map, |
553 | s, |
554 | t, |
555 | pareto_optimal_solutions, |
556 | pareto_optimal_resource_containers, |
557 | true, |
558 | rc, |
559 | ref, |
560 | dominance, |
561 | la, |
562 | vis ); |
563 | } |
564 | |
565 | // second overload: |
566 | // - return only one pareto-optimal solution |
567 | // - specify Label_Allocator and Visitor arguments |
568 | template<class Graph, |
569 | class VertexIndexMap, |
570 | class EdgeIndexMap, |
571 | class Resource_Container, |
572 | class Resource_Extension_Function, |
573 | class Dominance_Function, |
574 | class Label_Allocator, |
575 | class Visitor> |
576 | void r_c_shortest_paths |
577 | ( const Graph& g, |
578 | const VertexIndexMap& vertex_index_map, |
579 | const EdgeIndexMap& edge_index_map, |
580 | typename graph_traits<Graph>::vertex_descriptor s, |
581 | typename graph_traits<Graph>::vertex_descriptor t, |
582 | std::vector<typename graph_traits<Graph>::edge_descriptor>& |
583 | pareto_optimal_solution, |
584 | Resource_Container& pareto_optimal_resource_container, |
585 | // to initialize the first label/resource container |
586 | // and to carry the type information |
587 | const Resource_Container& rc, |
588 | const Resource_Extension_Function& ref, |
589 | const Dominance_Function& dominance, |
590 | // to specify the memory management strategy for the labels |
591 | Label_Allocator la, |
592 | Visitor vis ) |
593 | { |
594 | // each inner vector corresponds to a pareto-optimal path |
595 | std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> > |
596 | pareto_optimal_solutions; |
597 | std::vector<Resource_Container> pareto_optimal_resource_containers; |
598 | r_c_shortest_paths_dispatch( g, |
599 | vertex_index_map, |
600 | edge_index_map, |
601 | s, |
602 | t, |
603 | pareto_optimal_solutions, |
604 | pareto_optimal_resource_containers, |
605 | false, |
606 | rc, |
607 | ref, |
608 | dominance, |
609 | la, |
610 | vis ); |
611 | if (!pareto_optimal_solutions.empty()) { |
612 | pareto_optimal_solution = pareto_optimal_solutions[0]; |
613 | pareto_optimal_resource_container = pareto_optimal_resource_containers[0]; |
614 | } |
615 | } |
616 | |
617 | // third overload: |
618 | // - return all pareto-optimal solutions |
619 | // - use default Label_Allocator and Visitor |
620 | template<class Graph, |
621 | class VertexIndexMap, |
622 | class EdgeIndexMap, |
623 | class Resource_Container, |
624 | class Resource_Extension_Function, |
625 | class Dominance_Function> |
626 | void r_c_shortest_paths |
627 | ( const Graph& g, |
628 | const VertexIndexMap& vertex_index_map, |
629 | const EdgeIndexMap& edge_index_map, |
630 | typename graph_traits<Graph>::vertex_descriptor s, |
631 | typename graph_traits<Graph>::vertex_descriptor t, |
632 | // each inner vector corresponds to a pareto-optimal path |
633 | std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >& |
634 | pareto_optimal_solutions, |
635 | std::vector<Resource_Container>& pareto_optimal_resource_containers, |
636 | // to initialize the first label/resource container |
637 | // and to carry the type information |
638 | const Resource_Container& rc, |
639 | const Resource_Extension_Function& ref, |
640 | const Dominance_Function& dominance ) |
641 | { |
642 | r_c_shortest_paths_dispatch( g, |
643 | vertex_index_map, |
644 | edge_index_map, |
645 | s, |
646 | t, |
647 | pareto_optimal_solutions, |
648 | pareto_optimal_resource_containers, |
649 | true, |
650 | rc, |
651 | ref, |
652 | dominance, |
653 | default_r_c_shortest_paths_allocator(), |
654 | default_r_c_shortest_paths_visitor() ); |
655 | } |
656 | |
657 | // fourth overload: |
658 | // - return only one pareto-optimal solution |
659 | // - use default Label_Allocator and Visitor |
660 | template<class Graph, |
661 | class VertexIndexMap, |
662 | class EdgeIndexMap, |
663 | class Resource_Container, |
664 | class Resource_Extension_Function, |
665 | class Dominance_Function> |
666 | void r_c_shortest_paths |
667 | ( const Graph& g, |
668 | const VertexIndexMap& vertex_index_map, |
669 | const EdgeIndexMap& edge_index_map, |
670 | typename graph_traits<Graph>::vertex_descriptor s, |
671 | typename graph_traits<Graph>::vertex_descriptor t, |
672 | std::vector<typename graph_traits<Graph>::edge_descriptor>& |
673 | pareto_optimal_solution, |
674 | Resource_Container& pareto_optimal_resource_container, |
675 | // to initialize the first label/resource container |
676 | // and to carry the type information |
677 | const Resource_Container& rc, |
678 | const Resource_Extension_Function& ref, |
679 | const Dominance_Function& dominance ) |
680 | { |
681 | // each inner vector corresponds to a pareto-optimal path |
682 | std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> > |
683 | pareto_optimal_solutions; |
684 | std::vector<Resource_Container> pareto_optimal_resource_containers; |
685 | r_c_shortest_paths_dispatch( g, |
686 | vertex_index_map, |
687 | edge_index_map, |
688 | s, |
689 | t, |
690 | pareto_optimal_solutions, |
691 | pareto_optimal_resource_containers, |
692 | false, |
693 | rc, |
694 | ref, |
695 | dominance, |
696 | default_r_c_shortest_paths_allocator(), |
697 | default_r_c_shortest_paths_visitor() ); |
698 | if (!pareto_optimal_solutions.empty()) { |
699 | pareto_optimal_solution = pareto_optimal_solutions[0]; |
700 | pareto_optimal_resource_container = pareto_optimal_resource_containers[0]; |
701 | } |
702 | } |
703 | // r_c_shortest_paths |
704 | |
705 | |
706 | // check_r_c_path function |
707 | template<class Graph, |
708 | class Resource_Container, |
709 | class Resource_Extension_Function> |
710 | void check_r_c_path( const Graph& g, |
711 | const std::vector |
712 | <typename graph_traits |
713 | <Graph>::edge_descriptor>& ed_vec_path, |
714 | const Resource_Container& initial_resource_levels, |
715 | // if true, computed accumulated final resource levels must |
716 | // be equal to desired_final_resource_levels |
717 | // if false, computed accumulated final resource levels must |
718 | // be less than or equal to desired_final_resource_levels |
719 | bool b_result_must_be_equal_to_desired_final_resource_levels, |
720 | const Resource_Container& desired_final_resource_levels, |
721 | Resource_Container& actual_final_resource_levels, |
722 | const Resource_Extension_Function& ref, |
723 | bool& b_is_a_path_at_all, |
724 | bool& b_feasible, |
725 | bool& b_correctly_extended, |
726 | typename graph_traits<Graph>::edge_descriptor& |
727 | ed_last_extended_arc ) |
728 | { |
729 | size_t i_size_ed_vec_path = ed_vec_path.size(); |
730 | std::vector<typename graph_traits<Graph>::edge_descriptor> buf_path; |
731 | if( i_size_ed_vec_path == 0 ) |
732 | b_feasible = true; |
733 | else |
734 | { |
735 | if( i_size_ed_vec_path == 1 |
736 | || target( ed_vec_path[0], g ) == source( ed_vec_path[1], g ) ) |
737 | buf_path = ed_vec_path; |
738 | else |
739 | for( size_t i = i_size_ed_vec_path ; i > 0; --i ) |
740 | buf_path.push_back( ed_vec_path[i - 1] ); |
741 | for( size_t i = 0; i < i_size_ed_vec_path - 1; ++i ) |
742 | { |
743 | if( target( buf_path[i], g ) != source( buf_path[i + 1], g ) ) |
744 | { |
745 | b_is_a_path_at_all = false; |
746 | b_feasible = false; |
747 | b_correctly_extended = false; |
748 | return; |
749 | } |
750 | } |
751 | } |
752 | b_is_a_path_at_all = true; |
753 | b_feasible = true; |
754 | b_correctly_extended = false; |
755 | Resource_Container current_resource_levels = initial_resource_levels; |
756 | actual_final_resource_levels = current_resource_levels; |
757 | for( size_t i = 0; i < i_size_ed_vec_path; ++i ) |
758 | { |
759 | ed_last_extended_arc = buf_path[i]; |
760 | b_feasible = ref( g, |
761 | actual_final_resource_levels, |
762 | current_resource_levels, |
763 | buf_path[i] ); |
764 | current_resource_levels = actual_final_resource_levels; |
765 | if( !b_feasible ) |
766 | return; |
767 | } |
768 | if( b_result_must_be_equal_to_desired_final_resource_levels ) |
769 | b_correctly_extended = |
770 | actual_final_resource_levels == desired_final_resource_levels ? |
771 | true : false; |
772 | else |
773 | { |
774 | if( actual_final_resource_levels < desired_final_resource_levels |
775 | || actual_final_resource_levels == desired_final_resource_levels ) |
776 | b_correctly_extended = true; |
777 | } |
778 | } // check_path |
779 | |
780 | } // namespace |
781 | |
782 | #endif // BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP |
783 | |