Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:37:22 

0001 
0002 
0003 //
0004 //=======================================================================
0005 // Copyright (c) 2004 Kristopher Beevers
0006 //
0007 // Distributed under the Boost Software License, Version 1.0. (See
0008 // accompanying file LICENSE_1_0.txt or copy at
0009 // http://www.boost.org/LICENSE_1_0.txt)
0010 //=======================================================================
0011 //
0012 
0013 #ifndef BOOST_GRAPH_ASTAR_SEARCH_HPP
0014 #define BOOST_GRAPH_ASTAR_SEARCH_HPP
0015 
0016 #include <functional>
0017 #include <vector>
0018 #include <boost/limits.hpp>
0019 #include <boost/throw_exception.hpp>
0020 #include <boost/graph/named_function_params.hpp>
0021 #include <boost/graph/relax.hpp>
0022 #include <boost/graph/exception.hpp>
0023 #include <boost/graph/breadth_first_search.hpp>
0024 #include <boost/graph/iteration_macros.hpp>
0025 #include <boost/graph/detail/d_ary_heap.hpp>
0026 #include <boost/graph/property_maps/constant_property_map.hpp>
0027 #include <boost/property_map/property_map.hpp>
0028 #include <boost/property_map/vector_property_map.hpp>
0029 #include <boost/property_map/function_property_map.hpp>
0030 #include <boost/concept/assert.hpp>
0031 
0032 namespace boost
0033 {
0034 
0035 template < class Heuristic, class Graph > struct AStarHeuristicConcept
0036 {
0037     void constraints()
0038     {
0039         BOOST_CONCEPT_ASSERT((CopyConstructibleConcept< Heuristic >));
0040         h(u);
0041     }
0042     Heuristic h;
0043     typename graph_traits< Graph >::vertex_descriptor u;
0044 };
0045 
0046 template < class Graph, class CostType > class astar_heuristic
0047 {
0048 public:
0049     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0050     typedef Vertex argument_type;
0051     typedef CostType result_type;
0052     astar_heuristic() {}
0053     CostType operator()(Vertex u) { return static_cast< CostType >(0); }
0054 };
0055 
0056 template < class Visitor, class Graph > struct AStarVisitorConcept
0057 {
0058     void constraints()
0059     {
0060         BOOST_CONCEPT_ASSERT((CopyConstructibleConcept< Visitor >));
0061         vis.initialize_vertex(u, g);
0062         vis.discover_vertex(u, g);
0063         vis.examine_vertex(u, g);
0064         vis.examine_edge(e, g);
0065         vis.edge_relaxed(e, g);
0066         vis.edge_not_relaxed(e, g);
0067         vis.black_target(e, g);
0068         vis.finish_vertex(u, g);
0069     }
0070     Visitor vis;
0071     Graph g;
0072     typename graph_traits< Graph >::vertex_descriptor u;
0073     typename graph_traits< Graph >::edge_descriptor e;
0074 };
0075 
0076 template < class Visitors = null_visitor >
0077 class astar_visitor : public bfs_visitor< Visitors >
0078 {
0079 public:
0080     astar_visitor() {}
0081     astar_visitor(Visitors vis) : bfs_visitor< Visitors >(vis) {}
0082 
0083     template < class Edge, class Graph >
0084     void edge_relaxed(Edge e, const Graph& g)
0085     {
0086         invoke_visitors(this->m_vis, e, g, on_edge_relaxed());
0087     }
0088     template < class Edge, class Graph >
0089     void edge_not_relaxed(Edge e, const Graph& g)
0090     {
0091         invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());
0092     }
0093 
0094 private:
0095     template < class Edge, class Graph > void tree_edge(Edge e, const Graph& g)
0096     {
0097     }
0098     template < class Edge, class Graph >
0099     void non_tree_edge(Edge e, const Graph& g)
0100     {
0101     }
0102 };
0103 template < class Visitors >
0104 astar_visitor< Visitors > make_astar_visitor(Visitors vis)
0105 {
0106     return astar_visitor< Visitors >(vis);
0107 }
0108 typedef astar_visitor<> default_astar_visitor;
0109 
0110 namespace detail
0111 {
0112 
0113     template < class AStarHeuristic, class UniformCostVisitor,
0114         class UpdatableQueue, class PredecessorMap, class CostMap,
0115         class DistanceMap, class WeightMap, class ColorMap,
0116         class BinaryFunction, class BinaryPredicate >
0117     struct astar_bfs_visitor
0118     {
0119 
0120         typedef typename property_traits< CostMap >::value_type C;
0121         typedef typename property_traits< ColorMap >::value_type ColorValue;
0122         typedef color_traits< ColorValue > Color;
0123         typedef
0124             typename property_traits< DistanceMap >::value_type distance_type;
0125 
0126         astar_bfs_visitor(AStarHeuristic h, UniformCostVisitor vis,
0127             UpdatableQueue& Q, PredecessorMap p, CostMap c, DistanceMap d,
0128             WeightMap w, ColorMap col, BinaryFunction combine,
0129             BinaryPredicate compare, C zero)
0130         : m_h(h)
0131         , m_vis(vis)
0132         , m_Q(Q)
0133         , m_predecessor(p)
0134         , m_cost(c)
0135         , m_distance(d)
0136         , m_weight(w)
0137         , m_color(col)
0138         , m_combine(combine)
0139         , m_compare(compare)
0140         , m_zero(zero)
0141         {
0142         }
0143 
0144         template < class Vertex, class Graph >
0145         void initialize_vertex(Vertex u, const Graph& g)
0146         {
0147             m_vis.initialize_vertex(u, g);
0148         }
0149         template < class Vertex, class Graph >
0150         void discover_vertex(Vertex u, const Graph& g)
0151         {
0152             m_vis.discover_vertex(u, g);
0153         }
0154         template < class Vertex, class Graph >
0155         void examine_vertex(Vertex u, const Graph& g)
0156         {
0157             m_vis.examine_vertex(u, g);
0158         }
0159         template < class Vertex, class Graph >
0160         void finish_vertex(Vertex u, const Graph& g)
0161         {
0162             m_vis.finish_vertex(u, g);
0163         }
0164         template < class Edge, class Graph >
0165         void examine_edge(Edge e, const Graph& g)
0166         {
0167             if (m_compare(get(m_weight, e), m_zero))
0168                 BOOST_THROW_EXCEPTION(negative_edge());
0169             m_vis.examine_edge(e, g);
0170         }
0171         template < class Edge, class Graph >
0172         void non_tree_edge(Edge, const Graph&)
0173         {
0174         }
0175 
0176         template < class Edge, class Graph >
0177         void tree_edge(Edge e, const Graph& g)
0178         {
0179             using boost::get;
0180             bool m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
0181                 m_combine, m_compare);
0182 
0183             if (m_decreased)
0184             {
0185                 m_vis.edge_relaxed(e, g);
0186                 put(m_cost, target(e, g),
0187                     m_combine(
0188                         get(m_distance, target(e, g)), m_h(target(e, g))));
0189             }
0190             else
0191                 m_vis.edge_not_relaxed(e, g);
0192         }
0193 
0194         template < class Edge, class Graph >
0195         void gray_target(Edge e, const Graph& g)
0196         {
0197             using boost::get;
0198             bool m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
0199                 m_combine, m_compare);
0200 
0201             if (m_decreased)
0202             {
0203                 put(m_cost, target(e, g),
0204                     m_combine(
0205                         get(m_distance, target(e, g)), m_h(target(e, g))));
0206                 m_Q.update(target(e, g));
0207                 m_vis.edge_relaxed(e, g);
0208             }
0209             else
0210                 m_vis.edge_not_relaxed(e, g);
0211         }
0212 
0213         template < class Edge, class Graph >
0214         void black_target(Edge e, const Graph& g)
0215         {
0216             using boost::get;
0217             bool m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
0218                 m_combine, m_compare);
0219 
0220             if (m_decreased)
0221             {
0222                 m_vis.edge_relaxed(e, g);
0223                 put(m_cost, target(e, g),
0224                     m_combine(
0225                         get(m_distance, target(e, g)), m_h(target(e, g))));
0226                 m_Q.push(target(e, g));
0227                 put(m_color, target(e, g), Color::gray());
0228                 m_vis.black_target(e, g);
0229             }
0230             else
0231                 m_vis.edge_not_relaxed(e, g);
0232         }
0233 
0234         AStarHeuristic m_h;
0235         UniformCostVisitor m_vis;
0236         UpdatableQueue& m_Q;
0237         PredecessorMap m_predecessor;
0238         CostMap m_cost;
0239         DistanceMap m_distance;
0240         WeightMap m_weight;
0241         ColorMap m_color;
0242         BinaryFunction m_combine;
0243         BinaryPredicate m_compare;
0244         C m_zero;
0245     };
0246 
0247 } // namespace detail
0248 
0249 template < typename VertexListGraph, typename AStarHeuristic,
0250     typename AStarVisitor, typename PredecessorMap, typename CostMap,
0251     typename DistanceMap, typename WeightMap, typename ColorMap,
0252     typename VertexIndexMap, typename CompareFunction, typename CombineFunction,
0253     typename CostInf, typename CostZero >
0254 inline void astar_search_no_init(const VertexListGraph& g,
0255     typename graph_traits< VertexListGraph >::vertex_descriptor s,
0256     AStarHeuristic h, AStarVisitor vis, PredecessorMap predecessor,
0257     CostMap cost, DistanceMap distance, WeightMap weight, ColorMap color,
0258     VertexIndexMap index_map, CompareFunction compare, CombineFunction combine,
0259     CostInf /*inf*/, CostZero zero)
0260 {
0261     typedef typename graph_traits< VertexListGraph >::vertex_descriptor Vertex;
0262     typedef boost::vector_property_map< std::size_t, VertexIndexMap >
0263         IndexInHeapMap;
0264     IndexInHeapMap index_in_heap(index_map);
0265     typedef d_ary_heap_indirect< Vertex, 4, IndexInHeapMap, CostMap,
0266         CompareFunction >
0267         MutableQueue;
0268     MutableQueue Q(cost, index_in_heap, compare);
0269 
0270     detail::astar_bfs_visitor< AStarHeuristic, AStarVisitor, MutableQueue,
0271         PredecessorMap, CostMap, DistanceMap, WeightMap, ColorMap,
0272         CombineFunction, CompareFunction >
0273         bfs_vis(h, vis, Q, predecessor, cost, distance, weight, color, combine,
0274             compare, zero);
0275 
0276     breadth_first_visit(g, s, Q, bfs_vis, color);
0277 }
0278 
0279 namespace graph_detail
0280 {
0281     template < typename A, typename B > struct select1st
0282     {
0283         typedef std::pair< A, B > argument_type;
0284         typedef A result_type;
0285         A operator()(const std::pair< A, B >& p) const { return p.first; }
0286     };
0287 }
0288 
0289 template < typename VertexListGraph, typename AStarHeuristic,
0290     typename AStarVisitor, typename PredecessorMap, typename CostMap,
0291     typename DistanceMap, typename WeightMap, typename CompareFunction,
0292     typename CombineFunction, typename CostInf, typename CostZero >
0293 inline void astar_search_no_init_tree(const VertexListGraph& g,
0294     typename graph_traits< VertexListGraph >::vertex_descriptor s,
0295     AStarHeuristic h, AStarVisitor vis, PredecessorMap predecessor,
0296     CostMap cost, DistanceMap distance, WeightMap weight,
0297     CompareFunction compare, CombineFunction combine, CostInf /*inf*/,
0298     CostZero zero)
0299 {
0300     typedef typename graph_traits< VertexListGraph >::vertex_descriptor Vertex;
0301     typedef typename property_traits< DistanceMap >::value_type Distance;
0302     typedef d_ary_heap_indirect< std::pair< Distance, Vertex >, 4,
0303         null_property_map< std::pair< Distance, Vertex >, std::size_t >,
0304         function_property_map< graph_detail::select1st< Distance, Vertex >,
0305             std::pair< Distance, Vertex > >,
0306         CompareFunction >
0307         MutableQueue;
0308     MutableQueue Q(make_function_property_map< std::pair< Distance, Vertex > >(
0309                        graph_detail::select1st< Distance, Vertex >()),
0310         null_property_map< std::pair< Distance, Vertex >, std::size_t >(),
0311         compare);
0312 
0313     vis.discover_vertex(s, g);
0314     Q.push(std::make_pair(get(cost, s), s));
0315     while (!Q.empty())
0316     {
0317         Vertex v;
0318         Distance v_rank;
0319         boost::tie(v_rank, v) = Q.top();
0320         Q.pop();
0321         vis.examine_vertex(v, g);
0322         BGL_FORALL_OUTEDGES_T(v, e, g, VertexListGraph)
0323         {
0324             Vertex w = target(e, g);
0325             vis.examine_edge(e, g);
0326             Distance e_weight = get(weight, e);
0327             if (compare(e_weight, zero))
0328                 BOOST_THROW_EXCEPTION(negative_edge());
0329             bool decreased
0330                 = relax(e, g, weight, predecessor, distance, combine, compare);
0331             if (decreased)
0332             {
0333                 vis.edge_relaxed(e, g);
0334                 Distance w_rank = combine(get(distance, w), h(w));
0335                 put(cost, w, w_rank);
0336                 vis.discover_vertex(w, g);
0337                 Q.push(std::make_pair(w_rank, w));
0338             }
0339             else
0340             {
0341                 vis.edge_not_relaxed(e, g);
0342             }
0343         }
0344         vis.finish_vertex(v, g);
0345     }
0346 }
0347 
0348 // Non-named parameter interface
0349 template < typename VertexListGraph, typename AStarHeuristic,
0350     typename AStarVisitor, typename PredecessorMap, typename CostMap,
0351     typename DistanceMap, typename WeightMap, typename VertexIndexMap,
0352     typename ColorMap, typename CompareFunction, typename CombineFunction,
0353     typename CostInf, typename CostZero >
0354 inline void astar_search(const VertexListGraph& g,
0355     typename graph_traits< VertexListGraph >::vertex_descriptor s,
0356     AStarHeuristic h, AStarVisitor vis, PredecessorMap predecessor,
0357     CostMap cost, DistanceMap distance, WeightMap weight,
0358     VertexIndexMap index_map, ColorMap color, CompareFunction compare,
0359     CombineFunction combine, CostInf inf, CostZero zero)
0360 {
0361 
0362     typedef typename property_traits< ColorMap >::value_type ColorValue;
0363     typedef color_traits< ColorValue > Color;
0364     typename graph_traits< VertexListGraph >::vertex_iterator ui, ui_end;
0365     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
0366     {
0367         put(color, *ui, Color::white());
0368         put(distance, *ui, inf);
0369         put(cost, *ui, inf);
0370         put(predecessor, *ui, *ui);
0371         vis.initialize_vertex(*ui, g);
0372     }
0373     put(distance, s, zero);
0374     put(cost, s, h(s));
0375 
0376     astar_search_no_init(g, s, h, vis, predecessor, cost, distance, weight,
0377         color, index_map, compare, combine, inf, zero);
0378 }
0379 
0380 // Non-named parameter interface
0381 template < typename VertexListGraph, typename AStarHeuristic,
0382     typename AStarVisitor, typename PredecessorMap, typename CostMap,
0383     typename DistanceMap, typename WeightMap, typename CompareFunction,
0384     typename CombineFunction, typename CostInf, typename CostZero >
0385 inline void astar_search_tree(const VertexListGraph& g,
0386     typename graph_traits< VertexListGraph >::vertex_descriptor s,
0387     AStarHeuristic h, AStarVisitor vis, PredecessorMap predecessor,
0388     CostMap cost, DistanceMap distance, WeightMap weight,
0389     CompareFunction compare, CombineFunction combine, CostInf inf,
0390     CostZero zero)
0391 {
0392 
0393     typename graph_traits< VertexListGraph >::vertex_iterator ui, ui_end;
0394     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
0395     {
0396         put(distance, *ui, inf);
0397         put(cost, *ui, inf);
0398         put(predecessor, *ui, *ui);
0399         vis.initialize_vertex(*ui, g);
0400     }
0401     put(distance, s, zero);
0402     put(cost, s, h(s));
0403 
0404     astar_search_no_init_tree(g, s, h, vis, predecessor, cost, distance, weight,
0405         compare, combine, inf, zero);
0406 }
0407 
0408 // Named parameter interfaces
0409 template < typename VertexListGraph, typename AStarHeuristic, typename P,
0410     typename T, typename R >
0411 void astar_search(const VertexListGraph& g,
0412     typename graph_traits< VertexListGraph >::vertex_descriptor s,
0413     AStarHeuristic h, const bgl_named_params< P, T, R >& params)
0414 {
0415     using namespace boost::graph::keywords;
0416     typedef bgl_named_params< P, T, R > params_type;
0417     BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
0418 
0419     // Distance type is the value type of the distance map if there is one,
0420     // otherwise the value type of the weight map.
0421     typedef
0422         typename boost::detail::override_const_property_result< arg_pack_type,
0423             boost::graph::keywords::tag::weight_map, edge_weight_t,
0424             VertexListGraph >::type weight_map_type;
0425     typedef typename boost::property_traits< weight_map_type >::value_type D;
0426     const D inf = arg_pack[_distance_inf || detail::get_max< D >()];
0427     const D zero_actual = D();
0428     const D zero_d = arg_pack[_distance_zero | zero_actual];
0429     null_visitor null_vis;
0430     astar_visitor< null_visitor > default_visitor(null_vis);
0431     typename boost::parameter::binding< arg_pack_type,
0432         boost::graph::keywords::tag::visitor, dummy_property_map& >::type vis
0433         = arg_pack[_visitor | default_visitor];
0434     dummy_property_map dummy_prop;
0435     typename boost::parameter::binding< arg_pack_type,
0436         boost::graph::keywords::tag::predecessor_map,
0437         dummy_property_map& >::type pred_map
0438         = arg_pack[_predecessor_map | dummy_prop];
0439     boost::detail::make_property_map_from_arg_pack_gen<
0440         boost::graph::keywords::tag::rank_map, D >
0441         rank_map_gen(zero_actual);
0442     typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
0443         boost::graph::keywords::tag::rank_map, D >::map_type r_map
0444         = rank_map_gen(g, arg_pack);
0445     boost::detail::make_property_map_from_arg_pack_gen<
0446         boost::graph::keywords::tag::distance_map, D >
0447         dist_map_gen(zero_actual);
0448     typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
0449         boost::graph::keywords::tag::distance_map, D >::map_type dist_map
0450         = dist_map_gen(g, arg_pack);
0451     weight_map_type w_map = detail::override_const_property(
0452         arg_pack, _weight_map, g, edge_weight);
0453     typename boost::detail::override_const_property_result< arg_pack_type,
0454         boost::graph::keywords::tag::vertex_index_map, vertex_index_t,
0455         VertexListGraph >::type v_i_map
0456         = detail::override_const_property(
0457             arg_pack, _vertex_index_map, g, vertex_index);
0458     typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
0459         boost::graph::keywords::tag::color_map,
0460         boost::default_color_type >::map_type c_map
0461         = boost::detail::make_color_map_from_arg_pack(g, arg_pack);
0462     std::less< D > default_compare;
0463     typename boost::parameter::binding< arg_pack_type,
0464         boost::graph::keywords::tag::distance_compare, std::less< D >& >::type
0465         dist_comp
0466         = arg_pack[_distance_compare | default_compare];
0467     closed_plus< D > default_combine(inf);
0468     typename boost::parameter::binding< arg_pack_type,
0469         boost::graph::keywords::tag::distance_combine, closed_plus< D >& >::type
0470         dist_comb
0471         = arg_pack[_distance_combine | default_combine];
0472     astar_search(g, s, h, vis, pred_map, r_map, dist_map, w_map, v_i_map, c_map,
0473         dist_comp, dist_comb, inf, zero_d);
0474 }
0475 
0476 template < typename VertexListGraph, typename AStarHeuristic, typename P,
0477     typename T, typename R >
0478 void astar_search_tree(const VertexListGraph& g,
0479     typename graph_traits< VertexListGraph >::vertex_descriptor s,
0480     AStarHeuristic h, const bgl_named_params< P, T, R >& params)
0481 {
0482     using namespace boost::graph::keywords;
0483     typedef bgl_named_params< P, T, R > params_type;
0484     BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
0485 
0486     // Distance type is the value type of the distance map if there is one,
0487     // otherwise the value type of the weight map.
0488     typedef
0489         typename boost::detail::override_const_property_result< arg_pack_type,
0490             boost::graph::keywords::tag::weight_map, edge_weight_t,
0491             VertexListGraph >::type weight_map_type;
0492     typedef typename boost::property_traits< weight_map_type >::value_type D;
0493     const D inf = arg_pack[_distance_inf || detail::get_max< D >()];
0494     const D zero_actual = D();
0495     const D zero_d = arg_pack[_distance_zero | zero_actual];
0496     null_visitor null_vis;
0497     astar_visitor< null_visitor > default_visitor(null_vis);
0498     typename boost::parameter::binding< arg_pack_type,
0499         boost::graph::keywords::tag::visitor, dummy_property_map& >::type vis
0500         = arg_pack[_visitor | default_visitor];
0501     dummy_property_map dummy_prop;
0502     typename boost::parameter::binding< arg_pack_type,
0503         boost::graph::keywords::tag::predecessor_map,
0504         dummy_property_map& >::type pred_map
0505         = arg_pack[_predecessor_map | dummy_prop];
0506     boost::detail::make_property_map_from_arg_pack_gen<
0507         boost::graph::keywords::tag::rank_map, D >
0508         rank_map_gen(zero_actual);
0509     typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
0510         boost::graph::keywords::tag::rank_map, D >::map_type r_map
0511         = rank_map_gen(g, arg_pack);
0512     boost::detail::make_property_map_from_arg_pack_gen<
0513         boost::graph::keywords::tag::distance_map, D >
0514         dist_map_gen(zero_actual);
0515     typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
0516         boost::graph::keywords::tag::distance_map, D >::map_type dist_map
0517         = dist_map_gen(g, arg_pack);
0518     weight_map_type w_map = detail::override_const_property(
0519         arg_pack, _weight_map, g, edge_weight);
0520     std::less< D > default_compare;
0521     typename boost::parameter::binding< arg_pack_type,
0522         boost::graph::keywords::tag::distance_compare, std::less< D >& >::type
0523         dist_comp
0524         = arg_pack[_distance_compare | default_compare];
0525     closed_plus< D > default_combine(inf);
0526     typename boost::parameter::binding< arg_pack_type,
0527         boost::graph::keywords::tag::distance_combine, closed_plus< D >& >::type
0528         dist_comb
0529         = arg_pack[_distance_combine | default_combine];
0530     astar_search_tree(g, s, h, vis, pred_map, r_map, dist_map, w_map, dist_comp,
0531         dist_comb, inf, zero_d);
0532 }
0533 
0534 template < typename VertexListGraph, typename AStarHeuristic, typename P,
0535     typename T, typename R >
0536 void astar_search_no_init(const VertexListGraph& g,
0537     typename graph_traits< VertexListGraph >::vertex_descriptor s,
0538     AStarHeuristic h, const bgl_named_params< P, T, R >& params)
0539 {
0540     using namespace boost::graph::keywords;
0541     typedef bgl_named_params< P, T, R > params_type;
0542     BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
0543     typedef
0544         typename boost::detail::override_const_property_result< arg_pack_type,
0545             boost::graph::keywords::tag::weight_map, edge_weight_t,
0546             VertexListGraph >::type weight_map_type;
0547     typedef typename boost::property_traits< weight_map_type >::value_type D;
0548     const D inf = arg_pack[_distance_inf || detail::get_max< D >()];
0549     const D zero_actual = D();
0550     const D zero_d = arg_pack[_distance_zero | zero_actual];
0551     null_visitor null_vis;
0552     astar_visitor< null_visitor > default_visitor(null_vis);
0553     typename boost::parameter::binding< arg_pack_type,
0554         boost::graph::keywords::tag::visitor, dummy_property_map& >::type vis
0555         = arg_pack[_visitor | default_visitor];
0556     dummy_property_map dummy_prop;
0557     typename boost::parameter::binding< arg_pack_type,
0558         boost::graph::keywords::tag::predecessor_map,
0559         dummy_property_map& >::type pred_map
0560         = arg_pack[_predecessor_map | dummy_prop];
0561     boost::detail::make_property_map_from_arg_pack_gen<
0562         boost::graph::keywords::tag::rank_map, D >
0563         rank_map_gen(zero_actual);
0564     typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
0565         boost::graph::keywords::tag::rank_map, D >::map_type r_map
0566         = rank_map_gen(g, arg_pack);
0567     boost::detail::make_property_map_from_arg_pack_gen<
0568         boost::graph::keywords::tag::distance_map, D >
0569         dist_map_gen(zero_actual);
0570     typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
0571         boost::graph::keywords::tag::distance_map, D >::map_type dist_map
0572         = dist_map_gen(g, arg_pack);
0573     weight_map_type w_map = detail::override_const_property(
0574         arg_pack, _weight_map, g, edge_weight);
0575     typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
0576         boost::graph::keywords::tag::color_map,
0577         boost::default_color_type >::map_type c_map
0578         = boost::detail::make_color_map_from_arg_pack(g, arg_pack);
0579     typename boost::detail::override_const_property_result< arg_pack_type,
0580         boost::graph::keywords::tag::vertex_index_map, vertex_index_t,
0581         VertexListGraph >::type v_i_map
0582         = detail::override_const_property(
0583             arg_pack, _vertex_index_map, g, vertex_index);
0584     std::less< D > default_compare;
0585     typename boost::parameter::binding< arg_pack_type,
0586         boost::graph::keywords::tag::distance_compare, std::less< D >& >::type
0587         dist_comp
0588         = arg_pack[_distance_compare | default_compare];
0589     closed_plus< D > default_combine(inf);
0590     typename boost::parameter::binding< arg_pack_type,
0591         boost::graph::keywords::tag::distance_combine, closed_plus< D >& >::type
0592         dist_comb
0593         = arg_pack[_distance_combine | default_combine];
0594     astar_search_no_init(g, s, h, vis, pred_map, r_map, dist_map, w_map, c_map,
0595         v_i_map, dist_comp, dist_comb, inf, zero_d);
0596 }
0597 
0598 template < typename VertexListGraph, typename AStarHeuristic, typename P,
0599     typename T, typename R >
0600 void astar_search_no_init_tree(const VertexListGraph& g,
0601     typename graph_traits< VertexListGraph >::vertex_descriptor s,
0602     AStarHeuristic h, const bgl_named_params< P, T, R >& params)
0603 {
0604     using namespace boost::graph::keywords;
0605     typedef bgl_named_params< P, T, R > params_type;
0606     BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
0607     typedef
0608         typename boost::detail::override_const_property_result< arg_pack_type,
0609             boost::graph::keywords::tag::weight_map, edge_weight_t,
0610             VertexListGraph >::type weight_map_type;
0611     typedef typename boost::property_traits< weight_map_type >::value_type D;
0612     const D inf = arg_pack[_distance_inf || detail::get_max< D >()];
0613     const D zero_actual = D();
0614     const D zero_d = arg_pack[_distance_zero | zero_actual];
0615     null_visitor null_vis;
0616     astar_visitor< null_visitor > default_visitor(null_vis);
0617     typename boost::parameter::binding< arg_pack_type,
0618         boost::graph::keywords::tag::visitor, dummy_property_map& >::type vis
0619         = arg_pack[_visitor | default_visitor];
0620     dummy_property_map dummy_prop;
0621     typename boost::parameter::binding< arg_pack_type,
0622         boost::graph::keywords::tag::predecessor_map,
0623         dummy_property_map& >::type pred_map
0624         = arg_pack[_predecessor_map | dummy_prop];
0625     boost::detail::make_property_map_from_arg_pack_gen<
0626         boost::graph::keywords::tag::rank_map, D >
0627         rank_map_gen(zero_actual);
0628     typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
0629         boost::graph::keywords::tag::rank_map, D >::map_type r_map
0630         = rank_map_gen(g, arg_pack);
0631     boost::detail::make_property_map_from_arg_pack_gen<
0632         boost::graph::keywords::tag::distance_map, D >
0633         dist_map_gen(zero_actual);
0634     typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
0635         boost::graph::keywords::tag::distance_map, D >::map_type dist_map
0636         = dist_map_gen(g, arg_pack);
0637     weight_map_type w_map = detail::override_const_property(
0638         arg_pack, _weight_map, g, edge_weight);
0639     std::less< D > default_compare;
0640     typename boost::parameter::binding< arg_pack_type,
0641         boost::graph::keywords::tag::distance_compare, std::less< D >& >::type
0642         dist_comp
0643         = arg_pack[_distance_compare | default_compare];
0644     closed_plus< D > default_combine(inf);
0645     typename boost::parameter::binding< arg_pack_type,
0646         boost::graph::keywords::tag::distance_combine, closed_plus< D >& >::type
0647         dist_comb
0648         = arg_pack[_distance_combine | default_combine];
0649     astar_search_no_init_tree(g, s, h, vis, pred_map, r_map, dist_map, w_map,
0650         dist_comp, dist_comb, inf, zero_d);
0651 }
0652 
0653 } // namespace boost
0654 
0655 #endif // BOOST_GRAPH_ASTAR_SEARCH_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!