| // Copyright (C) 2007 The Trustees of Indiana University. |
| |
| // Use, modification and distribution is subject to the Boost Software |
| // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| |
| // Authors: Douglas Gregor |
| // Andrew Lumsdaine |
| |
| /************************************************************************** |
| * This source file implements the Delta-stepping algorithm: * |
| * * |
| * Ulrich Meyer and Peter Sanders. Parallel Shortest Path for Arbitrary * |
| * Graphs. In Proceedings from the 6th International Euro-Par * |
| * Conference on Parallel Processing, pages 461--470, 2000. * |
| * * |
| * Ulrich Meyer, Peter Sanders: [Delta]-stepping: A Parallelizable * |
| * Shortest Path Algorithm. J. Algorithms 49(1): 114-152, 2003. * |
| * * |
| * There are several potential optimizations we could still perform for * |
| * this algorithm implementation: * |
| * * |
| * - Implement "shortcuts", which bound the number of reinsertions * |
| * in a single bucket (to one). The computation of shortcuts looks * |
| * expensive in a distributed-memory setting, but it could be * |
| * ammortized over many queries. * |
| * * |
| * - The size of the "buckets" data structure can be bounded to * |
| * max_edge_weight/delta buckets, if we treat the buckets as a * |
| * circular array. * |
| * * |
| * - If we partition light/heavy edges ahead of time, we could improve * |
| * relaxation performance by only iterating over the right portion * |
| * of the out-edge list each time. * |
| * * |
| * - Implement a more sophisticated algorithm for guessing "delta", * |
| * based on the shortcut-finding algorithm. * |
| **************************************************************************/ |
| #ifndef BOOST_GRAPH_DELTA_STEPPING_SHORTEST_PATHS_HPP |
| #define BOOST_GRAPH_DELTA_STEPPING_SHORTEST_PATHS_HPP |
| |
| #ifndef BOOST_GRAPH_USE_MPI |
| #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" |
| #endif |
| |
| #include <boost/config.hpp> |
| #include <boost/graph/graph_traits.hpp> |
| #include <boost/property_map/property_map.hpp> |
| #include <boost/graph/iteration_macros.hpp> |
| #include <limits> |
| #include <list> |
| #include <vector> |
| #include <boost/graph/parallel/container_traits.hpp> |
| #include <boost/graph/parallel/properties.hpp> |
| #include <boost/graph/distributed/detail/dijkstra_shortest_paths.hpp> |
| #include <utility> // for std::pair |
| #include <functional> // for std::logical_or |
| #include <boost/graph/parallel/algorithm.hpp> // for all_reduce |
| #include <cassert> |
| #include <algorithm> // for std::min, std::max |
| #include <boost/graph/parallel/simple_trigger.hpp> |
| |
| #ifdef PBGL_DELTA_STEPPING_DEBUG |
| # include <iostream> // for std::cerr |
| #endif |
| |
| namespace boost { namespace graph { namespace distributed { |
| |
| template<typename Graph, typename PredecessorMap, typename DistanceMap, |
| typename EdgeWeightMap> |
| class delta_stepping_impl { |
| typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
| typedef typename graph_traits<Graph>::degree_size_type Degree; |
| typedef typename property_traits<EdgeWeightMap>::value_type Dist; |
| typedef typename boost::graph::parallel::process_group_type<Graph>::type |
| ProcessGroup; |
| |
| typedef std::list<Vertex> Bucket; |
| typedef typename Bucket::iterator BucketIterator; |
| typedef typename std::vector<Bucket*>::size_type BucketIndex; |
| |
| typedef detail::dijkstra_msg_value<DistanceMap, PredecessorMap> MessageValue; |
| |
| enum { |
| // Relax a remote vertex. The message contains a pair<Vertex, |
| // MessageValue>, the first part of which is the vertex whose |
| // tentative distance is being relaxed and the second part |
| // contains either the new distance (if there is no predecessor |
| // map) or a pair with the distance and predecessor. |
| msg_relax |
| }; |
| |
| public: |
| delta_stepping_impl(const Graph& g, |
| PredecessorMap predecessor, |
| DistanceMap distance, |
| EdgeWeightMap weight, |
| Dist delta); |
| |
| delta_stepping_impl(const Graph& g, |
| PredecessorMap predecessor, |
| DistanceMap distance, |
| EdgeWeightMap weight); |
| |
| void run(Vertex s); |
| |
| private: |
| // Relax the edge (u, v), creating a new best path of distance x. |
| void relax(Vertex u, Vertex v, Dist x); |
| |
| // Synchronize all of the processes, by receiving all messages that |
| // have not yet been received. |
| void synchronize(); |
| |
| // Handle a relax message that contains only the target and |
| // distance. This kind of message will be received when the |
| // predecessor map is a dummy_property_map. |
| void handle_relax_message(Vertex v, Dist x) { relax(v, v, x); } |
| |
| // Handle a relax message that contains the source (predecessor), |
| // target, and distance. This kind of message will be received when |
| // the predecessor map is not a dummy_property_map. |
| void handle_relax_message(Vertex v, const std::pair<Dist, Vertex>& p) |
| { relax(p.second, v, p.first); } |
| |
| // Setup triggers for msg_relax messages |
| void setup_triggers(); |
| |
| void handle_msg_relax(int /*source*/, int /*tag*/, |
| const std::pair<Vertex, typename MessageValue::type>& data, |
| trigger_receive_context) |
| { handle_relax_message(data.first, data.second); } |
| |
| const Graph& g; |
| PredecessorMap predecessor; |
| DistanceMap distance; |
| EdgeWeightMap weight; |
| Dist delta; |
| ProcessGroup pg; |
| typename property_map<Graph, vertex_owner_t>::const_type owner; |
| typename property_map<Graph, vertex_local_t>::const_type local; |
| |
| // A "property map" that contains the position of each vertex in |
| // whatever bucket it resides in. |
| std::vector<BucketIterator> position_in_bucket; |
| |
| // Bucket data structure. The ith bucket contains all local vertices |
| // with (tentative) distance in the range [i*delta, |
| // (i+1)*delta). |
| std::vector<Bucket*> buckets; |
| |
| // This "dummy" list is used only so that we can initialize the |
| // position_in_bucket property map with non-singular iterators. This |
| // won't matter for most implementations of the C++ Standard |
| // Library, but it avoids undefined behavior and allows us to run |
| // with library "debug modes". |
| std::list<Vertex> dummy_list; |
| |
| // A "property map" that states which vertices have been deleted |
| // from the bucket in this iteration. |
| std::vector<bool> vertex_was_deleted; |
| }; |
| |
| template<typename Graph, typename PredecessorMap, typename DistanceMap, |
| typename EdgeWeightMap> |
| delta_stepping_impl<Graph, PredecessorMap, DistanceMap, EdgeWeightMap>:: |
| delta_stepping_impl(const Graph& g, |
| PredecessorMap predecessor, |
| DistanceMap distance, |
| EdgeWeightMap weight, |
| Dist delta) |
| : g(g), |
| predecessor(predecessor), |
| distance(distance), |
| weight(weight), |
| delta(delta), |
| pg(boost::graph::parallel::process_group_adl(g), attach_distributed_object()), |
| owner(get(vertex_owner, g)), |
| local(get(vertex_local, g)) |
| { |
| setup_triggers(); |
| } |
| |
| template<typename Graph, typename PredecessorMap, typename DistanceMap, |
| typename EdgeWeightMap> |
| delta_stepping_impl<Graph, PredecessorMap, DistanceMap, EdgeWeightMap>:: |
| delta_stepping_impl(const Graph& g, |
| PredecessorMap predecessor, |
| DistanceMap distance, |
| EdgeWeightMap weight) |
| : g(g), |
| predecessor(predecessor), |
| distance(distance), |
| weight(weight), |
| pg(boost::graph::parallel::process_group_adl(g), attach_distributed_object()), |
| owner(get(vertex_owner, g)), |
| local(get(vertex_local, g)) |
| { |
| using boost::parallel::all_reduce; |
| using boost::parallel::maximum; |
| using std::max; |
| |
| // Compute the maximum edge weight and degree |
| Dist max_edge_weight = 0; |
| Degree max_degree = 0; |
| BGL_FORALL_VERTICES_T(u, g, Graph) { |
| max_degree = max BOOST_PREVENT_MACRO_SUBSTITUTION (max_degree, out_degree(u, g)); |
| BGL_FORALL_OUTEDGES_T(u, e, g, Graph) |
| max_edge_weight = max BOOST_PREVENT_MACRO_SUBSTITUTION (max_edge_weight, get(weight, e)); |
| } |
| |
| max_edge_weight = all_reduce(pg, max_edge_weight, maximum<Dist>()); |
| max_degree = all_reduce(pg, max_degree, maximum<Degree>()); |
| |
| // Take a guess at delta, based on what works well for random |
| // graphs. |
| delta = max_edge_weight / max_degree; |
| if (delta == 0) |
| delta = 1; |
| |
| setup_triggers(); |
| } |
| |
| template<typename Graph, typename PredecessorMap, typename DistanceMap, |
| typename EdgeWeightMap> |
| void |
| delta_stepping_impl<Graph, PredecessorMap, DistanceMap, EdgeWeightMap>:: |
| run(Vertex s) |
| { |
| Dist inf = (std::numeric_limits<Dist>::max)(); |
| |
| // None of the vertices are stored in the bucket. |
| position_in_bucket.clear(); |
| position_in_bucket.resize(num_vertices(g), dummy_list.end()); |
| |
| // None of the vertices have been deleted |
| vertex_was_deleted.clear(); |
| vertex_was_deleted.resize(num_vertices(g), false); |
| |
| // No path from s to any other vertex, yet |
| BGL_FORALL_VERTICES_T(v, g, Graph) |
| put(distance, v, inf); |
| |
| // The distance to the starting node is zero |
| if (get(owner, s) == process_id(pg)) |
| // Put "s" into its bucket (bucket 0) |
| relax(s, s, 0); |
| else |
| // Note that we know the distance to s is zero |
| cache(distance, s, 0); |
| |
| BucketIndex max_bucket = (std::numeric_limits<BucketIndex>::max)(); |
| BucketIndex current_bucket = 0; |
| do { |
| // Synchronize with all of the other processes. |
| synchronize(); |
| |
| // Find the next bucket that has something in it. |
| while (current_bucket < buckets.size() |
| && (!buckets[current_bucket] || buckets[current_bucket]->empty())) |
| ++current_bucket; |
| if (current_bucket >= buckets.size()) |
| current_bucket = max_bucket; |
| |
| #ifdef PBGL_DELTA_STEPPING_DEBUG |
| std::cerr << "#" << process_id(pg) << ": lowest bucket is #" |
| << current_bucket << std::endl; |
| #endif |
| // Find the smallest bucket (over all processes) that has vertices |
| // that need to be processed. |
| using boost::parallel::all_reduce; |
| using boost::parallel::minimum; |
| current_bucket = all_reduce(pg, current_bucket, minimum<BucketIndex>()); |
| |
| if (current_bucket == max_bucket) |
| // There are no non-empty buckets in any process; exit. |
| break; |
| |
| #ifdef PBGL_DELTA_STEPPING_DEBUG |
| if (process_id(pg) == 0) |
| std::cerr << "Processing bucket #" << current_bucket << std::endl; |
| #endif |
| |
| // Contains the set of vertices that have been deleted in the |
| // relaxation of "light" edges. Note that we keep track of which |
| // vertices were deleted with the property map |
| // "vertex_was_deleted". |
| std::vector<Vertex> deleted_vertices; |
| |
| // Repeatedly relax light edges |
| bool nonempty_bucket; |
| do { |
| // Someone has work to do in this bucket. |
| |
| if (current_bucket < buckets.size() && buckets[current_bucket]) { |
| Bucket& bucket = *buckets[current_bucket]; |
| // For each element in the bucket |
| while (!bucket.empty()) { |
| Vertex u = bucket.front(); |
| |
| #ifdef PBGL_DELTA_STEPPING_DEBUG |
| std::cerr << "#" << process_id(pg) << ": processing vertex " |
| << get(vertex_global, g, u).second << "@" |
| << get(vertex_global, g, u).first |
| << std::endl; |
| #endif |
| |
| // Remove u from the front of the bucket |
| bucket.pop_front(); |
| |
| // Insert u into the set of deleted vertices, if it hasn't |
| // been done already. |
| if (!vertex_was_deleted[get(local, u)]) { |
| vertex_was_deleted[get(local, u)] = true; |
| deleted_vertices.push_back(u); |
| } |
| |
| // Relax each light edge. |
| Dist u_dist = get(distance, u); |
| BGL_FORALL_OUTEDGES_T(u, e, g, Graph) |
| if (get(weight, e) <= delta) // light edge |
| relax(u, target(e, g), u_dist + get(weight, e)); |
| } |
| } |
| |
| // Synchronize with all of the other processes. |
| synchronize(); |
| |
| // Is the bucket empty now? |
| nonempty_bucket = (current_bucket < buckets.size() |
| && buckets[current_bucket] |
| && !buckets[current_bucket]->empty()); |
| } while (all_reduce(pg, nonempty_bucket, std::logical_or<bool>())); |
| |
| // Relax heavy edges for each of the vertices that we previously |
| // deleted. |
| for (typename std::vector<Vertex>::iterator iter = deleted_vertices.begin(); |
| iter != deleted_vertices.end(); ++iter) { |
| // Relax each heavy edge. |
| Vertex u = *iter; |
| Dist u_dist = get(distance, u); |
| BGL_FORALL_OUTEDGES_T(u, e, g, Graph) |
| if (get(weight, e) > delta) // heavy edge |
| relax(u, target(e, g), u_dist + get(weight, e)); |
| } |
| |
| // Go to the next bucket: the current bucket must already be empty. |
| ++current_bucket; |
| } while (true); |
| |
| // Delete all of the buckets. |
| for (typename std::vector<Bucket*>::iterator iter = buckets.begin(); |
| iter != buckets.end(); ++iter) { |
| if (*iter) { |
| delete *iter; |
| *iter = 0; |
| } |
| } |
| } |
| |
| template<typename Graph, typename PredecessorMap, typename DistanceMap, |
| typename EdgeWeightMap> |
| void |
| delta_stepping_impl<Graph, PredecessorMap, DistanceMap, EdgeWeightMap>:: |
| relax(Vertex u, Vertex v, Dist x) |
| { |
| #ifdef PBGL_DELTA_STEPPING_DEBUG |
| std::cerr << "#" << process_id(pg) << ": relax(" |
| << get(vertex_global, g, u).second << "@" |
| << get(vertex_global, g, u).first << ", " |
| << get(vertex_global, g, v).second << "@" |
| << get(vertex_global, g, v).first << ", " |
| << x << ")" << std::endl; |
| #endif |
| |
| if (x < get(distance, v)) { |
| // We're relaxing the edge to vertex v. |
| if (get(owner, v) == process_id(pg)) { |
| // Compute the new bucket index for v |
| BucketIndex new_index = static_cast<BucketIndex>(x / delta); |
| |
| // Make sure there is enough room in the buckets data structure. |
| if (new_index >= buckets.size()) buckets.resize(new_index + 1, 0); |
| |
| // Make sure that we have allocated the bucket itself. |
| if (!buckets[new_index]) buckets[new_index] = new Bucket; |
| |
| if (get(distance, v) != (std::numeric_limits<Dist>::max)() |
| && !vertex_was_deleted[get(local, v)]) { |
| // We're moving v from an old bucket into a new one. Compute |
| // the old index, then splice it in. |
| BucketIndex old_index |
| = static_cast<BucketIndex>(get(distance, v) / delta); |
| buckets[new_index]->splice(buckets[new_index]->end(), |
| *buckets[old_index], |
| position_in_bucket[get(local, v)]); |
| } else { |
| // We're inserting v into a bucket for the first time. Put it |
| // at the end. |
| buckets[new_index]->push_back(v); |
| } |
| |
| // v is now at the last position in the new bucket |
| position_in_bucket[get(local, v)] = buckets[new_index]->end(); |
| --position_in_bucket[get(local, v)]; |
| |
| // Update predecessor and tentative distance information |
| put(predecessor, v, u); |
| put(distance, v, x); |
| } else { |
| #ifdef PBGL_DELTA_STEPPING_DEBUG |
| std::cerr << "#" << process_id(pg) << ": sending relax(" |
| << get(vertex_global, g, u).second << "@" |
| << get(vertex_global, g, u).first << ", " |
| << get(vertex_global, g, v).second << "@" |
| << get(vertex_global, g, v).first << ", " |
| << x << ") to " << get(owner, v) << std::endl; |
| |
| #endif |
| // The vertex is remote: send a request to the vertex's owner |
| send(pg, get(owner, v), msg_relax, |
| std::make_pair(v, MessageValue::create(x, u))); |
| |
| // Cache tentative distance information |
| cache(distance, v, x); |
| } |
| } |
| } |
| |
| template<typename Graph, typename PredecessorMap, typename DistanceMap, |
| typename EdgeWeightMap> |
| void |
| delta_stepping_impl<Graph, PredecessorMap, DistanceMap, EdgeWeightMap>:: |
| synchronize() |
| { |
| using boost::graph::parallel::synchronize; |
| |
| // Synchronize at the process group level. |
| synchronize(pg); |
| |
| // Receive any relaxation request messages. |
| // typedef typename ProcessGroup::process_id_type process_id_type; |
| // while (optional<std::pair<process_id_type, int> > stp = probe(pg)) { |
| // // Receive the relaxation message |
| // assert(stp->second == msg_relax); |
| // std::pair<Vertex, typename MessageValue::type> data; |
| // receive(pg, stp->first, stp->second, data); |
| |
| // // Turn it into a "relax" call |
| // handle_relax_message(data.first, data.second); |
| // } |
| } |
| |
| template<typename Graph, typename PredecessorMap, typename DistanceMap, |
| typename EdgeWeightMap> |
| void |
| delta_stepping_impl<Graph, PredecessorMap, DistanceMap, EdgeWeightMap>:: |
| setup_triggers() |
| { |
| using boost::graph::parallel::simple_trigger; |
| |
| simple_trigger(pg, msg_relax, this, |
| &delta_stepping_impl::handle_msg_relax); |
| } |
| |
| template<typename Graph, typename PredecessorMap, typename DistanceMap, |
| typename EdgeWeightMap> |
| void |
| delta_stepping_shortest_paths |
| (const Graph& g, |
| typename graph_traits<Graph>::vertex_descriptor s, |
| PredecessorMap predecessor, DistanceMap distance, EdgeWeightMap weight, |
| typename property_traits<EdgeWeightMap>::value_type delta) |
| { |
| // The "distance" map needs to act like one, retrieving the default |
| // value of infinity. |
| set_property_map_role(vertex_distance, distance); |
| |
| // Construct the implementation object, which will perform all of |
| // the actual work. |
| delta_stepping_impl<Graph, PredecessorMap, DistanceMap, EdgeWeightMap> |
| impl(g, predecessor, distance, weight, delta); |
| |
| // Run the delta-stepping algorithm. The results will show up in |
| // "predecessor" and "weight". |
| impl.run(s); |
| } |
| |
| template<typename Graph, typename PredecessorMap, typename DistanceMap, |
| typename EdgeWeightMap> |
| void |
| delta_stepping_shortest_paths |
| (const Graph& g, |
| typename graph_traits<Graph>::vertex_descriptor s, |
| PredecessorMap predecessor, DistanceMap distance, EdgeWeightMap weight) |
| { |
| // The "distance" map needs to act like one, retrieving the default |
| // value of infinity. |
| set_property_map_role(vertex_distance, distance); |
| |
| // Construct the implementation object, which will perform all of |
| // the actual work. |
| delta_stepping_impl<Graph, PredecessorMap, DistanceMap, EdgeWeightMap> |
| impl(g, predecessor, distance, weight); |
| |
| // Run the delta-stepping algorithm. The results will show up in |
| // "predecessor" and "weight". |
| impl.run(s); |
| } |
| |
| } } } // end namespace boost::graph::distributed |
| |
| #endif // BOOST_GRAPH_DELTA_STEPPING_SHORTEST_PATHS_HPP |