boost/graph/r_c_shortest_paths.hpp

0001 // r_c_shortest_paths.hpp header file
0002
0003 // Copyright Michael Drexl 2005, 2006.
0004 // Distributed under the Boost Software License, Version 1.0.
0005 // (See accompanying file LICENSE_1_0.txt or copy at
0006 // http://boost.org/LICENSE_1_0.txt)
0007
0008 #ifndef BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP
0009 #define BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP
0010
0011 #include <map>
0012 #include <queue>
0013 #include <vector>
0014 #include <list>
0015
0016 #include <boost/make_shared.hpp>
0017 #include <boost/enable_shared_from_this.hpp>
0018 #include <boost/graph/graph_traits.hpp>
0019 #include <boost/graph/iteration_macros.hpp>
0020 #include <boost/property_map/property_map.hpp>
0021
0022 namespace boost
0023 {
0024
0025 // r_c_shortest_paths_label struct
0026 template < class Graph, class Resource_Container >
0027 struct r_c_shortest_paths_label
0028 : public boost::enable_shared_from_this<
0029       r_c_shortest_paths_label< Graph, Resource_Container > >
0030 {
0031     r_c_shortest_paths_label(const unsigned long n,
0032         const Resource_Container& rc = Resource_Container(),
0033         const boost::shared_ptr<
0034             r_c_shortest_paths_label< Graph, Resource_Container > >
0035             pl
0036         = boost::shared_ptr<
0037             r_c_shortest_paths_label< Graph, Resource_Container > >(),
0038         const typename graph_traits< Graph >::edge_descriptor& ed
0039         = graph_traits< Graph >::edge_descriptor(),
0040         const typename graph_traits< Graph >::vertex_descriptor& vd
0041         = graph_traits< Graph >::vertex_descriptor())
0042     : num(n)
0043     , cumulated_resource_consumption(rc)
0044     , p_pred_label(pl)
0045     , pred_edge(ed)
0046     , resident_vertex(vd)
0047     , b_is_dominated(false)
0048     , b_is_processed(false)
0049     {
0050     }
0051
0052     r_c_shortest_paths_label& operator=(const r_c_shortest_paths_label& other)
0053     {
0054         if (this == &other)
0055             return *this;
0056         this->~r_c_shortest_paths_label();
0057         new (this) r_c_shortest_paths_label(other);
0058         return *this;
0059     }
0060     const unsigned long num;
0061     Resource_Container cumulated_resource_consumption;
0062     const boost::shared_ptr<
0063         r_c_shortest_paths_label< Graph, Resource_Container > >
0064         p_pred_label;
0065     const typename graph_traits< Graph >::edge_descriptor pred_edge;
0066     const typename graph_traits< Graph >::vertex_descriptor resident_vertex;
0067     bool b_is_dominated;
0068     bool b_is_processed;
0069 }; // r_c_shortest_paths_label
0070
0071 template < class Graph, class Resource_Container >
0072 inline bool operator==(
0073     const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
0074     const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
0075 {
0076     return l1.cumulated_resource_consumption
0077         == l2.cumulated_resource_consumption;
0078 }
0079
0080 template < class Graph, class Resource_Container >
0081 inline bool operator!=(
0082     const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
0083     const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
0084 {
0085     return !(l1 == l2);
0086 }
0087
0088 template < class Graph, class Resource_Container >
0089 inline bool operator<(
0090     const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
0091     const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
0092 {
0093     return l1.cumulated_resource_consumption
0094         < l2.cumulated_resource_consumption;
0095 }
0096
0097 template < class Graph, class Resource_Container >
0098 inline bool operator>(
0099     const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
0100     const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
0101 {
0102     return l2.cumulated_resource_consumption
0103         < l1.cumulated_resource_consumption;
0104 }
0105
0106 template < class Graph, class Resource_Container >
0107 inline bool operator<=(
0108     const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
0109     const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
0110 {
0111     return l1 < l2 || l1 == l2;
0112 }
0113
0114 template < class Graph, class Resource_Container >
0115 inline bool operator>=(
0116     const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
0117     const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
0118 {
0119     return l2 < l1 || l1 == l2;
0120 }
0121
0122 template < typename Graph, typename Resource_Container >
0123 inline bool operator<(
0124     const boost::shared_ptr<
0125         r_c_shortest_paths_label< Graph, Resource_Container > >& t,
0126     const boost::shared_ptr<
0127         r_c_shortest_paths_label< Graph, Resource_Container > >& u)
0128 {
0129     return *t < *u;
0130 }
0131
0132 template < typename Graph, typename Resource_Container >
0133 inline bool operator<=(
0134     const boost::shared_ptr<
0135         r_c_shortest_paths_label< Graph, Resource_Container > >& t,
0136     const boost::shared_ptr<
0137         r_c_shortest_paths_label< Graph, Resource_Container > >& u)
0138 {
0139     return *t <= *u;
0140 }
0141
0142 template < typename Graph, typename Resource_Container >
0143 inline bool operator>(
0144     const boost::shared_ptr<
0145         r_c_shortest_paths_label< Graph, Resource_Container > >& t,
0146     const boost::shared_ptr<
0147         r_c_shortest_paths_label< Graph, Resource_Container > >& u)
0148 {
0149     return *t > *u;
0150 }
0151
0152 template < typename Graph, typename Resource_Container >
0153 inline bool operator>=(
0154     const boost::shared_ptr<
0155         r_c_shortest_paths_label< Graph, Resource_Container > >& t,
0156     const boost::shared_ptr<
0157         r_c_shortest_paths_label< Graph, Resource_Container > >& u)
0158 {
0159     return *t >= *u;
0160 }
0161
0162 namespace detail
0163 {
0164
0165     // r_c_shortest_paths_dispatch function (body/implementation)
0166     template < class Graph, class VertexIndexMap, class EdgeIndexMap,
0167         class Resource_Container, class Resource_Extension_Function,
0168         class Dominance_Function, class Label_Allocator, class Visitor >
0169     void r_c_shortest_paths_dispatch(const Graph& g,
0170         const VertexIndexMap& vertex_index_map,
0171         const EdgeIndexMap& /*edge_index_map*/,
0172         typename graph_traits< Graph >::vertex_descriptor s,
0173         typename graph_traits< Graph >::vertex_descriptor t,
0174         // each inner vector corresponds to a pareto-optimal path
0175         std::vector<
0176             std::vector< typename graph_traits< Graph >::edge_descriptor > >&
0177             pareto_optimal_solutions,
0178         std::vector< Resource_Container >& pareto_optimal_resource_containers,
0179         bool b_all_pareto_optimal_solutions,
0180         // to initialize the first label/resource container
0181         // and to carry the type information
0182         const Resource_Container& rc, Resource_Extension_Function& ref,
0183         Dominance_Function& dominance,
0184         // to specify the memory management strategy for the labels
0185         Label_Allocator /*la*/, Visitor vis)
0186     {
0187         pareto_optimal_resource_containers.clear();
0188         pareto_optimal_solutions.clear();
0189
0190         size_t i_label_num = 0;
0191 #if defined(BOOST_NO_CXX11_ALLOCATOR)
0192         typedef typename Label_Allocator::template rebind<
0193             r_c_shortest_paths_label< Graph, Resource_Container > >::other
0194             LAlloc;
0195 #else
0196         typedef typename std::allocator_traits< Label_Allocator >::
0197             template rebind_alloc<
0198                 r_c_shortest_paths_label< Graph, Resource_Container > >
0199                 LAlloc;
0200         typedef std::allocator_traits< LAlloc > LTraits;
0201 #endif
0202         LAlloc l_alloc;
0203         typedef boost::shared_ptr<
0204             r_c_shortest_paths_label< Graph, Resource_Container > >
0205             Splabel;
0206         std::priority_queue< Splabel, std::vector< Splabel >,
0207             std::greater< Splabel > >
0208             unprocessed_labels;
0209
0210         bool b_feasible = true;
0211         Splabel splabel_first_label = boost::allocate_shared<
0212             r_c_shortest_paths_label< Graph, Resource_Container > >(l_alloc,
0213             i_label_num++, rc,
0214             boost::shared_ptr<
0215                 r_c_shortest_paths_label< Graph, Resource_Container > >(),
0216             typename graph_traits< Graph >::edge_descriptor(), s);
0217
0218         unprocessed_labels.push(splabel_first_label);
0219         std::vector< std::list< Splabel > > vec_vertex_labels_data(
0220             num_vertices(g));
0221         iterator_property_map<
0222             typename std::vector< std::list< Splabel > >::iterator,
0223             VertexIndexMap >
0224             vec_vertex_labels(vec_vertex_labels_data.begin(), vertex_index_map);
0225         vec_vertex_labels[s].push_back(splabel_first_label);
0226         typedef std::vector< typename std::list< Splabel >::iterator >
0227             vec_last_valid_positions_for_dominance_data_type;
0228         vec_last_valid_positions_for_dominance_data_type
0229             vec_last_valid_positions_for_dominance_data(num_vertices(g));
0230         iterator_property_map<
0231             typename vec_last_valid_positions_for_dominance_data_type::iterator,
0232             VertexIndexMap >
0233             vec_last_valid_positions_for_dominance(
0234                 vec_last_valid_positions_for_dominance_data.begin(),
0235                 vertex_index_map);
0236         BGL_FORALL_VERTICES_T(v, g, Graph)
0237         {
0238             put(vec_last_valid_positions_for_dominance, v,
0239                 vec_vertex_labels[v].begin());
0240         }
0241         std::vector< size_t > vec_last_valid_index_for_dominance_data(
0242             num_vertices(g), 0);
0243         iterator_property_map< std::vector< size_t >::iterator, VertexIndexMap >
0244             vec_last_valid_index_for_dominance(
0245                 vec_last_valid_index_for_dominance_data.begin(),
0246                 vertex_index_map);
0247         std::vector< bool > b_vec_vertex_already_checked_for_dominance_data(
0248             num_vertices(g), false);
0249         iterator_property_map< std::vector< bool >::iterator, VertexIndexMap >
0250             b_vec_vertex_already_checked_for_dominance(
0251                 b_vec_vertex_already_checked_for_dominance_data.begin(),
0252                 vertex_index_map);
0253
0254         while (!unprocessed_labels.empty()
0255             && vis.on_enter_loop(unprocessed_labels, g))
0256         {
0257             Splabel cur_label = unprocessed_labels.top();
0258             unprocessed_labels.pop();
0259             vis.on_label_popped(*cur_label, g);
0260             // an Splabel object in unprocessed_labels and the respective
0261             // Splabel object in the respective list<Splabel> of
0262             // vec_vertex_labels share their embedded r_c_shortest_paths_label
0263             // object to avoid memory leaks, dominated r_c_shortest_paths_label
0264             // objects are marked and deleted when popped from
0265             // unprocessed_labels, as they can no longer be deleted at the end
0266             // of the function; only the Splabel object in unprocessed_labels
0267             // still references the r_c_shortest_paths_label object this is also
0268             // for efficiency, because the else branch is executed only if there
0269             // is a chance that extending the label leads to new undominated
0270             // labels, which in turn is possible only if the label to be
0271             // extended is undominated
0272             if (!cur_label->b_is_dominated)
0273             {
0274                 typename boost::graph_traits< Graph >::vertex_descriptor
0275                     i_cur_resident_vertex
0276                     = cur_label->resident_vertex;
0277                 std::list< Splabel >& list_labels_cur_vertex
0278                     = get(vec_vertex_labels, i_cur_resident_vertex);
0279                 if (list_labels_cur_vertex.size() >= 2
0280                     && vec_last_valid_index_for_dominance[i_cur_resident_vertex]
0281                         < list_labels_cur_vertex.size())
0282                 {
0283                     typename std::list< Splabel >::iterator outer_iter
0284                         = list_labels_cur_vertex.begin();
0285                     bool b_outer_iter_at_or_beyond_last_valid_pos_for_dominance
0286                         = false;
0287                     while (outer_iter != list_labels_cur_vertex.end())
0288                     {
0289                         Splabel cur_outer_splabel = *outer_iter;
0290                         typename std::list< Splabel >::iterator inner_iter
0291                             = outer_iter;
0292                         if (!b_outer_iter_at_or_beyond_last_valid_pos_for_dominance
0293                             && outer_iter
0294                                 == get(vec_last_valid_positions_for_dominance,
0295                                     i_cur_resident_vertex))
0296                             b_outer_iter_at_or_beyond_last_valid_pos_for_dominance
0297                                 = true;
0298                         if (!get(b_vec_vertex_already_checked_for_dominance,
0299                                 i_cur_resident_vertex)
0300                             || b_outer_iter_at_or_beyond_last_valid_pos_for_dominance)
0301                         {
0302                             ++inner_iter;
0303                         }
0304                         else
0305                         {
0306                             inner_iter
0307                                 = get(vec_last_valid_positions_for_dominance,
0308                                     i_cur_resident_vertex);
0309                             ++inner_iter;
0310                         }
0311                         bool b_outer_iter_erased = false;
0312                         while (inner_iter != list_labels_cur_vertex.end())
0313                         {
0314                             Splabel cur_inner_splabel = *inner_iter;
0315                             if (dominance(cur_outer_splabel
0316                                               ->cumulated_resource_consumption,
0317                                     cur_inner_splabel
0318                                         ->cumulated_resource_consumption))
0319                             {
0320                                 typename std::list< Splabel >::iterator buf
0321                                     = inner_iter;
0322                                 ++inner_iter;
0323                                 list_labels_cur_vertex.erase(buf);
0324                                 if (cur_inner_splabel->b_is_processed)
0325                                 {
0326                                     cur_inner_splabel.reset();
0327                                 }
0328                                 else
0329                                     cur_inner_splabel->b_is_dominated = true;
0330                                 continue;
0331                             }
0332                             else
0333                                 ++inner_iter;
0334                             if (dominance(cur_inner_splabel
0335                                               ->cumulated_resource_consumption,
0336                                     cur_outer_splabel
0337                                         ->cumulated_resource_consumption))
0338                             {
0339                                 typename std::list< Splabel >::iterator buf
0340                                     = outer_iter;
0341                                 ++outer_iter;
0342                                 list_labels_cur_vertex.erase(buf);
0343                                 b_outer_iter_erased = true;
0344                                 if (cur_outer_splabel->b_is_processed)
0345                                 {
0346                                     cur_outer_splabel.reset();
0347                                 }
0348                                 else
0349                                     cur_outer_splabel->b_is_dominated = true;
0350                                 break;
0351                             }
0352                         }
0353                         if (!b_outer_iter_erased)
0354                             ++outer_iter;
0355                     }
0356                     if (list_labels_cur_vertex.size() > 1)
0357                         put(vec_last_valid_positions_for_dominance,
0358                             i_cur_resident_vertex,
0359                             (--(list_labels_cur_vertex.end())));
0360                     else
0361                         put(vec_last_valid_positions_for_dominance,
0362                             i_cur_resident_vertex,
0363                             list_labels_cur_vertex.begin());
0364                     put(b_vec_vertex_already_checked_for_dominance,
0365                         i_cur_resident_vertex, true);
0366                     put(vec_last_valid_index_for_dominance,
0367                         i_cur_resident_vertex,
0368                         list_labels_cur_vertex.size() - 1);
0369                 }
0370             }
0371             if (!b_all_pareto_optimal_solutions
0372                 && cur_label->resident_vertex == t)
0373             {
0374                 // the devil don't sleep
0375                 if (cur_label->b_is_dominated)
0376                 {
0377                     cur_label.reset();
0378                 }
0379                 while (unprocessed_labels.size())
0380                 {
0381                     Splabel l = unprocessed_labels.top();
0382                     unprocessed_labels.pop();
0383                     // delete only dominated labels, because nondominated labels
0384                     // are deleted at the end of the function
0385                     if (l->b_is_dominated)
0386                     {
0387                         l.reset();
0388                     }
0389                 }
0390                 break;
0391             }
0392             if (!cur_label->b_is_dominated)
0393             {
0394                 cur_label->b_is_processed = true;
0395                 vis.on_label_not_dominated(*cur_label, g);
0396                 typename graph_traits< Graph >::vertex_descriptor cur_vertex
0397                     = cur_label->resident_vertex;
0398                 typename graph_traits< Graph >::out_edge_iterator oei, oei_end;
0399                 for (boost::tie(oei, oei_end) = out_edges(cur_vertex, g);
0400                      oei != oei_end; ++oei)
0401                 {
0402                     b_feasible = true;
0403                     Splabel new_label = boost::allocate_shared<
0404                         r_c_shortest_paths_label< Graph, Resource_Container > >(
0405                         l_alloc, i_label_num++,
0406                         cur_label->cumulated_resource_consumption, cur_label,
0407                         *oei, target(*oei, g));
0408                     b_feasible = ref(g,
0409                         new_label->cumulated_resource_consumption,
0410                         new_label->p_pred_label->cumulated_resource_consumption,
0411                         new_label->pred_edge);
0412
0413                     if (!b_feasible)
0414                     {
0415                         vis.on_label_not_feasible(*new_label, g);
0416                         new_label.reset();
0417                     }
0418                     else
0419                     {
0420                         vis.on_label_feasible(*new_label, g);
0421                         vec_vertex_labels[new_label->resident_vertex].push_back(
0422                             new_label);
0423                         unprocessed_labels.push(new_label);
0424                     }
0425                 }
0426             }
0427             else
0428             {
0429                 vis.on_label_dominated(*cur_label, g);
0430                 cur_label.reset();
0431             }
0432         }
0433         std::list< Splabel > dsplabels = get(vec_vertex_labels, t);
0434         typename std::list< Splabel >::const_iterator csi = dsplabels.begin();
0435         typename std::list< Splabel >::const_iterator csi_end = dsplabels.end();
0436         // if d could be reached from o
0437         if (!dsplabels.empty())
0438         {
0439             for (; csi != csi_end; ++csi)
0440             {
0441                 std::vector< typename graph_traits< Graph >::edge_descriptor >
0442                     cur_pareto_optimal_path;
0443                 boost::shared_ptr<
0444                     r_c_shortest_paths_label< Graph, Resource_Container > >
0445                     p_cur_label = *csi;
0446                 pareto_optimal_resource_containers.push_back(
0447                     p_cur_label->cumulated_resource_consumption);
0448                 while (p_cur_label->num != 0)
0449                 {
0450                     cur_pareto_optimal_path.push_back(p_cur_label->pred_edge);
0451                     p_cur_label = p_cur_label->p_pred_label;
0452
0453                     // assertion b_is_valid beyond this point is not correct if
0454                     // the domination function requires resource levels to be
0455                     // strictly greater than existing values
0456                     //
0457                     // Example
0458                     // Customers
0459                     // id   min_arrival   max_departure
0460                     //  2             0             974
0461                     //  3             0             972
0462                     //  4             0             964
0463                     //  5           678             801
0464                     //
0465                     // Path A: 2-3-4-5 (times: 0-16-49-84-678)
0466                     // Path B: 3-2-4-5 (times: 0-18-51-62-678)
0467                     // The partial path 3-2-4 dominates the other partial path
0468                     // 2-3-4, though the path 3-2-4-5 does not strictly dominate
0469                     // the path 2-3-4-5
0470                 }
0471                 pareto_optimal_solutions.push_back(cur_pareto_optimal_path);
0472                 if (!b_all_pareto_optimal_solutions)
0473                     break;
0474             }
0475         }
0476
0477         BGL_FORALL_VERTICES_T(i, g, Graph)
0478         {
0479             std::list< Splabel >& list_labels_cur_vertex = vec_vertex_labels[i];
0480             typename std::list< Splabel >::iterator si
0481                 = list_labels_cur_vertex.begin();
0482             const typename std::list< Splabel >::iterator si_end
0483                 = list_labels_cur_vertex.end();
0484             for (; si != si_end; ++si)
0485             {
0486                 (*si).reset();
0487             }
0488         }
0489     } // r_c_shortest_paths_dispatch
0490
0491 } // detail
0492
0493 // default_r_c_shortest_paths_visitor struct
0494 struct default_r_c_shortest_paths_visitor
0495 {
0496     template < class Label, class Graph >
0497     void on_label_popped(const Label&, const Graph&)
0498     {
0499     }
0500     template < class Label, class Graph >
0501     void on_label_feasible(const Label&, const Graph&)
0502     {
0503     }
0504     template < class Label, class Graph >
0505     void on_label_not_feasible(const Label&, const Graph&)
0506     {
0507     }
0508     template < class Label, class Graph >
0509     void on_label_dominated(const Label&, const Graph&)
0510     {
0511     }
0512     template < class Label, class Graph >
0513     void on_label_not_dominated(const Label&, const Graph&)
0514     {
0515     }
0516     template < class Queue, class Graph >
0517     bool on_enter_loop(const Queue& queue, const Graph& graph)
0518     {
0519         return true;
0520     }
0521 }; // default_r_c_shortest_paths_visitor
0522
0523 // default_r_c_shortest_paths_allocator
0524 typedef std::allocator< int > default_r_c_shortest_paths_allocator;
0525 // default_r_c_shortest_paths_allocator
0526
0527 // r_c_shortest_paths functions (handle/interface)
0528 // first overload:
0529 // - return all pareto-optimal solutions
0530 // - specify Label_Allocator and Visitor arguments
0531 template < class Graph, class VertexIndexMap, class EdgeIndexMap,
0532     class Resource_Container, class Resource_Extension_Function,
0533     class Dominance_Function, class Label_Allocator, class Visitor >
0534 void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map,
0535     const EdgeIndexMap& edge_index_map,
0536     typename graph_traits< Graph >::vertex_descriptor s,
0537     typename graph_traits< Graph >::vertex_descriptor t,
0538     // each inner vector corresponds to a pareto-optimal path
0539     std::vector<
0540         std::vector< typename graph_traits< Graph >::edge_descriptor > >&
0541         pareto_optimal_solutions,
0542     std::vector< Resource_Container >& pareto_optimal_resource_containers,
0543     // to initialize the first label/resource container
0544     // and to carry the type information
0545     const Resource_Container& rc, const Resource_Extension_Function& ref,
0546     const Dominance_Function& dominance,
0547     // to specify the memory management strategy for the labels
0548     Label_Allocator la, Visitor vis)
0549 {
0550     r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t,
0551         pareto_optimal_solutions, pareto_optimal_resource_containers, true, rc,
0552         ref, dominance, la, vis);
0553 }
0554
0555 // second overload:
0556 // - return only one pareto-optimal solution
0557 // - specify Label_Allocator and Visitor arguments
0558 template < class Graph, class VertexIndexMap, class EdgeIndexMap,
0559     class Resource_Container, class Resource_Extension_Function,
0560     class Dominance_Function, class Label_Allocator, class Visitor >
0561 void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map,
0562     const EdgeIndexMap& edge_index_map,
0563     typename graph_traits< Graph >::vertex_descriptor s,
0564     typename graph_traits< Graph >::vertex_descriptor t,
0565     std::vector< typename graph_traits< Graph >::edge_descriptor >&
0566         pareto_optimal_solution,
0567     Resource_Container& pareto_optimal_resource_container,
0568     // to initialize the first label/resource container
0569     // and to carry the type information
0570     const Resource_Container& rc, const Resource_Extension_Function& ref,
0571     const Dominance_Function& dominance,
0572     // to specify the memory management strategy for the labels
0573     Label_Allocator la, Visitor vis)
0574 {
0575     // each inner vector corresponds to a pareto-optimal path
0576     std::vector<
0577         std::vector< typename graph_traits< Graph >::edge_descriptor > >
0578         pareto_optimal_solutions;
0579     std::vector< Resource_Container > pareto_optimal_resource_containers;
0580     r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t,
0581         pareto_optimal_solutions, pareto_optimal_resource_containers, false, rc,
0582         ref, dominance, la, vis);
0583     if (!pareto_optimal_solutions.empty())
0584     {
0585         pareto_optimal_solution = pareto_optimal_solutions[0];
0586         pareto_optimal_resource_container
0587             = pareto_optimal_resource_containers[0];
0588     }
0589 }
0590
0591 // third overload:
0592 // - return all pareto-optimal solutions
0593 // - use default Label_Allocator and Visitor
0594 template < class Graph, class VertexIndexMap, class EdgeIndexMap,
0595     class Resource_Container, class Resource_Extension_Function,
0596     class Dominance_Function >
0597 void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map,
0598     const EdgeIndexMap& edge_index_map,
0599     typename graph_traits< Graph >::vertex_descriptor s,
0600     typename graph_traits< Graph >::vertex_descriptor t,
0601     // each inner vector corresponds to a pareto-optimal path
0602     std::vector<
0603         std::vector< typename graph_traits< Graph >::edge_descriptor > >&
0604         pareto_optimal_solutions,
0605     std::vector< Resource_Container >& pareto_optimal_resource_containers,
0606     // to initialize the first label/resource container
0607     // and to carry the type information
0608     const Resource_Container& rc, const Resource_Extension_Function& ref,
0609     const Dominance_Function& dominance)
0610 {
0611     r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t,
0612         pareto_optimal_solutions, pareto_optimal_resource_containers, true, rc,
0613         ref, dominance, default_r_c_shortest_paths_allocator(),
0614         default_r_c_shortest_paths_visitor());
0615 }
0616
0617 // fourth overload:
0618 // - return only one pareto-optimal solution
0619 // - use default Label_Allocator and Visitor
0620 template < class Graph, class VertexIndexMap, class EdgeIndexMap,
0621     class Resource_Container, class Resource_Extension_Function,
0622     class Dominance_Function >
0623 void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map,
0624     const EdgeIndexMap& edge_index_map,
0625     typename graph_traits< Graph >::vertex_descriptor s,
0626     typename graph_traits< Graph >::vertex_descriptor t,
0627     std::vector< typename graph_traits< Graph >::edge_descriptor >&
0628         pareto_optimal_solution,
0629     Resource_Container& pareto_optimal_resource_container,
0630     // to initialize the first label/resource container
0631     // and to carry the type information
0632     const Resource_Container& rc, const Resource_Extension_Function& ref,
0633     const Dominance_Function& dominance)
0634 {
0635     // each inner vector corresponds to a pareto-optimal path
0636     std::vector<
0637         std::vector< typename graph_traits< Graph >::edge_descriptor > >
0638         pareto_optimal_solutions;
0639     std::vector< Resource_Container > pareto_optimal_resource_containers;
0640     r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t,
0641         pareto_optimal_solutions, pareto_optimal_resource_containers, false, rc,
0642         ref, dominance, default_r_c_shortest_paths_allocator(),
0643         default_r_c_shortest_paths_visitor());
0644     if (!pareto_optimal_solutions.empty())
0645     {
0646         pareto_optimal_solution = pareto_optimal_solutions[0];
0647         pareto_optimal_resource_container
0648             = pareto_optimal_resource_containers[0];
0649     }
0650 }
0651 // r_c_shortest_paths
0652
0653 // check_r_c_path function
0654 template < class Graph, class Resource_Container,
0655     class Resource_Extension_Function >
0656 void check_r_c_path(const Graph& g,
0657     const std::vector< typename graph_traits< Graph >::edge_descriptor >&
0658         ed_vec_path,
0659     const Resource_Container& initial_resource_levels,
0660     // if true, computed accumulated final resource levels must
0661     // be equal to desired_final_resource_levels
0662     // if false, computed accumulated final resource levels must
0663     // be less than or equal to desired_final_resource_levels
0664     bool b_result_must_be_equal_to_desired_final_resource_levels,
0665     const Resource_Container& desired_final_resource_levels,
0666     Resource_Container& actual_final_resource_levels,
0667     const Resource_Extension_Function& ref, bool& b_is_a_path_at_all,
0668     bool& b_feasible, bool& b_correctly_extended,
0669     typename graph_traits< Graph >::edge_descriptor& ed_last_extended_arc)
0670 {
0671     size_t i_size_ed_vec_path = ed_vec_path.size();
0672     std::vector< typename graph_traits< Graph >::edge_descriptor > buf_path;
0673     if (i_size_ed_vec_path == 0)
0674         b_feasible = true;
0675     else
0676     {
0677         if (i_size_ed_vec_path == 1
0678             || target(ed_vec_path[0], g) == source(ed_vec_path[1], g))
0679             buf_path = ed_vec_path;
0680         else
0681             for (size_t i = i_size_ed_vec_path; i > 0; --i)
0682                 buf_path.push_back(ed_vec_path[i - 1]);
0683         for (size_t i = 0; i < i_size_ed_vec_path - 1; ++i)
0684         {
0685             if (target(buf_path[i], g) != source(buf_path[i + 1], g))
0686             {
0687                 b_is_a_path_at_all = false;
0688                 b_feasible = false;
0689                 b_correctly_extended = false;
0690                 return;
0691             }
0692         }
0693     }
0694     b_is_a_path_at_all = true;
0695     b_feasible = true;
0696     b_correctly_extended = false;
0697     Resource_Container current_resource_levels = initial_resource_levels;
0698     actual_final_resource_levels = current_resource_levels;
0699     for (size_t i = 0; i < i_size_ed_vec_path; ++i)
0700     {
0701         ed_last_extended_arc = buf_path[i];
0702         b_feasible = ref(g, actual_final_resource_levels,
0703             current_resource_levels, buf_path[i]);
0704         current_resource_levels = actual_final_resource_levels;
0705         if (!b_feasible)
0706             return;
0707     }
0708     if (b_result_must_be_equal_to_desired_final_resource_levels)
0709         b_correctly_extended
0710             = actual_final_resource_levels == desired_final_resource_levels
0711             ? true
0712             : false;
0713     else
0714     {
0715         if (actual_final_resource_levels < desired_final_resource_levels
0716             || actual_final_resource_levels == desired_final_resource_levels)
0717             b_correctly_extended = true;
0718     }
0719 } // check_path
0720
0721 } // namespace
0722
0723 #endif // BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP