Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r50812 - in trunk: boost/graph libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-01-27 14:59:40


Author: jewillco
Date: 2009-01-27 14:59:40 EST (Tue, 27 Jan 2009)
New Revision: 50812
URL: http://svn.boost.org/trac/boost/changeset/50812

Log:
Changed Dijkstra shortest path algorithm to use d-ary heap by default, and to use a vector_property_map when the graph does not model VertexListGraph (only supported for dijkstra_shortest_paths_no_init); fixes #708
Text files modified:
   trunk/boost/graph/dijkstra_shortest_paths.hpp | 76 ++++++++++++++++++++++++++++++++-------
   trunk/libs/graph/test/dijkstra_heap_performance.cpp | 9 ++--
   2 files changed, 66 insertions(+), 19 deletions(-)

Modified: trunk/boost/graph/dijkstra_shortest_paths.hpp
==============================================================================
--- trunk/boost/graph/dijkstra_shortest_paths.hpp (original)
+++ trunk/boost/graph/dijkstra_shortest_paths.hpp 2009-01-27 14:59:40 EST (Tue, 27 Jan 2009)
@@ -19,6 +19,9 @@
 #include <boost/pending/relaxed_heap.hpp>
 #include <boost/smart_ptr.hpp>
 #include <boost/graph/detail/d_ary_heap.hpp>
+#include <boost/property_map.hpp>
+#include <boost/vector_property_map.hpp>
+#include <boost/type_traits.hpp>
 
 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
 # include <boost/pending/mutable_queue.hpp>
@@ -27,6 +30,8 @@
 namespace boost {
 
 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
+ // This is a misnomer now: it now just refers to the "default heap", which is
+ // currently d-ary (d=4) but can be changed by a #define.
   static bool dijkstra_relaxed_heap = true;
 #endif
 
@@ -141,6 +146,42 @@
 
   } // namespace detail
 
+ namespace detail {
+ template <class Graph, class IndexMap, class Value, bool KnownNumVertices>
+ struct vertex_property_map_generator_helper {};
+
+ template <class Graph, class IndexMap, class Value>
+ struct vertex_property_map_generator_helper<Graph, IndexMap, Value, true> {
+ typedef boost::iterator_property_map<Value*, IndexMap> type;
+ static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) {
+ array_holder.reset(new Value[num_vertices(g)]);
+ std::fill(array_holder.get(), array_holder.get() + num_vertices(g), Value());
+ return make_iterator_property_map(array_holder.get(), index);
+ }
+ };
+
+ template <class Graph, class IndexMap, class Value>
+ struct vertex_property_map_generator_helper<Graph, IndexMap, Value, false> {
+ typedef boost::vector_property_map<Value, IndexMap> type;
+ static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) {
+ return make_vector_property_map(index);
+ }
+ };
+
+ template <class Graph, class IndexMap, class Value>
+ struct vertex_property_map_generator {
+ typedef boost::is_base_and_derived<
+ boost::vertex_list_graph_tag,
+ typename boost::graph_traits<Graph>::traversal_category>
+ known_num_vertices;
+ typedef vertex_property_map_generator_helper<Graph, IndexMap, Value, known_num_vertices::value> helper;
+ typedef typename helper::type type;
+ static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) {
+ return helper::build(g, index, array_holder);
+ }
+ };
+ }
+
   // Call breadth first search with default color map.
   template <class VertexListGraph, class DijkstraVisitor,
             class PredecessorMap, class DistanceMap,
@@ -155,11 +196,16 @@
      Compare compare, Combine combine, DistZero zero,
      DijkstraVisitor vis)
   {
- std::vector<default_color_type> color(num_vertices(g));
- default_color_type c = white_color;
+ boost::scoped_array<default_color_type> color_map_holder;
+ typedef
+ detail::vertex_property_map_generator<VertexListGraph, IndexMap, default_color_type>
+ ColorMapHelper;
+ typedef typename ColorMapHelper::type ColorMap;
+ ColorMap color =
+ ColorMapHelper::build(g, index_map, white_color, color_map_holder);
     dijkstra_shortest_paths_no_init( g, s, predecessor, distance, weight,
       index_map, compare, combine, zero, vis,
- make_iterator_property_map(&color[0], index_map, c));
+ color);
   }
 
   // Call breadth first search
@@ -183,20 +229,10 @@
 
 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
     if (!dijkstra_relaxed_heap) {
-#ifdef BOOST_GRAPH_TEST_D_ARY_HEAP
- boost::scoped_array<std::size_t> index_in_heap_map(new std::size_t[num_vertices(g)]);
- typedef boost::iterator_property_map<std::size_t*, IndexMap> IndexInHeapMap;
- IndexInHeapMap index_in_heap(&index_in_heap_map[0], index_map);
- typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, Compare>
- MutableQueue;
- MutableQueue Q(distance, index_in_heap, compare);
-#else
       typedef mutable_queue<Vertex, std::vector<Vertex>, IndirectCmp, IndexMap>
         MutableQueue;
 
       MutableQueue Q(num_vertices(g), icmp, index_map);
-#endif
-
       detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap,
         PredecessorMap, DistanceMap, Combine, Compare>
       bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
@@ -206,9 +242,21 @@
     }
 #endif // BOOST_GRAPH_DIJKSTRA_TESTING
 
+#ifdef BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP
     typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue;
-
     MutableQueue Q(num_vertices(g), icmp, index_map);
+#else // Now the default: use a d-ary heap
+ boost::scoped_array<std::size_t> index_in_heap_map_holder;
+ typedef
+ detail::vertex_property_map_generator<VertexListGraph, IndexMap, std::size_t>
+ IndexInHeapMapHelper;
+ typedef typename IndexInHeapMapHelper::type IndexInHeapMap;
+ IndexInHeapMap index_in_heap =
+ IndexInHeapMapHelper::build(g, index_map, index_in_heap_map_holder);
+ typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, Compare>
+ MutableQueue;
+ MutableQueue Q(distance, index_in_heap, compare);
+#endif
 
     detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap,
       PredecessorMap, DistanceMap, Combine, Compare>

Modified: trunk/libs/graph/test/dijkstra_heap_performance.cpp
==============================================================================
--- trunk/libs/graph/test/dijkstra_heap_performance.cpp (original)
+++ trunk/libs/graph/test/dijkstra_heap_performance.cpp 2009-01-27 14:59:40 EST (Tue, 27 Jan 2009)
@@ -8,7 +8,6 @@
 // Andrew Lumsdaine
 #ifndef BOOST_GRAPH_DIJKSTRA_TESTING_DIETMAR
 # define BOOST_GRAPH_DIJKSTRA_TESTING
-# define BOOST_GRAPH_TEST_D_ARY_HEAP
 #endif
 
 #include <boost/graph/dijkstra_shortest_paths.hpp>
@@ -107,11 +106,7 @@
   std::vector<double> relaxed_heap_distances(n);
 
   // Run binary or d-ary heap version
-#ifdef BOOST_GRAPH_TEST_D_ARY_HEAP
- std::cout << "Running Dijkstra's with d-ary heap...";
-#else
   std::cout << "Running Dijkstra's with binary heap...";
-#endif
   std::cout.flush();
   timer t;
 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING_DIETMAR
@@ -125,7 +120,11 @@
   std::cout << binary_heap_time << " seconds.\n";
 
   // Run relaxed heap version
+#ifdef BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP
   std::cout << "Running Dijkstra's with relaxed heap...";
+#else
+ std::cout << "Running Dijkstra's with d-ary heap (d=4)...";
+#endif
   std::cout.flush();
   t.restart();
 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING_DIETMAR


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk