[Boost-commit] svn:boost r53283 - trunk/libs/graph/test

Subject: [Boost-commit] svn:boost r53283 - trunk/libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-05-26 12:10:46

Author: jewillco
Date: 2009-05-26 12:10:45 EDT (Tue, 26 May 2009)
New Revision: 53283
URL: http://svn.boost.org/trac/boost/changeset/53283

Log:
Added no-color-map Dijkstra to test
Text files modified: 
   trunk/libs/graph/test/dijkstra_heap_performance.cpp |    36 ++++++++++++++++++++++++++++++++++++    
   1 files changed, 36 insertions(+), 0 deletions(-)

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-05-26 12:10:45 EDT (Tue, 26 May 2009)
@@ -11,6 +11,7 @@
 #endif
 
 #include <boost/graph/dijkstra_shortest_paths.hpp>
+#include <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/random/linear_congruential.hpp>
 #include <boost/lexical_cast.hpp>
@@ -104,6 +105,7 @@
 
   std::vector<double> binary_heap_distances(n);
   std::vector<double> relaxed_heap_distances(n);
+  std::vector<double> no_color_map_distances(n);
 
   // Run binary or d-ary heap version
   std::cout << "Running Dijkstra's with binary heap...";
@@ -141,6 +143,40 @@
   // Verify that the results are equivalent
   BOOST_TEST(binary_heap_distances == relaxed_heap_distances);
 
+  // Run Michael's no-color-map version
+#ifdef BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP
+  std::cout << "Running Dijkstra's (no color map) with relaxed heap...";
+#else
+  std::cout << "Running Dijkstra's (no color map) with d-ary heap (d=4)...";
+#endif
+  std::cout.flush();
+  t.restart();
+#ifdef BOOST_GRAPH_DIJKSTRA_TESTING_DIETMAR
+  dijkstra_heap_kind = dijkstra_relaxed_heap;
+#else
+  dijkstra_relaxed_heap = true;
+#endif
+  dijkstra_shortest_paths_no_color_map
+    (g, vertex(0, g),
+     boost::dummy_property_map(),
+     boost::make_iterator_property_map(&no_color_map_distances[0],
+                                       get(boost::vertex_index, g),
+                                       0.),
+     get(boost::edge_weight, g),
+     get(boost::vertex_index, g),
+     std::less<double>(),
+     boost::closed_plus<double>(),
+     (std::numeric_limits<double>::max)(),
+     0,
+     make_dijkstra_visitor(null_visitor())
+     );
+  double no_color_map_time = t.elapsed();
+  std::cout << no_color_map_time << " seconds.\n"
+            << "Speedup = " << (binary_heap_time / no_color_map_time) << ".\n";
+
+  // Verify that the results are equivalent
+  BOOST_TEST(binary_heap_distances == no_color_map_distances);
+
 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING_DIETMAR
   run_test(g, "d-ary heap (d=2)", dijkstra_d_heap_2, binary_heap_distances);
   run_test(g, "d-ary heap (d=3)", dijkstra_d_heap_3, binary_heap_distances);