Subject: [Boost-commit] svn:boost r50803 - trunk/boost/graph
From: jewillco_at_[hidden]
Date: 2009-01-27 12:54:01
Author: jewillco
Date: 2009-01-27 12:53:59 EST (Tue, 27 Jan 2009)
New Revision: 50803
URL: http://svn.boost.org/trac/boost/changeset/50803
Log:
Fixed astar_search_no_init to work on implicit graphs
Text files modified:
trunk/boost/graph/astar_search.hpp | 37 ++++++++++++++-----------------------
1 files changed, 14 insertions(+), 23 deletions(-)
Modified: trunk/boost/graph/astar_search.hpp
==============================================================================
--- trunk/boost/graph/astar_search.hpp (original)
+++ trunk/boost/graph/astar_search.hpp 2009-01-27 12:53:59 EST (Tue, 27 Jan 2009)
@@ -15,13 +15,15 @@
#include <functional>
+#include <vector>
#include <boost/limits.hpp>
#include <boost/graph/named_function_params.hpp>
-#include <boost/pending/mutable_queue.hpp>
#include <boost/graph/relax.hpp>
-#include <boost/pending/indirect_cmp.hpp>
#include <boost/graph/exception.hpp>
#include <boost/graph/breadth_first_search.hpp>
+#include <boost/graph/detail/d_ary_heap.hpp>
+#include <boost/property_map.hpp>
+#include <boost/vector_property_map.hpp>
namespace boost {
@@ -253,15 +255,13 @@
CompareFunction compare, CombineFunction combine,
CostInf inf, CostZero zero)
{
- typedef indirect_cmp<CostMap, CompareFunction> IndirectCmp;
- IndirectCmp icmp(cost, compare);
-
typedef typename graph_traits<VertexListGraph>::vertex_descriptor
Vertex;
- typedef mutable_queue<Vertex, std::vector<Vertex>,
- IndirectCmp, VertexIndexMap>
+ typedef boost::vector_property_map<std::size_t> IndexInHeapMap;
+ IndexInHeapMap index_in_heap;
+ typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, CostMap, CompareFunction>
MutableQueue;
- MutableQueue Q(num_vertices(g), icmp, index_map);
+ MutableQueue Q(cost, index_in_heap, compare);
detail::astar_bfs_visitor<AStarHeuristic, AStarVisitor,
MutableQueue, PredecessorMap, CostMap, DistanceMap,
@@ -356,25 +356,16 @@
const Params& params)
{
typedef typename property_traits<WeightMap>::value_type D;
- typename std::vector<D>::size_type
- n = is_default_param(distance) ? num_vertices(g) : 1;
- std::vector<D> distance_map(n);
- n = is_default_param(cost) ? num_vertices(g) : 1;
- std::vector<D> cost_map(n);
- std::vector<default_color_type> color_map(num_vertices(g));
- default_color_type c = white_color;
+ std::vector<D> distance_map;
+ std::vector<D> cost_map;
+ std::vector<default_color_type> color_map;
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])),
+ choose_param(cost, vector_property_map<D, IndexMap>(index_map)),
+ choose_param(distance, vector_property_map<D, IndexMap>(index_map)),
weight, index_map,
- choose_param(color, make_iterator_property_map
- (color_map.begin(), index_map, c)),
+ choose_param(color, vector_property_map<default_color_type, IndexMap>(index_map)),
params);
}
} // namespace detail