123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514 |
- #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/property_map/parallel/parallel_property_maps.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 {
-
-
-
-
-
- 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:
-
- void relax(Vertex u, Vertex v, Dist x);
-
-
- void synchronize();
-
-
-
- void handle_relax_message(Vertex v, Dist x) { relax(v, v, x); }
-
-
-
- void handle_relax_message(Vertex v, const std::pair<Dist, Vertex>& p)
- { relax(p.second, v, p.first); }
-
-
- void setup_triggers();
- void handle_msg_relax(int , int ,
- 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;
-
-
- std::vector<BucketIterator> position_in_bucket;
-
-
-
- std::vector<Bucket*> buckets;
-
-
-
-
-
- std::list<Vertex> dummy_list;
-
-
- 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;
-
- 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>());
-
-
- 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)();
-
- position_in_bucket.clear();
- position_in_bucket.resize(num_vertices(g), dummy_list.end());
-
- vertex_was_deleted.clear();
- vertex_was_deleted.resize(num_vertices(g), false);
-
- BGL_FORALL_VERTICES_T(v, g, Graph)
- put(distance, v, inf);
-
- if (get(owner, s) == process_id(pg))
-
- relax(s, s, 0);
- else
-
- cache(distance, s, 0);
- BucketIndex max_bucket = (std::numeric_limits<BucketIndex>::max)();
- BucketIndex current_bucket = 0;
- do {
-
- synchronize();
-
- 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
-
-
- using boost::parallel::all_reduce;
- using boost::parallel::minimum;
- current_bucket = all_reduce(pg, current_bucket, minimum<BucketIndex>());
- if (current_bucket == max_bucket)
-
- break;
- #ifdef PBGL_DELTA_STEPPING_DEBUG
- if (process_id(pg) == 0)
- std::cerr << "Processing bucket #" << current_bucket << std::endl;
- #endif
-
-
-
-
- std::vector<Vertex> deleted_vertices;
-
- bool nonempty_bucket;
- do {
-
- if (current_bucket < buckets.size() && buckets[current_bucket]) {
- Bucket& bucket = *buckets[current_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
-
- bucket.pop_front();
-
-
-
- if (!vertex_was_deleted[get(local, u)]) {
- vertex_was_deleted[get(local, u)] = true;
- deleted_vertices.push_back(u);
- }
-
- Dist u_dist = get(distance, u);
- BGL_FORALL_OUTEDGES_T(u, e, g, Graph)
- if (get(weight, e) <= delta)
- relax(u, target(e, g), u_dist + get(weight, e));
- }
- }
-
- synchronize();
-
- nonempty_bucket = (current_bucket < buckets.size()
- && buckets[current_bucket]
- && !buckets[current_bucket]->empty());
- } while (all_reduce(pg, nonempty_bucket, std::logical_or<bool>()));
-
-
- for (typename std::vector<Vertex>::iterator iter = deleted_vertices.begin();
- iter != deleted_vertices.end(); ++iter) {
-
- Vertex u = *iter;
- Dist u_dist = get(distance, u);
- BGL_FORALL_OUTEDGES_T(u, e, g, Graph)
- if (get(weight, e) > delta)
- relax(u, target(e, g), u_dist + get(weight, e));
- }
-
- ++current_bucket;
- } while (true);
-
- 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)) {
-
- if (get(owner, v) == process_id(pg)) {
-
- BucketIndex new_index = static_cast<BucketIndex>(x / delta);
-
-
- if (new_index >= buckets.size()) buckets.resize(new_index + 1, 0);
-
- if (!buckets[new_index]) buckets[new_index] = new Bucket;
- if (get(distance, v) != (std::numeric_limits<Dist>::max)()
- && !vertex_was_deleted[get(local, v)]) {
-
-
- 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 {
-
-
- buckets[new_index]->push_back(v);
- }
-
- position_in_bucket[get(local, v)] = buckets[new_index]->end();
- --position_in_bucket[get(local, v)];
-
- 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
-
- send(pg, get(owner, v), msg_relax,
- std::make_pair(v, MessageValue::create(x, u)));
-
- cache(distance, v, x);
- }
- }
- }
- template<typename Graph, typename PredecessorMap, typename DistanceMap,
- typename EdgeWeightMap>
- void
- delta_stepping_impl<Graph, PredecessorMap, DistanceMap, EdgeWeightMap>::
- synchronize()
- {
- using boost::parallel::synchronize;
-
- synchronize(pg);
-
- }
- 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)
- {
-
-
- set_property_map_role(vertex_distance, distance);
-
-
- delta_stepping_impl<Graph, PredecessorMap, DistanceMap, EdgeWeightMap>
- impl(g, predecessor, distance, weight, delta);
-
-
- 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)
- {
-
-
- set_property_map_role(vertex_distance, distance);
-
-
- delta_stepping_impl<Graph, PredecessorMap, DistanceMap, EdgeWeightMap>
- impl(g, predecessor, distance, weight);
-
-
- impl.run(s);
- }
-
- } } }
- #endif
|