ceph/src/boost/libs/graph_parallel/include/boost/graph/distributed/eager_dijkstra_shortest_paths.hpp

   1 // Copyright (C) 2004-2006 The Trustees of Indiana University.
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Douglas Gregor
   8 //           Andrew Lumsdaine
   9
  10 /**************************************************************************
  11  * This source file implements a variation on distributed Dijkstra's      *
  12  * algorithm that can expose additional parallelism by permitting         *
  13  * vertices within a certain distance from the minimum to be processed,   *
  14  * even though they may not be at their final distance. This can          *
  15  * introduce looping, but the algorithm will still terminate so long as   *
  16  * there are no negative loops.                                           *
  17  **************************************************************************/
  18 #ifndef BOOST_GRAPH_EAGER_DIJKSTRA_SHORTEST_PATHS_HPP
  19 #define BOOST_GRAPH_EAGER_DIJKSTRA_SHORTEST_PATHS_HPP
  20
  21 #ifndef BOOST_GRAPH_USE_MPI
  22 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
  23 #endif
  24
  25 #include <boost/assert.hpp>
  26 #include <boost/graph/distributed/detail/dijkstra_shortest_paths.hpp>
  27 #include <boost/property_map/parallel/caching_property_map.hpp>
  28 #include <boost/pending/indirect_cmp.hpp>
  29 #include <boost/graph/distributed/detail/remote_update_set.hpp>
  30 #include <vector>
  31 #include <boost/graph/breadth_first_search.hpp>
  32 #include <boost/graph/dijkstra_shortest_paths.hpp>
  33 #include <boost/graph/parallel/container_traits.hpp>
  34
  35 #ifdef PBGL_ACCOUNTING
  36 #  include <boost/graph/accounting.hpp>
  37 #  include <numeric>
  38 #endif // PBGL_ACCOUNTING
  39
  40 #ifdef MUTABLE_QUEUE
  41 #  include <boost/pending/mutable_queue.hpp>
  42 #endif
  43
  44 namespace boost { namespace graph { namespace distributed {
  45
  46 #ifdef PBGL_ACCOUNTING
  47 struct eager_dijkstra_shortest_paths_stats_t
  48 {
  49   /* The value of the lookahead parameter. */
  50   double lookahead;
  51
  52   /* Total wall-clock time used by the algorithm.*/
  53   accounting::time_type execution_time;
  54
  55   /* The number of vertices deleted in each superstep. */
  56   std::vector<std::size_t> deleted_vertices;
  57
  58   template<typename OutputStream>
  59   void print(OutputStream& out)
  60   {
  61     double avg_deletions = std::accumulate(deleted_vertices.begin(),
  62                                            deleted_vertices.end(),
  63                                            0.0);
  64     avg_deletions /= deleted_vertices.size();
  65
  66     out << "Problem = \"Single-Source Shortest Paths\"\n"
  67         << "Algorithm = \"Eager Dijkstra\"\n"
  68         << "Function = eager_dijkstra_shortest_paths\n"
  69         << "(P) Lookahead = " << lookahead << "\n"
  70         << "Wall clock time = " << accounting::print_time(execution_time)
  71         << "\nSupersteps = " << deleted_vertices.size() << "\n"
  72         << "Avg. deletions per superstep = " << avg_deletions << "\n";
  73   }
  74 };
  75
  76 static eager_dijkstra_shortest_paths_stats_t eager_dijkstra_shortest_paths_stats;
  77 #endif
  78
  79 namespace detail {
  80
  81 // Borrowed from BGL's dijkstra_shortest_paths
  82 template <class UniformCostVisitor, class Queue,
  83           class WeightMap, class PredecessorMap, class DistanceMap,
  84           class BinaryFunction, class BinaryPredicate>
  85  struct parallel_dijkstra_bfs_visitor : bfs_visitor<>
  86 {
  87   typedef typename property_traits<DistanceMap>::value_type distance_type;
  88
  89   parallel_dijkstra_bfs_visitor(UniformCostVisitor vis, Queue& Q,
  90                                 WeightMap w, PredecessorMap p, DistanceMap d,
  91                                 BinaryFunction combine, BinaryPredicate compare,
  92                                 distance_type zero)
  93     : m_vis(vis), m_Q(Q), m_weight(w), m_predecessor(p), m_distance(d),
  94       m_combine(combine), m_compare(compare), m_zero(zero)  { }
  95
  96   template <class Vertex, class Graph>
  97   void initialize_vertex(Vertex u, Graph& g)
  98     { m_vis.initialize_vertex(u, g); }
  99   template <class Vertex, class Graph>
 100   void discover_vertex(Vertex u, Graph& g) { m_vis.discover_vertex(u, g); }
 101   template <class Vertex, class Graph>
 102   void examine_vertex(Vertex u, Graph& g) { m_vis.examine_vertex(u, g); }
 103
 104   /* Since the eager formulation of Parallel Dijkstra's algorithm can
 105      loop, we may relax on *any* edge, not just those associated with
 106      white and gray targets. */
 107   template <class Edge, class Graph>
 108   void examine_edge(Edge e, Graph& g) {
 109     if (m_compare(get(m_weight, e), m_zero))
 110         boost::throw_exception(negative_edge());
 111
 112     m_vis.examine_edge(e, g);
 113
 114     boost::parallel::caching_property_map<PredecessorMap> c_pred(m_predecessor);
 115     boost::parallel::caching_property_map<DistanceMap> c_dist(m_distance);
 116
 117     distance_type old_distance = get(c_dist, target(e, g));
 118
 119     bool m_decreased = relax(e, g, m_weight, c_pred, c_dist,
 120                              m_combine, m_compare);
 121
 122     /* On x86 Linux with optimization, we sometimes get into a
 123        horrible case where m_decreased is true but the distance hasn't
 124        actually changed. This occurs when the comparison inside
 125        relax() occurs with the 80-bit precision of the x87 floating
 126        point unit, but the difference is lost when the resulting
 127        values are written back to lower-precision memory (e.g., a
 128        double). With the eager Dijkstra's implementation, this results
 129        in looping. */
 130     if (m_decreased && old_distance != get(c_dist, target(e, g))) {
 131       m_Q.update(target(e, g));
 132       m_vis.edge_relaxed(e, g);
 133     } else
 134       m_vis.edge_not_relaxed(e, g);
 135   }
 136   template <class Vertex, class Graph>
 137   void finish_vertex(Vertex u, Graph& g) { m_vis.finish_vertex(u, g); }
 138
 139   UniformCostVisitor m_vis;
 140   Queue& m_Q;
 141   WeightMap m_weight;
 142   PredecessorMap m_predecessor;
 143   DistanceMap m_distance;
 144   BinaryFunction m_combine;
 145   BinaryPredicate m_compare;
 146   distance_type m_zero;
 147 };
 148
 149   /**********************************************************************
 150    * Dijkstra queue that implements arbitrary "lookahead"               *
 151    **********************************************************************/
 152   template<typename Graph, typename Combine, typename Compare,
 153            typename VertexIndexMap, typename DistanceMap,
 154            typename PredecessorMap>
 155   class lookahead_dijkstra_queue
 156     : public graph::detail::remote_update_set<
 157                lookahead_dijkstra_queue<
 158                  Graph, Combine, Compare, VertexIndexMap, DistanceMap,
 159                  PredecessorMap>,
 160                typename boost::graph::parallel::process_group_type<Graph>::type,
 161                typename dijkstra_msg_value<DistanceMap, PredecessorMap>::type,
 162                typename property_map<Graph, vertex_owner_t>::const_type>
 163   {
 164     typedef typename graph_traits<Graph>::vertex_descriptor
 165       vertex_descriptor;
 166     typedef lookahead_dijkstra_queue self_type;
 167     typedef typename boost::graph::parallel::process_group_type<Graph>::type
 168       process_group_type;
 169     typedef dijkstra_msg_value<DistanceMap, PredecessorMap> msg_value_creator;
 170     typedef typename msg_value_creator::type msg_value_type;
 171     typedef typename property_map<Graph, vertex_owner_t>::const_type
 172       OwnerPropertyMap;
 173
 174     typedef graph::detail::remote_update_set<self_type, process_group_type,
 175                                              msg_value_type, OwnerPropertyMap>
 176       inherited;
 177
 178     // Priority queue for tentative distances
 179     typedef indirect_cmp<DistanceMap, Compare> queue_compare_type;
 180
 181     typedef typename property_traits<DistanceMap>::value_type distance_type;
 182
 183 #ifdef MUTABLE_QUEUE
 184     typedef mutable_queue<vertex_descriptor, std::vector<vertex_descriptor>,
 185                           queue_compare_type, VertexIndexMap> queue_type;
 186
 187 #else
 188     typedef relaxed_heap<vertex_descriptor, queue_compare_type,
 189                          VertexIndexMap> queue_type;
 190 #endif // MUTABLE_QUEUE
 191
 192     typedef typename process_group_type::process_id_type process_id_type;
 193
 194   public:
 195     typedef vertex_descriptor value_type;
 196
 197     lookahead_dijkstra_queue(const Graph& g,
 198                              const Combine& combine,
 199                              const Compare& compare,
 200                              const VertexIndexMap& id,
 201                              const DistanceMap& distance_map,
 202                              const PredecessorMap& predecessor_map,
 203                              distance_type lookahead)
 204       : inherited(boost::graph::parallel::process_group(g), get(vertex_owner, g)),
 205         queue(num_vertices(g), queue_compare_type(distance_map, compare), id),
 206         distance_map(distance_map),
 207         predecessor_map(predecessor_map),
 208         min_distance(0),
 209         lookahead(lookahead)
 210 #ifdef PBGL_ACCOUNTING
 211         , local_deletions(0)
 212 #endif
 213     { }
 214
 215     void push(const value_type& x)
 216     {
 217       msg_value_type msg_value =
 218         msg_value_creator::create(get(distance_map, x),
 219                                   predecessor_value(get(predecessor_map, x)));
 220       inherited::update(x, msg_value);
 221     }
 222
 223     void update(const value_type& x) { push(x); }
 224
 225     void pop()
 226     {
 227       queue.pop();
 228 #ifdef PBGL_ACCOUNTING
 229       ++local_deletions;
 230 #endif
 231     }
 232
 233     value_type&       top()       { return queue.top(); }
 234     const value_type& top() const { return queue.top(); }
 235
 236     bool empty()
 237     {
 238       inherited::collect();
 239
 240       // If there are no suitable messages, wait until we get something
 241       while (!has_suitable_vertex()) {
 242         if (do_synchronize()) return true;
 243       }
 244
 245       // Return true only if nobody has any messages; false if we
 246       // have suitable messages
 247       return false;
 248     }
 249
 250   private:
 251     vertex_descriptor predecessor_value(vertex_descriptor v) const
 252     { return v; }
 253
 254     vertex_descriptor
 255     predecessor_value(property_traits<dummy_property_map>::reference) const
 256     { return graph_traits<Graph>::null_vertex(); }
 257
 258     bool has_suitable_vertex() const
 259     {
 260       return (!queue.empty()
 261               && get(distance_map, queue.top()) <= min_distance + lookahead);
 262     }
 263
 264     bool do_synchronize()
 265     {
 266       using boost::parallel::all_reduce;
 267       using boost::parallel::minimum;
 268
 269       inherited::synchronize();
 270
 271       // TBD: could use combine here, but then we need to stop using
 272       // minimum<distance_type>() as the function object.
 273       distance_type local_distance =
 274         queue.empty()? (std::numeric_limits<distance_type>::max)()
 275         : get(distance_map, queue.top());
 276
 277       all_reduce(this->process_group, &local_distance, &local_distance + 1,
 278                  &min_distance, minimum<distance_type>());
 279
 280 #ifdef PBGL_ACCOUNTING
 281       std::size_t deletions = 0;
 282       all_reduce(this->process_group, &local_deletions, &local_deletions + 1,
 283                  &deletions, std::plus<std::size_t>());
 284       if (process_id(this->process_group) == 0)
 285         eager_dijkstra_shortest_paths_stats.deleted_vertices
 286           .push_back(deletions);
 287       local_deletions = 0;
 288       BOOST_ASSERT(deletions > 0);
 289 #endif
 290
 291       return min_distance == (std::numeric_limits<distance_type>::max)();
 292     }
 293
 294   public:
 295     void
 296     receive_update(process_id_type source, vertex_descriptor vertex,
 297                    distance_type distance)
 298     {
 299       // Update the queue if the received distance is better than
 300       // the distance we know locally
 301       if (distance <= get(distance_map, vertex)) {
 302
 303         // Update the local distance map
 304         put(distance_map, vertex, distance);
 305
 306         bool is_in_queue = queue.contains(vertex);
 307
 308         if (!is_in_queue)
 309           queue.push(vertex);
 310         else
 311           queue.update(vertex);
 312       }
 313     }
 314
 315     void
 316     receive_update(process_id_type source, vertex_descriptor vertex,
 317                    std::pair<distance_type, vertex_descriptor> p)
 318     {
 319       if (p.first <= get(distance_map, vertex)) {
 320         put(predecessor_map, vertex, p.second);
 321         receive_update(source, vertex, p.first);
 322       }
 323     }
 324
 325   private:
 326     queue_type     queue;
 327     DistanceMap    distance_map;
 328     PredecessorMap predecessor_map;
 329     distance_type  min_distance;
 330     distance_type  lookahead;
 331 #ifdef PBGL_ACCOUNTING
 332     std::size_t    local_deletions;
 333 #endif
 334   };
 335   /**********************************************************************/
 336 } // end namespace detail
 337
 338 template<typename DistributedGraph, typename DijkstraVisitor,
 339          typename PredecessorMap, typename DistanceMap, typename WeightMap,
 340          typename IndexMap, typename ColorMap, typename Compare,
 341          typename Combine, typename DistInf, typename DistZero>
 342 void
 343 eager_dijkstra_shortest_paths
 344   (const DistributedGraph& g,
 345    typename graph_traits<DistributedGraph>::vertex_descriptor s,
 346    PredecessorMap predecessor, DistanceMap distance,
 347    typename property_traits<DistanceMap>::value_type lookahead,
 348    WeightMap weight, IndexMap index_map, ColorMap color_map,
 349    Compare compare, Combine combine, DistInf inf, DistZero zero,
 350    DijkstraVisitor vis)
 351 {
 352 #ifdef PBGL_ACCOUNTING
 353   eager_dijkstra_shortest_paths_stats.deleted_vertices.clear();
 354   eager_dijkstra_shortest_paths_stats.lookahead = lookahead;
 355   eager_dijkstra_shortest_paths_stats.execution_time = accounting::get_time();
 356 #endif
 357
 358   // Initialize local portion of property maps
 359   typename graph_traits<DistributedGraph>::vertex_iterator ui, ui_end;
 360   for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
 361     put(distance, *ui, inf);
 362     put(predecessor, *ui, *ui);
 363   }
 364   put(distance, s, zero);
 365
 366   // Dijkstra Queue
 367   typedef detail::lookahead_dijkstra_queue
 368             <DistributedGraph, Combine, Compare, IndexMap, DistanceMap,
 369              PredecessorMap> Queue;
 370
 371   Queue Q(g, combine, compare, index_map, distance,
 372           predecessor, lookahead);
 373
 374   // Parallel Dijkstra visitor
 375   detail::parallel_dijkstra_bfs_visitor
 376     <DijkstraVisitor, Queue, WeightMap, PredecessorMap, DistanceMap, Combine,
 377      Compare> bfs_vis(vis, Q, weight, predecessor, distance, combine, compare,
 378                       zero);
 379
 380   set_property_map_role(vertex_color, color_map);
 381   set_property_map_role(vertex_distance, distance);
 382
 383   breadth_first_search(g, s, Q, bfs_vis, color_map);
 384
 385 #ifdef PBGL_ACCOUNTING
 386   eager_dijkstra_shortest_paths_stats.execution_time =
 387     accounting::get_time()
 388     - eager_dijkstra_shortest_paths_stats.execution_time;
 389 #endif
 390 }
 391
 392 template<typename DistributedGraph, typename DijkstraVisitor,
 393          typename PredecessorMap, typename DistanceMap, typename WeightMap>
 394 void
 395 eager_dijkstra_shortest_paths
 396   (const DistributedGraph& g,
 397    typename graph_traits<DistributedGraph>::vertex_descriptor s,
 398    PredecessorMap predecessor, DistanceMap distance,
 399    typename property_traits<DistanceMap>::value_type lookahead,
 400    WeightMap weight)
 401 {
 402   typedef typename property_traits<DistanceMap>::value_type distance_type;
 403
 404   std::vector<default_color_type> colors(num_vertices(g), white_color);
 405
 406   eager_dijkstra_shortest_paths(g, s, predecessor, distance, lookahead, weight,
 407                                 get(vertex_index, g),
 408                                 make_iterator_property_map(&colors[0],
 409                                                            get(vertex_index,
 410                                                                g)),
 411                                 std::less<distance_type>(),
 412                                 closed_plus<distance_type>(),
 413                                 distance_type(),
 414                                 (std::numeric_limits<distance_type>::max)(),
 415                                 dijkstra_visitor<>());
 416 }
 417
 418 template<typename DistributedGraph, typename DijkstraVisitor,
 419          typename PredecessorMap, typename DistanceMap>
 420 void
 421 eager_dijkstra_shortest_paths
 422   (const DistributedGraph& g,
 423    typename graph_traits<DistributedGraph>::vertex_descriptor s,
 424    PredecessorMap predecessor, DistanceMap distance,
 425    typename property_traits<DistanceMap>::value_type lookahead)
 426 {
 427   eager_dijkstra_shortest_paths(g, s, predecessor, distance, lookahead,
 428                                get(edge_weight, g));
 429 }
 430 } // end namespace distributed
 431
 432 #ifdef PBGL_ACCOUNTING
 433 using distributed::eager_dijkstra_shortest_paths_stats;
 434 #endif
 435
 436 using distributed::eager_dijkstra_shortest_paths;
 437
 438 } } // end namespace boost::graph
 439
 440 #endif // BOOST_GRAPH_EAGER_DIJKSTRA_SHORTEST_PATHS_HPP