diff -r 666f914201fb -r 2fe1408b6811 epoc32/include/stdapis/boost/graph/astar_search.hpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/epoc32/include/stdapis/boost/graph/astar_search.hpp Tue Mar 16 16:12:26 2010 +0000 @@ -0,0 +1,407 @@ + + +// +//======================================================================= +// Copyright (c) 2004 Kristopher Beevers +// +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +//======================================================================= +// + +#ifndef BOOST_GRAPH_ASTAR_SEARCH_HPP +#define BOOST_GRAPH_ASTAR_SEARCH_HPP + + +#include +#include +#include +#include +#include +#include +#include +#include + + +namespace boost { + + + template + struct AStarHeuristicConcept { + void constraints() + { + function_requires< CopyConstructibleConcept >(); + h(u); + } + Heuristic h; + typename graph_traits::vertex_descriptor u; + }; + + + template + class astar_heuristic : public std::unary_function< + typename graph_traits::vertex_descriptor, CostType> + { + public: + typedef typename graph_traits::vertex_descriptor Vertex; + astar_heuristic() {} + CostType operator()(Vertex u) { return static_cast(0); } + }; + + + + template + struct AStarVisitorConcept { + void constraints() + { + function_requires< CopyConstructibleConcept >(); + vis.initialize_vertex(u, g); + vis.discover_vertex(u, g); + vis.examine_vertex(u, g); + vis.examine_edge(e, g); + vis.edge_relaxed(e, g); + vis.edge_not_relaxed(e, g); + vis.black_target(e, g); + vis.finish_vertex(u, g); + } + Visitor vis; + Graph g; + typename graph_traits::vertex_descriptor u; + typename graph_traits::edge_descriptor e; + }; + + + template + class astar_visitor : public bfs_visitor { + public: + astar_visitor() {} + astar_visitor(Visitors vis) + : bfs_visitor(vis) {} + + template + void edge_relaxed(Edge e, Graph& g) { + invoke_visitors(this->m_vis, e, g, on_edge_relaxed()); + } + template + void edge_not_relaxed(Edge e, Graph& g) { + invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed()); + } + private: + template + void tree_edge(Edge e, Graph& g) {} + template + void non_tree_edge(Edge e, Graph& g) {} + }; + template + astar_visitor + make_astar_visitor(Visitors vis) { + return astar_visitor(vis); + } + typedef astar_visitor<> default_astar_visitor; + + + namespace detail { + + template + struct astar_bfs_visitor + { + + typedef typename property_traits::value_type C; + typedef typename property_traits::value_type ColorValue; + typedef color_traits Color; + typedef typename property_traits::value_type distance_type; + + astar_bfs_visitor(AStarHeuristic h, UniformCostVisitor vis, + UpdatableQueue& Q, PredecessorMap p, + CostMap c, DistanceMap d, WeightMap w, + ColorMap col, BinaryFunction combine, + BinaryPredicate compare, C zero) + : m_h(h), m_vis(vis), m_Q(Q), m_predecessor(p), m_cost(c), + m_distance(d), m_weight(w), m_color(col), + m_combine(combine), m_compare(compare), m_zero(zero) {} + + + template + void initialize_vertex(Vertex u, Graph& g) { + m_vis.initialize_vertex(u, g); + } + template + void discover_vertex(Vertex u, Graph& g) { + m_vis.discover_vertex(u, g); + } + template + void examine_vertex(Vertex u, Graph& g) { + m_vis.examine_vertex(u, g); + } + template + void finish_vertex(Vertex u, Graph& g) { + m_vis.finish_vertex(u, g); + } + template + void examine_edge(Edge e, Graph& g) { + if (m_compare(get(m_weight, e), m_zero)) + throw negative_edge(); + m_vis.examine_edge(e, g); + } + template + void non_tree_edge(Edge, Graph&) {} + + + + template + void tree_edge(Edge e, Graph& g) { + m_decreased = relax(e, g, m_weight, m_predecessor, m_distance, + m_combine, m_compare); + + if(m_decreased) { + m_vis.edge_relaxed(e, g); + put(m_cost, target(e, g), + m_combine(get(m_distance, target(e, g)), + m_h(target(e, g)))); + } else + m_vis.edge_not_relaxed(e, g); + } + + + template + void gray_target(Edge e, Graph& g) { + distance_type old_distance = get(m_distance, target(e, g)); + + m_decreased = relax(e, g, m_weight, m_predecessor, m_distance, + m_combine, m_compare); + + /* On x86 Linux with optimization, we sometimes get into a + horrible case where m_decreased is true but the distance hasn't + actually changed. This occurs when the comparison inside + relax() occurs with the 80-bit precision of the x87 floating + point unit, but the difference is lost when the resulting + values are written back to lower-precision memory (e.g., a + double). With the eager Dijkstra's implementation, this results + in looping. */ + if(m_decreased && old_distance != get(m_distance, target(e, g))) { + put(m_cost, target(e, g), + m_combine(get(m_distance, target(e, g)), + m_h(target(e, g)))); + m_Q.update(target(e, g)); + m_vis.edge_relaxed(e, g); + } else + m_vis.edge_not_relaxed(e, g); + } + + + template + void black_target(Edge e, Graph& g) { + distance_type old_distance = get(m_distance, target(e, g)); + + m_decreased = relax(e, g, m_weight, m_predecessor, m_distance, + m_combine, m_compare); + + /* See comment in gray_target */ + if(m_decreased && old_distance != get(m_distance, target(e, g))) { + m_vis.edge_relaxed(e, g); + put(m_cost, target(e, g), + m_combine(get(m_distance, target(e, g)), + m_h(target(e, g)))); + m_Q.push(target(e, g)); + put(m_color, target(e, g), Color::gray()); + m_vis.black_target(e, g); + } else + m_vis.edge_not_relaxed(e, g); + } + + + + AStarHeuristic m_h; + UniformCostVisitor m_vis; + UpdatableQueue& m_Q; + PredecessorMap m_predecessor; + CostMap m_cost; + DistanceMap m_distance; + WeightMap m_weight; + ColorMap m_color; + BinaryFunction m_combine; + BinaryPredicate m_compare; + bool m_decreased; + C m_zero; + + }; + + } // namespace detail + + + + template + inline void + astar_search_no_init + (VertexListGraph &g, + typename graph_traits::vertex_descriptor s, + AStarHeuristic h, AStarVisitor vis, + PredecessorMap predecessor, CostMap cost, + DistanceMap distance, WeightMap weight, + ColorMap color, VertexIndexMap index_map, + CompareFunction compare, CombineFunction combine, + CostInf inf, CostZero zero) + { + typedef indirect_cmp IndirectCmp; + IndirectCmp icmp(cost, compare); + + typedef typename graph_traits::vertex_descriptor + Vertex; + typedef mutable_queue, + IndirectCmp, VertexIndexMap> + MutableQueue; + MutableQueue Q(num_vertices(g), icmp, index_map); + + detail::astar_bfs_visitor + bfs_vis(h, vis, Q, predecessor, cost, distance, weight, + color, combine, compare, zero); + + breadth_first_visit(g, s, Q, bfs_vis, color); + } + + + // Non-named parameter interface + template + inline void + astar_search + (VertexListGraph &g, + typename graph_traits::vertex_descriptor s, + AStarHeuristic h, AStarVisitor vis, + PredecessorMap predecessor, CostMap cost, + DistanceMap distance, WeightMap weight, + VertexIndexMap index_map, ColorMap color, + CompareFunction compare, CombineFunction combine, + CostInf inf, CostZero zero) + { + + typedef typename property_traits::value_type ColorValue; + typedef color_traits Color; + typename graph_traits::vertex_iterator ui, ui_end; + for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { + put(color, *ui, Color::white()); + put(distance, *ui, inf); + put(cost, *ui, inf); + put(predecessor, *ui, *ui); + vis.initialize_vertex(*ui, g); + } + put(distance, s, zero); + put(cost, s, h(s)); + + astar_search_no_init + (g, s, h, vis, predecessor, cost, distance, weight, + color, index_map, compare, combine, inf, zero); + + } + + + + namespace detail { + template + inline void + astar_dispatch2 + (VertexListGraph& g, + typename graph_traits::vertex_descriptor s, + AStarHeuristic h, CostMap cost, DistanceMap distance, + WeightMap weight, IndexMap index_map, ColorMap color, + const Params& params) + { + dummy_property_map p_map; + typedef typename property_traits::value_type C; + astar_search + (g, s, h, + choose_param(get_param(params, graph_visitor), + make_astar_visitor(null_visitor())), + choose_param(get_param(params, vertex_predecessor), p_map), + cost, distance, weight, index_map, color, + choose_param(get_param(params, distance_compare_t()), + std::less()), + choose_param(get_param(params, distance_combine_t()), + closed_plus()), + choose_param(get_param(params, distance_inf_t()), + std::numeric_limits::max BOOST_PREVENT_MACRO_SUBSTITUTION ()), + choose_param(get_param(params, distance_zero_t()), + C())); + } + + template + inline void + astar_dispatch1 + (VertexListGraph& g, + typename graph_traits::vertex_descriptor s, + AStarHeuristic h, CostMap cost, DistanceMap distance, + WeightMap weight, IndexMap index_map, ColorMap color, + const Params& params) + { + typedef typename property_traits::value_type D; + typename std::vector::size_type + n = is_default_param(distance) ? num_vertices(g) : 1; + std::vector distance_map(n); + n = is_default_param(cost) ? num_vertices(g) : 1; + std::vector cost_map(n); + std::vector color_map(num_vertices(g)); + default_color_type c = white_color; + + detail::astar_dispatch2 + (g, s, h, + choose_param(cost, make_iterator_property_map + (cost_map.begin(), index_map, + cost_map[0])), + choose_param(distance, make_iterator_property_map + (distance_map.begin(), index_map, + distance_map[0])), + weight, index_map, + choose_param(color, make_iterator_property_map + (color_map.begin(), index_map, c)), + params); + } + } // namespace detail + + + // Named parameter interface + template + void + astar_search + (VertexListGraph &g, + typename graph_traits::vertex_descriptor s, + AStarHeuristic h, const bgl_named_params& params) + { + + detail::astar_dispatch1 + (g, s, h, + get_param(params, vertex_rank), + get_param(params, vertex_distance), + choose_const_pmap(get_param(params, edge_weight), g, edge_weight), + choose_const_pmap(get_param(params, vertex_index), g, vertex_index), + get_param(params, vertex_color), + params); + + } + +} // namespace boost + +#endif // BOOST_GRAPH_ASTAR_SEARCH_HPP