[Boost-commit] svn:boost r85348 - trunk/boost/graph

Subject: [Boost-commit] svn:boost r85348 - trunk/boost/graph
From: jewillco_at_[hidden]
Date: 2013-08-14 11:34:02

Author: jewillco
Date: 2013-08-14 11:34:02 EDT (Wed, 14 Aug 2013)
New Revision: 85348
URL: http://svn.boost.org/trac/boost/changeset/85348

Log:
Added MSSP support for non-named parameter versions

Text files modified: 
   trunk/boost/graph/dijkstra_shortest_paths.hpp |   138 ++++++++++++++++++++++++++++++++++----- 
   1 files changed, 120 insertions(+), 18 deletions(-)

Modified: trunk/boost/graph/dijkstra_shortest_paths.hpp
==============================================================================
--- trunk/boost/graph/dijkstra_shortest_paths.hpp	Wed Aug 14 11:31:48 2013	(r85347)
+++ trunk/boost/graph/dijkstra_shortest_paths.hpp	2013-08-14 11:34:02 EDT (Wed, 14 Aug 2013)	(r85348)
@@ -256,14 +256,14 @@
   }
 
   // Call breadth first search with default color map.
-  template <class Graph, class DijkstraVisitor,
+  template <class Graph, class SourceInputIter, class DijkstraVisitor,
             class PredecessorMap, class DistanceMap,
             class WeightMap, class IndexMap, class Compare, class Combine,
             class DistZero>
   inline void
   dijkstra_shortest_paths_no_init
     (const Graph& g,
-     typename graph_traits<Graph>::vertex_descriptor s,
+     SourceInputIter s_begin, SourceInputIter s_end,
      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
      IndexMap index_map,
      Compare compare, Combine combine, DistZero zero,
@@ -275,16 +275,16 @@
     typedef typename ColorMapHelper::type ColorMap;
     ColorMap color =
       ColorMapHelper::build(g, index_map);
-    dijkstra_shortest_paths_no_init( g, s, predecessor, distance, weight,
+    dijkstra_shortest_paths_no_init( g, s_begin, s_end, predecessor, distance, weight,
       index_map, compare, combine, zero, vis,
         color);
   }
 
-  // Call breadth first search
+  // Call breadth first search with default color map.
   template <class Graph, class DijkstraVisitor,
             class PredecessorMap, class DistanceMap,
             class WeightMap, class IndexMap, class Compare, class Combine,
-            class DistZero, class ColorMap>
+            class DistZero>
   inline void
   dijkstra_shortest_paths_no_init
     (const Graph& g,
@@ -292,6 +292,25 @@
      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
      IndexMap index_map,
      Compare compare, Combine combine, DistZero zero,
+     DijkstraVisitor vis)
+  {
+    dijkstra_shortest_paths_no_init(g, &s, &s + 1, predecessor, distance,
+                                    weight, index_map, compare, combine, zero,
+                                    vis);
+  }
+
+  // Call breadth first search
+  template <class Graph, class SourceInputIter, class DijkstraVisitor,
+            class PredecessorMap, class DistanceMap,
+            class WeightMap, class IndexMap, class Compare, class Combine,
+            class DistZero, class ColorMap>
+  inline void
+  dijkstra_shortest_paths_no_init
+    (const Graph& g,
+     SourceInputIter s_begin, SourceInputIter s_end,
+     PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
+     IndexMap index_map,
+     Compare compare, Combine combine, DistZero zero,
      DijkstraVisitor vis, ColorMap color)
   {
     typedef indirect_cmp<DistanceMap, Compare> IndirectCmp;
@@ -309,7 +328,7 @@
         PredecessorMap, DistanceMap, Combine, Compare>
       bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
 
-      breadth_first_visit(g, s, Q, bfs_vis, color);
+      breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color);
       return;
     }
 #endif // BOOST_GRAPH_DIJKSTRA_TESTING
@@ -334,11 +353,30 @@
       PredecessorMap, DistanceMap, Combine, Compare>
         bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
 
-    breadth_first_visit(g, s, Q, bfs_vis, color);
+    breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color);
+  }
+
+  // Call breadth first search
+  template <class Graph, class DijkstraVisitor,
+            class PredecessorMap, class DistanceMap,
+            class WeightMap, class IndexMap, class Compare, class Combine,
+            class DistZero, class ColorMap>
+  inline void
+  dijkstra_shortest_paths_no_init
+    (const Graph& g,
+     typename graph_traits<Graph>::vertex_descriptor s,
+     PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
+     IndexMap index_map,
+     Compare compare, Combine combine, DistZero zero,
+     DijkstraVisitor vis, ColorMap color)
+  {
+    dijkstra_shortest_paths_no_init(g, &s, &s + 1, predecessor, distance,
+                                    weight, index_map, compare, combine,
+                                    zero, vis, color);
   }
 
   // Initialize distances and call breadth first search with default color map
-  template <class VertexListGraph, class DijkstraVisitor,
+  template <class VertexListGraph, class SourceInputIter, class DijkstraVisitor,
             class PredecessorMap, class DistanceMap,
             class WeightMap, class IndexMap, class Compare, class Combine,
             class DistInf, class DistZero, typename T, typename Tag, 
