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

Subject: [Boost-commit] svn:boost r72960 - trunk/boost/graph
From: jewillco_at_[hidden]
Date: 2011-07-07 17:07:42

Author: jewillco
Date: 2011-07-07 17:07:41 EDT (Thu, 07 Jul 2011)
New Revision: 72960
URL: http://svn.boost.org/trac/boost/changeset/72960

Log:
Applied patch from #5659, plus made similar changes to other algorithms that have inf parameters; did not add inf parameters to algorithms that did not already have them; fixes #5659
Text files modified: 
   trunk/boost/graph/astar_search.hpp                         |    10 ++++++----                              
   trunk/boost/graph/dag_shortest_paths.hpp                   |     8 +++++---                                
   trunk/boost/graph/dijkstra_shortest_paths.hpp              |     8 +++++---                                
   trunk/boost/graph/dijkstra_shortest_paths_no_color_map.hpp |     8 +++++---                                
   trunk/boost/graph/floyd_warshall_shortest.hpp              |    16 ++++++++++------                        
   trunk/boost/graph/relax.hpp                                |     6 +++++-                                  
   6 files changed, 36 insertions(+), 20 deletions(-)

Modified: trunk/boost/graph/astar_search.hpp
==============================================================================
--- trunk/boost/graph/astar_search.hpp	(original)
+++ trunk/boost/graph/astar_search.hpp	2011-07-07 17:07:41 EDT (Thu, 07 Jul 2011)
@@ -325,6 +325,7 @@
       typename detail::map_maker<VertexListGraph, arg_pack_type, tag::distance_map, W>::map_type
       distance_map_type;
     typedef typename boost::property_traits<distance_map_type>::value_type D;
+    const D inf = arg_pack[_distance_inf | (std::numeric_limits<D>::max)()];
 
     astar_search
       (g, s, h,
@@ -336,8 +337,8 @@
        detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index),
        detail::make_color_map_from_arg_pack(g, arg_pack),
        arg_pack[_distance_compare | std::less<D>()],
-       arg_pack[_distance_combine | closed_plus<D>()],
-       arg_pack[_distance_inf | (std::numeric_limits<D>::max)()],
+       arg_pack[_distance_combine | closed_plus<D>(inf)],
+       inf,
        arg_pack[_distance_zero | D()]);
   }
 
@@ -358,6 +359,7 @@
                  arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type
                weight_map_type;
     typedef typename boost::property_traits<weight_map_type>::value_type D;
+    const D inf = arg_pack[_distance_inf | (std::numeric_limits<D>::max)()];
     astar_search_no_init
       (g, s, h,
        arg_pack[_visitor | make_astar_visitor(null_visitor())],
@@ -368,8 +370,8 @@
        detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index),
        detail::make_color_map_from_arg_pack(g, arg_pack),
        arg_pack[_distance_compare | std::less<D>()],
-       arg_pack[_distance_combine | closed_plus<D>()],
-       arg_pack[_distance_inf | (std::numeric_limits<D>::max)()],
+       arg_pack[_distance_combine | closed_plus<D>(inf)],
+       inf,
        arg_pack[_distance_zero | D()]);
   }
 

Modified: trunk/boost/graph/dag_shortest_paths.hpp
==============================================================================
--- trunk/boost/graph/dag_shortest_paths.hpp	(original)
+++ trunk/boost/graph/dag_shortest_paths.hpp	2011-07-07 17:07:41 EDT (Thu, 07 Jul 2011)
@@ -88,14 +88,16 @@
     {
       typedef typename property_traits<DistanceMap>::value_type D;
       dummy_property_map p_map;
+      D inf =
+        choose_param(get_param(params, distance_inf_t()), 
+                     (std::numeric_limits<D>::max)());
       dag_shortest_paths
         (g, s, distance, weight, color, 
          choose_param(get_param(params, vertex_predecessor), p_map),
          vis, 
          choose_param(get_param(params, distance_compare_t()), std::less<D>()),
-         choose_param(get_param(params, distance_combine_t()), closed_plus<D>()),
-         choose_param(get_param(params, distance_inf_t()), 
-                      (std::numeric_limits<D>::max)()),
+         choose_param(get_param(params, distance_combine_t()), closed_plus<D>(inf)),
+         inf,
          choose_param(get_param(params, distance_zero_t()), 
                       D()));
     }

Modified: trunk/boost/graph/dijkstra_shortest_paths.hpp
==============================================================================
--- trunk/boost/graph/dijkstra_shortest_paths.hpp	(original)
+++ trunk/boost/graph/dijkstra_shortest_paths.hpp	2011-07-07 17:07:41 EDT (Thu, 07 Jul 2011)
@@ -420,6 +420,9 @@
       dummy_property_map p_map;
 
       typedef typename property_traits<DistanceMap>::value_type D;
