graph/distributed/eager_dijkstra_shortest_paths.hpp

0001 // Copyright (C) 2004-2006 The Trustees of Indiana University.
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Douglas Gregor
0008 //           Andrew Lumsdaine
0009
0010 /**************************************************************************
0011  * This source file implements a variation on distributed Dijkstra's      *
0012  * algorithm that can expose additional parallelism by permitting         *
0013  * vertices within a certain distance from the minimum to be processed,   *
0014  * even though they may not be at their final distance. This can          *
0015  * introduce looping, but the algorithm will still terminate so long as   *
0016  * there are no negative loops.                                           *
0017  **************************************************************************/
0018 #ifndef BOOST_GRAPH_EAGER_DIJKSTRA_SHORTEST_PATHS_HPP
0019 #define BOOST_GRAPH_EAGER_DIJKSTRA_SHORTEST_PATHS_HPP
0020
0021 #ifndef BOOST_GRAPH_USE_MPI
0022 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
0023 #endif
0024
0025 #include <boost/assert.hpp>
0026 #include <boost/graph/distributed/detail/dijkstra_shortest_paths.hpp>
0027 #include <boost/property_map/parallel/caching_property_map.hpp>
0028 #include <boost/pending/indirect_cmp.hpp>
0029 #include <boost/graph/distributed/detail/remote_update_set.hpp>
0030 #include <vector>
0031 #include <boost/graph/breadth_first_search.hpp>
0032 #include <boost/graph/dijkstra_shortest_paths.hpp>
0033 #include <boost/graph/parallel/container_traits.hpp>
0034 #include <boost/pending/relaxed_heap.hpp>
0035
0036 #ifdef PBGL_ACCOUNTING
0037 #  include <boost/graph/accounting.hpp>
0038 #  include <numeric>
0039 #endif // PBGL_ACCOUNTING
0040
0041 #ifdef MUTABLE_QUEUE
0042 #  include <boost/pending/mutable_queue.hpp>
0043 #endif
0044
0045 namespace boost { namespace graph { namespace distributed {
0046
0047 #ifdef PBGL_ACCOUNTING
0048 struct eager_dijkstra_shortest_paths_stats_t
0049 {
0050   /* The value of the lookahead parameter. */
0051   double lookahead;
0052
0053   /* Total wall-clock time used by the algorithm.*/
0054   accounting::time_type execution_time;
0055
0056   /* The number of vertices deleted in each superstep. */
0057   std::vector<std::size_t> deleted_vertices;
0058
0059   template<typename OutputStream>
0060   void print(OutputStream& out)
0061   {
0062     double avg_deletions = std::accumulate(deleted_vertices.begin(),
0063                                            deleted_vertices.end(),
0064                                            0.0);
0065     avg_deletions /= deleted_vertices.size();
0066
0067     out << "Problem = \"Single-Source Shortest Paths\"\n"
0068         << "Algorithm = \"Eager Dijkstra\"\n"
0069         << "Function = eager_dijkstra_shortest_paths\n"
0070         << "(P) Lookahead = " << lookahead << "\n"
0071         << "Wall clock time = " << accounting::print_time(execution_time)
0072         << "\nSupersteps = " << deleted_vertices.size() << "\n"
0073         << "Avg. deletions per superstep = " << avg_deletions << "\n";
0074   }
0075 };
0076
0077 static eager_dijkstra_shortest_paths_stats_t eager_dijkstra_shortest_paths_stats;
0078 #endif
0079
0080 namespace detail {
0081
0082 // Borrowed from BGL's dijkstra_shortest_paths
0083 template <class UniformCostVisitor, class Queue,
0084           class WeightMap, class PredecessorMap, class DistanceMap,
0085           class BinaryFunction, class BinaryPredicate>
0086  struct parallel_dijkstra_bfs_visitor : bfs_visitor<>
0087 {
0088   typedef typename property_traits<DistanceMap>::value_type distance_type;
0089
0090   parallel_dijkstra_bfs_visitor(UniformCostVisitor vis, Queue& Q,
0091                                 WeightMap w, PredecessorMap p, DistanceMap d,
0092                                 BinaryFunction combine, BinaryPredicate compare,
0093                                 distance_type zero)
0094     : m_vis(vis), m_Q(Q), m_weight(w), m_predecessor(p), m_distance(d),
0095       m_combine(combine), m_compare(compare), m_zero(zero)  { }
0096
0097   template <class Vertex, class Graph>
0098   void initialize_vertex(Vertex u, Graph& g)
0099     { m_vis.initialize_vertex(u, g); }
0100   template <class Vertex, class Graph>
0101   void discover_vertex(Vertex u, Graph& g) { m_vis.discover_vertex(u, g); }
0102   template <class Vertex, class Graph>
0103   void examine_vertex(Vertex u, Graph& g) { m_vis.examine_vertex(u, g); }
0104
0105   /* Since the eager formulation of Parallel Dijkstra's algorithm can
0106      loop, we may relax on *any* edge, not just those associated with
0107      white and gray targets. */
0108   template <class Edge, class Graph>
0109   void examine_edge(Edge e, Graph& g) {
0110     if (m_compare(get(m_weight, e), m_zero))
0111         boost::throw_exception(negative_edge());
0112
0113     m_vis.examine_edge(e, g);
0114
0115     boost::parallel::caching_property_map<PredecessorMap> c_pred(m_predecessor);
0116     boost::parallel::caching_property_map<DistanceMap> c_dist(m_distance);
0117
0118     distance_type old_distance = get(c_dist, target(e, g));
0119
0120     bool m_decreased = relax(e, g, m_weight, c_pred, c_dist,
0121                              m_combine, m_compare);
0122
0123     /* On x86 Linux with optimization, we sometimes get into a
0124        horrible case where m_decreased is true but the distance hasn't
0125        actually changed. This occurs when the comparison inside
0126        relax() occurs with the 80-bit precision of the x87 floating
0127        point unit, but the difference is lost when the resulting
0128        values are written back to lower-precision memory (e.g., a
0129        double). With the eager Dijkstra's implementation, this results
0130        in looping. */
0131     if (m_decreased && old_distance != get(c_dist, target(e, g))) {
0132       m_Q.update(target(e, g));
0133       m_vis.edge_relaxed(e, g);
0134     } else
0135       m_vis.edge_not_relaxed(e, g);
0136   }
0137   template <class Vertex, class Graph>
0138   void finish_vertex(Vertex u, Graph& g) { m_vis.finish_vertex(u, g); }
0139
0140   UniformCostVisitor m_vis;
0141   Queue& m_Q;
0142   WeightMap m_weight;
0143   PredecessorMap m_predecessor;
0144   DistanceMap m_distance;
0145   BinaryFunction m_combine;
0146   BinaryPredicate m_compare;
0147   distance_type m_zero;
0148 };
0149
0150   /**********************************************************************
0151    * Dijkstra queue that implements arbitrary "lookahead"               *
0152    **********************************************************************/
0153   template<typename Graph, typename Combine, typename Compare,
0154            typename VertexIndexMap, typename DistanceMap,
0155            typename PredecessorMap>
0156   class lookahead_dijkstra_queue
0157     : public graph::detail::remote_update_set<
0158                lookahead_dijkstra_queue<
0159                  Graph, Combine, Compare, VertexIndexMap, DistanceMap,
0160                  PredecessorMap>,
0161                typename boost::graph::parallel::process_group_type<Graph>::type,
0162                typename dijkstra_msg_value<DistanceMap, PredecessorMap>::type,
0163                typename property_map<Graph, vertex_owner_t>::const_type>
0164   {
0165     typedef typename graph_traits<Graph>::vertex_descriptor
0166       vertex_descriptor;
0167     typedef lookahead_dijkstra_queue self_type;
0168     typedef typename boost::graph::parallel::process_group_type<Graph>::type
0169       process_group_type;
0170     typedef dijkstra_msg_value<DistanceMap, PredecessorMap> msg_value_creator;
0171     typedef typename msg_value_creator::type msg_value_type;
0172     typedef typename property_map<Graph, vertex_owner_t>::const_type
0173       OwnerPropertyMap;
0174
0175     typedef graph::detail::remote_update_set<self_type, process_group_type,
0176                                              msg_value_type, OwnerPropertyMap>
0177       inherited;
0178
0179     // Priority queue for tentative distances
0180     typedef indirect_cmp<DistanceMap, Compare> queue_compare_type;
0181
0182     typedef typename property_traits<DistanceMap>::value_type distance_type;
0183
0184 #ifdef MUTABLE_QUEUE
0185     typedef mutable_queue<vertex_descriptor, std::vector<vertex_descriptor>,
0186                           queue_compare_type, VertexIndexMap> queue_type;
0187
0188 #else
0189     typedef relaxed_heap<vertex_descriptor, queue_compare_type,
0190                          VertexIndexMap> queue_type;
0191 #endif // MUTABLE_QUEUE
0192
0193     typedef typename process_group_type::process_id_type process_id_type;
0194
0195   public:
0196     typedef vertex_descriptor value_type;
0197
0198     lookahead_dijkstra_queue(const Graph& g,
0199                              const Combine& combine,
0200                              const Compare& compare,
0201                              const VertexIndexMap& id,
0202                              const DistanceMap& distance_map,
0203                              const PredecessorMap& predecessor_map,
0204                              distance_type lookahead)
0205       : inherited(boost::graph::parallel::process_group(g), get(vertex_owner, g)),
0206         queue(num_vertices(g), queue_compare_type(distance_map, compare), id),
0207         distance_map(distance_map),
0208         predecessor_map(predecessor_map),
0209         min_distance(0),
0210         lookahead(lookahead)
0211 #ifdef PBGL_ACCOUNTING
0212         , local_deletions(0)
0213 #endif
0214     { }
0215
0216     void push(const value_type& x)
0217     {
0218       msg_value_type msg_value =
0219         msg_value_creator::create(get(distance_map, x),
0220                                   predecessor_value(get(predecessor_map, x)));
0221       inherited::update(x, msg_value);
0222     }
0223
0224     void update(const value_type& x) { push(x); }
0225
0226     void pop()
0227     {
0228       queue.pop();
0229 #ifdef PBGL_ACCOUNTING
0230       ++local_deletions;
0231 #endif
0232     }
0233
0234     value_type&       top()       { return queue.top(); }
0235     const value_type& top() const { return queue.top(); }
0236
0237     bool empty()
0238     {
0239       inherited::collect();
0240
0241       // If there are no suitable messages, wait until we get something
0242       while (!has_suitable_vertex()) {
0243         if (do_synchronize()) return true;
0244       }
0245
0246       // Return true only if nobody has any messages; false if we
0247       // have suitable messages
0248       return false;
0249     }
0250
0251   private:
0252     vertex_descriptor predecessor_value(vertex_descriptor v) const
0253     { return v; }
0254
0255     vertex_descriptor
0256     predecessor_value(property_traits<dummy_property_map>::reference) const
0257     { return graph_traits<Graph>::null_vertex(); }
0258
0259     bool has_suitable_vertex() const
0260     {
0261       return (!queue.empty()
0262               && get(distance_map, queue.top()) <= min_distance + lookahead);
0263     }
0264
0265     bool do_synchronize()
0266     {
0267       using boost::parallel::all_reduce;
0268       using boost::parallel::minimum;
0269
0270       inherited::synchronize();
0271
0272       // TBD: could use combine here, but then we need to stop using
0273       // minimum<distance_type>() as the function object.
0274       distance_type local_distance =
0275         queue.empty()? (std::numeric_limits<distance_type>::max)()
0276         : get(distance_map, queue.top());
0277
0278       all_reduce(this->process_group, &local_distance, &local_distance + 1,
0279                  &min_distance, minimum<distance_type>());
0280
0281 #ifdef PBGL_ACCOUNTING
0282       std::size_t deletions = 0;
0283       all_reduce(this->process_group, &local_deletions, &local_deletions + 1,
0284                  &deletions, std::plus<std::size_t>());
0285       if (process_id(this->process_group) == 0)
0286         eager_dijkstra_shortest_paths_stats.deleted_vertices
0287           .push_back(deletions);
0288       local_deletions = 0;
0289       BOOST_ASSERT(deletions > 0);
0290 #endif
0291
0292       return min_distance == (std::numeric_limits<distance_type>::max)();
0293     }
0294
0295   public:
0296     void
0297     receive_update(process_id_type source, vertex_descriptor vertex,
0298                    distance_type distance)
0299     {
0300       // Update the queue if the received distance is better than
0301       // the distance we know locally
0302       if (distance <= get(distance_map, vertex)) {
0303
0304         // Update the local distance map
0305         put(distance_map, vertex, distance);
0306
0307         bool is_in_queue = queue.contains(vertex);
0308
0309         if (!is_in_queue)
0310           queue.push(vertex);
0311         else
0312           queue.update(vertex);
0313       }
0314     }
0315
0316     void
0317     receive_update(process_id_type source, vertex_descriptor vertex,
0318                    std::pair<distance_type, vertex_descriptor> p)
0319     {
0320       if (p.first <= get(distance_map, vertex)) {
0321         put(predecessor_map, vertex, p.second);
0322         receive_update(source, vertex, p.first);
0323       }
0324     }
0325
0326   private:
0327     queue_type     queue;
0328     DistanceMap    distance_map;
0329     PredecessorMap predecessor_map;
0330     distance_type  min_distance;
0331     distance_type  lookahead;
0332 #ifdef PBGL_ACCOUNTING
0333     std::size_t    local_deletions;
0334 #endif
0335   };
0336   /**********************************************************************/
0337 } // end namespace detail
0338
0339 template<typename DistributedGraph, typename DijkstraVisitor,
0340          typename PredecessorMap, typename DistanceMap, typename WeightMap,
0341          typename IndexMap, typename ColorMap, typename Compare,
0342          typename Combine, typename DistInf, typename DistZero>
0343 void
0344 eager_dijkstra_shortest_paths
0345   (const DistributedGraph& g,
0346    typename graph_traits<DistributedGraph>::vertex_descriptor s,
0347    PredecessorMap predecessor, DistanceMap distance,
0348    typename property_traits<DistanceMap>::value_type lookahead,
0349    WeightMap weight, IndexMap index_map, ColorMap color_map,
0350    Compare compare, Combine combine, DistInf inf, DistZero zero,
0351    DijkstraVisitor vis)
0352 {
0353 #ifdef PBGL_ACCOUNTING
0354   eager_dijkstra_shortest_paths_stats.deleted_vertices.clear();
0355   eager_dijkstra_shortest_paths_stats.lookahead = lookahead;
0356   eager_dijkstra_shortest_paths_stats.execution_time = accounting::get_time();
0357 #endif
0358
0359   // Initialize local portion of property maps
0360   typename graph_traits<DistributedGraph>::vertex_iterator ui, ui_end;
0361   for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
0362     put(distance, *ui, inf);
0363     put(predecessor, *ui, *ui);
0364   }
0365   put(distance, s, zero);
0366
0367   // Dijkstra Queue
0368   typedef detail::lookahead_dijkstra_queue
0369             <DistributedGraph, Combine, Compare, IndexMap, DistanceMap,
0370              PredecessorMap> Queue;
0371
0372   Queue Q(g, combine, compare, index_map, distance,
0373           predecessor, lookahead);
0374
0375   // Parallel Dijkstra visitor
0376   detail::parallel_dijkstra_bfs_visitor
0377     <DijkstraVisitor, Queue, WeightMap, PredecessorMap, DistanceMap, Combine,
0378      Compare> bfs_vis(vis, Q, weight, predecessor, distance, combine, compare,
0379                       zero);
0380
0381   set_property_map_role(vertex_color, color_map);
0382   set_property_map_role(vertex_distance, distance);
0383
0384   breadth_first_search(g, s, Q, bfs_vis, color_map);
0385
0386 #ifdef PBGL_ACCOUNTING
0387   eager_dijkstra_shortest_paths_stats.execution_time =
0388     accounting::get_time()
0389     - eager_dijkstra_shortest_paths_stats.execution_time;
0390 #endif
0391 }
0392
0393 template<typename DistributedGraph, typename DijkstraVisitor,
0394          typename PredecessorMap, typename DistanceMap, typename WeightMap>
0395 void
0396 eager_dijkstra_shortest_paths
0397   (const DistributedGraph& g,
0398    typename graph_traits<DistributedGraph>::vertex_descriptor s,
0399    PredecessorMap predecessor, DistanceMap distance,
0400    typename property_traits<DistanceMap>::value_type lookahead,
0401    WeightMap weight)
0402 {
0403   typedef typename property_traits<DistanceMap>::value_type distance_type;
0404
0405   std::vector<default_color_type> colors(num_vertices(g), white_color);
0406
0407   eager_dijkstra_shortest_paths(g, s, predecessor, distance, lookahead, weight,
0408                                 get(vertex_index, g),
0409                                 make_iterator_property_map(&colors[0],
0410                                                            get(vertex_index,
0411                                                                g)),
0412                                 std::less<distance_type>(),
0413                                 closed_plus<distance_type>(),
0414                                 distance_type(),
0415                                 (std::numeric_limits<distance_type>::max)(),
0416                                 dijkstra_visitor<>());
0417 }
0418
0419 template<typename DistributedGraph, typename DijkstraVisitor,
0420          typename PredecessorMap, typename DistanceMap>
0421 void
0422 eager_dijkstra_shortest_paths
0423   (const DistributedGraph& g,
0424    typename graph_traits<DistributedGraph>::vertex_descriptor s,
0425    PredecessorMap predecessor, DistanceMap distance,
0426    typename property_traits<DistanceMap>::value_type lookahead)
0427 {
0428   eager_dijkstra_shortest_paths(g, s, predecessor, distance, lookahead,
0429                                get(edge_weight, g));
0430 }
0431 } // end namespace distributed
0432
0433 #ifdef PBGL_ACCOUNTING
0434 using distributed::eager_dijkstra_shortest_paths_stats;
0435 #endif
0436
0437 using distributed::eager_dijkstra_shortest_paths;
0438
0439 } } // end namespace boost::graph
0440
0441 #endif // BOOST_GRAPH_EAGER_DIJKSTRA_SHORTEST_PATHS_HPP