@@ -346,7 +384,7 @@
   inline void
   dijkstra_shortest_paths
     (const VertexListGraph& g,
-     typename graph_traits<VertexListGraph>::vertex_descriptor s,
+     SourceInputIter s_begin, SourceInputIter s_end,
      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
      IndexMap index_map,
      Compare compare, Combine combine, DistInf inf, DistZero zero,
@@ -355,16 +393,17 @@
      BOOST_GRAPH_ENABLE_IF_MODELS_PARM(VertexListGraph,vertex_list_graph_tag))
   {
     boost::two_bit_color_map<IndexMap> color(num_vertices(g), index_map);
-    dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map,
-                            compare, combine, inf, zero, vis,
+    dijkstra_shortest_paths(g, s_begin, s_end, predecessor, distance, weight,
+                            index_map, compare, combine, inf, zero, vis,
                             color);
   }
 
-  // Initialize distances and call breadth first search
+  // Initialize distances and call breadth first search with default color map
   template <class VertexListGraph, class DijkstraVisitor,
             class PredecessorMap, class DistanceMap,
             class WeightMap, class IndexMap, class Compare, class Combine,
-            class DistInf, class DistZero, class ColorMap>
+            class DistInf, class DistZero, typename T, typename Tag, 
+            typename Base>
   inline void
   dijkstra_shortest_paths
     (const VertexListGraph& g,
@@ -372,6 +411,26 @@
      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
      IndexMap index_map,
      Compare compare, Combine combine, DistInf inf, DistZero zero,
+     DijkstraVisitor vis,
+     const bgl_named_params<T, Tag, Base>&
+     BOOST_GRAPH_ENABLE_IF_MODELS_PARM(VertexListGraph,vertex_list_graph_tag))
+  {
+    dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight,
+                            index_map, compare, combine, inf, zero, vis);
+  }
+
+  // Initialize distances and call breadth first search
+  template <class VertexListGraph, class SourceInputIter, class DijkstraVisitor,
+            class PredecessorMap, class DistanceMap,
+            class WeightMap, class IndexMap, class Compare, class Combine,
+            class DistInf, class DistZero, class ColorMap>
+  inline void
+  dijkstra_shortest_paths
+    (const VertexListGraph& g,
+     SourceInputIter s_begin, SourceInputIter s_end,
+     PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
+     IndexMap index_map,
+     Compare compare, Combine combine, DistInf inf, DistZero zero,
      DijkstraVisitor vis, ColorMap color)
   {
     typedef typename property_traits<ColorMap>::value_type ColorValue;
@@ -383,17 +442,20 @@
       put(predecessor, *ui, *ui);
       put(color, *ui, Color::white());
     }
-    put(distance, s, zero);
+    for (SourceInputIter it = s_begin; it != s_end; ++it) {
+      put(distance, *it, zero);
+    }
 
-    dijkstra_shortest_paths_no_init(g, s, predecessor, distance, weight,
-                            index_map, compare, combine, zero, vis, color);
+    dijkstra_shortest_paths_no_init(g, s_begin, s_end, predecessor, distance,
+                            weight, index_map, compare, combine, zero, vis,
+                            color);
   }
 
   // Initialize distances and call breadth first search
   template <class VertexListGraph, class DijkstraVisitor,
             class PredecessorMap, class DistanceMap,
             class WeightMap, class IndexMap, class Compare, class Combine,
-            class DistInf, class DistZero>
+            class DistInf, class DistZero, class ColorMap>
   inline void
   dijkstra_shortest_paths
     (const VertexListGraph& g,
@@ -401,13 +463,53 @@
      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
      IndexMap index_map,
      Compare compare, Combine combine, DistInf inf, DistZero zero,
+     DijkstraVisitor vis, ColorMap color)
+  {
+    dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight,
+                            index_map, compare, combine, inf, zero,
+                            vis, color);
+  }
+
+  // Initialize distances and call breadth first search
+  template <class VertexListGraph, class SourceInputIter,
+            class DijkstraVisitor,
+            class PredecessorMap, class DistanceMap,
+            class WeightMap, class IndexMap, class Compare, class Combine,
+            class DistInf, class DistZero>
+  inline void
+  dijkstra_shortest_paths
+    (const VertexListGraph& g,
+     SourceInputIter s_begin, SourceInputIter s_end,
+     PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
+     IndexMap index_map,
+     Compare compare, Combine combine, DistInf inf, DistZero zero,
      DijkstraVisitor vis)
   {
-    dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map,
+    dijkstra_shortest_paths(g, s_begin, s_end, predecessor, distance,
+                            weight, index_map,
                             compare, combine, inf, zero, vis,
                             no_named_parameters());
   }
 
+  // Initialize distances and call breadth first search
+  template <class VertexListGraph, class DijkstraVisitor,
+            class PredecessorMap, class DistanceMap,
+            class WeightMap, class IndexMap, class Compare, class Combine,
+            class DistInf, class DistZero>
+  inline void
+  dijkstra_shortest_paths
+    (const VertexListGraph& g,
+     typename graph_traits<VertexListGraph>::vertex_descriptor s,
+     PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
+     IndexMap index_map,
+     Compare compare, Combine combine, DistInf inf, DistZero zero,
+     DijkstraVisitor vis)
+  {
+    dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance,
+                            weight, index_map,
+                            compare, combine, inf, zero, vis);
+  }
+
   namespace detail {
 
     // Handle defaults for PredecessorMap and