+      D inf = choose_param(get_param(params, distance_inf_t()),
+                           (std::numeric_limits<D>::max)());
+
       dijkstra_shortest_paths
         (g, s,
          choose_param(get_param(params, vertex_predecessor), p_map),
@@ -427,9 +430,8 @@
          choose_param(get_param(params, distance_compare_t()),
                       std::less<D>()),
          choose_param(get_param(params, distance_combine_t()),
-                      closed_plus<D>()),
-         choose_param(get_param(params, distance_inf_t()),
-                      (std::numeric_limits<D>::max)()),
+                      closed_plus<D>(inf)),
+         inf,
          choose_param(get_param(params, distance_zero_t()),
                       D()),
          choose_param(get_param(params, graph_visitor),

Modified: trunk/boost/graph/dijkstra_shortest_paths_no_color_map.hpp
==============================================================================
--- trunk/boost/graph/dijkstra_shortest_paths_no_color_map.hpp	(original)
+++ trunk/boost/graph/dijkstra_shortest_paths_no_color_map.hpp	2011-07-07 17:07:41 EDT (Thu, 07 Jul 2011)
@@ -186,6 +186,9 @@
       dummy_property_map predecessor_map;
 
       typedef typename property_traits<DistanceMap>::value_type DistanceType;
+      DistanceType inf =
+        choose_param(get_param(params, distance_inf_t()),
+                     (std::numeric_limits<DistanceType>::max)());
       dijkstra_shortest_paths_no_color_map
         (graph, start_vertex,
          choose_param(get_param(params, vertex_predecessor), predecessor_map),
@@ -193,9 +196,8 @@
          choose_param(get_param(params, distance_compare_t()),
                       std::less<DistanceType>()),
          choose_param(get_param(params, distance_combine_t()),
-                      closed_plus<DistanceType>()),
-         choose_param(get_param(params, distance_inf_t()),
-                      (std::numeric_limits<DistanceType>::max)()),
+                      closed_plus<DistanceType>(inf)),
+         inf,
          choose_param(get_param(params, distance_zero_t()),
                       DistanceType()),
          choose_param(get_param(params, graph_visitor),

Modified: trunk/boost/graph/floyd_warshall_shortest.hpp
==============================================================================
--- trunk/boost/graph/floyd_warshall_shortest.hpp	(original)
+++ trunk/boost/graph/floyd_warshall_shortest.hpp	2011-07-07 17:07:41 EDT (Thu, 07 Jul 2011)
@@ -163,14 +163,16 @@
       const bgl_named_params<P, T, R>& params)
     {
       typedef typename property_traits<WeightMap>::value_type WM;
+      WM inf =
+        choose_param(get_param(params, distance_inf_t()), 
+          std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION());
     
       return floyd_warshall_initialized_all_pairs_shortest_paths(g, d,
         choose_param(get_param(params, distance_compare_t()), 
           std::less<WM>()),
         choose_param(get_param(params, distance_combine_t()), 
-          closed_plus<WM>()),
-        choose_param(get_param(params, distance_inf_t()), 
-          std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()),
+          closed_plus<WM>(inf)),
+        inf,
         choose_param(get_param(params, distance_zero_t()), 
           WM()));
     }
@@ -185,13 +187,15 @@
     {
       typedef typename property_traits<WeightMap>::value_type WM;
     
+      WM inf =
+        choose_param(get_param(params, distance_inf_t()), 
+          std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION());
       return floyd_warshall_all_pairs_shortest_paths(g, d, w,
         choose_param(get_param(params, distance_compare_t()), 
           std::less<WM>()),
         choose_param(get_param(params, distance_combine_t()), 
-          closed_plus<WM>()),
-        choose_param(get_param(params, distance_inf_t()), 
-          std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()),
+          closed_plus<WM>(inf)),
+        inf,
         choose_param(get_param(params, distance_zero_t()), 
           WM()));
     }

Modified: trunk/boost/graph/relax.hpp
==============================================================================
--- trunk/boost/graph/relax.hpp	(original)
+++ trunk/boost/graph/relax.hpp	2011-07-07 17:07:41 EDT (Thu, 07 Jul 2011)
@@ -22,9 +22,13 @@
     template <class T>
     struct closed_plus
     {
+      const T inf;
+
+      closed_plus() : inf(std::numeric_limits<T>::max()) { }
+      closed_plus(T inf) : inf(inf) { }
+
       T operator()(const T& a, const T& b) const {
         using namespace std;
-       const T inf = (std::numeric_limits<T>::max)();
        if (a == inf) return inf;
        if (b == inf) return inf;
        return a + b;