Chris@16: // Copyright 2004 The Trustees of Indiana University.
Chris@16: 
Chris@16: // Distributed under the Boost Software License, Version 1.0.
Chris@16: // (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: //  Authors: Douglas Gregor
Chris@16: //           Andrew Lumsdaine
Chris@16: #ifndef BOOST_GRAPH_PARALLEL_BRANDES_BETWEENNESS_CENTRALITY_HPP
Chris@16: #define BOOST_GRAPH_PARALLEL_BRANDES_BETWEENNESS_CENTRALITY_HPP
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_USE_MPI
Chris@16: #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
Chris@16: #endif
Chris@16: 
Chris@16: // #define COMPUTE_PATH_COUNTS_INLINE
Chris@16: 
Chris@16: #include <boost/graph/betweenness_centrality.hpp>
Chris@16: #include <boost/graph/overloading.hpp>
Chris@16: #include <boost/graph/distributed/concepts.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/assert.hpp>
Chris@16: 
Chris@16: // For additive_reducer
Chris@16: #include <boost/graph/distributed/distributed_graph_utility.hpp>
Chris@16: #include <boost/type_traits/is_convertible.hpp>
Chris@16: #include <boost/type_traits/is_same.hpp>
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: #include <boost/graph/named_function_params.hpp>
Chris@16: 
Chris@16: #include <boost/property_map/parallel/distributed_property_map.hpp>
Chris@16: #include <boost/graph/distributed/detail/dijkstra_shortest_paths.hpp>
Chris@16: #include <boost/tuple/tuple.hpp>
Chris@16: 
Chris@16: // NGE - Needed for minstd_rand at L807, should pass vertex list
Chris@16: //       or generator instead 
Chris@16: #include <boost/random/linear_congruential.hpp>
Chris@16: 
Chris@16: #include <algorithm>
Chris@16: #include <stack>
Chris@16: #include <vector>
Chris@16: 
Chris@16: // Appending reducer
Chris@16: template <typename T>
Chris@16: struct append_reducer {
Chris@16:   BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);
Chris@16:       
Chris@16:   template<typename K>
Chris@16:   T operator()(const K&) const { return T(); }
Chris@16:       
Chris@16:   template<typename K>
Chris@16:   T operator()(const K&, const T& x, const T& y) const 
Chris@16:   { 
Chris@16:     T z(x.begin(), x.end());
Chris@16:     for (typename T::const_iterator iter = y.begin(); iter != y.end(); ++iter)
Chris@16:       if (std::find(z.begin(), z.end(), *iter) == z.end())
Chris@16:         z.push_back(*iter);
Chris@16:     
Chris@16:     return z;
Chris@16:   }
Chris@16: };
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   namespace serialization {
Chris@16: 
Chris@16:     // TODO(nge): Write generalized serialization for tuples
Chris@16:     template<typename Archive, typename T1, typename T2, typename T3, 
Chris@16:              typename T4>
Chris@16:     void serialize(Archive & ar,
Chris@16:                    boost::tuple<T1,T2,T3, T4>& t,
Chris@16:                    const unsigned int)
Chris@16:     {
Chris@16:       ar & boost::tuples::get<0>(t);
Chris@16:       ar & boost::tuples::get<1>(t);
Chris@16:       ar & boost::tuples::get<2>(t);
Chris@16:       ar & boost::tuples::get<3>(t);
Chris@16:     }
Chris@16: 
Chris@16:   } // serialization
Chris@16: 
Chris@16:   template <typename OwnerMap, typename Tuple>
Chris@16:   class get_owner_of_first_tuple_element {
Chris@16: 
Chris@16:   public:
Chris@16:     typedef typename property_traits<OwnerMap>::value_type owner_type;
Chris@16:     
Chris@16:     get_owner_of_first_tuple_element(OwnerMap owner) : owner(owner) { }
Chris@16: 
Chris@16:     owner_type get_owner(Tuple t) { return get(owner, boost::tuples::get<0>(t)); }
Chris@16: 
Chris@16:   private:
Chris@16:     OwnerMap owner;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename OwnerMap, typename Tuple>
Chris@16:   typename get_owner_of_first_tuple_element<OwnerMap, Tuple>::owner_type
Chris@16:   get(get_owner_of_first_tuple_element<OwnerMap, Tuple> o, Tuple t)
Chris@16:   { return o.get_owner(t); } 
Chris@16: 
Chris@16:   template <typename OwnerMap>
Chris@16:   class get_owner_of_first_pair_element {
Chris@16: 
Chris@16:   public:
Chris@16:     typedef typename property_traits<OwnerMap>::value_type owner_type;
Chris@16:     
Chris@16:     get_owner_of_first_pair_element(OwnerMap owner) : owner(owner) { }
Chris@16: 
Chris@16:     template <typename Vertex, typename T>
Chris@16:     owner_type get_owner(std::pair<Vertex, T> p) { return get(owner, p.first); }
Chris@16: 
Chris@16:   private:
Chris@16:     OwnerMap owner;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename OwnerMap, typename Vertex, typename T>
Chris@16:   typename get_owner_of_first_pair_element<OwnerMap>::owner_type
Chris@16:   get(get_owner_of_first_pair_element<OwnerMap> o, std::pair<Vertex, T> p)
Chris@16:   { return o.get_owner(p); } 
Chris@16: 
Chris@16:   namespace graph { namespace parallel { namespace detail {
Chris@16: 
Chris@16:   template<typename DistanceMap, typename IncomingMap>
Chris@16:   class betweenness_centrality_msg_value
Chris@16:   {
Chris@16:     typedef typename property_traits<DistanceMap>::value_type distance_type;
Chris@16:     typedef typename property_traits<IncomingMap>::value_type incoming_type;
Chris@16:     typedef typename incoming_type::value_type incoming_value_type;
Chris@16: 
Chris@16:   public:
Chris@16:     typedef std::pair<distance_type, incoming_value_type> type;
Chris@16:     
Chris@16:     static type create(distance_type dist, incoming_value_type source)
Chris@16:     { return std::make_pair(dist, source); }
Chris@16:   };
Chris@16: 
Chris@16: 
Chris@16:   /************************************************************************/
Chris@16:   /* Delta-stepping Betweenness Centrality                                */
Chris@16:   /************************************************************************/
Chris@16: 
Chris@16:   template<typename Graph, typename DistanceMap, typename IncomingMap, 
Chris@16:            typename EdgeWeightMap, typename PathCountMap
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:            , typename IsSettledMap, typename VertexIndexMap
Chris@16: #endif
Chris@16:            >
Chris@16:   class betweenness_centrality_delta_stepping_impl { 
Chris@16:     // Could inherit from delta_stepping_impl to get run() method
Chris@16:     // but for the time being it's just reproduced here
Chris@16: 
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:     typedef typename graph_traits<Graph>::degree_size_type Degree;
Chris@16:     typedef typename property_traits<EdgeWeightMap>::value_type Dist;
Chris@16:     typedef typename property_traits<IncomingMap>::value_type IncomingType;
Chris@16:     typedef typename boost::graph::parallel::process_group_type<Graph>::type 
Chris@16:       ProcessGroup;
Chris@16:     
Chris@16:     typedef std::list<Vertex> Bucket;
Chris@16:     typedef typename Bucket::iterator BucketIterator;
Chris@16:     typedef typename std::vector<Bucket*>::size_type BucketIndex;
Chris@16: 
Chris@16:     typedef betweenness_centrality_msg_value<DistanceMap, IncomingMap> 
Chris@16:       MessageValue;
Chris@16:     
Chris@16:     enum { 
Chris@16:       // Relax a remote vertex. The message contains a pair<Vertex,
Chris@16:       // MessageValue>, the first part of which is the vertex whose
Chris@16:       // tentative distance is being relaxed and the second part
Chris@16:       // contains either the new distance (if there is no predecessor
Chris@16:       // map) or a pair with the distance and predecessor.
Chris@16:       msg_relax 
Chris@16:     };
Chris@16: 
Chris@16:   public:
Chris@16: 
Chris@16:     // Must supply delta, ctor that guesses delta removed 
Chris@16:     betweenness_centrality_delta_stepping_impl(const Graph& g,
Chris@16:                                                DistanceMap distance, 
Chris@16:                                                IncomingMap incoming,
Chris@16:                                                EdgeWeightMap weight,
Chris@16:                                                PathCountMap path_count,
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:                                                IsSettledMap is_settled,
Chris@16:                                                VertexIndexMap vertex_index,
Chris@16: #endif
Chris@16:                                                Dist delta);
Chris@16:     
Chris@16:     void run(Vertex s);
Chris@16: 
Chris@16:   private:
Chris@16:     // Relax the edge (u, v), creating a new best path of distance x.
Chris@16:     void relax(Vertex u, Vertex v, Dist x);
Chris@16: 
Chris@16:     // Synchronize all of the processes, by receiving all messages that
Chris@16:     // have not yet been received.
Chris@16:     void synchronize()
Chris@16:     {
Chris@101:       using boost::parallel::synchronize;
Chris@16:       synchronize(pg);
Chris@16:     }
Chris@16:     
Chris@16:     // Setup triggers for msg_relax messages
Chris@16:     void setup_triggers()
Chris@16:     {
Chris@101:       using boost::parallel::simple_trigger;
Chris@16:       simple_trigger(pg, msg_relax, this, 
Chris@16:                      &betweenness_centrality_delta_stepping_impl::handle_msg_relax);
Chris@16:     }
Chris@16: 
Chris@16:     void handle_msg_relax(int /*source*/, int /*tag*/,
Chris@16:                           const std::pair<Vertex, typename MessageValue::type>& data,
Chris@101:                           boost::parallel::trigger_receive_context)
Chris@16:     { relax(data.second.second, data.first, data.second.first); }
Chris@16: 
Chris@16:     const Graph& g;
Chris@16:     IncomingMap incoming;
Chris@16:     DistanceMap distance;
Chris@16:     EdgeWeightMap weight;
Chris@16:     PathCountMap path_count;
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:     IsSettledMap is_settled;
Chris@16:     VertexIndexMap vertex_index;
Chris@16: #endif
Chris@16:     Dist delta;
Chris@16:     ProcessGroup pg;
Chris@16:     typename property_map<Graph, vertex_owner_t>::const_type owner;
Chris@16:     typename property_map<Graph, vertex_local_t>::const_type local;
Chris@16:     
Chris@16:     // A "property map" that contains the position of each vertex in
Chris@16:     // whatever bucket it resides in.
Chris@16:     std::vector<BucketIterator> position_in_bucket;
Chris@16:     
Chris@16:     // Bucket data structure. The ith bucket contains all local vertices
Chris@16:     // with (tentative) distance in the range [i*delta,
Chris@16:     // (i+1)*delta). 
Chris@16:     std::vector<Bucket*> buckets;
Chris@16:     
Chris@16:     // This "dummy" list is used only so that we can initialize the
Chris@16:     // position_in_bucket property map with non-singular iterators. This
Chris@16:     // won't matter for most implementations of the C++ Standard
Chris@16:     // Library, but it avoids undefined behavior and allows us to run
Chris@16:     // with library "debug modes".
Chris@16:     std::list<Vertex> dummy_list;
Chris@16:     
Chris@16:     // A "property map" that states which vertices have been deleted
Chris@16:     // from the bucket in this iteration.
Chris@16:     std::vector<bool> vertex_was_deleted;
Chris@16:   };
Chris@16: 
Chris@16:   template<typename Graph, typename DistanceMap, typename IncomingMap, 
Chris@16:            typename EdgeWeightMap, typename PathCountMap
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:            , typename IsSettledMap, typename VertexIndexMap
Chris@16: #endif
Chris@16:            >
Chris@16:   betweenness_centrality_delta_stepping_impl<
Chris@16:     Graph, DistanceMap, IncomingMap, EdgeWeightMap, PathCountMap
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:            , IsSettledMap, VertexIndexMap
Chris@16: #endif
Chris@16:     >::
Chris@16:   betweenness_centrality_delta_stepping_impl(const Graph& g,
Chris@16:                                              DistanceMap distance,
Chris@16:                                              IncomingMap incoming,
Chris@16:                                              EdgeWeightMap weight,
Chris@16:                                              PathCountMap path_count,
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:                                              IsSettledMap is_settled,
Chris@16:                                              VertexIndexMap vertex_index,
Chris@16: #endif
Chris@16:                                              Dist delta)
Chris@16:     : g(g),
Chris@16:       incoming(incoming),
Chris@16:       distance(distance),
Chris@16:       weight(weight),
Chris@16:       path_count(path_count),
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:       is_settled(is_settled),
Chris@16:       vertex_index(vertex_index),
Chris@16: #endif
Chris@16:       delta(delta),
Chris@101:       pg(boost::graph::parallel::process_group_adl(g), boost::parallel::attach_distributed_object()),
Chris@16:       owner(get(vertex_owner, g)),
Chris@16:       local(get(vertex_local, g))
Chris@16: 
Chris@16:   { setup_triggers(); }
Chris@16: 
Chris@16:   template<typename Graph, typename DistanceMap, typename IncomingMap, 
Chris@16:            typename EdgeWeightMap, typename PathCountMap
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:            , typename IsSettledMap, typename VertexIndexMap
Chris@16: #endif
Chris@16:            >
Chris@16:   void
Chris@16:   betweenness_centrality_delta_stepping_impl<
Chris@16:     Graph, DistanceMap, IncomingMap, EdgeWeightMap, PathCountMap
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:            , IsSettledMap, VertexIndexMap
Chris@16: #endif
Chris@16:     >::
Chris@16:   run(Vertex s)
Chris@16:   {
Chris@16:     typedef typename boost::graph::parallel::process_group_type<Graph>::type 
Chris@16:       process_group_type;
Chris@16:     typename process_group_type::process_id_type id = process_id(pg);
Chris@16: 
Chris@16:     Dist inf = (std::numeric_limits<Dist>::max)();
Chris@16:     
Chris@16:     // None of the vertices are stored in the bucket.
Chris@16:     position_in_bucket.clear();
Chris@16:     position_in_bucket.resize(num_vertices(g), dummy_list.end());
Chris@16:     
Chris@16:     // None of the vertices have been deleted
Chris@16:     vertex_was_deleted.clear();
Chris@16:     vertex_was_deleted.resize(num_vertices(g), false);
Chris@16:     
Chris@16:     // No path from s to any other vertex, yet
Chris@16:     BGL_FORALL_VERTICES_T(v, g, Graph)
Chris@16:       put(distance, v, inf);
Chris@16:     
Chris@16:     // The distance to the starting node is zero
Chris@16:     if (get(owner, s) == id) 
Chris@16:       // Put "s" into its bucket (bucket 0)
Chris@16:       relax(s, s, 0);
Chris@16:     else
Chris@16:       // Note that we know the distance to s is zero
Chris@16:       cache(distance, s, 0);
Chris@16:     
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:     // Synchronize here to deliver initial relaxation since we don't
Chris@16:     // synchronize at the beginning of the inner loop any more
Chris@16:     synchronize(); 
Chris@16: 
Chris@16:     // Incoming edge count map is an implementation detail and should
Chris@16:     // be freed as soon as possible so build it here
Chris@16:     typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
Chris@16: 
Chris@16:     std::vector<edges_size_type> incoming_edge_countS(num_vertices(g));
Chris@16:     iterator_property_map<typename std::vector<edges_size_type>::iterator, VertexIndexMap> 
Chris@16:       incoming_edge_count(incoming_edge_countS.begin(), vertex_index);
Chris@16: #endif
Chris@16: 
Chris@16:     BucketIndex max_bucket = (std::numeric_limits<BucketIndex>::max)();
Chris@16:     BucketIndex current_bucket = 0;
Chris@16:     do {
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:       // We need to clear the outgoing map after every bucket so just build it here
Chris@16:       std::vector<IncomingType> outgoingS(num_vertices(g));
Chris@16:       IncomingMap outgoing(outgoingS.begin(), vertex_index);
Chris@16:       
Chris@16:       outgoing.set_reduce(append_reducer<IncomingType>());
Chris@16: #else
Chris@16:       // Synchronize with all of the other processes.
Chris@16:       synchronize();
Chris@16: #endif    
Chris@16:   
Chris@16:       // Find the next bucket that has something in it.
Chris@16:       while (current_bucket < buckets.size() 
Chris@16:              && (!buckets[current_bucket] || buckets[current_bucket]->empty()))
Chris@16:         ++current_bucket;
Chris@16:       if (current_bucket >= buckets.size())
Chris@16:         current_bucket = max_bucket;
Chris@16:       
Chris@16:       // Find the smallest bucket (over all processes) that has vertices
Chris@16:       // that need to be processed.
Chris@16:       using boost::parallel::all_reduce;
Chris@16:       using boost::parallel::minimum;
Chris@16:       current_bucket = all_reduce(pg, current_bucket, minimum<BucketIndex>());
Chris@16:       
Chris@16:       if (current_bucket == max_bucket)
Chris@16:         // There are no non-empty buckets in any process; exit. 
Chris@16:         break;
Chris@16:       
Chris@16:       // Contains the set of vertices that have been deleted in the
Chris@16:       // relaxation of "light" edges. Note that we keep track of which
Chris@16:       // vertices were deleted with the property map
Chris@16:       // "vertex_was_deleted".
Chris@16:       std::vector<Vertex> deleted_vertices;
Chris@16:       
Chris@16:       // Repeatedly relax light edges
Chris@16:       bool nonempty_bucket;
Chris@16:       do {
Chris@16:         // Someone has work to do in this bucket.
Chris@16:         
Chris@16:         if (current_bucket < buckets.size() && buckets[current_bucket]) {
Chris@16:           Bucket& bucket = *buckets[current_bucket];
Chris@16:           // For each element in the bucket
Chris@16:           while (!bucket.empty()) {
Chris@16:             Vertex u = bucket.front();
Chris@16:             
Chris@16:             // Remove u from the front of the bucket
Chris@16:             bucket.pop_front();
Chris@16:             
Chris@16:             // Insert u into the set of deleted vertices, if it hasn't
Chris@16:             // been done already.
Chris@16:             if (!vertex_was_deleted[get(local, u)]) {
Chris@16:               vertex_was_deleted[get(local, u)] = true;
Chris@16:               deleted_vertices.push_back(u);
Chris@16:             }
Chris@16:             
Chris@16:             // Relax each light edge. 
Chris@16:             Dist u_dist = get(distance, u);
Chris@16:             BGL_FORALL_OUTEDGES_T(u, e, g, Graph)
Chris@16:               if (get(weight, e) <= delta) // light edge 
Chris@16:                 relax(u, target(e, g), u_dist + get(weight, e));
Chris@16:           }
Chris@16:         }
Chris@16: 
Chris@16:         // Synchronize with all of the other processes.
Chris@16:         synchronize();
Chris@16:         
Chris@16:         // Is the bucket empty now?
Chris@16:         nonempty_bucket = (current_bucket < buckets.size() 
Chris@16:                            && buckets[current_bucket]
Chris@16:                            && !buckets[current_bucket]->empty());
Chris@16:       } while (all_reduce(pg, nonempty_bucket, std::logical_or<bool>()));
Chris@16:       
Chris@16:       // Relax heavy edges for each of the vertices that we previously
Chris@16:       // deleted.
Chris@16:       for (typename std::vector<Vertex>::iterator iter = deleted_vertices.begin();
Chris@16:            iter != deleted_vertices.end(); ++iter) {
Chris@16:         // Relax each heavy edge. 
Chris@16:         Vertex u = *iter;
Chris@16:         Dist u_dist = get(distance, u);
Chris@16:         BGL_FORALL_OUTEDGES_T(u, e, g, Graph)
Chris@16:           if (get(weight, e) > delta) // heavy edge
Chris@16:             relax(u, target(e, g), u_dist + get(weight, e)); 
Chris@16: 
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:         // Set outgoing paths
Chris@16:         IncomingType in = get(incoming, u);
Chris@16:         for (typename IncomingType::iterator pred = in.begin(); pred != in.end(); ++pred) 
Chris@16:           if (get(owner, *pred) == id) {
Chris@16:             IncomingType x = get(outgoing, *pred);
Chris@16:             if (std::find(x.begin(), x.end(), u) == x.end())
Chris@16:               x.push_back(u);
Chris@16:             put(outgoing, *pred, x);
Chris@16:           } else {
Chris@16:             IncomingType in;
Chris@16:             in.push_back(u);
Chris@16:             put(outgoing, *pred, in);
Chris@16:           }
Chris@16: 
Chris@16:         // Set incoming edge counts
Chris@16:         put(incoming_edge_count, u, in.size());
Chris@16: #endif
Chris@16:       }
Chris@16: 
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:       synchronize();  // Deliver heavy edge relaxations and outgoing paths
Chris@16: 
Chris@16:       // Build Queue
Chris@16:       typedef typename property_traits<PathCountMap>::value_type PathCountType;
Chris@16:       typedef std::pair<Vertex, PathCountType> queue_value_type;
Chris@16:       typedef typename property_map<Graph, vertex_owner_t>::const_type OwnerMap;
Chris@16:       typedef typename get_owner_of_first_pair_element<OwnerMap> IndirectOwnerMap;
Chris@16: 
Chris@16:       typedef boost::queue<queue_value_type> local_queue_type;
Chris@16:       typedef boost::graph::distributed::distributed_queue<process_group_type,
Chris@16:                                                            IndirectOwnerMap,
Chris@16:                                                            local_queue_type> dist_queue_type;
Chris@16: 
Chris@16:       IndirectOwnerMap indirect_owner(owner);
Chris@16:       dist_queue_type Q(pg, indirect_owner);
Chris@16: 
Chris@16:       // Find sources to initialize queue
Chris@16:       BGL_FORALL_VERTICES_T(v, g, Graph) {
Chris@16:         if (get(is_settled, v) && !(get(outgoing, v).empty())) {
Chris@16:           put(incoming_edge_count, v, 1); 
Chris@16:           Q.push(std::make_pair(v, 0)); // Push this vertex with no additional path count
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       // Set path counts for vertices in this bucket
Chris@16:       while (!Q.empty()) {
Chris@16:         queue_value_type t = Q.top(); Q.pop();
Chris@16:         Vertex v = t.first;
Chris@16:         PathCountType p = t.second;
Chris@16: 
Chris@16:         put(path_count, v, get(path_count, v) + p);
Chris@16:         put(incoming_edge_count, v, get(incoming_edge_count, v) - 1);
Chris@16: 
Chris@16:         if (get(incoming_edge_count, v) == 0) {
Chris@16:           IncomingType out = get(outgoing, v);
Chris@16:           for (typename IncomingType::iterator iter = out.begin(); iter != out.end(); ++iter)
Chris@16:             Q.push(std::make_pair(*iter, get(path_count, v)));
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       // Mark the vertices in this bucket settled 
Chris@16:       for (typename std::vector<Vertex>::iterator iter = deleted_vertices.begin();
Chris@16:            iter != deleted_vertices.end(); ++iter) 
Chris@16:         put(is_settled, *iter, true);
Chris@16: 
Chris@16:       // No need to clear path count map as it is never read/written remotely
Chris@16:       // No need to clear outgoing map as it is re-alloced every bucket 
Chris@16: #endif
Chris@16:       
Chris@16:       // Go to the next bucket: the current bucket must already be empty.
Chris@16:       ++current_bucket;
Chris@16:     } while (true);
Chris@16:     
Chris@16:     // Delete all of the buckets.
Chris@16:     for (typename std::vector<Bucket*>::iterator iter = buckets.begin();
Chris@16:          iter != buckets.end(); ++iter) {
Chris@16:       if (*iter) {
Chris@16:         delete *iter;
Chris@16:         *iter = 0;
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16:         
Chris@16:   template<typename Graph, typename DistanceMap, typename IncomingMap, 
Chris@16:            typename EdgeWeightMap, typename PathCountMap
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:            , typename IsSettledMap, typename VertexIndexMap
Chris@16: #endif
Chris@16:            >
Chris@16:   void
Chris@16:   betweenness_centrality_delta_stepping_impl<
Chris@16:     Graph, DistanceMap, IncomingMap, EdgeWeightMap, PathCountMap
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:            , IsSettledMap, VertexIndexMap
Chris@16: #endif
Chris@16:     >::
Chris@16:   relax(Vertex u, Vertex v, Dist x)
Chris@16:   {
Chris@16: 
Chris@16:     if (x <= get(distance, v)) {
Chris@16:       
Chris@16:       // We're relaxing the edge to vertex v.
Chris@16:       if (get(owner, v) == process_id(pg)) {
Chris@16:         if (x < get(distance, v)) {
Chris@16:           // Compute the new bucket index for v
Chris@16:           BucketIndex new_index = static_cast<BucketIndex>(x / delta);
Chris@16:         
Chris@16:           // Make sure there is enough room in the buckets data structure.
Chris@16:           if (new_index >= buckets.size()) buckets.resize(new_index + 1, 0);
Chris@16:         
Chris@16:           // Make sure that we have allocated the bucket itself.
Chris@16:           if (!buckets[new_index]) buckets[new_index] = new Bucket;
Chris@16:           
Chris@16:           if (get(distance, v) != (std::numeric_limits<Dist>::max)()
Chris@16:               && !vertex_was_deleted[get(local, v)]) {
Chris@16:             // We're moving v from an old bucket into a new one. Compute
Chris@16:             // the old index, then splice it in.
Chris@16:             BucketIndex old_index 
Chris@16:               = static_cast<BucketIndex>(get(distance, v) / delta);
Chris@16:             buckets[new_index]->splice(buckets[new_index]->end(),
Chris@16:                                        *buckets[old_index],
Chris@16:                                        position_in_bucket[get(local, v)]);
Chris@16:           } else {
Chris@16:             // We're inserting v into a bucket for the first time. Put it
Chris@16:             // at the end.
Chris@16:             buckets[new_index]->push_back(v);
Chris@16:           }
Chris@16:           
Chris@16:           // v is now at the last position in the new bucket
Chris@16:           position_in_bucket[get(local, v)] = buckets[new_index]->end();
Chris@16:           --position_in_bucket[get(local, v)];
Chris@16:           
Chris@16:           // Update tentative distance information and incoming, path_count
Chris@16:           if (u != v) put(incoming, v, IncomingType(1, u));
Chris@16:           put(distance, v, x);
Chris@16:         }        // u != v covers initial source relaxation and self-loops
Chris@16:         else if (x == get(distance, v) && u != v) {
Chris@16: 
Chris@16:           // Add incoming edge if it's not already in the list
Chris@16:           IncomingType in = get(incoming, v);
Chris@16:           if (std::find(in.begin(), in.end(), u) == in.end()) {
Chris@16:             in.push_back(u);
Chris@16:             put(incoming, v, in);
Chris@16:           }
Chris@16:         }
Chris@16:       } else {
Chris@16:         // The vertex is remote: send a request to the vertex's owner
Chris@16:         send(pg, get(owner, v), msg_relax, 
Chris@16:              std::make_pair(v, MessageValue::create(x, u)));
Chris@16: 
Chris@16:         // Cache tentative distance information
Chris@16:         cache(distance, v, x);
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   /************************************************************************/
Chris@16:   /* Shortest Paths function object for betweenness centrality            */
Chris@16:   /************************************************************************/
Chris@16: 
Chris@16:   template<typename WeightMap>
Chris@16:   struct brandes_shortest_paths {
Chris@16:     typedef typename property_traits<WeightMap>::value_type weight_type;
Chris@16: 
Chris@16:     brandes_shortest_paths() 
Chris@16:       : weight(1), delta(0)  { }
Chris@16:     brandes_shortest_paths(weight_type delta) 
Chris@16:       : weight(1), delta(delta)  { }
Chris@16:     brandes_shortest_paths(WeightMap w) 
Chris@16:       : weight(w), delta(0)  { }
Chris@16:     brandes_shortest_paths(WeightMap w, weight_type delta) 
Chris@16:       : weight(w), delta(delta)  { }
Chris@16: 
Chris@16:     template<typename Graph, typename IncomingMap, typename DistanceMap,
Chris@16:              typename PathCountMap
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:              , typename IsSettledMap, typename VertexIndexMap
Chris@16: #endif
Chris@16: 
Chris@16:              > 
Chris@16:     void 
Chris@16:     operator()(Graph& g, 
Chris@16:                typename graph_traits<Graph>::vertex_descriptor s,
Chris@16:                IncomingMap incoming,
Chris@16:                DistanceMap distance,
Chris@16:                PathCountMap path_count
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:                , IsSettledMap is_settled,
Chris@16:                VertexIndexMap vertex_index 
Chris@16: #endif
Chris@16:                )
Chris@16:     {  
Chris@16:       // The "distance" map needs to act like one, retrieving the default
Chris@16:       // value of infinity.
Chris@16:       set_property_map_role(vertex_distance, distance);
Chris@16:       
Chris@16:       // Only calculate delta the first time operator() is called
Chris@16:       // This presumes g is the same every time, but so does the fact
Chris@16:       // that we're reusing the weight map
Chris@16:       if (delta == 0)
Chris@16:         set_delta(g);
Chris@16:       
Chris@16:       // TODO (NGE): Restructure the code so we don't have to construct
Chris@16:       //             impl every time?
Chris@16:       betweenness_centrality_delta_stepping_impl<
Chris@16:           Graph, DistanceMap, IncomingMap, WeightMap, PathCountMap
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:           , IsSettledMap, VertexIndexMap
Chris@16: #endif
Chris@16:             >
Chris@16:         impl(g, distance, incoming, weight, path_count, 
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:              is_settled, vertex_index, 
Chris@16: #endif
Chris@16:              delta);
Chris@16: 
Chris@16:       impl.run(s);
Chris@16:     }
Chris@16: 
Chris@16:   private:
Chris@16: 
Chris@16:     template <typename Graph>
Chris@16:     void
Chris@16:     set_delta(const Graph& g)
Chris@16:     {
Chris@16:       using boost::parallel::all_reduce;
Chris@16:       using boost::parallel::maximum;
Chris@16:       using std::max;
Chris@16: 
Chris@16:       typedef typename graph_traits<Graph>::degree_size_type Degree;
Chris@16:       typedef weight_type Dist;
Chris@16: 
Chris@16:       // Compute the maximum edge weight and degree
Chris@16:       Dist max_edge_weight = 0;
Chris@16:       Degree max_degree = 0;
Chris@16:       BGL_FORALL_VERTICES_T(u, g, Graph) {
Chris@16:         max_degree = max BOOST_PREVENT_MACRO_SUBSTITUTION (max_degree, out_degree(u, g));
Chris@16:         BGL_FORALL_OUTEDGES_T(u, e, g, Graph)
Chris@16:           max_edge_weight = max BOOST_PREVENT_MACRO_SUBSTITUTION (max_edge_weight, get(weight, e));
Chris@16:       }
Chris@16:       
Chris@16:       max_edge_weight = all_reduce(process_group(g), max_edge_weight, maximum<Dist>());
Chris@16:       max_degree = all_reduce(process_group(g), max_degree, maximum<Degree>());
Chris@16:       
Chris@16:       // Take a guess at delta, based on what works well for random
Chris@16:       // graphs.
Chris@16:       delta = max_edge_weight / max_degree;
Chris@16:       if (delta == 0)
Chris@16:         delta = 1;
Chris@16:     }
Chris@16: 
Chris@16:     WeightMap     weight;
Chris@16:     weight_type   delta;
Chris@16:   };
Chris@16: 
Chris@16:   // Perform a single SSSP from the specified vertex and update the centrality map(s)
Chris@16:   template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
Chris@16:            typename IncomingMap, typename DistanceMap, typename DependencyMap, 
Chris@16:            typename PathCountMap, 
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:            typename IsSettledMap,
Chris@16: #endif 
Chris@16:            typename VertexIndexMap, typename ShortestPaths> 
Chris@16:   void
Chris@16:   do_brandes_sssp(const Graph& g, 
Chris@16:                   CentralityMap centrality,     
Chris@16:                   EdgeCentralityMap edge_centrality_map,
Chris@16:                   IncomingMap incoming,
Chris@16:                   DistanceMap distance,
Chris@16:                   DependencyMap dependency,
Chris@16:                   PathCountMap path_count, 
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:                   IsSettledMap is_settled,
Chris@16: #endif 
Chris@16:                   VertexIndexMap vertex_index,
Chris@16:                   ShortestPaths shortest_paths,
Chris@16:                   typename graph_traits<Graph>::vertex_descriptor s)
Chris@16:   {
Chris@16:     using boost::detail::graph::update_centrality;      
Chris@16:     using boost::graph::parallel::process_group;
Chris@16: 
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16:     typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
Chris@16: 
Chris@16:     typedef typename property_traits<IncomingMap>::value_type incoming_type;
Chris@16:     typedef typename property_traits<DistanceMap>::value_type distance_type;
Chris@16:     typedef typename property_traits<DependencyMap>::value_type dependency_type;
Chris@16:     typedef typename property_traits<PathCountMap>::value_type path_count_type;
Chris@16: 
Chris@16:     typedef typename incoming_type::iterator incoming_iterator;
Chris@16: 
Chris@16:     typedef typename property_map<Graph, vertex_owner_t>::const_type OwnerMap;
Chris@16:     OwnerMap owner = get(vertex_owner, g);
Chris@16: 
Chris@16:     typedef typename boost::graph::parallel::process_group_type<Graph>::type 
Chris@16:       process_group_type;
Chris@16:     process_group_type pg = process_group(g);
Chris@16:     typename process_group_type::process_id_type id = process_id(pg);
Chris@16: 
Chris@16:     // TODO: Is it faster not to clear some of these maps?
Chris@16:     // Initialize for this iteration
Chris@16:     distance.clear();
Chris@16:     incoming.clear();
Chris@16:     path_count.clear();
Chris@16:     dependency.clear();
Chris@16:     BGL_FORALL_VERTICES_T(v, g, Graph) {
Chris@16:       put(path_count, v, 0);
Chris@16:       put(dependency, v, 0);
Chris@16:     }
Chris@16: 
Chris@16:     if (get(owner, s) == id) {
Chris@16:       put(incoming, s, incoming_type());
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:       put(path_count, s, 1);
Chris@16:       put(is_settled, s, true);
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     // Execute the shortest paths algorithm. This will be either
Chris@16:     // a weighted or unweighted customized breadth-first search,
Chris@16:     shortest_paths(g, s, incoming, distance, path_count
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:                    , is_settled, vertex_index
Chris@16: #endif 
Chris@16:                    );
Chris@16: 
Chris@16: #ifndef COMPUTE_PATH_COUNTS_INLINE
Chris@16: 
Chris@16:     //
Chris@16:     // TODO: Optimize case where source has no out-edges
Chris@16:     //
Chris@16:  
Chris@16:     // Count of incoming edges to tell when all incoming edges have been relaxed in 
Chris@16:     // the induced shortest paths DAG 
Chris@16:     std::vector<edges_size_type> incoming_edge_countS(num_vertices(g));
Chris@16:     iterator_property_map<typename std::vector<edges_size_type>::iterator, VertexIndexMap> 
Chris@16:       incoming_edge_count(incoming_edge_countS.begin(), vertex_index);
Chris@16: 
Chris@16:     BGL_FORALL_VERTICES_T(v, g, Graph) {
Chris@16:       put(incoming_edge_count, v, get(incoming, v).size());
Chris@16:     }
Chris@16: 
Chris@16:     if (get(owner, s) == id) {
Chris@16:       put(incoming_edge_count, s, 1);
Chris@16:       put(incoming, s, incoming_type());
Chris@16:     }
Chris@16: 
Chris@16:     std::vector<incoming_type> outgoingS(num_vertices(g));
Chris@16:     iterator_property_map<typename std::vector<incoming_type>::iterator, VertexIndexMap> 
Chris@16:       outgoing(outgoingS.begin(), vertex_index);
Chris@16: 
Chris@16:     outgoing.set_reduce(append_reducer<incoming_type>());
Chris@16: 
Chris@16:     // Mark forward adjacencies in DAG of shortest paths
Chris@16: 
Chris@16:     // TODO: It's possible to do this using edge flags but it's not currently done this way
Chris@16:     //       because during traversal of the DAG we would have to examine all out edges
Chris@16:     //       which would lead to more memory accesses and a larger cache footprint.
Chris@16:     //
Chris@16:     //       In the bidirectional graph case edge flags would be an excellent way of marking
Chris@16:     //       edges in the DAG of shortest paths  
Chris@16:     BGL_FORALL_VERTICES_T(v, g, Graph) {
Chris@16:       incoming_type i = get(incoming, v);
Chris@16:       for (typename incoming_type::iterator iter = i.begin(); iter != i.end(); ++iter) {
Chris@16:         if (get(owner, *iter) == id) {
Chris@16:           incoming_type x = get(outgoing, *iter);
Chris@16:           if (std::find(x.begin(), x.end(), v) == x.end())
Chris@16:             x.push_back(v);
Chris@16:           put(outgoing, *iter, x);
Chris@16:         } else {
Chris@16:           incoming_type in;
Chris@16:           in.push_back(v);
Chris@16:           put(outgoing, *iter, in);
Chris@16:         }
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     synchronize(pg);
Chris@16: 
Chris@16:     // Traverse DAG induced by forward edges in dependency order and compute path counts
Chris@16:     {
Chris@16:       typedef std::pair<vertex_descriptor, path_count_type> queue_value_type;
Chris@16:       typedef get_owner_of_first_pair_element<OwnerMap> IndirectOwnerMap;
Chris@16: 
Chris@16:       typedef boost::queue<queue_value_type> local_queue_type;
Chris@16:       typedef boost::graph::distributed::distributed_queue<process_group_type,
Chris@16:                                                            IndirectOwnerMap,
Chris@16:                                                            local_queue_type> dist_queue_type;
Chris@16: 
Chris@16:       IndirectOwnerMap indirect_owner(owner);
Chris@16:       dist_queue_type Q(pg, indirect_owner);
Chris@16: 
Chris@16:       if (get(owner, s) == id)
Chris@16:         Q.push(std::make_pair(s, 1));
Chris@16: 
Chris@16:       while (!Q.empty()) {
Chris@16:         queue_value_type t = Q.top(); Q.pop();
Chris@16:         vertex_descriptor v = t.first;
Chris@16:         path_count_type p = t.second;
Chris@16: 
Chris@16:         put(path_count, v, get(path_count, v) + p);
Chris@16:         put(incoming_edge_count, v, get(incoming_edge_count, v) - 1);
Chris@16: 
Chris@16:         if (get(incoming_edge_count, v) == 0) {
Chris@16:           incoming_type out = get(outgoing, v);
Chris@16:           for (typename incoming_type::iterator iter = out.begin(); iter != out.end(); ++iter)
Chris@16:             Q.push(std::make_pair(*iter, get(path_count, v)));
Chris@16:         }
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16: #endif // COMPUTE_PATH_COUNTS_INLINE
Chris@16: 
Chris@16:     //
Chris@16:     // Compute dependencies 
Chris@16:     //    
Chris@16: 
Chris@16: 
Chris@16:     // Build the distributed_queue
Chris@16:     // Value type consists of 1) target of update 2) source of update
Chris@16:     // 3) dependency of source 4) path count of source
Chris@16:     typedef boost::tuple<vertex_descriptor, vertex_descriptor, dependency_type, path_count_type>
Chris@16:       queue_value_type;
Chris@16:     typedef get_owner_of_first_tuple_element<OwnerMap, queue_value_type> IndirectOwnerMap;
Chris@16: 
Chris@16:     typedef boost::queue<queue_value_type> local_queue_type;
Chris@16:     typedef boost::graph::distributed::distributed_queue<process_group_type,
Chris@16:                                                          IndirectOwnerMap,
Chris@16:                                                          local_queue_type> dist_queue_type;
Chris@16: 
Chris@16:     IndirectOwnerMap indirect_owner(owner);
Chris@16:     dist_queue_type Q(pg, indirect_owner);
Chris@16: 
Chris@16:     // Calculate number of vertices each vertex depends on, when a vertex has been pushed
Chris@16:     // that number of times then we will update it
Chris@16:     // AND Request path counts of sources of incoming edges
Chris@16:     std::vector<dependency_type> dependency_countS(num_vertices(g), 0);
Chris@16:     iterator_property_map<typename std::vector<dependency_type>::iterator, VertexIndexMap> 
Chris@16:       dependency_count(dependency_countS.begin(), vertex_index);
Chris@16: 
Chris@16:     dependency_count.set_reduce(boost::graph::distributed::additive_reducer<dependency_type>());
Chris@16: 
Chris@16:     path_count.set_max_ghost_cells(0);
Chris@16: 
Chris@16:     BGL_FORALL_VERTICES_T(v, g, Graph) {
Chris@16:       if (get(distance, v) < (std::numeric_limits<distance_type>::max)()) {
Chris@16:         incoming_type el = get(incoming, v);
Chris@16:         for (incoming_iterator vw = el.begin(); vw != el.end(); ++vw) {
Chris@16:           if (get(owner, *vw) == id)
Chris@16:             put(dependency_count, *vw, get(dependency_count, *vw) + 1);
Chris@16:           else {
Chris@16:             put(dependency_count, *vw, 1);
Chris@16: 
Chris@16:             // Request path counts
Chris@16:             get(path_count, *vw); 
Chris@16:           }
Chris@16: 
Chris@16:           // request() doesn't work here, perhaps because we don't have a copy of this 
Chris@16:           // ghost cell already?
Chris@16:         }
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     synchronize(pg);
Chris@16: 
Chris@16:     // Push vertices with non-zero distance/path count and zero dependency count
Chris@16:     BGL_FORALL_VERTICES_T(v, g, Graph) {
Chris@16:       if (get(distance, v) < (std::numeric_limits<distance_type>::max)()
Chris@16:           && get(dependency_count, v) == 0) 
Chris@16:         Q.push(boost::make_tuple(v, v, get(dependency, v), get(path_count, v)));
Chris@16:     }
Chris@16: 
Chris@16:     dependency.set_max_ghost_cells(0);
Chris@16:     while(!Q.empty()) {
Chris@16: 
Chris@16:       queue_value_type x = Q.top(); Q.pop();
Chris@16:       vertex_descriptor w = boost::tuples::get<0>(x);
Chris@16:       vertex_descriptor source = boost::tuples::get<1>(x);
Chris@16:       dependency_type dep = boost::tuples::get<2>(x);
Chris@16:       path_count_type pc = boost::tuples::get<3>(x);
Chris@16: 
Chris@16:       cache(dependency, source, dep);
Chris@16:       cache(path_count, source, pc);
Chris@16: 
Chris@16:       if (get(dependency_count, w) != 0)
Chris@16:         put(dependency_count, w, get(dependency_count, w) - 1);
Chris@16: 
Chris@16:       if (get(dependency_count, w) == 0) { 
Chris@16: 
Chris@16:         // Update dependency and centrality of sources of incoming edges
Chris@16:         incoming_type el = get(incoming, w);
Chris@16:         for (incoming_iterator vw = el.begin(); vw != el.end(); ++vw) {
Chris@16:           vertex_descriptor v = *vw;
Chris@16: 
Chris@16:           BOOST_ASSERT(get(path_count, w) != 0);
Chris@16: 
Chris@16:           dependency_type factor = dependency_type(get(path_count, v))
Chris@16:             / dependency_type(get(path_count, w));
Chris@16:           factor *= (dependency_type(1) + get(dependency, w));
Chris@16:           
Chris@16:           if (get(owner, v) == id)
Chris@16:             put(dependency, v, get(dependency, v) + factor);
Chris@16:           else
Chris@16:             put(dependency, v, factor);
Chris@16:           
Chris@16:           update_centrality(edge_centrality_map, v, factor);
Chris@16:         }
Chris@16:         
Chris@16:         if (w != s)
Chris@16:           update_centrality(centrality, w, get(dependency, w));
Chris@16: 
Chris@16:         // Push sources of edges in incoming edge list
Chris@16:         for (incoming_iterator vw = el.begin(); vw != el.end(); ++vw)
Chris@16:           Q.push(boost::make_tuple(*vw, w, get(dependency, w), get(path_count, w)));
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
Chris@16:            typename IncomingMap, typename DistanceMap, typename DependencyMap, 
Chris@16:            typename PathCountMap, typename VertexIndexMap, typename ShortestPaths, 
Chris@16:            typename Buffer>
Chris@16:   void 
Chris@16:   brandes_betweenness_centrality_impl(const Graph& g, 
Chris@16:                                       CentralityMap centrality,     
Chris@16:                                       EdgeCentralityMap edge_centrality_map,
Chris@16:                                       IncomingMap incoming,
Chris@16:                                       DistanceMap distance,
Chris@16:                                       DependencyMap dependency,
Chris@16:                                       PathCountMap path_count, 
Chris@16:                                       VertexIndexMap vertex_index,
Chris@16:                                       ShortestPaths shortest_paths,
Chris@16:                                       Buffer sources)
Chris@16:   {
Chris@16:     using boost::detail::graph::init_centrality_map;
Chris@16:     using boost::detail::graph::divide_centrality_by_two;       
Chris@16:     using boost::graph::parallel::process_group;
Chris@16:     
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16: 
Chris@16:     typedef typename property_traits<DistanceMap>::value_type distance_type;
Chris@16:     typedef typename property_traits<DependencyMap>::value_type dependency_type;
Chris@16: 
Chris@16:     // Initialize centrality
Chris@16:     init_centrality_map(vertices(g), centrality);
Chris@16:     init_centrality_map(edges(g), edge_centrality_map);
Chris@16: 
Chris@16:     // Set the reduction operation on the dependency map to be addition
Chris@16:     dependency.set_reduce(boost::graph::distributed::additive_reducer<dependency_type>()); 
Chris@16:     distance.set_reduce(boost::graph::distributed::choose_min_reducer<distance_type>());
Chris@16: 
Chris@16:     // Don't allow remote procs to write incoming or path_count maps
Chris@16:     // updating them is handled inside the betweenness_centrality_queue
Chris@16:     incoming.set_consistency_model(0);
Chris@16:     path_count.set_consistency_model(0);
Chris@16: 
Chris@16:     typedef typename boost::graph::parallel::process_group_type<Graph>::type 
Chris@16:       process_group_type;
Chris@16:     process_group_type pg = process_group(g);
Chris@16: 
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:     // Build is_settled maps
Chris@16:     std::vector<bool> is_settledS(num_vertices(g));
Chris@16:     typedef iterator_property_map<std::vector<bool>::iterator, VertexIndexMap> 
Chris@16:       IsSettledMap;
Chris@16: 
Chris@16:     IsSettledMap is_settled(is_settledS.begin(), vertex_index);
Chris@16: #endif
Chris@16: 
Chris@16:     if (!sources.empty()) {
Chris@16:       // DO SSSPs
Chris@16:       while (!sources.empty()) {
Chris@16:         do_brandes_sssp(g, centrality, edge_centrality_map, incoming, distance,
Chris@16:                         dependency, path_count, 
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:                         is_settled,
Chris@16: #endif 
Chris@16:                         vertex_index, shortest_paths, sources.top());
Chris@16:         sources.pop();
Chris@16:       }
Chris@16:     } else { // Exact Betweenness Centrality
Chris@16:       typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
Chris@16:       vertices_size_type n = num_vertices(g);
Chris@16:       n = boost::parallel::all_reduce(pg, n, std::plus<vertices_size_type>());
Chris@16:       
Chris@16:       for (vertices_size_type i = 0; i < n; ++i) {
Chris@16:         vertex_descriptor v = vertex(i, g);
Chris@16: 
Chris@16:         do_brandes_sssp(g, centrality, edge_centrality_map, incoming, distance,
Chris@16:                         dependency, path_count, 
Chris@16: #ifdef COMPUTE_PATH_COUNTS_INLINE
Chris@16:                         is_settled,
Chris@16: #endif 
Chris@16:                         vertex_index, shortest_paths, v);
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     typedef typename graph_traits<Graph>::directed_category directed_category;
Chris@16:     const bool is_undirected = 
Chris@16:       is_convertible<directed_category*, undirected_tag*>::value;
Chris@16:     if (is_undirected) {
Chris@16:       divide_centrality_by_two(vertices(g), centrality);
Chris@16:       divide_centrality_by_two(edges(g), edge_centrality_map);
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
Chris@16:            typename IncomingMap, typename DistanceMap, typename DependencyMap, 
Chris@16:            typename PathCountMap, typename VertexIndexMap, typename ShortestPaths,
Chris@16:            typename Stack>
Chris@16:   void
Chris@16:   do_sequential_brandes_sssp(const Graph& g, 
Chris@16:                              CentralityMap centrality,     
Chris@16:                              EdgeCentralityMap edge_centrality_map,
Chris@16:                              IncomingMap incoming,
Chris@16:                              DistanceMap distance,
Chris@16:                              DependencyMap dependency,
Chris@16:                              PathCountMap path_count, 
Chris@16:                              VertexIndexMap vertex_index,
Chris@16:                              ShortestPaths shortest_paths,
Chris@16:                              Stack& ordered_vertices,
Chris@16:                              typename graph_traits<Graph>::vertex_descriptor v)
Chris@16:   {
Chris@16:     using boost::detail::graph::update_centrality;
Chris@16: 
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16: 
Chris@16:     // Initialize for this iteration
Chris@16:     BGL_FORALL_VERTICES_T(w, g, Graph) {
Chris@16:       // put(path_count, w, 0);
Chris@16:       incoming[w].clear();
Chris@16:       put(dependency, w, 0);
Chris@16:     }
Chris@16: 
Chris@16:     put(path_count, v, 1);
Chris@16:     incoming[v].clear();
Chris@16: 
Chris@16:     // Execute the shortest paths algorithm. This will be either
Chris@16:     // Dijkstra's algorithm or a customized breadth-first search,
Chris@16:     // depending on whether the graph is weighted or unweighted.
Chris@16:     shortest_paths(g, v, ordered_vertices, incoming, distance,
Chris@16:                    path_count, vertex_index);
Chris@16:     
Chris@16:     while (!ordered_vertices.empty()) {
Chris@16:       vertex_descriptor w = ordered_vertices.top();
Chris@16:       ordered_vertices.pop();
Chris@16:       
Chris@16:       typedef typename property_traits<IncomingMap>::value_type
Chris@16:             incoming_type;
Chris@16:       typedef typename incoming_type::iterator incoming_iterator;
Chris@16:       typedef typename property_traits<DependencyMap>::value_type 
Chris@16:         dependency_type;
Chris@16:       
Chris@16:       for (incoming_iterator vw = incoming[w].begin();
Chris@16:            vw != incoming[w].end(); ++vw) {
Chris@16:         vertex_descriptor v = source(*vw, g);
Chris@16:         dependency_type factor = dependency_type(get(path_count, v))
Chris@16:           / dependency_type(get(path_count, w));
Chris@16:         factor *= (dependency_type(1) + get(dependency, w));
Chris@16:         put(dependency, v, get(dependency, v) + factor);
Chris@16:         update_centrality(edge_centrality_map, *vw, factor);
Chris@16:       }
Chris@16:       
Chris@16:       if (w != v) {
Chris@16:         update_centrality(centrality, w, get(dependency, w));
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   // Betweenness Centrality variant that duplicates graph across processors
Chris@16:   // and parallizes SSSPs
Chris@16:   // This function expects a non-distributed graph and property-maps
Chris@16:   template<typename ProcessGroup, typename Graph, 
Chris@16:            typename CentralityMap, typename EdgeCentralityMap,
Chris@16:            typename IncomingMap, typename DistanceMap, 
Chris@16:            typename DependencyMap, typename PathCountMap,
Chris@16:            typename VertexIndexMap, typename ShortestPaths,
Chris@16:            typename Buffer>
Chris@16:   void
Chris@16:   non_distributed_brandes_betweenness_centrality_impl(const ProcessGroup& pg,
Chris@16:                                                       const Graph& g,
Chris@16:                                                       CentralityMap centrality,
Chris@16:                                                       EdgeCentralityMap edge_centrality_map,
Chris@16:                                                       IncomingMap incoming, // P
Chris@16:                                                       DistanceMap distance,         // d
Chris@16:                                                       DependencyMap dependency,     // delta
Chris@16:                                                       PathCountMap path_count,      // sigma
Chris@16:                                                       VertexIndexMap vertex_index,
Chris@16:                                                       ShortestPaths shortest_paths,
Chris@16:                                                       Buffer sources)
Chris@16:   {
Chris@16:     using boost::detail::graph::init_centrality_map;
Chris@16:     using boost::detail::graph::divide_centrality_by_two;       
Chris@16:     using boost::graph::parallel::process_group;
Chris@16: 
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16: 
Chris@16:     typedef ProcessGroup process_group_type;
Chris@16: 
Chris@16:     typename process_group_type::process_id_type id = process_id(pg);
Chris@16:     typename process_group_type::process_size_type p = num_processes(pg);
Chris@16: 
Chris@16:     // Initialize centrality
Chris@16:     init_centrality_map(vertices(g), centrality);
Chris@16:     init_centrality_map(edges(g), edge_centrality_map);
Chris@16: 
Chris@16:     std::stack<vertex_descriptor> ordered_vertices;
Chris@16: 
Chris@16:     if (!sources.empty()) {
Chris@16:       std::vector<vertex_descriptor> local_sources;
Chris@16: 
Chris@16:       for (int i = 0; i < id; ++i) if (!sources.empty()) sources.pop();
Chris@16:       while (!sources.empty()) {
Chris@16:         local_sources.push_back(sources.top());
Chris@16: 
Chris@16:         for (int i = 0; i < p; ++i) if (!sources.empty()) sources.pop();
Chris@16:       }
Chris@16: 
Chris@16:       // DO SSSPs
Chris@16:       for(size_t i = 0; i < local_sources.size(); ++i)
Chris@16:         do_sequential_brandes_sssp(g, centrality, edge_centrality_map, incoming,
Chris@16:                                    distance, dependency, path_count, vertex_index,
Chris@16:                                    shortest_paths, ordered_vertices, local_sources[i]);
Chris@16: 
Chris@16:     } else { // Exact Betweenness Centrality
Chris@16:       typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
Chris@16:       vertices_size_type n = num_vertices(g);
Chris@16:       
Chris@16:       for (vertices_size_type i = id; i < n; i += p) {
Chris@16:         vertex_descriptor v = vertex(i, g);
Chris@16: 
Chris@16:         do_sequential_brandes_sssp(g, centrality, edge_centrality_map, incoming,
Chris@16:                                    distance, dependency, path_count, vertex_index,
Chris@16:                                    shortest_paths, ordered_vertices, v);
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     typedef typename graph_traits<Graph>::directed_category directed_category;
Chris@16:     const bool is_undirected = 
Chris@16:       is_convertible<directed_category*, undirected_tag*>::value;
Chris@16:     if (is_undirected) {
Chris@16:       divide_centrality_by_two(vertices(g), centrality);
Chris@16:       divide_centrality_by_two(edges(g), edge_centrality_map);
Chris@16:     }
Chris@16: 
Chris@16:     // Merge the centrality maps by summing the values at each vertex)
Chris@16:     // TODO(nge): this copy-out, reduce, copy-in is lame
Chris@16:     typedef typename property_traits<CentralityMap>::value_type centrality_type;
Chris@16:     typedef typename property_traits<EdgeCentralityMap>::value_type edge_centrality_type;
Chris@16: 
Chris@16:     std::vector<centrality_type> centrality_v(num_vertices(g));
Chris@16:     std::vector<edge_centrality_type> edge_centrality_v;
Chris@16:     edge_centrality_v.reserve(num_edges(g));
Chris@16: 
Chris@16:     BGL_FORALL_VERTICES_T(v, g, Graph) {
Chris@16:       centrality_v[get(vertex_index, v)] = get(centrality, v);
Chris@16:     }
Chris@16:     
Chris@16:     // Skip when EdgeCentralityMap is a dummy_property_map
Chris@16:     if (!is_same<EdgeCentralityMap, dummy_property_map>::value) {
Chris@16:       BGL_FORALL_EDGES_T(e, g, Graph) {
Chris@16:         edge_centrality_v.push_back(get(edge_centrality_map, e));
Chris@16:       }
Chris@16:       // NGE: If we trust that the order of elements in the vector isn't changed in the
Chris@16:       //      all_reduce below then this method avoids the need for an edge index map
Chris@16:     }
Chris@16: 
Chris@16:     using boost::parallel::all_reduce;
Chris@16: 
Chris@16:     all_reduce(pg, &centrality_v[0], &centrality_v[centrality_v.size()],
Chris@16:                &centrality_v[0], std::plus<centrality_type>());
Chris@16: 
Chris@16:     if (edge_centrality_v.size()) 
Chris@16:       all_reduce(pg, &edge_centrality_v[0], &edge_centrality_v[edge_centrality_v.size()],
Chris@16:                  &edge_centrality_v[0], std::plus<edge_centrality_type>());
Chris@16: 
Chris@16:     BGL_FORALL_VERTICES_T(v, g, Graph) {
Chris@16:       put(centrality, v, centrality_v[get(vertex_index, v)]);
Chris@16:     }
Chris@16: 
Chris@16:     // Skip when EdgeCentralityMap is a dummy_property_map
Chris@16:     if (!is_same<EdgeCentralityMap, dummy_property_map>::value) {
Chris@16:       int i = 0;
Chris@16:       BGL_FORALL_EDGES_T(e, g, Graph) {
Chris@16:         put(edge_centrality_map, e, edge_centrality_v[i]);
Chris@16:         ++i;
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16: } } } // end namespace graph::parallel::detail
Chris@16: 
Chris@16: template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
Chris@16:          typename IncomingMap, typename DistanceMap, typename DependencyMap, 
Chris@16:          typename PathCountMap, typename VertexIndexMap, typename Buffer>
Chris@16: void 
Chris@16: brandes_betweenness_centrality(const Graph& g, 
Chris@16:                                CentralityMap centrality,
Chris@16:                                EdgeCentralityMap edge_centrality_map,
Chris@16:                                IncomingMap incoming, 
Chris@16:                                DistanceMap distance, 
Chris@16:                                DependencyMap dependency,     
Chris@16:                                PathCountMap path_count,   
Chris@16:                                VertexIndexMap vertex_index,
Chris@16:                                Buffer sources,
Chris@16:                                typename property_traits<DistanceMap>::value_type delta
Chris@16:                                BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,distributed_graph_tag))
Chris@16: {
Chris@16:   typedef typename property_traits<DistanceMap>::value_type distance_type;
Chris@16:   typedef static_property_map<distance_type> WeightMap;
Chris@16: 
Chris@16:   graph::parallel::detail::brandes_shortest_paths<WeightMap> 
Chris@16:     shortest_paths(delta);
Chris@16: 
Chris@16:   graph::parallel::detail::brandes_betweenness_centrality_impl(g, centrality, 
Chris@16:                                                                edge_centrality_map,
Chris@16:                                                                incoming, distance,
Chris@16:                                                                dependency, path_count,
Chris@16:                                                                vertex_index, 
Chris@16:                                                                shortest_paths,
Chris@16:                                                                sources);
Chris@16: }
Chris@16: 
Chris@16: template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, 
Chris@16:          typename IncomingMap, typename DistanceMap, typename DependencyMap, 
Chris@16:          typename PathCountMap, typename VertexIndexMap, typename WeightMap, 
Chris@16:          typename Buffer>    
Chris@16: void 
Chris@16: brandes_betweenness_centrality(const Graph& g, 
Chris@16:                                CentralityMap centrality,
Chris@16:                                EdgeCentralityMap edge_centrality_map,
Chris@16:                                IncomingMap incoming, 
Chris@16:                                DistanceMap distance, 
Chris@16:                                DependencyMap dependency,
Chris@16:                                PathCountMap path_count, 
Chris@16:                                VertexIndexMap vertex_index,
Chris@16:                                Buffer sources,
Chris@16:                                typename property_traits<WeightMap>::value_type delta,
Chris@16:                                WeightMap weight_map
Chris@16:                                BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,distributed_graph_tag))
Chris@16: {
Chris@16:   graph::parallel::detail::brandes_shortest_paths<WeightMap> shortest_paths(weight_map, delta);
Chris@16: 
Chris@16:   graph::parallel::detail::brandes_betweenness_centrality_impl(g, centrality, 
Chris@16:                                                                edge_centrality_map,
Chris@16:                                                                incoming, distance,
Chris@16:                                                                dependency, path_count,
Chris@16:                                                                vertex_index, 
Chris@16:                                                                shortest_paths,
Chris@16:                                                                sources);
Chris@16: }
Chris@16: 
Chris@16: namespace graph { namespace parallel { namespace detail {
Chris@16:   template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
Chris@16:            typename WeightMap, typename VertexIndexMap, typename Buffer>
Chris@16:   void 
Chris@16:   brandes_betweenness_centrality_dispatch2(const Graph& g,
Chris@16:                                            CentralityMap centrality,
Chris@16:                                            EdgeCentralityMap edge_centrality_map,
Chris@16:                                            WeightMap weight_map,
Chris@16:                                            VertexIndexMap vertex_index,
Chris@16:                                            Buffer sources,
Chris@16:                                            typename property_traits<WeightMap>::value_type delta)
Chris@16:   {
Chris@16:     typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16:     typedef typename mpl::if_c<(is_same<CentralityMap, 
Chris@16:                                         dummy_property_map>::value),
Chris@16:                                          EdgeCentralityMap, 
Chris@16:                                CentralityMap>::type a_centrality_map;
Chris@16:     typedef typename property_traits<a_centrality_map>::value_type 
Chris@16:       centrality_type;
Chris@16: 
Chris@16:     typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
Chris@16: 
Chris@16:     std::vector<std::vector<vertex_descriptor> > incoming(V);
Chris@16:     std::vector<centrality_type> distance(V);
Chris@16:     std::vector<centrality_type> dependency(V);
Chris@16:     std::vector<degree_size_type> path_count(V);
Chris@16: 
Chris@16:     brandes_betweenness_centrality(
Chris@16:       g, centrality, edge_centrality_map,
Chris@16:       make_iterator_property_map(incoming.begin(), vertex_index),
Chris@16:       make_iterator_property_map(distance.begin(), vertex_index),
Chris@16:       make_iterator_property_map(dependency.begin(), vertex_index),
Chris@16:       make_iterator_property_map(path_count.begin(), vertex_index),
Chris@16:       vertex_index, unwrap_ref(sources), delta,
Chris@16:       weight_map);
Chris@16:   }
Chris@16:   
Chris@16:   // TODO: Should the type of the distance and dependency map depend on the 
Chris@16:   //       value type of the centrality map?
Chris@16:   template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
Chris@16:            typename VertexIndexMap, typename Buffer>
Chris@16:   void 
Chris@16:   brandes_betweenness_centrality_dispatch2(const Graph& g,
Chris@16:                                            CentralityMap centrality,
Chris@16:                                            EdgeCentralityMap edge_centrality_map,
Chris@16:                                            VertexIndexMap vertex_index,
Chris@16:                                            Buffer sources,
Chris@16:                                            typename graph_traits<Graph>::edges_size_type delta)
Chris@16:   {
Chris@16:     typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
Chris@16:     typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16: 
Chris@16:     typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
Chris@16:     
Chris@16:     std::vector<std::vector<vertex_descriptor> > incoming(V);
Chris@16:     std::vector<edges_size_type> distance(V);
Chris@16:     std::vector<edges_size_type> dependency(V);
Chris@16:     std::vector<degree_size_type> path_count(V);
Chris@16: 
Chris@16:     brandes_betweenness_centrality(
Chris@16:       g, centrality, edge_centrality_map,
Chris@16:       make_iterator_property_map(incoming.begin(), vertex_index),
Chris@16:       make_iterator_property_map(distance.begin(), vertex_index),
Chris@16:       make_iterator_property_map(dependency.begin(), vertex_index),
Chris@16:       make_iterator_property_map(path_count.begin(), vertex_index),
Chris@16:       vertex_index, unwrap_ref(sources), delta); 
Chris@16:   }
Chris@16: 
Chris@16:   template<typename WeightMap>
Chris@16:   struct brandes_betweenness_centrality_dispatch1
Chris@16:   {
Chris@16:     template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, 
Chris@16:              typename VertexIndexMap, typename Buffer>
Chris@16:     static void 
Chris@16:     run(const Graph& g, CentralityMap centrality, EdgeCentralityMap edge_centrality_map, 
Chris@16:         VertexIndexMap vertex_index, Buffer sources,
Chris@16:         typename property_traits<WeightMap>::value_type delta, WeightMap weight_map) 
Chris@16:     {
Chris@16:       boost::graph::parallel::detail::brandes_betweenness_centrality_dispatch2(
Chris@16:        g, centrality, edge_centrality_map, weight_map, vertex_index, sources, delta);
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template<>
Chris@16:   struct brandes_betweenness_centrality_dispatch1<boost::param_not_found> 
Chris@16:   {
Chris@16:     template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, 
Chris@16:              typename VertexIndexMap, typename Buffer>
Chris@16:     static void 
Chris@16:     run(const Graph& g, CentralityMap centrality, EdgeCentralityMap edge_centrality_map, 
Chris@16:         VertexIndexMap vertex_index, Buffer sources,
Chris@16:         typename graph_traits<Graph>::edges_size_type delta,
Chris@16:         boost::param_not_found)
Chris@16:     {
Chris@16:       boost::graph::parallel::detail::brandes_betweenness_centrality_dispatch2(
Chris@16:        g, centrality, edge_centrality_map, vertex_index, sources, delta);
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16: } } } // end namespace graph::parallel::detail
Chris@16: 
Chris@16: template<typename Graph, typename Param, typename Tag, typename Rest>
Chris@16: void 
Chris@16: brandes_betweenness_centrality(const Graph& g, 
Chris@16:                                const bgl_named_params<Param,Tag,Rest>& params
Chris@16:                                BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,distributed_graph_tag))
Chris@16: {
Chris@16:   typedef bgl_named_params<Param,Tag,Rest> named_params;
Chris@16: 
Chris@16:   typedef queue<typename graph_traits<Graph>::vertex_descriptor> queue_t;
Chris@16:   queue_t q;
Chris@16: 
Chris@16:   typedef typename get_param_type<edge_weight_t, named_params>::type ew_param;
Chris@16:   typedef typename detail::choose_impl_result<mpl::true_, Graph, ew_param, edge_weight_t>::type ew;
Chris@16:   graph::parallel::detail::brandes_betweenness_centrality_dispatch1<ew>::run(
Chris@16:     g, 
Chris@16:     choose_param(get_param(params, vertex_centrality), 
Chris@16:                  dummy_property_map()),
Chris@16:     choose_param(get_param(params, edge_centrality), 
Chris@16:                  dummy_property_map()),
Chris@16:     choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
Chris@16:     choose_param(get_param(params, buffer_param_t()), boost::ref(q)),
Chris@16:     choose_param(get_param(params, lookahead_t()), 0),
Chris@16:     choose_const_pmap(get_param(params, edge_weight), g, edge_weight));
Chris@16: }
Chris@16: 
Chris@16: template<typename Graph, typename CentralityMap>
Chris@16: void 
Chris@16: brandes_betweenness_centrality(const Graph& g, CentralityMap centrality
Chris@16:                                BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,distributed_graph_tag))
Chris@16: {
Chris@16:   typedef queue<typename graph_traits<Graph>::vertex_descriptor> queue_t;
Chris@16:   queue_t q;
Chris@16: 
Chris@16:   boost::graph::parallel::detail::brandes_betweenness_centrality_dispatch2(
Chris@16:     g, centrality, dummy_property_map(), get(vertex_index, g), boost::ref(q), 0);
Chris@16: }
Chris@16: 
Chris@16: template<typename Graph, typename CentralityMap, typename EdgeCentralityMap>
Chris@16: void 
Chris@16: brandes_betweenness_centrality(const Graph& g, CentralityMap centrality,
Chris@16:                                EdgeCentralityMap edge_centrality_map
Chris@16:                                BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,distributed_graph_tag))
Chris@16: {
Chris@16:   typedef queue<int> queue_t;
Chris@16:   queue_t q;
Chris@16: 
Chris@16:   boost::graph::parallel::detail::brandes_betweenness_centrality_dispatch2(
Chris@16:     g, centrality, edge_centrality_map, get(vertex_index, g), boost::ref(q), 0);
Chris@16: }
Chris@16:   
Chris@16: template<typename ProcessGroup, typename Graph, typename CentralityMap, 
Chris@16:          typename EdgeCentralityMap, typename IncomingMap, typename DistanceMap, 
Chris@16:          typename DependencyMap, typename PathCountMap, typename VertexIndexMap, 
Chris@16:          typename Buffer>
Chris@16: void 
Chris@16: non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg,
Chris@16:                                                const Graph& g, 
Chris@16:                                                CentralityMap centrality,
Chris@16:                                                EdgeCentralityMap edge_centrality_map,
Chris@16:                                                IncomingMap incoming, 
Chris@16:                                                DistanceMap distance, 
Chris@16:                                                DependencyMap dependency,     
Chris@16:                                                PathCountMap path_count,      
Chris@16:                                                VertexIndexMap vertex_index,
Chris@16:                                                Buffer sources)
Chris@16: {
Chris@16:   detail::graph::brandes_unweighted_shortest_paths shortest_paths;
Chris@16:   
Chris@16:   graph::parallel::detail::non_distributed_brandes_betweenness_centrality_impl(pg, g, centrality, 
Chris@16:                                                                                edge_centrality_map,
Chris@16:                                                                                incoming, distance,
Chris@16:                                                                                dependency, path_count,
Chris@16:                                                                                vertex_index, 
Chris@16:                                                                                shortest_paths,
Chris@16:                                                                                sources);
Chris@16: }
Chris@16:   
Chris@16: template<typename ProcessGroup, typename Graph, typename CentralityMap, 
Chris@16:          typename EdgeCentralityMap, typename IncomingMap, typename DistanceMap, 
Chris@16:          typename DependencyMap, typename PathCountMap, typename VertexIndexMap, 
Chris@16:          typename WeightMap, typename Buffer>
Chris@16: void 
Chris@16: non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg,
Chris@16:                                                const Graph& g, 
Chris@16:                                                CentralityMap centrality,
Chris@16:                                                EdgeCentralityMap edge_centrality_map,
Chris@16:                                                IncomingMap incoming, 
Chris@16:                                                DistanceMap distance, 
Chris@16:                                                DependencyMap dependency,
Chris@16:                                                PathCountMap path_count, 
Chris@16:                                                VertexIndexMap vertex_index,
Chris@16:                                                WeightMap weight_map,
Chris@16:                                                Buffer sources)
Chris@16: {
Chris@16:   detail::graph::brandes_dijkstra_shortest_paths<WeightMap> shortest_paths(weight_map);
Chris@16: 
Chris@16:   graph::parallel::detail::non_distributed_brandes_betweenness_centrality_impl(pg, g, centrality, 
Chris@16:                                                                                edge_centrality_map,
Chris@16:                                                                                incoming, distance,
Chris@16:                                                                                dependency, path_count,
Chris@16:                                                                                vertex_index, 
Chris@16:                                                                                shortest_paths,
Chris@16:                                                                                sources);
Chris@16: }
Chris@16: 
Chris@16: namespace detail { namespace graph {
Chris@16:   template<typename ProcessGroup, typename Graph, typename CentralityMap, 
Chris@16:            typename EdgeCentralityMap, typename WeightMap, typename VertexIndexMap,
Chris@16:            typename Buffer>
Chris@16:   void 
Chris@16:   non_distributed_brandes_betweenness_centrality_dispatch2(const ProcessGroup& pg,
Chris@16:                                                            const Graph& g,
Chris@16:                                                            CentralityMap centrality,
Chris@16:                                                            EdgeCentralityMap edge_centrality_map,
Chris@16:                                                            WeightMap weight_map,
Chris@16:                                                            VertexIndexMap vertex_index,
Chris@16:                                                            Buffer sources)
Chris@16:   {
Chris@16:     typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
Chris@16:     typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
Chris@16:     typedef typename mpl::if_c<(is_same<CentralityMap, 
Chris@16:                                         dummy_property_map>::value),
Chris@16:                                          EdgeCentralityMap, 
Chris@16:                                CentralityMap>::type a_centrality_map;
Chris@16:     typedef typename property_traits<a_centrality_map>::value_type 
Chris@16:       centrality_type;
Chris@16: 
Chris@16:     typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
Chris@16:     
Chris@16:     std::vector<std::vector<edge_descriptor> > incoming(V);
Chris@16:     std::vector<centrality_type> distance(V);
Chris@16:     std::vector<centrality_type> dependency(V);
Chris@16:     std::vector<degree_size_type> path_count(V);
Chris@16: 
Chris@16:     non_distributed_brandes_betweenness_centrality(
Chris@16:       pg, g, centrality, edge_centrality_map,
Chris@16:       make_iterator_property_map(incoming.begin(), vertex_index),
Chris@16:       make_iterator_property_map(distance.begin(), vertex_index),
Chris@16:       make_iterator_property_map(dependency.begin(), vertex_index),
Chris@16:       make_iterator_property_map(path_count.begin(), vertex_index),
Chris@16:       vertex_index, weight_map, unwrap_ref(sources));
Chris@16:   }
Chris@16:   
Chris@16: 
Chris@16:   template<typename ProcessGroup, typename Graph, typename CentralityMap, 
Chris@16:            typename EdgeCentralityMap, typename VertexIndexMap, typename Buffer>
Chris@16:   void 
Chris@16:   non_distributed_brandes_betweenness_centrality_dispatch2(const ProcessGroup& pg,
Chris@16:                                                            const Graph& g,
Chris@16:                                                            CentralityMap centrality,
Chris@16:                                                            EdgeCentralityMap edge_centrality_map,
Chris@16:                                                            VertexIndexMap vertex_index,
Chris@16:                                                            Buffer sources)
Chris@16:   {
Chris@16:     typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
Chris@16:     typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
Chris@16:     typedef typename mpl::if_c<(is_same<CentralityMap, 
Chris@16:                                         dummy_property_map>::value),
Chris@16:                                          EdgeCentralityMap, 
Chris@16:                                CentralityMap>::type a_centrality_map;
Chris@16:     typedef typename property_traits<a_centrality_map>::value_type 
Chris@16:       centrality_type;
Chris@16: 
Chris@16:     typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
Chris@16:     
Chris@16:     std::vector<std::vector<edge_descriptor> > incoming(V);
Chris@16:     std::vector<centrality_type> distance(V);
Chris@16:     std::vector<centrality_type> dependency(V);
Chris@16:     std::vector<degree_size_type> path_count(V);
Chris@16: 
Chris@16:     non_distributed_brandes_betweenness_centrality(
Chris@16:       pg, g, centrality, edge_centrality_map,
Chris@16:       make_iterator_property_map(incoming.begin(), vertex_index),
Chris@16:       make_iterator_property_map(distance.begin(), vertex_index),
Chris@16:       make_iterator_property_map(dependency.begin(), vertex_index),
Chris@16:       make_iterator_property_map(path_count.begin(), vertex_index),
Chris@16:       vertex_index, unwrap_ref(sources));
Chris@16:   }
Chris@16: 
Chris@16:   template<typename WeightMap>
Chris@16:   struct non_distributed_brandes_betweenness_centrality_dispatch1
Chris@16:   {
Chris@16:     template<typename ProcessGroup, typename Graph, typename CentralityMap, 
Chris@16:              typename EdgeCentralityMap, typename VertexIndexMap, typename Buffer>
Chris@16:     static void 
Chris@16:     run(const ProcessGroup& pg, const Graph& g, CentralityMap centrality, 
Chris@16:         EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
Chris@16:         Buffer sources, WeightMap weight_map)
Chris@16:     {
Chris@16:       non_distributed_brandes_betweenness_centrality_dispatch2(pg, g, centrality, edge_centrality_map,
Chris@16:                                                                weight_map, vertex_index, sources);
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template<>
Chris@16:   struct non_distributed_brandes_betweenness_centrality_dispatch1<param_not_found>
Chris@16:   {
Chris@16:     template<typename ProcessGroup, typename Graph, typename CentralityMap, 
Chris@16:              typename EdgeCentralityMap, typename VertexIndexMap, typename Buffer>
Chris@16:     static void 
Chris@16:     run(const ProcessGroup& pg, const Graph& g, CentralityMap centrality, 
Chris@16:         EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
Chris@16:         Buffer sources, param_not_found)
Chris@16:     {
Chris@16:       non_distributed_brandes_betweenness_centrality_dispatch2(pg, g, centrality, edge_centrality_map,
Chris@16:                                                                vertex_index, sources);
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16: } } // end namespace detail::graph
Chris@16: 
Chris@16: template<typename ProcessGroup, typename Graph, typename Param, typename Tag, typename Rest>
Chris@16: void 
Chris@16: non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g, 
Chris@16:                                                const bgl_named_params<Param,Tag,Rest>& params)
Chris@16: {
Chris@16:   typedef bgl_named_params<Param,Tag,Rest> named_params;
Chris@16: 
Chris@16:   typedef queue<int> queue_t;
Chris@16:   queue_t q;
Chris@16: 
Chris@16:   typedef typename get_param_type<edge_weight_t, named_params>::type ew_param;
Chris@16:   typedef typename detail::choose_impl_result<mpl::true_, Graph, ew_param, edge_weight_t>::type ew;
Chris@16:   detail::graph::non_distributed_brandes_betweenness_centrality_dispatch1<ew>::run(
Chris@16:     pg, g, 
Chris@16:     choose_param(get_param(params, vertex_centrality), 
Chris@16:                  dummy_property_map()),
Chris@16:     choose_param(get_param(params, edge_centrality), 
Chris@16:                  dummy_property_map()),
Chris@16:     choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
Chris@16:     choose_param(get_param(params, buffer_param_t()),  boost::ref(q)),
Chris@16:     choose_const_pmap(get_param(params, edge_weight), g, edge_weight));
Chris@16: }
Chris@16: 
Chris@16: template<typename ProcessGroup, typename Graph, typename CentralityMap>
Chris@16: void 
Chris@16: non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g, 
Chris@16:                                                CentralityMap centrality)
Chris@16: {
Chris@16:   typedef queue<int> queue_t;
Chris@16:   queue_t q;
Chris@16: 
Chris@16:   detail::graph::non_distributed_brandes_betweenness_centrality_dispatch2(
Chris@16:     pg, g, centrality, dummy_property_map(), get(vertex_index, g), boost::ref(q));
Chris@16: }
Chris@16: 
Chris@16: template<typename ProcessGroup, typename Graph, typename CentralityMap, 
Chris@16:          typename Buffer>
Chris@16: void 
Chris@16: non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g, 
Chris@16:                                                CentralityMap centrality, Buffer sources)
Chris@16: {
Chris@16:   detail::graph::non_distributed_brandes_betweenness_centrality_dispatch2(
Chris@16:     pg, g, centrality, dummy_property_map(), get(vertex_index, g), sources);
Chris@16: }
Chris@16: 
Chris@16: template<typename ProcessGroup, typename Graph, typename CentralityMap, 
Chris@16:          typename EdgeCentralityMap, typename Buffer>
Chris@16: void 
Chris@16: non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g, 
Chris@16:                                                CentralityMap centrality,
Chris@16:                                                EdgeCentralityMap edge_centrality_map, 
Chris@16:                                                Buffer sources)
Chris@16: {
Chris@16:   detail::graph::non_distributed_brandes_betweenness_centrality_dispatch2(
Chris@16:     pg, g, centrality, edge_centrality_map, get(vertex_index, g), sources);
Chris@16: }
Chris@16: 
Chris@16: // Compute the central point dominance of a graph.
Chris@16: // TODO: Make sure central point dominance works in parallel case
Chris@16: template<typename Graph, typename CentralityMap>
Chris@16: typename property_traits<CentralityMap>::value_type
Chris@16: central_point_dominance(const Graph& g, CentralityMap centrality
Chris@16:                         BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,distributed_graph_tag))
Chris@16: {
Chris@16:   using std::max;
Chris@16: 
Chris@16:   typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
Chris@16:   typedef typename property_traits<CentralityMap>::value_type centrality_type;
Chris@16:   typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
Chris@16: 
Chris@16:   typedef typename boost::graph::parallel::process_group_type<Graph>::type 
Chris@16:     process_group_type;
Chris@16:   process_group_type pg = boost::graph::parallel::process_group(g);
Chris@16: 
Chris@16:   vertices_size_type n = num_vertices(g);
Chris@16: 
Chris@16:   using boost::parallel::all_reduce;  
Chris@16:   n = all_reduce(pg, n, std::plus<vertices_size_type>());
Chris@16: 
Chris@16:   // Find max centrality
Chris@16:   centrality_type max_centrality(0);
Chris@16:   vertex_iterator v, v_end;
Chris@16:   for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v) {
Chris@16:     max_centrality = (max)(max_centrality, get(centrality, *v));
Chris@16:   }
Chris@16: 
Chris@16:   // All reduce to get global max centrality
Chris@16:   max_centrality = all_reduce(pg, max_centrality, boost::parallel::maximum<centrality_type>());
Chris@16: 
Chris@16:   // Compute central point dominance
Chris@16:   centrality_type sum(0);
Chris@16:   for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v) {
Chris@16:     sum += (max_centrality - get(centrality, *v));
Chris@16:   }
Chris@16: 
Chris@16:   sum = all_reduce(pg, sum, std::plus<centrality_type>());
Chris@16: 
Chris@16:   return sum/(n-1);
Chris@16: }
Chris@16: 
Chris@16: } // end namespace boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_PARALLEL_BRANDES_BETWEENNESS_CENTRALITY_HPP