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
19namespace boost {
20
21// r_c_shortest_paths_label struct
22template<class Graph, class Resource_Container>
23struct 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
60template<class Graph, class Resource_Container>
61inline 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
70template<class Graph, class Resource_Container>
71inline 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
80template<class Graph, class Resource_Container>
81inline 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
90template<class Graph, class Resource_Container>
91inline 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
100template<class Graph, class Resource_Container>
101inline 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
110template<class Graph, class Resource_Container>
111inline 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
119namespace 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.
127template<class T>
128class ks_smart_pointer
129{
130public:
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; }
158private:
159 T* pt;
160}; // ks_smart_pointer
161
162
163// r_c_shortest_paths_dispatch function (body/implementation)
164template<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>
172void 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
496struct 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
514typedef
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
523template<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>
531void 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
568template<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>
576void 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
620template<class Graph,
621 class VertexIndexMap,
622 class EdgeIndexMap,
623 class Resource_Container,
624 class Resource_Extension_Function,
625 class Dominance_Function>
626void 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
660template<class Graph,
661 class VertexIndexMap,
662 class EdgeIndexMap,
663 class Resource_Container,
664 class Resource_Extension_Function,
665 class Dominance_Function>
666void 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
707template<class Graph,
708 class Resource_Container,
709 class Resource_Extension_Function>
710void 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

source code of boost/boost/graph/r_c_shortest_paths.hpp