projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
1 | |
| 2 | ||
| 3 | // | |
| 4 | //======================================================================= | |
| 5 | // Copyright (c) 2004 Kristopher Beevers | |
| 6 | // | |
| 7 | // Distributed under the Boost Software License, Version 1.0. (See | |
| 8 | // accompanying file LICENSE_1_0.txt or copy at | |
| 9 | // http://www.boost.org/LICENSE_1_0.txt) | |
| 10 | //======================================================================= | |
| 11 | // | |
| 12 | ||
| 13 | #ifndef BOOST_GRAPH_ASTAR_SEARCH_HPP | |
| 14 | #define BOOST_GRAPH_ASTAR_SEARCH_HPP | |
| 15 | ||
| 16 | ||
| 17 | #include <functional> | |
| 18 | #include <vector> | |
| 19 | #include <boost/limits.hpp> | |
| 20 | #include <boost/throw_exception.hpp> | |
| 21 | #include <boost/graph/named_function_params.hpp> | |
| 22 | #include <boost/graph/relax.hpp> | |
| 23 | #include <boost/graph/exception.hpp> | |
| 24 | #include <boost/graph/breadth_first_search.hpp> | |
| 25 | #include <boost/graph/iteration_macros.hpp> | |
| 26 | #include <boost/graph/detail/d_ary_heap.hpp> | |
| 27 | #include <boost/graph/property_maps/constant_property_map.hpp> | |
| 28 | #include <boost/property_map/property_map.hpp> | |
| 29 | #include <boost/property_map/vector_property_map.hpp> | |
| 30 | #include <boost/property_map/function_property_map.hpp> | |
| 31 | #include <boost/concept/assert.hpp> | |
| 32 | ||
| 33 | namespace boost { | |
| 34 | ||
| 35 | ||
| 36 | template <class Heuristic, class Graph> | |
| 37 | struct AStarHeuristicConcept { | |
| 38 | void constraints() | |
| 39 | { | |
| 40 | BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Heuristic> )); | |
| 41 | h(u); | |
| 42 | } | |
| 43 | Heuristic h; | |
| 44 | typename graph_traits<Graph>::vertex_descriptor u; | |
| 45 | }; | |
| 46 | ||
| 47 | ||
| 48 | template <class Graph, class CostType> | |
| 92f5a8d4 | 49 | class astar_heuristic |
| 7c673cae FG |
50 | { |
| 51 | public: | |
| 52 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
| 92f5a8d4 TL |
53 | typedef Vertex argument_type; |
| 54 | typedef CostType result_type; | |
| 7c673cae FG |
55 | astar_heuristic() {} |
| 56 | CostType operator()(Vertex u) { return static_cast<CostType>(0); } | |
| 57 | }; | |
| 58 | ||
| 59 | ||
| 60 | ||
| 61 | template <class Visitor, class Graph> | |
| 62 | struct AStarVisitorConcept { | |
| 63 | void constraints() | |
| 64 | { | |
| 65 | BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> )); | |
| 66 | vis.initialize_vertex(u, g); | |
| 67 | vis.discover_vertex(u, g); | |
| 68 | vis.examine_vertex(u, g); | |
| 69 | vis.examine_edge(e, g); | |
| 70 | vis.edge_relaxed(e, g); | |
| 71 | vis.edge_not_relaxed(e, g); | |
| 72 | vis.black_target(e, g); | |
| 73 | vis.finish_vertex(u, g); | |
| 74 | } | |
| 75 | Visitor vis; | |
| 76 | Graph g; | |
| 77 | typename graph_traits<Graph>::vertex_descriptor u; | |
| 78 | typename graph_traits<Graph>::edge_descriptor e; | |
| 79 | }; | |
| 80 | ||
| 81 | ||
| 82 | template <class Visitors = null_visitor> | |
| 83 | class astar_visitor : public bfs_visitor<Visitors> { | |
| 84 | public: | |
| 85 | astar_visitor() {} | |
| 86 | astar_visitor(Visitors vis) | |
| 87 | : bfs_visitor<Visitors>(vis) {} | |
| 88 | ||
| 89 | template <class Edge, class Graph> | |
| 90 | void edge_relaxed(Edge e, const Graph& g) { | |
| 91 | invoke_visitors(this->m_vis, e, g, on_edge_relaxed()); | |
| 92 | } | |
| 93 | template <class Edge, class Graph> | |
| 94 | void edge_not_relaxed(Edge e, const Graph& g) { | |
| 95 | invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed()); | |
| 96 | } | |
| 97 | private: | |
| 98 | template <class Edge, class Graph> | |
| 99 | void tree_edge(Edge e, const Graph& g) {} | |
| 100 | template <class Edge, class Graph> | |
| 101 | void non_tree_edge(Edge e, const Graph& g) {} | |
| 102 | }; | |
| 103 | template <class Visitors> | |
| 104 | astar_visitor<Visitors> | |
| 105 | make_astar_visitor(Visitors vis) { | |
| 106 | return astar_visitor<Visitors>(vis); | |
| 107 | } | |
| 108 | typedef astar_visitor<> default_astar_visitor; | |
| 109 | ||
| 110 | ||
| 111 | namespace detail { | |
| 112 | ||
| 113 | template <class AStarHeuristic, class UniformCostVisitor, | |
| 114 | class UpdatableQueue, class PredecessorMap, | |
| 115 | class CostMap, class DistanceMap, class WeightMap, | |
| 116 | class ColorMap, class BinaryFunction, | |
| 117 | class BinaryPredicate> | |
| 118 | struct astar_bfs_visitor | |
| 119 | { | |
| 120 | ||
| 121 | typedef typename property_traits<CostMap>::value_type C; | |
| 122 | typedef typename property_traits<ColorMap>::value_type ColorValue; | |
| 123 | typedef color_traits<ColorValue> Color; | |
| 124 | typedef typename property_traits<DistanceMap>::value_type distance_type; | |
| 125 | ||
| 126 | astar_bfs_visitor(AStarHeuristic h, UniformCostVisitor vis, | |
| 127 | UpdatableQueue& Q, PredecessorMap p, | |
| 128 | CostMap c, DistanceMap d, WeightMap w, | |
| 129 | ColorMap col, BinaryFunction combine, | |
| 130 | BinaryPredicate compare, C zero) | |
| 131 | : m_h(h), m_vis(vis), m_Q(Q), m_predecessor(p), m_cost(c), | |
| 132 | m_distance(d), m_weight(w), m_color(col), | |
| 133 | m_combine(combine), m_compare(compare), m_zero(zero) {} | |
| 134 | ||
| 135 | ||
| 136 | template <class Vertex, class Graph> | |
| 137 | void initialize_vertex(Vertex u, const Graph& g) { | |
| 138 | m_vis.initialize_vertex(u, g); | |
| 139 | } | |
| 140 | template <class Vertex, class Graph> | |
| 141 | void discover_vertex(Vertex u, const Graph& g) { | |
| 142 | m_vis.discover_vertex(u, g); | |
| 143 | } | |
| 144 | template <class Vertex, class Graph> | |
| 145 | void examine_vertex(Vertex u, const Graph& g) { | |
| 146 | m_vis.examine_vertex(u, g); | |
| 147 | } | |
| 148 | template <class Vertex, class Graph> | |
| 149 | void finish_vertex(Vertex u, const Graph& g) { | |
| 150 | m_vis.finish_vertex(u, g); | |
| 151 | } | |
| 152 | template <class Edge, class Graph> | |
| 153 | void examine_edge(Edge e, const Graph& g) { | |
| 154 | if (m_compare(get(m_weight, e), m_zero)) | |
| 155 | BOOST_THROW_EXCEPTION(negative_edge()); | |
| 156 | m_vis.examine_edge(e, g); | |
| 157 | } | |
| 158 | template <class Edge, class Graph> | |
| 159 | void non_tree_edge(Edge, const Graph&) {} | |
| 160 | ||
| 161 | ||
| 162 | ||
| 163 | template <class Edge, class Graph> | |
| 164 | void tree_edge(Edge e, const Graph& g) { | |
| 165 | using boost::get; | |
| 166 | bool m_decreased = | |
| 167 | relax(e, g, m_weight, m_predecessor, m_distance, | |
| 168 | m_combine, m_compare); | |
| 169 | ||
| 170 | if(m_decreased) { | |
| 171 | m_vis.edge_relaxed(e, g); | |
| 172 | put(m_cost, target(e, g), | |
| 173 | m_combine(get(m_distance, target(e, g)), | |
| 174 | m_h(target(e, g)))); | |
| 175 | } else | |
| 176 | m_vis.edge_not_relaxed(e, g); | |
| 177 | } | |
| 178 | ||
| 179 | ||
| 180 | template <class Edge, class Graph> | |
| 181 | void gray_target(Edge e, const Graph& g) { | |
| 182 | using boost::get; | |
| 183 | bool m_decreased = | |
| 184 | relax(e, g, m_weight, m_predecessor, m_distance, | |
| 185 | m_combine, m_compare); | |
| 186 | ||
| 187 | if(m_decreased) { | |
| 188 | put(m_cost, target(e, g), | |
| 189 | m_combine(get(m_distance, target(e, g)), | |
| 190 | m_h(target(e, g)))); | |
| 191 | m_Q.update(target(e, g)); | |
| 192 | m_vis.edge_relaxed(e, g); | |
| 193 | } else | |
| 194 | m_vis.edge_not_relaxed(e, g); | |
| 195 | } | |
| 196 | ||
| 197 | ||
| 198 | template <class Edge, class Graph> | |
| 199 | void black_target(Edge e, const Graph& g) { | |
| 200 | using boost::get; | |
| 201 | bool m_decreased = | |
| 202 | relax(e, g, m_weight, m_predecessor, m_distance, | |
| 203 | m_combine, m_compare); | |
| 204 | ||
| 205 | if(m_decreased) { | |
| 206 | m_vis.edge_relaxed(e, g); | |
| 207 | put(m_cost, target(e, g), | |
| 208 | m_combine(get(m_distance, target(e, g)), | |
| 209 | m_h(target(e, g)))); | |
| 210 | m_Q.push(target(e, g)); | |
| 211 | put(m_color, target(e, g), Color::gray()); | |
| 212 | m_vis.black_target(e, g); | |
| 213 | } else | |
| 214 | m_vis.edge_not_relaxed(e, g); | |
| 215 | } | |
| 216 | ||
| 217 | ||
| 218 | ||
| 219 | AStarHeuristic m_h; | |
| 220 | UniformCostVisitor m_vis; | |
| 221 | UpdatableQueue& m_Q; | |
| 222 | PredecessorMap m_predecessor; | |
| 223 | CostMap m_cost; | |
| 224 | DistanceMap m_distance; | |
| 225 | WeightMap m_weight; | |
| 226 | ColorMap m_color; | |
| 227 | BinaryFunction m_combine; | |
| 228 | BinaryPredicate m_compare; | |
| 229 | C m_zero; | |
| 230 | ||
| 231 | }; | |
| 232 | ||
| 233 | } // namespace detail | |
| 234 | ||
| 235 | ||
| 236 | ||
| 237 | template <typename VertexListGraph, typename AStarHeuristic, | |
| 238 | typename AStarVisitor, typename PredecessorMap, | |
| 239 | typename CostMap, typename DistanceMap, | |
| 240 | typename WeightMap, typename ColorMap, | |
| 241 | typename VertexIndexMap, | |
| 242 | typename CompareFunction, typename CombineFunction, | |
| 243 | typename CostInf, typename CostZero> | |
| 244 | inline void | |
| 245 | astar_search_no_init | |
| 246 | (const VertexListGraph &g, | |
| 247 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
| 248 | AStarHeuristic h, AStarVisitor vis, | |
| 249 | PredecessorMap predecessor, CostMap cost, | |
| 250 | DistanceMap distance, WeightMap weight, | |
| 251 | ColorMap color, VertexIndexMap index_map, | |
| 252 | CompareFunction compare, CombineFunction combine, | |
| 253 | CostInf /*inf*/, CostZero zero) | |
| 254 | { | |
| 255 | typedef typename graph_traits<VertexListGraph>::vertex_descriptor | |
| 256 | Vertex; | |
| 257 | typedef boost::vector_property_map<std::size_t, VertexIndexMap> IndexInHeapMap; | |
| 258 | IndexInHeapMap index_in_heap(index_map); | |
| 259 | typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, CostMap, CompareFunction> | |
| 260 | MutableQueue; | |
| 261 | MutableQueue Q(cost, index_in_heap, compare); | |
| 262 | ||
| 263 | detail::astar_bfs_visitor<AStarHeuristic, AStarVisitor, | |
| 264 | MutableQueue, PredecessorMap, CostMap, DistanceMap, | |
| 265 | WeightMap, ColorMap, CombineFunction, CompareFunction> | |
| 266 | bfs_vis(h, vis, Q, predecessor, cost, distance, weight, | |
| 267 | color, combine, compare, zero); | |
| 268 | ||
| 269 | breadth_first_visit(g, s, Q, bfs_vis, color); | |
| 270 | } | |
| 271 | ||
| 272 | namespace graph_detail { | |
| 273 | template <typename A, typename B> | |
| 274 | struct select1st { | |
| 275 | typedef std::pair<A, B> argument_type; | |
| 276 | typedef A result_type; | |
| 277 | A operator()(const std::pair<A, B>& p) const {return p.first;} | |
| 278 | }; | |
| 279 | } | |
| 280 | ||
| 281 | template <typename VertexListGraph, typename AStarHeuristic, | |
| 282 | typename AStarVisitor, typename PredecessorMap, | |
| 283 | typename CostMap, typename DistanceMap, | |
| 284 | typename WeightMap, | |
| 285 | typename CompareFunction, typename CombineFunction, | |
| 286 | typename CostInf, typename CostZero> | |
| 287 | inline void | |
| 288 | astar_search_no_init_tree | |
| 289 | (const VertexListGraph &g, | |
| 290 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
| 291 | AStarHeuristic h, AStarVisitor vis, | |
| 292 | PredecessorMap predecessor, CostMap cost, | |
| 293 | DistanceMap distance, WeightMap weight, | |
| 294 | CompareFunction compare, CombineFunction combine, | |
| 295 | CostInf /*inf*/, CostZero zero) | |
| 296 | { | |
| 297 | typedef typename graph_traits<VertexListGraph>::vertex_descriptor | |
| 298 | Vertex; | |
| 299 | typedef typename property_traits<DistanceMap>::value_type Distance; | |
| 300 | typedef d_ary_heap_indirect< | |
| 301 | std::pair<Distance, Vertex>, | |
| 302 | 4, | |
| 303 | null_property_map<std::pair<Distance, Vertex>, std::size_t>, | |
| 304 | function_property_map<graph_detail::select1st<Distance, Vertex>, std::pair<Distance, Vertex> >, | |
| 305 | CompareFunction> | |
| 306 | MutableQueue; | |
| 307 | MutableQueue Q( | |
| 308 | make_function_property_map<std::pair<Distance, Vertex> >(graph_detail::select1st<Distance, Vertex>()), | |
| 309 | null_property_map<std::pair<Distance, Vertex>, std::size_t>(), | |
| 310 | compare); | |
| 311 | ||
| 312 | vis.discover_vertex(s, g); | |
| 313 | Q.push(std::make_pair(get(cost, s), s)); | |
| 314 | while (!Q.empty()) { | |
| 315 | Vertex v; | |
| 316 | Distance v_rank; | |
| 317 | boost::tie(v_rank, v) = Q.top(); | |
| 318 | Q.pop(); | |
| 319 | vis.examine_vertex(v, g); | |
| 320 | BGL_FORALL_OUTEDGES_T(v, e, g, VertexListGraph) { | |
| 321 | Vertex w = target(e, g); | |
| 322 | vis.examine_edge(e, g); | |
| 323 | Distance e_weight = get(weight, e); | |
| 324 | if (compare(e_weight, zero)) | |
| 325 | BOOST_THROW_EXCEPTION(negative_edge()); | |
| 326 | bool decreased = | |
| 327 | relax(e, g, weight, predecessor, distance, | |
| 328 | combine, compare); | |
| 92f5a8d4 | 329 | combine(get(distance, v), e_weight); |
| 7c673cae FG |
330 | if (decreased) { |
| 331 | vis.edge_relaxed(e, g); | |
| 332 | Distance w_rank = combine(get(distance, w), h(w)); | |
| 333 | put(cost, w, w_rank); | |
| 334 | vis.discover_vertex(w, g); | |
| 335 | Q.push(std::make_pair(w_rank, w)); | |
| 336 | } else { | |
| 337 | vis.edge_not_relaxed(e, g); | |
| 338 | } | |
| 339 | } | |
| 340 | vis.finish_vertex(v, g); | |
| 341 | } | |
| 342 | } | |
| 343 | ||
| 344 | // Non-named parameter interface | |
| 345 | template <typename VertexListGraph, typename AStarHeuristic, | |
| 346 | typename AStarVisitor, typename PredecessorMap, | |
| 347 | typename CostMap, typename DistanceMap, | |
| 348 | typename WeightMap, typename VertexIndexMap, | |
| 349 | typename ColorMap, | |
| 350 | typename CompareFunction, typename CombineFunction, | |
| 351 | typename CostInf, typename CostZero> | |
| 352 | inline void | |
| 353 | astar_search | |
| 354 | (const VertexListGraph &g, | |
| 355 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
| 356 | AStarHeuristic h, AStarVisitor vis, | |
| 357 | PredecessorMap predecessor, CostMap cost, | |
| 358 | DistanceMap distance, WeightMap weight, | |
| 359 | VertexIndexMap index_map, ColorMap color, | |
| 360 | CompareFunction compare, CombineFunction combine, | |
| 361 | CostInf inf, CostZero zero) | |
| 362 | { | |
| 363 | ||
| 364 | typedef typename property_traits<ColorMap>::value_type ColorValue; | |
| 365 | typedef color_traits<ColorValue> Color; | |
| 366 | typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end; | |
| 367 | for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { | |
| 368 | put(color, *ui, Color::white()); | |
| 369 | put(distance, *ui, inf); | |
| 370 | put(cost, *ui, inf); | |
| 371 | put(predecessor, *ui, *ui); | |
| 372 | vis.initialize_vertex(*ui, g); | |
| 373 | } | |
| 374 | put(distance, s, zero); | |
| 375 | put(cost, s, h(s)); | |
| 376 | ||
| 377 | astar_search_no_init | |
| 378 | (g, s, h, vis, predecessor, cost, distance, weight, | |
| 379 | color, index_map, compare, combine, inf, zero); | |
| 380 | ||
| 381 | } | |
| 382 | ||
| 383 | // Non-named parameter interface | |
| 384 | template <typename VertexListGraph, typename AStarHeuristic, | |
| 385 | typename AStarVisitor, typename PredecessorMap, | |
| 386 | typename CostMap, typename DistanceMap, | |
| 387 | typename WeightMap, | |
| 388 | typename CompareFunction, typename CombineFunction, | |
| 389 | typename CostInf, typename CostZero> | |
| 390 | inline void | |
| 391 | astar_search_tree | |
| 392 | (const VertexListGraph &g, | |
| 393 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
| 394 | AStarHeuristic h, AStarVisitor vis, | |
| 395 | PredecessorMap predecessor, CostMap cost, | |
| 396 | DistanceMap distance, WeightMap weight, | |
| 397 | CompareFunction compare, CombineFunction combine, | |
| 398 | CostInf inf, CostZero zero) | |
| 399 | { | |
| 400 | ||
| 401 | typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end; | |
| 402 | for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { | |
| 403 | put(distance, *ui, inf); | |
| 404 | put(cost, *ui, inf); | |
| 405 | put(predecessor, *ui, *ui); | |
| 406 | vis.initialize_vertex(*ui, g); | |
| 407 | } | |
| 408 | put(distance, s, zero); | |
| 409 | put(cost, s, h(s)); | |
| 410 | ||
| 411 | astar_search_no_init_tree | |
| 412 | (g, s, h, vis, predecessor, cost, distance, weight, | |
| 413 | compare, combine, inf, zero); | |
| 414 | ||
| 415 | } | |
| 416 | ||
| 417 | // Named parameter interfaces | |
| 418 | template <typename VertexListGraph, | |
| 419 | typename AStarHeuristic, | |
| 420 | typename P, typename T, typename R> | |
| 421 | void | |
| 422 | astar_search | |
| 423 | (const VertexListGraph &g, | |
| 424 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
| 425 | AStarHeuristic h, const bgl_named_params<P, T, R>& params) | |
| 426 | { | |
| 427 | using namespace boost::graph::keywords; | |
| 428 | typedef bgl_named_params<P, T, R> params_type; | |
| 429 | BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) | |
| 430 | ||
| 431 | // Distance type is the value type of the distance map if there is one, | |
| 432 | // otherwise the value type of the weight map. | |
| 92f5a8d4 TL |
433 | typedef typename boost::detail::override_const_property_result< |
| 434 | arg_pack_type, | |
| 435 | boost::graph::keywords::tag::weight_map, | |
| 436 | edge_weight_t, | |
| 437 | VertexListGraph | |
| 438 | >::type weight_map_type; | |
| 439 | typedef typename boost::property_traits<weight_map_type>::value_type D; | |
| 7c673cae | 440 | const D inf = arg_pack[_distance_inf || detail::get_max<D>()]; |
| 92f5a8d4 TL |
441 | const D zero_actual = D(); |
| 442 | const D zero_d = arg_pack[_distance_zero | zero_actual]; | |
| 443 | null_visitor null_vis; | |
| 444 | astar_visitor<null_visitor> default_visitor(null_vis); | |
| 445 | typename boost::parameter::binding< | |
| 446 | arg_pack_type, | |
| 447 | boost::graph::keywords::tag::visitor, | |
| 448 | dummy_property_map& | |
| 449 | >::type vis = arg_pack[_visitor | default_visitor]; | |
| 450 | dummy_property_map dummy_prop; | |
| 451 | typename boost::parameter::binding< | |
| 452 | arg_pack_type, | |
| 453 | boost::graph::keywords::tag::predecessor_map, | |
| 454 | dummy_property_map& | |
| 455 | >::type pred_map = arg_pack[_predecessor_map | dummy_prop]; | |
| 456 | boost::detail::make_property_map_from_arg_pack_gen< | |
| 457 | boost::graph::keywords::tag::rank_map, | |
| 458 | D | |
| 459 | > rank_map_gen(zero_actual); | |
| 460 | typename boost::detail::map_maker< | |
| 461 | VertexListGraph, | |
| 462 | arg_pack_type, | |
| 463 | boost::graph::keywords::tag::rank_map, | |
| 464 | D | |
| 465 | >::map_type r_map = rank_map_gen(g, arg_pack); | |
| 466 | boost::detail::make_property_map_from_arg_pack_gen< | |
| 467 | boost::graph::keywords::tag::distance_map, | |
| 468 | D | |
| 469 | > dist_map_gen(zero_actual); | |
| 470 | typename boost::detail::map_maker< | |
| 471 | VertexListGraph, | |
| 472 | arg_pack_type, | |
| 473 | boost::graph::keywords::tag::distance_map, | |
| 474 | D | |
| 475 | >::map_type dist_map = dist_map_gen(g, arg_pack); | |
| 476 | weight_map_type w_map = detail::override_const_property(arg_pack, _weight_map, g, edge_weight); | |
| 477 | typename boost::detail::override_const_property_result< | |
| 478 | arg_pack_type, | |
| 479 | boost::graph::keywords::tag::vertex_index_map, | |
| 480 | vertex_index_t, | |
| 481 | VertexListGraph | |
| 482 | >::type v_i_map = detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index); | |
| 483 | typename boost::detail::map_maker< | |
| 484 | VertexListGraph, | |
| 485 | arg_pack_type, | |
| 486 | boost::graph::keywords::tag::color_map, | |
| 487 | boost::default_color_type | |
| 488 | >::map_type c_map = boost::detail::make_color_map_from_arg_pack(g, arg_pack); | |
| 489 | std::less<D> default_compare; | |
| 490 | typename boost::parameter::binding< | |
| 491 | arg_pack_type, | |
| 492 | boost::graph::keywords::tag::distance_compare, | |
| 493 | std::less<D>& | |
| 494 | >::type dist_comp = arg_pack[_distance_compare | default_compare]; | |
| 495 | closed_plus<D> default_combine(inf); | |
| 496 | typename boost::parameter::binding< | |
| 497 | arg_pack_type, | |
| 498 | boost::graph::keywords::tag::distance_combine, | |
| 499 | closed_plus<D>& | |
| 500 | >::type dist_comb = arg_pack[_distance_combine | default_combine]; | |
| 7c673cae FG |
501 | astar_search |
| 502 | (g, s, h, | |
| 92f5a8d4 TL |
503 | vis, |
| 504 | pred_map, | |
| 505 | r_map, | |
| 506 | dist_map, | |
| 507 | w_map, | |
| 508 | v_i_map, | |
| 509 | c_map, | |
| 510 | dist_comp, | |
| 511 | dist_comb, | |
| 7c673cae | 512 | inf, |
| 92f5a8d4 | 513 | zero_d); |
| 7c673cae FG |
514 | } |
| 515 | ||
| 7c673cae FG |
516 | template <typename VertexListGraph, |
| 517 | typename AStarHeuristic, | |
| 518 | typename P, typename T, typename R> | |
| 519 | void | |
| 520 | astar_search_tree | |
| 521 | (const VertexListGraph &g, | |
| 522 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
| 523 | AStarHeuristic h, const bgl_named_params<P, T, R>& params) | |
| 524 | { | |
| 525 | using namespace boost::graph::keywords; | |
| 526 | typedef bgl_named_params<P, T, R> params_type; | |
| 527 | BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) | |
| 528 | ||
| 529 | // Distance type is the value type of the distance map if there is one, | |
| 530 | // otherwise the value type of the weight map. | |
| 92f5a8d4 TL |
531 | typedef typename boost::detail::override_const_property_result< |
| 532 | arg_pack_type, | |
| 533 | boost::graph::keywords::tag::weight_map, | |
| 534 | edge_weight_t, | |
| 535 | VertexListGraph | |
| 536 | >::type weight_map_type; | |
| 537 | typedef typename boost::property_traits<weight_map_type>::value_type D; | |
| 7c673cae | 538 | const D inf = arg_pack[_distance_inf || detail::get_max<D>()]; |
| 92f5a8d4 TL |
539 | const D zero_actual = D(); |
| 540 | const D zero_d = arg_pack[_distance_zero | zero_actual]; | |
| 541 | null_visitor null_vis; | |
| 542 | astar_visitor<null_visitor> default_visitor(null_vis); | |
| 543 | typename boost::parameter::binding< | |
| 544 | arg_pack_type, | |
| 545 | boost::graph::keywords::tag::visitor, | |
| 546 | dummy_property_map& | |
| 547 | >::type vis = arg_pack[_visitor | default_visitor]; | |
| 548 | dummy_property_map dummy_prop; | |
| 549 | typename boost::parameter::binding< | |
| 550 | arg_pack_type, | |
| 551 | boost::graph::keywords::tag::predecessor_map, | |
| 552 | dummy_property_map& | |
| 553 | >::type pred_map = arg_pack[_predecessor_map | dummy_prop]; | |
| 554 | boost::detail::make_property_map_from_arg_pack_gen< | |
| 555 | boost::graph::keywords::tag::rank_map, | |
| 556 | D | |
| 557 | > rank_map_gen(zero_actual); | |
| 558 | typename boost::detail::map_maker< | |
| 559 | VertexListGraph, | |
| 560 | arg_pack_type, | |
| 561 | boost::graph::keywords::tag::rank_map, | |
| 562 | D | |
| 563 | >::map_type r_map = rank_map_gen(g, arg_pack); | |
| 564 | boost::detail::make_property_map_from_arg_pack_gen< | |
| 565 | boost::graph::keywords::tag::distance_map, | |
| 566 | D | |
| 567 | > dist_map_gen(zero_actual); | |
| 568 | typename boost::detail::map_maker< | |
| 569 | VertexListGraph, | |
| 570 | arg_pack_type, | |
| 571 | boost::graph::keywords::tag::distance_map, | |
| 572 | D | |
| 573 | >::map_type dist_map = dist_map_gen(g, arg_pack); | |
| 574 | weight_map_type w_map = detail::override_const_property(arg_pack, _weight_map, g, edge_weight); | |
| 575 | std::less<D> default_compare; | |
| 576 | typename boost::parameter::binding< | |
| 577 | arg_pack_type, | |
| 578 | boost::graph::keywords::tag::distance_compare, | |
| 579 | std::less<D>& | |
| 580 | >::type dist_comp = arg_pack[_distance_compare | default_compare]; | |
| 581 | closed_plus<D> default_combine(inf); | |
| 582 | typename boost::parameter::binding< | |
| 583 | arg_pack_type, | |
| 584 | boost::graph::keywords::tag::distance_combine, | |
| 585 | closed_plus<D>& | |
| 586 | >::type dist_comb = arg_pack[_distance_combine | default_combine]; | |
| 7c673cae FG |
587 | astar_search_tree |
| 588 | (g, s, h, | |
| 92f5a8d4 TL |
589 | vis, |
| 590 | pred_map, | |
| 591 | r_map, | |
| 592 | dist_map, | |
| 593 | w_map, | |
| 594 | dist_comp, | |
| 595 | dist_comb, | |
| 7c673cae | 596 | inf, |
| 92f5a8d4 | 597 | zero_d); |
| 7c673cae FG |
598 | } |
| 599 | ||
| 600 | template <typename VertexListGraph, | |
| 601 | typename AStarHeuristic, | |
| 602 | typename P, typename T, typename R> | |
| 603 | void | |
| 604 | astar_search_no_init | |
| 605 | (const VertexListGraph &g, | |
| 606 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
| 607 | AStarHeuristic h, const bgl_named_params<P, T, R>& params) | |
| 608 | { | |
| 609 | using namespace boost::graph::keywords; | |
| 610 | typedef bgl_named_params<P, T, R> params_type; | |
| 611 | BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) | |
| 92f5a8d4 TL |
612 | typedef typename boost::detail::override_const_property_result< |
| 613 | arg_pack_type, | |
| 614 | boost::graph::keywords::tag::weight_map, | |
| 615 | edge_weight_t, | |
| 616 | VertexListGraph | |
| 617 | >::type weight_map_type; | |
| 7c673cae FG |
618 | typedef typename boost::property_traits<weight_map_type>::value_type D; |
| 619 | const D inf = arg_pack[_distance_inf || detail::get_max<D>()]; | |
| 92f5a8d4 TL |
620 | const D zero_actual = D(); |
| 621 | const D zero_d = arg_pack[_distance_zero | zero_actual]; | |
| 622 | null_visitor null_vis; | |
| 623 | astar_visitor<null_visitor> default_visitor(null_vis); | |
| 624 | typename boost::parameter::binding< | |
| 625 | arg_pack_type, | |
| 626 | boost::graph::keywords::tag::visitor, | |
| 627 | dummy_property_map& | |
| 628 | >::type vis = arg_pack[_visitor | default_visitor]; | |
| 629 | dummy_property_map dummy_prop; | |
| 630 | typename boost::parameter::binding< | |
| 631 | arg_pack_type, | |
| 632 | boost::graph::keywords::tag::predecessor_map, | |
| 633 | dummy_property_map& | |
| 634 | >::type pred_map = arg_pack[_predecessor_map | dummy_prop]; | |
| 635 | boost::detail::make_property_map_from_arg_pack_gen< | |
| 636 | boost::graph::keywords::tag::rank_map, | |
| 637 | D | |
| 638 | > rank_map_gen(zero_actual); | |
| 639 | typename boost::detail::map_maker< | |
| 640 | VertexListGraph, | |
| 641 | arg_pack_type, | |
| 642 | boost::graph::keywords::tag::rank_map, | |
| 643 | D | |
| 644 | >::map_type r_map = rank_map_gen(g, arg_pack); | |
| 645 | boost::detail::make_property_map_from_arg_pack_gen< | |
| 646 | boost::graph::keywords::tag::distance_map, | |
| 647 | D | |
| 648 | > dist_map_gen(zero_actual); | |
| 649 | typename boost::detail::map_maker< | |
| 650 | VertexListGraph, | |
| 651 | arg_pack_type, | |
| 652 | boost::graph::keywords::tag::distance_map, | |
| 653 | D | |
| 654 | >::map_type dist_map = dist_map_gen(g, arg_pack); | |
| 655 | weight_map_type w_map = detail::override_const_property(arg_pack, _weight_map, g, edge_weight); | |
| 656 | typename boost::detail::map_maker< | |
| 657 | VertexListGraph, | |
| 658 | arg_pack_type, | |
| 659 | boost::graph::keywords::tag::color_map, | |
| 660 | boost::default_color_type | |
| 661 | >::map_type c_map = boost::detail::make_color_map_from_arg_pack(g, arg_pack); | |
| 662 | typename boost::detail::override_const_property_result< | |
| 663 | arg_pack_type, | |
| 664 | boost::graph::keywords::tag::vertex_index_map, | |
| 665 | vertex_index_t, | |
| 666 | VertexListGraph | |
| 667 | >::type v_i_map = detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index); | |
| 668 | std::less<D> default_compare; | |
| 669 | typename boost::parameter::binding< | |
| 670 | arg_pack_type, | |
| 671 | boost::graph::keywords::tag::distance_compare, | |
| 672 | std::less<D>& | |
| 673 | >::type dist_comp = arg_pack[_distance_compare | default_compare]; | |
| 674 | closed_plus<D> default_combine(inf); | |
| 675 | typename boost::parameter::binding< | |
| 676 | arg_pack_type, | |
| 677 | boost::graph::keywords::tag::distance_combine, | |
| 678 | closed_plus<D>& | |
| 679 | >::type dist_comb = arg_pack[_distance_combine | default_combine]; | |
| 7c673cae FG |
680 | astar_search_no_init |
| 681 | (g, s, h, | |
| 92f5a8d4 TL |
682 | vis, |
| 683 | pred_map, | |
| 684 | r_map, | |
| 685 | dist_map, | |
| 686 | w_map, | |
| 687 | c_map, | |
| 688 | v_i_map, | |
| 689 | dist_comp, | |
| 690 | dist_comb, | |
| 7c673cae | 691 | inf, |
| 92f5a8d4 | 692 | zero_d); |
| 7c673cae FG |
693 | } |
| 694 | ||
| 695 | template <typename VertexListGraph, | |
| 696 | typename AStarHeuristic, | |
| 697 | typename P, typename T, typename R> | |
| 698 | void | |
| 699 | astar_search_no_init_tree | |
| 700 | (const VertexListGraph &g, | |
| 701 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
| 702 | AStarHeuristic h, const bgl_named_params<P, T, R>& params) | |
| 703 | { | |
| 704 | using namespace boost::graph::keywords; | |
| 705 | typedef bgl_named_params<P, T, R> params_type; | |
| 706 | BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) | |
| 92f5a8d4 TL |
707 | typedef typename boost::detail::override_const_property_result< |
| 708 | arg_pack_type, | |
| 709 | boost::graph::keywords::tag::weight_map, | |
| 710 | edge_weight_t, | |
| 711 | VertexListGraph | |
| 712 | >::type weight_map_type; | |
| 7c673cae FG |
713 | typedef typename boost::property_traits<weight_map_type>::value_type D; |
| 714 | const D inf = arg_pack[_distance_inf || detail::get_max<D>()]; | |
| 92f5a8d4 TL |
715 | const D zero_actual = D(); |
| 716 | const D zero_d = arg_pack[_distance_zero | zero_actual]; | |
| 717 | null_visitor null_vis; | |
| 718 | astar_visitor<null_visitor> default_visitor(null_vis); | |
| 719 | typename boost::parameter::binding< | |
| 720 | arg_pack_type, | |
| 721 | boost::graph::keywords::tag::visitor, | |
| 722 | dummy_property_map& | |
| 723 | >::type vis = arg_pack[_visitor | default_visitor]; | |
| 724 | dummy_property_map dummy_prop; | |
| 725 | typename boost::parameter::binding< | |
| 726 | arg_pack_type, | |
| 727 | boost::graph::keywords::tag::predecessor_map, | |
| 728 | dummy_property_map& | |
| 729 | >::type pred_map = arg_pack[_predecessor_map | dummy_prop]; | |
| 730 | boost::detail::make_property_map_from_arg_pack_gen< | |
| 731 | boost::graph::keywords::tag::rank_map, | |
| 732 | D | |
| 733 | > rank_map_gen(zero_actual); | |
| 734 | typename boost::detail::map_maker< | |
| 735 | VertexListGraph, | |
| 736 | arg_pack_type, | |
| 737 | boost::graph::keywords::tag::rank_map, | |
| 738 | D | |
| 739 | >::map_type r_map = rank_map_gen(g, arg_pack); | |
| 740 | boost::detail::make_property_map_from_arg_pack_gen< | |
| 741 | boost::graph::keywords::tag::distance_map, | |
| 742 | D | |
| 743 | > dist_map_gen(zero_actual); | |
| 744 | typename boost::detail::map_maker< | |
| 745 | VertexListGraph, | |
| 746 | arg_pack_type, | |
| 747 | boost::graph::keywords::tag::distance_map, | |
| 748 | D | |
| 749 | >::map_type dist_map = dist_map_gen(g, arg_pack); | |
| 750 | weight_map_type w_map = detail::override_const_property(arg_pack, _weight_map, g, edge_weight); | |
| 751 | std::less<D> default_compare; | |
| 752 | typename boost::parameter::binding< | |
| 753 | arg_pack_type, | |
| 754 | boost::graph::keywords::tag::distance_compare, | |
| 755 | std::less<D>& | |
| 756 | >::type dist_comp = arg_pack[_distance_compare | default_compare]; | |
| 757 | closed_plus<D> default_combine(inf); | |
| 758 | typename boost::parameter::binding< | |
| 759 | arg_pack_type, | |
| 760 | boost::graph::keywords::tag::distance_combine, | |
| 761 | closed_plus<D>& | |
| 762 | >::type dist_comb = arg_pack[_distance_combine | default_combine]; | |
| 7c673cae FG |
763 | astar_search_no_init_tree |
| 764 | (g, s, h, | |
| 92f5a8d4 TL |
765 | vis, |
| 766 | pred_map, | |
| 767 | r_map, | |
| 768 | dist_map, | |
| 769 | w_map, | |
| 770 | dist_comp, | |
| 771 | dist_comb, | |
| 7c673cae | 772 | inf, |
| 92f5a8d4 | 773 | zero_d); |
| 7c673cae FG |
774 | } |
| 775 | ||
| 776 | } // namespace boost | |
| 777 | ||
| 778 | #endif // BOOST_GRAPH_ASTAR_SEARCH_HPP |