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         if(!b_all_pareto_optimal_solutions)
0435         {
0436             dsplabels.sort();
0437         }
0438         typename std::list< Splabel >::const_iterator csi = dsplabels.begin();
0439         typename std::list< Splabel >::const_iterator csi_end = dsplabels.end();
0440         // if d could be reached from o
0441         if (!dsplabels.empty())
0442         {
0443             for (; csi != csi_end; ++csi)
0444             {
0445                 std::vector< typename graph_traits< Graph >::edge_descriptor >
0446                     cur_pareto_optimal_path;
0447                 boost::shared_ptr<
0448                     r_c_shortest_paths_label< Graph, Resource_Container > >
0449                     p_cur_label = *csi;
0450                 pareto_optimal_resource_containers.push_back(
0451                     p_cur_label->cumulated_resource_consumption);
0452                 while (p_cur_label->num != 0)
0453                 {
0454                     cur_pareto_optimal_path.push_back(p_cur_label->pred_edge);
0455                     p_cur_label = p_cur_label->p_pred_label;
0456
0457                     // assertion b_is_valid beyond this point is not correct if
0458                     // the domination function requires resource levels to be
0459                     // strictly greater than existing values
0460                     //
0461                     // Example
0462                     // Customers
0463                     // id   min_arrival   max_departure
0464                     //  2             0             974
0465                     //  3             0             972
0466                     //  4             0             964
0467                     //  5           678             801
0468                     //
0469                     // Path A: 2-3-4-5 (times: 0-16-49-84-678)
0470                     // Path B: 3-2-4-5 (times: 0-18-51-62-678)
0471                     // The partial path 3-2-4 dominates the other partial path
0472                     // 2-3-4, though the path 3-2-4-5 does not strictly dominate
0473                     // the path 2-3-4-5
0474                 }
0475                 pareto_optimal_solutions.push_back(cur_pareto_optimal_path);
0476                 if (!b_all_pareto_optimal_solutions)
0477                     break;
0478             }
0479         }
0480
0481         BGL_FORALL_VERTICES_T(i, g, Graph)
0482         {
0483             std::list< Splabel >& list_labels_cur_vertex = vec_vertex_labels[i];
0484             typename std::list< Splabel >::iterator si
0485                 = list_labels_cur_vertex.begin();
0486             const typename std::list< Splabel >::iterator si_end
0487                 = list_labels_cur_vertex.end();
0488             for (; si != si_end; ++si)
0489             {
0490                 (*si).reset();
0491             }
0492         }
0493     } // r_c_shortest_paths_dispatch
0494
0495 } // detail
0496
0497 // default_r_c_shortest_paths_visitor struct
0498 struct default_r_c_shortest_paths_visitor
0499 {
0500     template < class Label, class Graph >
0501     void on_label_popped(const Label&, const Graph&)
0502     {
0503     }
0504     template < class Label, class Graph >
0505     void on_label_feasible(const Label&, const Graph&)
0506     {
0507     }
0508     template < class Label, class Graph >
0509     void on_label_not_feasible(const Label&, const Graph&)
0510     {
0511     }
0512     template < class Label, class Graph >
0513     void on_label_dominated(const Label&, const Graph&)
0514     {
0515     }
0516     template < class Label, class Graph >
0517     void on_label_not_dominated(const Label&, const Graph&)
0518     {
0519     }
0520     template < class Queue, class Graph >
0521     bool on_enter_loop(const Queue& queue, const Graph& graph)
0522     {
0523         return true;
0524     }
0525 }; // default_r_c_shortest_paths_visitor
0526
0527 // default_r_c_shortest_paths_allocator
0528 typedef std::allocator< int > default_r_c_shortest_paths_allocator;
0529 // default_r_c_shortest_paths_allocator
0530
0531 // r_c_shortest_paths functions (handle/interface)
0532 // first overload:
0533 // - return all pareto-optimal solutions
0534 // - specify Label_Allocator and Visitor arguments
0535 template < class Graph, class VertexIndexMap, class EdgeIndexMap,
0536     class Resource_Container, class Resource_Extension_Function,
0537     class Dominance_Function, class Label_Allocator, class Visitor >
0538 void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map,
0539     const EdgeIndexMap& edge_index_map,
0540     typename graph_traits< Graph >::vertex_descriptor s,
0541     typename graph_traits< Graph >::vertex_descriptor t,
0542     // each inner vector corresponds to a pareto-optimal path
0543     std::vector<
0544         std::vector< typename graph_traits< Graph >::edge_descriptor > >&
0545         pareto_optimal_solutions,
0546     std::vector< Resource_Container >& pareto_optimal_resource_containers,
0547     // to initialize the first label/resource container
0548     // and to carry the type information
0549     const Resource_Container& rc, const Resource_Extension_Function& ref,
0550     const Dominance_Function& dominance,
0551     // to specify the memory management strategy for the labels
0552     Label_Allocator la, Visitor vis)
0553 {
0554     r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t,
0555         pareto_optimal_solutions, pareto_optimal_resource_containers, true, rc,
0556         ref, dominance, la, vis);
0557 }
0558
0559 // second overload:
0560 // - return only one pareto-optimal solution
0561 // - specify Label_Allocator and Visitor arguments
0562 template < class Graph, class VertexIndexMap, class EdgeIndexMap,
0563     class Resource_Container, class Resource_Extension_Function,
0564     class Dominance_Function, class Label_Allocator, class Visitor >
0565 void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map,
0566     const EdgeIndexMap& edge_index_map,
0567     typename graph_traits< Graph >::vertex_descriptor s,
0568     typename graph_traits< Graph >::vertex_descriptor t,
0569     std::vector< typename graph_traits< Graph >::edge_descriptor >&
0570         pareto_optimal_solution,
0571     Resource_Container& pareto_optimal_resource_container,
0572     // to initialize the first label/resource container
0573     // and to carry the type information
0574     const Resource_Container& rc, const Resource_Extension_Function& ref,
0575     const Dominance_Function& dominance,
0576     // to specify the memory management strategy for the labels
0577     Label_Allocator la, Visitor vis)
0578 {
0579     // each inner vector corresponds to a pareto-optimal path
0580     std::vector<
0581         std::vector< typename graph_traits< Graph >::edge_descriptor > >
0582         pareto_optimal_solutions;
0583     std::vector< Resource_Container > pareto_optimal_resource_containers;
0584     r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t,
0585         pareto_optimal_solutions, pareto_optimal_resource_containers, false, rc,
0586         ref, dominance, la, vis);
0587     if (!pareto_optimal_solutions.empty())
0588     {
0589         pareto_optimal_solution = pareto_optimal_solutions[0];
0590         pareto_optimal_resource_container
0591             = pareto_optimal_resource_containers[0];
0592     }
0593 }
0594
0595 // third overload:
0596 // - return all pareto-optimal solutions
0597 // - use default Label_Allocator and Visitor
0598 template < class Graph, class VertexIndexMap, class EdgeIndexMap,
0599     class Resource_Container, class Resource_Extension_Function,
0600     class Dominance_Function >
0601 void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map,
0602     const EdgeIndexMap& edge_index_map,
0603     typename graph_traits< Graph >::vertex_descriptor s,
0604     typename graph_traits< Graph >::vertex_descriptor t,
0605     // each inner vector corresponds to a pareto-optimal path
0606     std::vector<
0607         std::vector< typename graph_traits< Graph >::edge_descriptor > >&
0608         pareto_optimal_solutions,
0609     std::vector< Resource_Container >& pareto_optimal_resource_containers,
0610     // to initialize the first label/resource container
0611     // and to carry the type information
0612     const Resource_Container& rc, const Resource_Extension_Function& ref,
0613     const Dominance_Function& dominance)
0614 {
0615     r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t,
0616         pareto_optimal_solutions, pareto_optimal_resource_containers, true, rc,
0617         ref, dominance, default_r_c_shortest_paths_allocator(),
0618         default_r_c_shortest_paths_visitor());
0619 }
0620
0621 // fourth overload:
0622 // - return only one pareto-optimal solution
0623 // - use default Label_Allocator and Visitor
0624 template < class Graph, class VertexIndexMap, class EdgeIndexMap,
0625     class Resource_Container, class Resource_Extension_Function,
0626     class Dominance_Function >
0627 void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map,
0628     const EdgeIndexMap& edge_index_map,
0629     typename graph_traits< Graph >::vertex_descriptor s,
0630     typename graph_traits< Graph >::vertex_descriptor t,
0631     std::vector< typename graph_traits< Graph >::edge_descriptor >&
0632         pareto_optimal_solution,
0633     Resource_Container& pareto_optimal_resource_container,
0634     // to initialize the first label/resource container
0635     // and to carry the type information
0636     const Resource_Container& rc, const Resource_Extension_Function& ref,
0637     const Dominance_Function& dominance)
0638 {
0639     // each inner vector corresponds to a pareto-optimal path
0640     std::vector<
0641         std::vector< typename graph_traits< Graph >::edge_descriptor > >
0642         pareto_optimal_solutions;
0643     std::vector< Resource_Container > pareto_optimal_resource_containers;
0644     r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t,
0645         pareto_optimal_solutions, pareto_optimal_resource_containers, false, rc,
0646         ref, dominance, default_r_c_shortest_paths_allocator(),
0647         default_r_c_shortest_paths_visitor());
0648     if (!pareto_optimal_solutions.empty())
0649     {
0650         pareto_optimal_solution = pareto_optimal_solutions[0];
0651         pareto_optimal_resource_container
0652             = pareto_optimal_resource_containers[0];
0653     }
0654 }
0655 // r_c_shortest_paths
0656
0657 // check_r_c_path function
0658 template < class Graph, class Resource_Container,
0659     class Resource_Extension_Function >
0660 void check_r_c_path(const Graph& g,
0661     const std::vector< typename graph_traits< Graph >::edge_descriptor >&
0662         ed_vec_path,
0663     const Resource_Container& initial_resource_levels,
0664     // if true, computed accumulated final resource levels must
0665     // be equal to desired_final_resource_levels
0666     // if false, computed accumulated final resource levels must
0667     // be less than or equal to desired_final_resource_levels
0668     bool b_result_must_be_equal_to_desired_final_resource_levels,
0669     const Resource_Container& desired_final_resource_levels,
0670     Resource_Container& actual_final_resource_levels,
0671     const Resource_Extension_Function& ref, bool& b_is_a_path_at_all,
0672     bool& b_feasible, bool& b_correctly_extended,
0673     typename graph_traits< Graph >::edge_descriptor& ed_last_extended_arc)
0674 {
0675     size_t i_size_ed_vec_path = ed_vec_path.size();
0676     std::vector< typename graph_traits< Graph >::edge_descriptor > buf_path;
0677     if (i_size_ed_vec_path == 0)
0678         b_feasible = true;
0679     else
0680     {
0681         if (i_size_ed_vec_path == 1
0682             || target(ed_vec_path[0], g) == source(ed_vec_path[1], g))
0683             buf_path = ed_vec_path;
0684         else
0685             for (size_t i = i_size_ed_vec_path; i > 0; --i)
0686                 buf_path.push_back(ed_vec_path[i - 1]);
0687         for (size_t i = 0; i < i_size_ed_vec_path - 1; ++i)
0688         {
0689             if (target(buf_path[i], g) != source(buf_path[i + 1], g))
0690             {
0691                 b_is_a_path_at_all = false;
0692                 b_feasible = false;
0693                 b_correctly_extended = false;
0694                 return;
0695             }
0696         }
0697     }
0698     b_is_a_path_at_all = true;
0699     b_feasible = true;
0700     b_correctly_extended = false;
0701     Resource_Container current_resource_levels = initial_resource_levels;
0702     actual_final_resource_levels = current_resource_levels;
0703     for (size_t i = 0; i < i_size_ed_vec_path; ++i)
0704     {
0705         ed_last_extended_arc = buf_path[i];
0706         b_feasible = ref(g, actual_final_resource_levels,
0707             current_resource_levels, buf_path[i]);
0708         current_resource_levels = actual_final_resource_levels;
0709         if (!b_feasible)
0710             return;
0711     }
0712     if (b_result_must_be_equal_to_desired_final_resource_levels)
0713         b_correctly_extended
0714             = actual_final_resource_levels == desired_final_resource_levels
0715             ? true
0716             : false;
0717     else
0718     {
0719         if (actual_final_resource_levels < desired_final_resource_levels
0720             || actual_final_resource_levels == desired_final_resource_levels)
0721             b_correctly_extended = true;
0722     }
0723 } // check_path
0724
0725 } // namespace
0726
0727 #endif // BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP