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