Attachment 913792 Details for Bug 1115124 – update boost/graph/dijkstra_shortest_paths.hpp to 1.55.0

[patch] update boost/graph/dijkstra_shortest_paths.hpp to 1.55.0

dijkstra_1_55_0.patch (text/plain), 12.96 KB, created by Thomas Sailer on 2014-07-01 15:25:06 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Thomas Sailer

Created: 2014-07-01 15:25:06 UTC

Size: 12.96 KB

patch

obsolete

>--- boost_1_54_0/boost/graph/dijkstra_shortest_paths.hpp	2013-05-16 17:38:05.000000000 +0200
>+++ boost_1_55_0/boost/graph/dijkstra_shortest_paths.hpp	2013-09-21 22:17:00.000000000 +0200
>@@ -118,6 +118,7 @@
>     struct dijkstra_bfs_visitor
>     {
>       typedef typename property_traits<DistanceMap>::value_type D;
>+      typedef typename property_traits<WeightMap>::value_type W;
> 
>       dijkstra_bfs_visitor(UniformCostVisitor vis, UpdatableQueue& Q,
>                            WeightMap w, PredecessorMap p, DistanceMap d,
>@@ -159,13 +160,39 @@
>       void examine_vertex(Vertex u, Graph& g) { m_vis.examine_vertex(u, g); }
>       template <class Edge, class Graph>
>       void examine_edge(Edge e, Graph& g) {
>-        // Comparison needs to be more complicated because distance and weight
>-        // types may not be the same; see bug 8398
>-        // (https://svn.boost.org/trac/boost/ticket/8398)
>-        D source_dist = get(m_distance, source(e, g));
>-        if (m_compare(m_combine(source_dist, get(m_weight, e)), source_dist))
>+        // Test for negative-weight edges:
>+        //
>+        // Reasons that other comparisons do not work:
>+        //
>+        // m_compare(e_weight, D(0)):
>+        //    m_compare only needs to work on distances, not weights, and those
>+        //    types do not need to be the same (bug 8398,
>+        //    https://svn.boost.org/trac/boost/ticket/8398).
>+        // m_compare(m_combine(source_dist, e_weight), source_dist):
>+        //    if m_combine is project2nd (as in prim_minimum_spanning_tree),
>+        //    this test will claim that the edge weight is negative whenever
>+        //    the edge weight is less than source_dist, even if both of those
>+        //    are positive (bug 9012,
>+        //    https://svn.boost.org/trac/boost/ticket/9012).
>+        // m_compare(m_combine(e_weight, source_dist), source_dist):
>+        //    would fix project2nd issue, but documentation only requires that
>+        //    m_combine be able to take a distance and a weight (in that order)
>+        //    and return a distance.
>+
>+        // W e_weight = get(m_weight, e);
>+        // sd_plus_ew = source_dist + e_weight.
>+        // D sd_plus_ew = m_combine(source_dist, e_weight);
>+        // sd_plus_2ew = source_dist + 2 * e_weight.
>+        // D sd_plus_2ew = m_combine(sd_plus_ew, e_weight);
>+        // The test here is equivalent to e_weight < 0 if m_combine has a
>+        // cancellation law, but always returns false when m_combine is a
>+        // projection operator.
>+        if (m_compare(m_combine(m_zero, get(m_weight, e)), m_zero)) 
>             boost::throw_exception(negative_edge());
>+        // End of test for negative-weight edges.
>+
>         m_vis.examine_edge(e, g);
>+
>       }
>       template <class Edge, class Graph>
>       void black_target(Edge, Graph&) { }
>@@ -256,14 +283,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 +302,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 +319,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 +355,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 +380,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 +411,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 +420,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 +438,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 +469,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 +490,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

Actions: View | Diff

Attachments on bug 1115124: 913792