graph/distributed/dehne_gotz_min_spanning_tree.hpp

0001 // Copyright (C) 2004-2006 The Trustees of Indiana University.
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Douglas Gregor
0008 //           Andrew Lumsdaine
0009
0010 /**
0011  * This header implements four distributed algorithms to compute
0012  * the minimum spanning tree (actually, minimum spanning forest) of a
0013  * graph. All of the algorithms were implemented as specified in the
0014  * paper by Dehne and Gotz:
0015  *
0016  *   Frank Dehne and Silvia Gotz. Practical Parallel Algorithms for Minimum
0017  *   Spanning Trees. In Symposium on Reliable Distributed Systems,
0018  *   pages 366--371, 1998.
0019  *
0020  * There are four algorithm variants implemented.
0021  */
0022
0023 #ifndef BOOST_DEHNE_GOTZ_MIN_SPANNING_TREE_HPP
0024 #define BOOST_DEHNE_GOTZ_MIN_SPANNING_TREE_HPP
0025
0026 #ifndef BOOST_GRAPH_USE_MPI
0027 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
0028 #endif
0029
0030 #include <boost/graph/graph_traits.hpp>
0031 #include <boost/property_map/property_map.hpp>
0032 #include <boost/property_map/parallel/parallel_property_maps.hpp>
0033 #include <vector>
0034 #include <boost/graph/parallel/algorithm.hpp>
0035 #include <boost/limits.hpp>
0036 #include <utility>
0037 #include <boost/pending/disjoint_sets.hpp>
0038 #include <boost/pending/indirect_cmp.hpp>
0039 #include <boost/property_map/parallel/caching_property_map.hpp>
0040 #include <boost/graph/vertex_and_edge_range.hpp>
0041 #include <boost/graph/kruskal_min_spanning_tree.hpp>
0042 #include <boost/iterator/counting_iterator.hpp>
0043 #include <boost/iterator/transform_iterator.hpp>
0044 #include <boost/graph/parallel/container_traits.hpp>
0045 #include <boost/graph/parallel/detail/untracked_pair.hpp>
0046 #include <cmath>
0047
0048 namespace boost { namespace graph { namespace distributed {
0049
0050 namespace detail {
0051   /**
0052    * Binary function object type that selects the (edge, weight) pair
0053    * with the minimum weight. Used within a Boruvka merge step to select
0054    * the candidate edges incident to each supervertex.
0055    */
0056   struct smaller_weighted_edge
0057   {
0058     template<typename Edge, typename Weight>
0059     std::pair<Edge, Weight>
0060     operator()(const std::pair<Edge, Weight>& x,
0061                const std::pair<Edge, Weight>& y) const
0062     { return x.second < y.second? x : y; }
0063   };
0064
0065   /**
0066    * Unary predicate that determines if the source and target vertices
0067    * of the given edge have the same representative within a disjoint
0068    * sets data structure. Used to indicate when an edge is now a
0069    * self-loop because of supervertex merging in Boruvka's algorithm.
0070    */
0071   template<typename DisjointSets, typename Graph>
0072   class do_has_same_supervertex
0073   {
0074   public:
0075     typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
0076
0077     do_has_same_supervertex(DisjointSets& dset, const Graph& g)
0078       : dset(dset), g(g) { }
0079
0080     bool operator()(edge_descriptor e)
0081     { return dset.find_set(source(e, g)) == dset.find_set(target(e, g));    }
0082
0083   private:
0084     DisjointSets&  dset;
0085     const Graph&   g;
0086   };
0087
0088   /**
0089    * Build a @ref do_has_same_supervertex object.
0090    */
0091   template<typename DisjointSets, typename Graph>
0092   inline do_has_same_supervertex<DisjointSets, Graph>
0093   has_same_supervertex(DisjointSets& dset, const Graph& g)
0094   { return do_has_same_supervertex<DisjointSets, Graph>(dset, g); }
0095
0096   /** \brief A single distributed Boruvka merge step.
0097    *
0098    * A distributed Boruvka merge step involves computing (globally)
0099    * the minimum weight edges incident on each supervertex and then
0100    * merging supervertices along these edges. Once supervertices are
0101    * merged, self-loops are eliminated.
0102    *
0103    * The set of parameters passed to this algorithm is large, and
0104    * considering this algorithm in isolation there are several
0105    * redundancies. However, the more asymptotically efficient
0106    * distributed MSF algorithms require mixing Boruvka steps with the
0107    * merging of local MSFs (implemented in
0108    * merge_local_minimum_spanning_trees_step): the interaction of the
0109    * two algorithms mandates the addition of these parameters.
0110    *
0111    * \param pg The process group over which communication should be
0112    * performed. Within the distributed Boruvka algorithm, this will be
0113    * equivalent to \code process_group(g); however, in the context of
0114    * the mixed MSF algorithms, the process group @p pg will be a
0115    * (non-strict) process subgroup of \code process_group(g).
0116    *
0117    * \param g The underlying graph on which the MSF is being
0118    * computed. The type of @p g must model DistributedGraph, but there
0119    * are no other requirements because the edge and (super)vertex
0120    * lists are passed separately.
0121    *
0122    * \param weight_map Property map containing the weights of each
0123    * edge. The type of this property map must model
0124    * ReadablePropertyMap and must support caching.
0125    *
0126    * \param out An output iterator that will be written with the set
0127    * of edges selected to build the MSF. Every process within the
0128    * process group @p pg will receive all edges in the MSF.
0129    *
0130    * \param dset Disjoint sets data structure mapping from vertices in
0131    * the graph @p g to their representative supervertex.
0132    *
0133    * \param supervertex_map Mapping from supervertex descriptors to
0134    * indices.
0135    *
0136    * \param supervertices A vector containing all of the
0137    * supervertices. Will be modified to include only the remaining
0138    * supervertices after merging occurs.
0139    *
0140    * \param edge_list The list of edges that remain in the graph. This
0141    * list will be pruned to remove self-loops once MSF edges have been
0142    * found.
0143    */
0144   template<typename ProcessGroup, typename Graph, typename WeightMap,
0145            typename OutputIterator, typename RankMap, typename ParentMap,
0146            typename SupervertexMap, typename Vertex, typename EdgeList>
0147   OutputIterator
0148   boruvka_merge_step(ProcessGroup pg, const Graph& g, WeightMap weight_map,
0149                      OutputIterator out,
0150                      disjoint_sets<RankMap, ParentMap>& dset,
0151                      SupervertexMap supervertex_map,
0152                      std::vector<Vertex>& supervertices,
0153                      EdgeList& edge_list)
0154   {
0155     typedef typename graph_traits<Graph>::vertex_descriptor
0156                                                            vertex_descriptor;
0157     typedef typename graph_traits<Graph>::vertices_size_type
0158                                                            vertices_size_type;
0159     typedef typename graph_traits<Graph>::edge_descriptor  edge_descriptor;
0160     typedef typename EdgeList::iterator                    edge_iterator;
0161     typedef typename property_traits<WeightMap>::value_type
0162                                                            weight_type;
0163     typedef boost::parallel::detail::untracked_pair<edge_descriptor,
0164                                        weight_type>        w_edge;
0165     typedef typename property_traits<SupervertexMap>::value_type
0166                                                            supervertex_index;
0167
0168     smaller_weighted_edge min_edge;
0169     weight_type inf = (std::numeric_limits<weight_type>::max)();
0170
0171     // Renumber the supervertices
0172     for (std::size_t i = 0; i < supervertices.size(); ++i)
0173       put(supervertex_map, supervertices[i], i);
0174
0175     // BSP-B1: Find local minimum-weight edges for each supervertex
0176     std::vector<w_edge> candidate_edges(supervertices.size(),
0177                                         w_edge(edge_descriptor(), inf));
0178     for (edge_iterator ei = edge_list.begin(); ei != edge_list.end(); ++ei) {
0179       weight_type w = get(weight_map, *ei);
0180       supervertex_index u =
0181         get(supervertex_map, dset.find_set(source(*ei, g)));
0182       supervertex_index v =
0183         get(supervertex_map, dset.find_set(target(*ei, g)));
0184
0185       if (u != v) {
0186         candidate_edges[u] = min_edge(candidate_edges[u], w_edge(*ei, w));
0187         candidate_edges[v] = min_edge(candidate_edges[v], w_edge(*ei, w));
0188       }
0189     }
0190
0191     // BSP-B2 (a): Compute global minimum edges for each supervertex
0192     all_reduce(pg,
0193                &candidate_edges[0],
0194                &candidate_edges[0] + candidate_edges.size(),
0195                &candidate_edges[0], min_edge);
0196
0197     // BSP-B2 (b): Use the edges to compute sequentially the new
0198     // connected components and emit the edges.
0199     for (vertices_size_type i = 0; i < candidate_edges.size(); ++i) {
0200       if (candidate_edges[i].second != inf) {
0201         edge_descriptor e = candidate_edges[i].first;
0202         vertex_descriptor u = dset.find_set(source(e, g));
0203         vertex_descriptor v = dset.find_set(target(e, g));
0204         if (u != v) {
0205           // Emit the edge, but cache the weight so everyone knows it
0206           cache(weight_map, e, candidate_edges[i].second);
0207           *out++ = e;
0208
0209           // Link the two supervertices
0210           dset.link(u, v);
0211
0212           // Whichever vertex was reparented will be removed from the
0213           // list of supervertices.
0214           vertex_descriptor victim = u;
0215           if (dset.find_set(u) == u) victim = v;
0216           supervertices[get(supervertex_map, victim)] =
0217             graph_traits<Graph>::null_vertex();
0218         }
0219       }
0220     }
0221
0222     // BSP-B3: Eliminate self-loops
0223     edge_list.erase(std::remove_if(edge_list.begin(), edge_list.end(),
0224                                    has_same_supervertex(dset, g)),
0225                     edge_list.end());
0226
0227     // TBD: might also eliminate multiple edges between supervertices
0228     // when the edges do not have the best weight, but this is not
0229     // strictly necessary.
0230
0231     // Eliminate supervertices that have been absorbed
0232     supervertices.erase(std::remove(supervertices.begin(),
0233                                     supervertices.end(),
0234                                     graph_traits<Graph>::null_vertex()),
0235                         supervertices.end());
0236
0237     return out;
0238   }
0239
0240   /**
0241    * An edge descriptor adaptor that reroutes the source and target
0242    * edges to different vertices, but retains the original edge
0243    * descriptor for, e.g., property maps. This is used when we want to
0244    * turn a set of edges in the overall graph into a set of edges
0245    * between supervertices.
0246    */
0247   template<typename Graph>
0248   struct supervertex_edge_descriptor
0249   {
0250     typedef supervertex_edge_descriptor self_type;
0251     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
0252     typedef typename graph_traits<Graph>::edge_descriptor Edge;
0253
0254     Vertex source;
0255     Vertex target;
0256     Edge e;
0257
0258     operator Edge() const { return e; }
0259
0260     friend inline bool operator==(const self_type& x, const self_type& y)
0261     { return x.e == y.e; }
0262
0263     friend inline bool operator!=(const self_type& x, const self_type& y)
0264     { return x.e != y.e; }
0265   };
0266
0267   template<typename Graph>
0268   inline typename supervertex_edge_descriptor<Graph>::Vertex
0269   source(supervertex_edge_descriptor<Graph> se, const Graph&)
0270   { return se.source; }
0271
0272   template<typename Graph>
0273   inline typename supervertex_edge_descriptor<Graph>::Vertex
0274   target(supervertex_edge_descriptor<Graph> se, const Graph&)
0275   { return se.target; }
0276
0277   /**
0278    * Build a supervertex edge descriptor from a normal edge descriptor
0279    * using the given disjoint sets data structure to identify
0280    * supervertex representatives.
0281    */
0282   template<typename Graph, typename DisjointSets>
0283   struct build_supervertex_edge_descriptor
0284   {
0285     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
0286     typedef typename graph_traits<Graph>::edge_descriptor   Edge;
0287
0288     typedef Edge argument_type;
0289     typedef supervertex_edge_descriptor<Graph> result_type;
0290
0291     build_supervertex_edge_descriptor() : g(0), dsets(0) { }
0292
0293     build_supervertex_edge_descriptor(const Graph& g, DisjointSets& dsets)
0294       : g(&g), dsets(&dsets) { }
0295
0296     result_type operator()(argument_type e) const
0297     {
0298       result_type result;
0299       result.source = dsets->find_set(source(e, *g));
0300       result.target = dsets->find_set(target(e, *g));
0301       result.e = e;
0302       return result;
0303     }
0304
0305   private:
0306     const Graph* g;
0307     DisjointSets* dsets;
0308   };
0309
0310   template<typename Graph, typename DisjointSets>
0311   inline build_supervertex_edge_descriptor<Graph, DisjointSets>
0312   make_supervertex_edge_descriptor(const Graph& g, DisjointSets& dsets)
0313   { return build_supervertex_edge_descriptor<Graph, DisjointSets>(g, dsets); }
0314
0315   template<typename T>
0316   struct identity_function
0317   {
0318     typedef T argument_type;
0319     typedef T result_type;
0320
0321     result_type operator()(argument_type x) const { return x; }
0322   };
0323
0324   template<typename Graph, typename DisjointSets, typename EdgeMapper>
0325   class is_not_msf_edge
0326   {
0327     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
0328     typedef typename graph_traits<Graph>::edge_descriptor Edge;
0329
0330   public:
0331     is_not_msf_edge(const Graph& g, DisjointSets dset, EdgeMapper edge_mapper)
0332       : g(g), dset(dset), edge_mapper(edge_mapper) { }
0333
0334     bool operator()(Edge e)
0335     {
0336       Vertex u = dset.find_set(source(edge_mapper(e), g));
0337       Vertex v = dset.find_set(target(edge_mapper(e), g));
0338       if (u == v) return true;
0339       else {
0340         dset.link(u, v);
0341         return false;
0342       }
0343     }
0344
0345   private:
0346     const Graph& g;
0347     DisjointSets dset;
0348     EdgeMapper edge_mapper;
0349   };
0350
0351   template<typename Graph, typename ForwardIterator, typename EdgeList,
0352            typename EdgeMapper, typename RankMap, typename ParentMap>
0353   void
0354   sorted_mutating_kruskal(const Graph& g,
0355                           ForwardIterator first_vertex,
0356                           ForwardIterator last_vertex,
0357                           EdgeList& edge_list, EdgeMapper edge_mapper,
0358                           RankMap rank_map, ParentMap parent_map)
0359   {
0360     typedef disjoint_sets<RankMap, ParentMap> DisjointSets;
0361
0362     // Build and initialize disjoint-sets data structure
0363     DisjointSets dset(rank_map, parent_map);
0364     for (ForwardIterator v = first_vertex; v != last_vertex; ++v)
0365       dset.make_set(*v);
0366
0367     is_not_msf_edge<Graph, DisjointSets, EdgeMapper>
0368       remove_non_msf_edges(g, dset, edge_mapper);
0369     edge_list.erase(std::remove_if(edge_list.begin(), edge_list.end(),
0370                                    remove_non_msf_edges),
0371                     edge_list.end());
0372   }
0373
0374   /**
0375    * Merge local minimum spanning forests from p processes into
0376    * minimum spanning forests on p/D processes (where D is the tree
0377    * factor, currently fixed at 3), eliminating unnecessary edges in
0378    * the process.
0379    *
0380    * As with @ref boruvka_merge_step, this routine has many
0381    * parameters, not all of which make sense within the limited
0382    * context of this routine. The parameters are required for the
0383    * Boruvka and local MSF merging steps to interoperate.
0384    *
0385    * \param pg The process group on which local minimum spanning
0386    * forests should be merged. The top (D-1)p/D processes will be
0387    * eliminated, and a new process subgroup containing p/D processors
0388    * will be returned. The value D is a constant factor that is
0389    * currently fixed to 3.
0390    *
0391    * \param g The underlying graph whose MSF is being computed. It must model
0392    * the DistributedGraph concept.
0393    *
0394    * \param first_vertex Iterator to the first vertex in the graph
0395    * that should be considered. While the local MSF merging algorithm
0396    * typically operates on the entire vertex set, within the hybrid
0397    * distributed MSF algorithms this will refer to the first
0398    * supervertex.
0399    *
0400    * \param last_vertex The past-the-end iterator for the vertex list.
0401    *
0402    * \param edge_list The list of local edges that will be
0403    * considered. For the p/D processes that remain, this list will
0404    * contain edges in the MSF known to the vertex after other
0405    * processes' edge lists have been merged. The edge list must be
0406    * sorted in order of increasing weight.
0407    *
0408    * \param weight Property map containing the weights of each
0409    * edge. The type of this property map must model
0410    * ReadablePropertyMap and must support caching.
0411    *
0412    * \param global_index Mapping from vertex descriptors to a global
0413    * index. The type must model ReadablePropertyMap.
0414    *
0415    * \param edge_mapper A function object that can remap edge descriptors
0416    * in the edge list to any alternative edge descriptor. This
0417    * function object will be the identity function when a pure merging
0418    * of local MSFs is required, but may be a mapping to a supervertex
0419    * edge when the local MSF merging occurs on a supervertex
0420    * graph. This function object saves us the trouble of having to
0421    * build a supervertex graph adaptor.
0422    *
0423    * \param already_local_msf True when the edge list already
0424    * constitutes a local MSF. If false, Kruskal's algorithm will first
0425    * be applied to the local edge list to select MSF edges.
0426    *
0427    * \returns The process subgroup containing the remaining p/D
0428    * processes. If the size of this process group is greater than one,
0429    * the MSF edges contained in the edge list do not constitute an MSF
0430    * for the entire graph.
0431    */
0432   template<typename ProcessGroup, typename Graph, typename ForwardIterator,
0433            typename EdgeList, typename WeightMap, typename GlobalIndexMap,
0434            typename EdgeMapper>
0435   ProcessGroup
0436   merge_local_minimum_spanning_trees_step(ProcessGroup pg,
0437                                           const Graph& g,
0438                                           ForwardIterator first_vertex,
0439                                           ForwardIterator last_vertex,
0440                                           EdgeList& edge_list,
0441                                           WeightMap weight,
0442                                           GlobalIndexMap global_index,
0443                                           EdgeMapper edge_mapper,
0444                                           bool already_local_msf)
0445   {
0446     typedef typename ProcessGroup::process_id_type process_id_type;
0447     typedef typename EdgeList::value_type edge_descriptor;
0448     typedef typename property_traits<WeightMap>::value_type weight_type;
0449     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
0450
0451     // The tree factor, often called "D"
0452     process_id_type const tree_factor = 3;
0453     process_id_type num_procs = num_processes(pg);
0454     process_id_type id = process_id(pg);
0455     process_id_type procs_left = (num_procs + tree_factor - 1) / tree_factor;
0456     std::size_t n = std::size_t(last_vertex - first_vertex);
0457
0458     if (!already_local_msf) {
0459       // Compute local minimum spanning forest. We only care about the
0460       // edges in the MSF, because only edges in the local MSF can be in
0461       // the global MSF.
0462       std::vector<std::size_t> ranks(n);
0463       std::vector<vertex_descriptor> parents(n);
0464       detail::sorted_mutating_kruskal
0465         (g, first_vertex, last_vertex,
0466          edge_list, edge_mapper,
0467          make_iterator_property_map(ranks.begin(), global_index),
0468          make_iterator_property_map(parents.begin(), global_index));
0469     }
0470
0471     typedef std::pair<edge_descriptor, weight_type> w_edge;
0472
0473     // Order edges based on their weights.
0474     indirect_cmp<WeightMap, std::less<weight_type> > cmp_edge_weight(weight);
0475
0476     if (id < procs_left) {
0477       // The p/D processes that remain will receive local MSF edges from
0478       // D-1 other processes.
0479       synchronize(pg);
0480       for (process_id_type from_id = procs_left + id; from_id < num_procs;
0481            from_id += procs_left) {
0482         std::size_t num_incoming_edges;
0483         receive(pg, from_id, 0, num_incoming_edges);
0484         if (num_incoming_edges > 0) {
0485           std::vector<w_edge> incoming_edges(num_incoming_edges);
0486           receive(pg, from_id, 1, &incoming_edges[0], num_incoming_edges);
0487
0488           edge_list.reserve(edge_list.size() + num_incoming_edges);
0489           for (std::size_t i = 0; i < num_incoming_edges; ++i) {
0490             cache(weight, incoming_edges[i].first, incoming_edges[i].second);
0491             edge_list.push_back(incoming_edges[i].first);
0492           }
0493           std::inplace_merge(edge_list.begin(),
0494                              edge_list.end() - num_incoming_edges,
0495                              edge_list.end(),
0496                              cmp_edge_weight);
0497         }
0498       }
0499
0500       // Compute the local MSF from union of the edges in the MSFs of
0501       // all children.
0502       std::vector<std::size_t> ranks(n);
0503       std::vector<vertex_descriptor> parents(n);
0504       detail::sorted_mutating_kruskal
0505         (g, first_vertex, last_vertex,
0506          edge_list, edge_mapper,
0507          make_iterator_property_map(ranks.begin(), global_index),
0508          make_iterator_property_map(parents.begin(), global_index));
0509     } else {
0510       // The (D-1)p/D processes that are dropping out of further
0511       // computations merely send their MSF edges to their parent
0512       // process in the process tree.
0513       send(pg, id % procs_left, 0, edge_list.size());
0514       if (edge_list.size() > 0) {
0515         std::vector<w_edge> outgoing_edges;
0516         outgoing_edges.reserve(edge_list.size());
0517         for (std::size_t i = 0; i < edge_list.size(); ++i) {
0518           outgoing_edges.push_back(std::make_pair(edge_list[i],
0519                                                   get(weight, edge_list[i])));
0520         }
0521         send(pg, id % procs_left, 1, &outgoing_edges[0],
0522              outgoing_edges.size());
0523       }
0524       synchronize(pg);
0525     }
0526
0527     // Return a process subgroup containing the p/D parent processes
0528     return process_subgroup(pg,
0529                             make_counting_iterator(process_id_type(0)),
0530                             make_counting_iterator(procs_left));
0531   }
0532 } // end namespace detail
0533
0534 // ---------------------------------------------------------------------
0535 // Dense Boruvka MSF algorithm
0536 // ---------------------------------------------------------------------
0537 template<typename Graph, typename WeightMap, typename OutputIterator,
0538          typename VertexIndexMap, typename RankMap, typename ParentMap,
0539          typename SupervertexMap>
0540 OutputIterator
0541 dense_boruvka_minimum_spanning_tree(const Graph& g, WeightMap weight_map,
0542                                     OutputIterator out,
0543                                     VertexIndexMap index_map,
0544                                     RankMap rank_map, ParentMap parent_map,
0545                                     SupervertexMap supervertex_map)
0546 {
0547   using boost::graph::parallel::process_group;
0548
0549   typedef typename graph_traits<Graph>::traversal_category traversal_category;
0550
0551   BOOST_STATIC_ASSERT((is_convertible<traversal_category*,
0552                                       vertex_list_graph_tag*>::value));
0553
0554   typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
0555   typedef typename graph_traits<Graph>::vertex_descriptor  vertex_descriptor;
0556   typedef typename graph_traits<Graph>::vertex_iterator    vertex_iterator;
0557   typedef typename graph_traits<Graph>::edge_descriptor    edge_descriptor;
0558
0559   // Don't throw away cached edge weights
0560   weight_map.set_max_ghost_cells(0);
0561
0562   // Initialize the disjoint sets structures
0563   disjoint_sets<RankMap, ParentMap> dset(rank_map, parent_map);
0564   vertex_iterator vi, vi_end;
0565   for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
0566     dset.make_set(*vi);
0567
0568   std::vector<vertex_descriptor> supervertices;
0569   supervertices.assign(vertices(g).first, vertices(g).second);
0570
0571   // Use Kruskal's algorithm to find the minimum spanning forest
0572   // considering only the local edges. The resulting edges are not
0573   // necessarily going to be in the final minimum spanning
0574   // forest. However, any edge not part of the local MSF cannot be a
0575   // part of the global MSF, so we should have eliminated some edges
0576   // from consideration.
0577   std::vector<edge_descriptor> edge_list;
0578   kruskal_minimum_spanning_tree
0579     (make_vertex_and_edge_range(g, vertices(g).first, vertices(g).second,
0580                                 edges(g).first, edges(g).second),
0581      std::back_inserter(edge_list),
0582      boost::weight_map(weight_map).
0583      vertex_index_map(index_map));
0584
0585   // While the number of supervertices is decreasing, keep executing
0586   // Boruvka steps to identify additional MSF edges. This loop will
0587   // execute log |V| times.
0588   vertices_size_type old_num_supervertices;
0589   do {
0590     old_num_supervertices = supervertices.size();
0591     out = detail::boruvka_merge_step(process_group(g), g,
0592                                      weight_map, out,
0593                                      dset, supervertex_map, supervertices,
0594                                      edge_list);
0595   } while (supervertices.size() < old_num_supervertices);
0596
0597   return out;
0598 }
0599
0600 template<typename Graph, typename WeightMap, typename OutputIterator,
0601          typename VertexIndex>
0602 OutputIterator
0603 dense_boruvka_minimum_spanning_tree(const Graph& g, WeightMap weight_map,
0604                                     OutputIterator out, VertexIndex i_map)
0605 {
0606   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
0607
0608   std::vector<std::size_t> ranks(num_vertices(g));
0609   std::vector<vertex_descriptor> parents(num_vertices(g));
0610   std::vector<std::size_t> supervertices(num_vertices(g));
0611
0612   return dense_boruvka_minimum_spanning_tree
0613            (g, weight_map, out, i_map,
0614             make_iterator_property_map(ranks.begin(), i_map),
0615             make_iterator_property_map(parents.begin(), i_map),
0616             make_iterator_property_map(supervertices.begin(), i_map));
0617 }
0618
0619 template<typename Graph, typename WeightMap, typename OutputIterator>
0620 OutputIterator
0621 dense_boruvka_minimum_spanning_tree(const Graph& g, WeightMap weight_map,
0622                                     OutputIterator out)
0623 {
0624   return dense_boruvka_minimum_spanning_tree(g, weight_map, out,
0625                                              get(vertex_index, g));
0626 }
0627
0628 // ---------------------------------------------------------------------
0629 // Merge local MSFs MSF algorithm
0630 // ---------------------------------------------------------------------
0631 template<typename Graph, typename WeightMap, typename OutputIterator,
0632          typename GlobalIndexMap>
0633 OutputIterator
0634 merge_local_minimum_spanning_trees(const Graph& g, WeightMap weight,
0635                                    OutputIterator out,
0636                                    GlobalIndexMap global_index)
0637 {
0638   using boost::graph::parallel::process_group_type;
0639   using boost::graph::parallel::process_group;
0640
0641   typedef typename graph_traits<Graph>::traversal_category traversal_category;
0642
0643   BOOST_STATIC_ASSERT((is_convertible<traversal_category*,
0644                                       vertex_list_graph_tag*>::value));
0645
0646   typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
0647
0648   // Don't throw away cached edge weights
0649   weight.set_max_ghost_cells(0);
0650
0651   // Compute the initial local minimum spanning forests
0652   std::vector<edge_descriptor> edge_list;
0653   kruskal_minimum_spanning_tree
0654     (make_vertex_and_edge_range(g, vertices(g).first, vertices(g).second,
0655                                 edges(g).first, edges(g).second),
0656      std::back_inserter(edge_list),
0657      boost::weight_map(weight).vertex_index_map(global_index));
0658
0659   // Merge the local MSFs from p processes into p/D processes,
0660   // reducing the number of processes in each step. Continue looping
0661   // until either (a) the current process drops out or (b) only one
0662   // process remains in the group. This loop will execute log_D p
0663   // times.
0664   typename process_group_type<Graph>::type pg = process_group(g);
0665   while (pg && num_processes(pg) > 1) {
0666     pg = detail::merge_local_minimum_spanning_trees_step
0667            (pg, g, vertices(g).first, vertices(g).second,
0668             edge_list, weight, global_index,
0669             detail::identity_function<edge_descriptor>(), true);
0670   }
0671
0672   // Only process 0 has the entire edge list, so emit it to the output
0673   // iterator.
0674   if (pg && process_id(pg) == 0) {
0675     out = std::copy(edge_list.begin(), edge_list.end(), out);
0676   }
0677
0678   synchronize(process_group(g));
0679   return out;
0680 }
0681
0682 template<typename Graph, typename WeightMap, typename OutputIterator>
0683 inline OutputIterator
0684 merge_local_minimum_spanning_trees(const Graph& g, WeightMap weight,
0685                                    OutputIterator out)
0686 {
0687   return merge_local_minimum_spanning_trees(g, weight, out,
0688                                             get(vertex_index, g));
0689 }
0690
0691 // ---------------------------------------------------------------------
0692 // Boruvka-then-merge MSF algorithm
0693 // ---------------------------------------------------------------------
0694 template<typename Graph, typename WeightMap, typename OutputIterator,
0695          typename GlobalIndexMap, typename RankMap, typename ParentMap,
0696          typename SupervertexMap>
0697 OutputIterator
0698 boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out,
0699                    GlobalIndexMap index, RankMap rank_map,
0700                    ParentMap parent_map, SupervertexMap supervertex_map)
0701 {
0702   using std::log;
0703   using boost::graph::parallel::process_group_type;
0704   using boost::graph::parallel::process_group;
0705
0706   typedef typename graph_traits<Graph>::traversal_category traversal_category;
0707
0708   BOOST_STATIC_ASSERT((is_convertible<traversal_category*,
0709                                       vertex_list_graph_tag*>::value));
0710
0711   typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
0712   typedef typename graph_traits<Graph>::vertex_descriptor  vertex_descriptor;
0713   typedef typename graph_traits<Graph>::vertex_iterator    vertex_iterator;
0714   typedef typename graph_traits<Graph>::edge_descriptor    edge_descriptor;
0715
0716   // Don't throw away cached edge weights
0717   weight.set_max_ghost_cells(0);
0718
0719   // Compute the initial local minimum spanning forests
0720   std::vector<edge_descriptor> edge_list;
0721   kruskal_minimum_spanning_tree
0722     (make_vertex_and_edge_range(g, vertices(g).first, vertices(g).second,
0723                                 edges(g).first, edges(g).second),
0724      std::back_inserter(edge_list),
0725      boost::weight_map(weight).
0726      vertex_index_map(index));
0727
0728   // Initialize the disjoint sets structures for Boruvka steps
0729   disjoint_sets<RankMap, ParentMap> dset(rank_map, parent_map);
0730   vertex_iterator vi, vi_end;
0731   for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
0732     dset.make_set(*vi);
0733
0734   // Construct the initial set of supervertices (all vertices)
0735   std::vector<vertex_descriptor> supervertices;
0736   supervertices.assign(vertices(g).first, vertices(g).second);
0737
0738   // Continue performing Boruvka merge steps until the number of
0739   // supervertices reaches |V| / (log_D p)^2.
0740   const std::size_t tree_factor = 3; // TBD: same as above! should be param
0741   double log_d_p = log((double)num_processes(process_group(g)))
0742                  / log((double)tree_factor);
0743   vertices_size_type target_supervertices =
0744     vertices_size_type(num_vertices(g) / (log_d_p * log_d_p));
0745   vertices_size_type old_num_supervertices;
0746   while (supervertices.size() > target_supervertices) {
0747     old_num_supervertices = supervertices.size();
0748     out = detail::boruvka_merge_step(process_group(g), g,
0749                                      weight, out, dset,
0750                                      supervertex_map, supervertices,
0751                                      edge_list);
0752     if (supervertices.size() == old_num_supervertices)
0753       return out;
0754   }
0755
0756   // Renumber the supervertices
0757   for (std::size_t i = 0; i < supervertices.size(); ++i)
0758     put(supervertex_map, supervertices[i], i);
0759
0760   // Merge local MSFs on the supervertices. (D-1)p/D processors drop
0761   // out each iteration, so this loop executes log_D p times.
0762   typename process_group_type<Graph>::type pg = process_group(g);
0763   bool have_msf = false;
0764   while (pg && num_processes(pg) > 1) {
0765     pg = detail::merge_local_minimum_spanning_trees_step
0766            (pg, g, supervertices.begin(), supervertices.end(),
0767             edge_list, weight, supervertex_map,
0768             detail::make_supervertex_edge_descriptor(g, dset),
0769             have_msf);
0770     have_msf = true;
0771   }
0772
0773   // Only process 0 has the complete list of _supervertex_ MST edges,
0774   // so emit those to the output iterator. This is not the complete
0775   // list of edges in the MSF, however: the Boruvka steps in the
0776   // beginning of the algorithm emitted any edges used to merge
0777   // supervertices.
0778   if (pg && process_id(pg) == 0)
0779     out = std::copy(edge_list.begin(), edge_list.end(), out);
0780
0781   synchronize(process_group(g));
0782   return out;
0783 }
0784
0785 template<typename Graph, typename WeightMap, typename OutputIterator,
0786          typename GlobalIndexMap>
0787 inline OutputIterator
0788 boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out,
0789                     GlobalIndexMap index)
0790 {
0791   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
0792   typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
0793   std::vector<vertices_size_type> ranks(num_vertices(g));
0794   std::vector<vertex_descriptor> parents(num_vertices(g));
0795   std::vector<vertices_size_type> supervertex_indices(num_vertices(g));
0796
0797   return boruvka_then_merge
0798            (g, weight, out, index,
0799             make_iterator_property_map(ranks.begin(), index),
0800             make_iterator_property_map(parents.begin(), index),
0801             make_iterator_property_map(supervertex_indices.begin(), index));
0802 }
0803
0804 template<typename Graph, typename WeightMap, typename OutputIterator>
0805 inline OutputIterator
0806 boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out)
0807 { return boruvka_then_merge(g, weight, out, get(vertex_index, g)); }
0808
0809 // ---------------------------------------------------------------------
0810 // Boruvka-mixed-merge MSF algorithm
0811 // ---------------------------------------------------------------------
0812 template<typename Graph, typename WeightMap, typename OutputIterator,
0813          typename GlobalIndexMap, typename RankMap, typename ParentMap,
0814          typename SupervertexMap>
0815 OutputIterator
0816 boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out,
0817                     GlobalIndexMap index, RankMap rank_map,
0818                     ParentMap parent_map, SupervertexMap supervertex_map)
0819 {
0820   using boost::graph::parallel::process_group_type;
0821   using boost::graph::parallel::process_group;
0822
0823   typedef typename graph_traits<Graph>::traversal_category traversal_category;
0824
0825   BOOST_STATIC_ASSERT((is_convertible<traversal_category*,
0826                                       vertex_list_graph_tag*>::value));
0827
0828   typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
0829   typedef typename graph_traits<Graph>::vertex_descriptor  vertex_descriptor;
0830   typedef typename graph_traits<Graph>::vertex_iterator    vertex_iterator;
0831   typedef typename graph_traits<Graph>::edge_descriptor    edge_descriptor;
0832
0833   // Don't throw away cached edge weights
0834   weight.set_max_ghost_cells(0);
0835
0836   // Initialize the disjoint sets structures for Boruvka steps
0837   disjoint_sets<RankMap, ParentMap> dset(rank_map, parent_map);
0838   vertex_iterator vi, vi_end;
0839   for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
0840     dset.make_set(*vi);
0841
0842   // Construct the initial set of supervertices (all vertices)
0843   std::vector<vertex_descriptor> supervertices;
0844   supervertices.assign(vertices(g).first, vertices(g).second);
0845
0846   // Compute the initial local minimum spanning forests
0847   std::vector<edge_descriptor> edge_list;
0848   kruskal_minimum_spanning_tree
0849     (make_vertex_and_edge_range(g, vertices(g).first, vertices(g).second,
0850                                 edges(g).first, edges(g).second),
0851      std::back_inserter(edge_list),
0852      boost::weight_map(weight).
0853      vertex_index_map(index));
0854
0855   if (num_processes(process_group(g)) == 1) {
0856     return std::copy(edge_list.begin(), edge_list.end(), out);
0857   }
0858
0859   // Like the merging local MSFs algorithm and the Boruvka-then-merge
0860   // algorithm, each iteration of this loop reduces the number of
0861   // processes by a constant factor D, and therefore we require log_D
0862   // p iterations. Note also that the number of edges in the edge list
0863   // decreases geometrically, giving us an efficient distributed MSF
0864   // algorithm.
0865   typename process_group_type<Graph>::type pg = process_group(g);
0866   vertices_size_type old_num_supervertices;
0867   while (pg && num_processes(pg) > 1) {
0868     // A single Boruvka step. If this doesn't change anything, we're done
0869     old_num_supervertices = supervertices.size();
0870     out = detail::boruvka_merge_step(pg, g, weight, out, dset,
0871                                      supervertex_map, supervertices,
0872                                      edge_list);
0873     if (old_num_supervertices == supervertices.size()) {
0874       edge_list.clear();
0875       break;
0876     }
0877
0878     // Renumber the supervertices
0879     for (std::size_t i = 0; i < supervertices.size(); ++i)
0880       put(supervertex_map, supervertices[i], i);
0881
0882     // A single merging of local MSTs, which reduces the number of
0883     // processes we're using by a constant factor D.
0884     pg = detail::merge_local_minimum_spanning_trees_step
0885            (pg, g, supervertices.begin(), supervertices.end(),
0886             edge_list, weight, supervertex_map,
0887             detail::make_supervertex_edge_descriptor(g, dset),
0888             true);
0889
0890   }
0891
0892   // Only process 0 has the complete edge list, so emit it for the
0893   // user. Note that list edge list only contains the MSF edges in the
0894   // final supervertex graph: all of the other edges were used to
0895   // merge supervertices and have been emitted by the Boruvka steps,
0896   // although only process 0 has received the complete set.
0897   if (pg && process_id(pg) == 0)
0898     out = std::copy(edge_list.begin(), edge_list.end(), out);
0899
0900   synchronize(process_group(g));
0901   return out;
0902 }
0903
0904 template<typename Graph, typename WeightMap, typename OutputIterator,
0905          typename GlobalIndexMap>
0906 inline OutputIterator
0907 boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out,
0908                     GlobalIndexMap index)
0909 {
0910   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
0911   typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
0912   std::vector<vertices_size_type> ranks(num_vertices(g));
0913   std::vector<vertex_descriptor> parents(num_vertices(g));
0914   std::vector<vertices_size_type> supervertex_indices(num_vertices(g));
0915
0916   return boruvka_mixed_merge
0917            (g, weight, out, index,
0918             make_iterator_property_map(ranks.begin(), index),
0919             make_iterator_property_map(parents.begin(), index),
0920             make_iterator_property_map(supervertex_indices.begin(), index));
0921 }
0922
0923 template<typename Graph, typename WeightMap, typename OutputIterator>
0924 inline OutputIterator
0925 boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out)
0926 { return boruvka_mixed_merge(g, weight, out, get(vertex_index, g)); }
0927
0928 } // end namespace distributed
0929
0930 using distributed::dense_boruvka_minimum_spanning_tree;
0931 using distributed::merge_local_minimum_spanning_trees;
0932 using distributed::boruvka_then_merge;
0933 using distributed::boruvka_mixed_merge;
0934
0935 } } // end namespace boost::graph
0936
0937
0938 #endif // BOOST_DEHNE_GOTZ_MIN_SPANNING_TREE_HPP