import new upstream nautilus stable release 14.2.8

[ceph.git] / ceph / src / boost / boost / graph / dijkstra_shortest_paths_no_color_map.hpp

diff --git a/ceph/src/boost/boost/graph/dijkstra_shortest_paths_no_color_map.hpp b/ceph/src/boost/boost/graph/dijkstra_shortest_paths_no_color_map.hpp
index b1a9ef58909df28ceac17ddb1deb860039785839..ae8769fc6f2f69ec81eb46b95a684600833840e7 100644 (file)
--- a/ceph/src/boost/boost/graph/dijkstra_shortest_paths_no_color_map.hpp
+++ b/ceph/src/boost/boost/graph/dijkstra_shortest_paths_no_color_map.hpp
@@ -13,7 +13,6 @@
 
 #include <boost/pending/indirect_cmp.hpp>
 #include <boost/graph/relax.hpp>
-#include <boost/pending/relaxed_heap.hpp>
 #include <boost/graph/detail/d_ary_heap.hpp>
 #include <boost/graph/dijkstra_shortest_paths.hpp>
 #include <boost/graph/iteration_macros.hpp>
@@ -41,19 +40,12 @@ namespace boost {
   {
     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
     typedef typename property_traits<DistanceMap>::value_type Distance;
-    
+
     typedef indirect_cmp<DistanceMap, DistanceCompare> DistanceIndirectCompare;
     DistanceIndirectCompare
       distance_indirect_compare(distance_map, distance_compare);
-  
-    // Choose vertex queue type
-#if BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP
-    typedef relaxed_heap<Vertex, DistanceIndirectCompare, VertexIndexMap>
-      VertexQueue;
-    VertexQueue vertex_queue(num_vertices(graph),
-                             distance_indirect_compare,
-                             index_map);
-#else
+
+
     // Default - use d-ary heap (d = 4)
     typedef
       detail::vertex_property_map_generator<Graph, VertexIndexMap, std::size_t>
@@ -62,54 +54,53 @@ namespace boost {
     typedef
       d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, DistanceCompare>
       VertexQueue;
-  
+
     boost::scoped_array<std::size_t> index_in_heap_map_holder;
     IndexInHeapMap index_in_heap =
       IndexInHeapMapHelper::build(graph, index_map,
-                                  index_in_heap_map_holder);  
+                                  index_in_heap_map_holder);
     VertexQueue vertex_queue(distance_map, index_in_heap, distance_compare);
-#endif
-  
+
     // Add vertex to the queue
     vertex_queue.push(start_vertex);
-  
+
     // Starting vertex will always be the first discovered vertex
     visitor.discover_vertex(start_vertex, graph);
-  
+
     while (!vertex_queue.empty()) {
       Vertex min_vertex = vertex_queue.top();
       vertex_queue.pop();
-      
+
       visitor.examine_vertex(min_vertex, graph);
-  
+
       // Check if any other vertices can be reached
       Distance min_vertex_distance = get(distance_map, min_vertex);
-      
+
       if (!distance_compare(min_vertex_distance, distance_infinity)) {
         // This is the minimum vertex, so all other vertices are unreachable
         return;
       }
-  
+
       // Examine neighbors of min_vertex
       BGL_FORALL_OUTEDGES_T(min_vertex, current_edge, graph, Graph) {
         visitor.examine_edge(current_edge, graph);
-        
+
         // Check if the edge has a negative weight
         if (distance_compare(get(weight_map, current_edge), distance_zero)) {
           boost::throw_exception(negative_edge());
         }
-  
+
         // Extract the neighboring vertex and get its distance
         Vertex neighbor_vertex = target(current_edge, graph);
         Distance neighbor_vertex_distance = get(distance_map, neighbor_vertex);
-        bool is_neighbor_undiscovered = 
+        bool is_neighbor_undiscovered =
           !distance_compare(neighbor_vertex_distance, distance_infinity);
 
         // Attempt to relax the edge
-        bool was_edge_relaxed = relax(current_edge, graph, weight_map,
+        bool was_edge_relaxed = relax_target(current_edge, graph, weight_map,
           predecessor_map, distance_map,
           distance_weight_combine, distance_compare);
-  
+
         if (was_edge_relaxed) {
           visitor.edge_relaxed(current_edge, graph);
           if (is_neighbor_undiscovered) {
@@ -121,9 +112,9 @@ namespace boost {
         } else {
           visitor.edge_not_relaxed(current_edge, graph);
         }
-  
+
       } // end out edge iteration
-  
+
       visitor.finish_vertex(min_vertex, graph);
     } // end while queue not empty
   }
@@ -150,17 +141,17 @@ namespace boost {
     // Initialize vertices
     BGL_FORALL_VERTICES_T(current_vertex, graph, Graph) {
       visitor.initialize_vertex(current_vertex, graph);
-      
+
       // Default all distances to infinity
       put(distance_map, current_vertex, distance_infinity);
-  
+
       // Default all vertex predecessors to the vertex itself
       put(predecessor_map, current_vertex, current_vertex);
     }
-  
+
     // Set distance for start_vertex to zero
     put(distance_map, start_vertex, distance_zero);
-  
+
     // Pass everything on to the no_init version
     dijkstra_shortest_paths_no_color_map_no_init(graph,
       start_vertex, predecessor_map, distance_map, weight_map,
@@ -195,7 +186,7 @@ namespace boost {
          choose_param(get_param(params, distance_compare_t()),
                       std::less<DistanceType>()),
          choose_param(get_param(params, distance_combine_t()),
-                      closed_plus<DistanceType>(inf)),
+                      std::plus<DistanceType>()),
          inf,
          choose_param(get_param(params, distance_zero_t()),
                       DistanceType()),
@@ -216,7 +207,7 @@ namespace boost {
       typedef typename property_traits<WeightMap>::value_type DistanceType;
       typename std::vector<DistanceType>::size_type
         vertex_count = is_default_param(distance_map) ? num_vertices(graph) : 1;
-        
+
       std::vector<DistanceType> default_distance_map(vertex_count);
 
       detail::dijkstra_no_color_map_dispatch2