168492376
/
gnss-sim
1
0
Fork 0
Code Issues 10 Pull Requests Packages Projects Releases Wiki Activity
gnss-sim/3rdparty/boost/graph/distributed/dehne_gotz_min_spanning_tre...

939 lines
38 KiB
C++
Raw Permalink Blame History

// Copyright (C) 2004-2006 The Trustees of Indiana University.
// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
// Authors: Douglas Gregor
// Andrew Lumsdaine
/**
* This header implements four distributed algorithms to compute
* the minimum spanning tree (actually, minimum spanning forest) of a
* graph. All of the algorithms were implemented as specified in the
* paper by Dehne and Gotz:
*
* Frank Dehne and Silvia Gotz. Practical Parallel Algorithms for Minimum
* Spanning Trees. In Symposium on Reliable Distributed Systems,
* pages 366--371, 1998.
*
* There are four algorithm variants implemented.
*/
#ifndef BOOST_DEHNE_GOTZ_MIN_SPANNING_TREE_HPP
#define BOOST_DEHNE_GOTZ_MIN_SPANNING_TREE_HPP
#ifndef BOOST_GRAPH_USE_MPI
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
#endif
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/property_map/parallel/parallel_property_maps.hpp>
#include <vector>
#include <boost/graph/parallel/algorithm.hpp>
#include <boost/limits.hpp>
#include <utility>
#include <boost/pending/disjoint_sets.hpp>
#include <boost/pending/indirect_cmp.hpp>
#include <boost/property_map/parallel/caching_property_map.hpp>
#include <boost/graph/vertex_and_edge_range.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <boost/iterator/counting_iterator.hpp>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/graph/parallel/container_traits.hpp>
#include <boost/graph/parallel/detail/untracked_pair.hpp>
#include <cmath>
namespace boost { namespace graph { namespace distributed {
namespace detail {
/**
* Binary function object type that selects the (edge, weight) pair
* with the minimum weight. Used within a Boruvka merge step to select
* the candidate edges incident to each supervertex.
*/
struct smaller_weighted_edge
{
template<typename Edge, typename Weight>
std::pair<Edge, Weight>
operator()(const std::pair<Edge, Weight>& x,
const std::pair<Edge, Weight>& y) const
{ return x.second < y.second? x : y; }
};
/**
* Unary predicate that determines if the source and target vertices
* of the given edge have the same representative within a disjoint
* sets data structure. Used to indicate when an edge is now a
* self-loop because of supervertex merging in Boruvka's algorithm.
*/
template<typename DisjointSets, typename Graph>
class do_has_same_supervertex
{
public:
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
do_has_same_supervertex(DisjointSets& dset, const Graph& g)
: dset(dset), g(g) { }
bool operator()(edge_descriptor e)
{ return dset.find_set(source(e, g)) == dset.find_set(target(e, g)); }
private:
DisjointSets& dset;
const Graph& g;
};
/**
* Build a @ref do_has_same_supervertex object.
*/
template<typename DisjointSets, typename Graph>
inline do_has_same_supervertex<DisjointSets, Graph>
has_same_supervertex(DisjointSets& dset, const Graph& g)
{ return do_has_same_supervertex<DisjointSets, Graph>(dset, g); }
/** \brief A single distributed Boruvka merge step.
*
* A distributed Boruvka merge step involves computing (globally)
* the minimum weight edges incident on each supervertex and then
* merging supervertices along these edges. Once supervertices are
* merged, self-loops are eliminated.
*
* The set of parameters passed to this algorithm is large, and
* considering this algorithm in isolation there are several
* redundancies. However, the more asymptotically efficient
* distributed MSF algorithms require mixing Boruvka steps with the
* merging of local MSFs (implemented in
* merge_local_minimum_spanning_trees_step): the interaction of the
* two algorithms mandates the addition of these parameters.
*
* \param pg The process group over which communication should be
* performed. Within the distributed Boruvka algorithm, this will be
* equivalent to \code process_group(g); however, in the context of
* the mixed MSF algorithms, the process group @p pg will be a
* (non-strict) process subgroup of \code process_group(g).
*
* \param g The underlying graph on which the MSF is being
* computed. The type of @p g must model DistributedGraph, but there
* are no other requirements because the edge and (super)vertex
* lists are passed separately.
*
* \param weight_map Property map containing the weights of each
* edge. The type of this property map must model
* ReadablePropertyMap and must support caching.
*
* \param out An output iterator that will be written with the set
* of edges selected to build the MSF. Every process within the
* process group @p pg will receive all edges in the MSF.
*
* \param dset Disjoint sets data structure mapping from vertices in
* the graph @p g to their representative supervertex.
*
* \param supervertex_map Mapping from supervertex descriptors to
* indices.
*
* \param supervertices A vector containing all of the
* supervertices. Will be modified to include only the remaining
* supervertices after merging occurs.
*
* \param edge_list The list of edges that remain in the graph. This
* list will be pruned to remove self-loops once MSF edges have been
* found.
*/
template<typename ProcessGroup, typename Graph, typename WeightMap,
typename OutputIterator, typename RankMap, typename ParentMap,
typename SupervertexMap, typename Vertex, typename EdgeList>
OutputIterator
boruvka_merge_step(ProcessGroup pg, const Graph& g, WeightMap weight_map,
OutputIterator out,
disjoint_sets<RankMap, ParentMap>& dset,
SupervertexMap supervertex_map,
std::vector<Vertex>& supervertices,
EdgeList& edge_list)
{
typedef typename graph_traits<Graph>::vertex_descriptor
vertex_descriptor;
typedef typename graph_traits<Graph>::vertices_size_type
vertices_size_type;
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
typedef typename EdgeList::iterator edge_iterator;
typedef typename property_traits<WeightMap>::value_type
weight_type;
typedef boost::parallel::detail::untracked_pair<edge_descriptor,
weight_type> w_edge;
typedef typename property_traits<SupervertexMap>::value_type
supervertex_index;
smaller_weighted_edge min_edge;
weight_type inf = (std::numeric_limits<weight_type>::max)();
// Renumber the supervertices
for (std::size_t i = 0; i < supervertices.size(); ++i)
put(supervertex_map, supervertices[i], i);
// BSP-B1: Find local minimum-weight edges for each supervertex
std::vector<w_edge> candidate_edges(supervertices.size(),
w_edge(edge_descriptor(), inf));
for (edge_iterator ei = edge_list.begin(); ei != edge_list.end(); ++ei) {
weight_type w = get(weight_map, *ei);
supervertex_index u =
get(supervertex_map, dset.find_set(source(*ei, g)));
supervertex_index v =
get(supervertex_map, dset.find_set(target(*ei, g)));
if (u != v) {
candidate_edges[u] = min_edge(candidate_edges[u], w_edge(*ei, w));
candidate_edges[v] = min_edge(candidate_edges[v], w_edge(*ei, w));
}
}
// BSP-B2 (a): Compute global minimum edges for each supervertex
all_reduce(pg,
&candidate_edges[0],
&candidate_edges[0] + candidate_edges.size(),
&candidate_edges[0], min_edge);
// BSP-B2 (b): Use the edges to compute sequentially the new
// connected components and emit the edges.
for (vertices_size_type i = 0; i < candidate_edges.size(); ++i) {
if (candidate_edges[i].second != inf) {
edge_descriptor e = candidate_edges[i].first;
vertex_descriptor u = dset.find_set(source(e, g));
vertex_descriptor v = dset.find_set(target(e, g));
if (u != v) {
// Emit the edge, but cache the weight so everyone knows it
cache(weight_map, e, candidate_edges[i].second);
*out++ = e;
// Link the two supervertices
dset.link(u, v);
// Whichever vertex was reparented will be removed from the
// list of supervertices.
vertex_descriptor victim = u;
if (dset.find_set(u) == u) victim = v;
supervertices[get(supervertex_map, victim)] =
graph_traits<Graph>::null_vertex();
}
}
}
// BSP-B3: Eliminate self-loops
edge_list.erase(std::remove_if(edge_list.begin(), edge_list.end(),
has_same_supervertex(dset, g)),
edge_list.end());
// TBD: might also eliminate multiple edges between supervertices
// when the edges do not have the best weight, but this is not
// strictly necessary.
// Eliminate supervertices that have been absorbed
supervertices.erase(std::remove(supervertices.begin(),
supervertices.end(),
graph_traits<Graph>::null_vertex()),
supervertices.end());
return out;
}
/**
* An edge descriptor adaptor that reroutes the source and target
* edges to different vertices, but retains the original edge
* descriptor for, e.g., property maps. This is used when we want to
* turn a set of edges in the overall graph into a set of edges
* between supervertices.
*/
template<typename Graph>
struct supervertex_edge_descriptor
{
typedef supervertex_edge_descriptor self_type;
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::edge_descriptor Edge;
Vertex source;
Vertex target;
Edge e;
operator Edge() const { return e; }
friend inline bool operator==(const self_type& x, const self_type& y)
{ return x.e == y.e; }
friend inline bool operator!=(const self_type& x, const self_type& y)
{ return x.e != y.e; }
};
template<typename Graph>
inline typename supervertex_edge_descriptor<Graph>::Vertex
source(supervertex_edge_descriptor<Graph> se, const Graph&)
{ return se.source; }
template<typename Graph>
inline typename supervertex_edge_descriptor<Graph>::Vertex
target(supervertex_edge_descriptor<Graph> se, const Graph&)
{ return se.target; }
/**
* Build a supervertex edge descriptor from a normal edge descriptor
* using the given disjoint sets data structure to identify
* supervertex representatives.
*/
template<typename Graph, typename DisjointSets>
struct build_supervertex_edge_descriptor
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::edge_descriptor Edge;
typedef Edge argument_type;
typedef supervertex_edge_descriptor<Graph> result_type;
build_supervertex_edge_descriptor() : g(0), dsets(0) { }
build_supervertex_edge_descriptor(const Graph& g, DisjointSets& dsets)
: g(&g), dsets(&dsets) { }
result_type operator()(argument_type e) const
{
result_type result;
result.source = dsets->find_set(source(e, *g));
result.target = dsets->find_set(target(e, *g));
result.e = e;
return result;
}
private:
const Graph* g;
DisjointSets* dsets;
};
template<typename Graph, typename DisjointSets>
inline build_supervertex_edge_descriptor<Graph, DisjointSets>
make_supervertex_edge_descriptor(const Graph& g, DisjointSets& dsets)
{ return build_supervertex_edge_descriptor<Graph, DisjointSets>(g, dsets); }
template<typename T>
struct identity_function
{
typedef T argument_type;
typedef T result_type;
result_type operator()(argument_type x) const { return x; }
};
template<typename Graph, typename DisjointSets, typename EdgeMapper>
class is_not_msf_edge
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::edge_descriptor Edge;
public:
is_not_msf_edge(const Graph& g, DisjointSets dset, EdgeMapper edge_mapper)
: g(g), dset(dset), edge_mapper(edge_mapper) { }
bool operator()(Edge e)
{
Vertex u = dset.find_set(source(edge_mapper(e), g));
Vertex v = dset.find_set(target(edge_mapper(e), g));
if (u == v) return true;
else {
dset.link(u, v);
return false;
}
}
private:
const Graph& g;
DisjointSets dset;
EdgeMapper edge_mapper;
};
template<typename Graph, typename ForwardIterator, typename EdgeList,
typename EdgeMapper, typename RankMap, typename ParentMap>
void
sorted_mutating_kruskal(const Graph& g,
ForwardIterator first_vertex,
ForwardIterator last_vertex,
EdgeList& edge_list, EdgeMapper edge_mapper,
RankMap rank_map, ParentMap parent_map)
{
typedef disjoint_sets<RankMap, ParentMap> DisjointSets;
// Build and initialize disjoint-sets data structure
DisjointSets dset(rank_map, parent_map);
for (ForwardIterator v = first_vertex; v != last_vertex; ++v)
dset.make_set(*v);
is_not_msf_edge<Graph, DisjointSets, EdgeMapper>
remove_non_msf_edges(g, dset, edge_mapper);
edge_list.erase(std::remove_if(edge_list.begin(), edge_list.end(),
remove_non_msf_edges),
edge_list.end());
}
/**
* Merge local minimum spanning forests from p processes into
* minimum spanning forests on p/D processes (where D is the tree
* factor, currently fixed at 3), eliminating unnecessary edges in
* the process.
*
* As with @ref boruvka_merge_step, this routine has many
* parameters, not all of which make sense within the limited
* context of this routine. The parameters are required for the
* Boruvka and local MSF merging steps to interoperate.
*
* \param pg The process group on which local minimum spanning
* forests should be merged. The top (D-1)p/D processes will be
* eliminated, and a new process subgroup containing p/D processors
* will be returned. The value D is a constant factor that is
* currently fixed to 3.
*
* \param g The underlying graph whose MSF is being computed. It must model
* the DistributedGraph concept.
*
* \param first_vertex Iterator to the first vertex in the graph
* that should be considered. While the local MSF merging algorithm
* typically operates on the entire vertex set, within the hybrid
* distributed MSF algorithms this will refer to the first
* supervertex.
*
* \param last_vertex The past-the-end iterator for the vertex list.
*
* \param edge_list The list of local edges that will be
* considered. For the p/D processes that remain, this list will
* contain edges in the MSF known to the vertex after other
* processes' edge lists have been merged. The edge list must be
* sorted in order of increasing weight.
*
* \param weight Property map containing the weights of each
* edge. The type of this property map must model
* ReadablePropertyMap and must support caching.
*
* \param global_index Mapping from vertex descriptors to a global
* index. The type must model ReadablePropertyMap.
*
* \param edge_mapper A function object that can remap edge descriptors
* in the edge list to any alternative edge descriptor. This
* function object will be the identity function when a pure merging
* of local MSFs is required, but may be a mapping to a supervertex
* edge when the local MSF merging occurs on a supervertex
* graph. This function object saves us the trouble of having to
* build a supervertex graph adaptor.
*
* \param already_local_msf True when the edge list already
* constitutes a local MSF. If false, Kruskal's algorithm will first
* be applied to the local edge list to select MSF edges.
*
* \returns The process subgroup containing the remaining p/D
* processes. If the size of this process group is greater than one,
* the MSF edges contained in the edge list do not constitute an MSF
* for the entire graph.
*/
template<typename ProcessGroup, typename Graph, typename ForwardIterator,
typename EdgeList, typename WeightMap, typename GlobalIndexMap,
typename EdgeMapper>
ProcessGroup
merge_local_minimum_spanning_trees_step(ProcessGroup pg,
const Graph& g,
ForwardIterator first_vertex,
ForwardIterator last_vertex,
EdgeList& edge_list,
WeightMap weight,
GlobalIndexMap global_index,
EdgeMapper edge_mapper,
bool already_local_msf)
{
typedef typename ProcessGroup::process_id_type process_id_type;
typedef typename EdgeList::value_type edge_descriptor;
typedef typename property_traits<WeightMap>::value_type weight_type;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
// The tree factor, often called "D"
process_id_type const tree_factor = 3;
process_id_type num_procs = num_processes(pg);
process_id_type id = process_id(pg);
process_id_type procs_left = (num_procs + tree_factor - 1) / tree_factor;
std::size_t n = std::size_t(last_vertex - first_vertex);
if (!already_local_msf) {
// Compute local minimum spanning forest. We only care about the
// edges in the MSF, because only edges in the local MSF can be in
// the global MSF.
std::vector<std::size_t> ranks(n);
std::vector<vertex_descriptor> parents(n);
detail::sorted_mutating_kruskal
(g, first_vertex, last_vertex,
edge_list, edge_mapper,
make_iterator_property_map(ranks.begin(), global_index),
make_iterator_property_map(parents.begin(), global_index));
}
typedef std::pair<edge_descriptor, weight_type> w_edge;
// Order edges based on their weights.
indirect_cmp<WeightMap, std::less<weight_type> > cmp_edge_weight(weight);
if (id < procs_left) {
// The p/D processes that remain will receive local MSF edges from
// D-1 other processes.
synchronize(pg);
for (process_id_type from_id = procs_left + id; from_id < num_procs;
from_id += procs_left) {
std::size_t num_incoming_edges;
receive(pg, from_id, 0, num_incoming_edges);
if (num_incoming_edges > 0) {
std::vector<w_edge> incoming_edges(num_incoming_edges);
receive(pg, from_id, 1, &incoming_edges[0], num_incoming_edges);
edge_list.reserve(edge_list.size() + num_incoming_edges);
for (std::size_t i = 0; i < num_incoming_edges; ++i) {
cache(weight, incoming_edges[i].first, incoming_edges[i].second);
edge_list.push_back(incoming_edges[i].first);
}
std::inplace_merge(edge_list.begin(),
edge_list.end() - num_incoming_edges,
edge_list.end(),
cmp_edge_weight);
}
}
// Compute the local MSF from union of the edges in the MSFs of
// all children.
std::vector<std::size_t> ranks(n);
std::vector<vertex_descriptor> parents(n);
detail::sorted_mutating_kruskal
(g, first_vertex, last_vertex,
edge_list, edge_mapper,
make_iterator_property_map(ranks.begin(), global_index),
make_iterator_property_map(parents.begin(), global_index));
} else {
// The (D-1)p/D processes that are dropping out of further
// computations merely send their MSF edges to their parent
// process in the process tree.
send(pg, id % procs_left, 0, edge_list.size());
if (edge_list.size() > 0) {
std::vector<w_edge> outgoing_edges;
outgoing_edges.reserve(edge_list.size());
for (std::size_t i = 0; i < edge_list.size(); ++i) {
outgoing_edges.push_back(std::make_pair(edge_list[i],
get(weight, edge_list[i])));
}
send(pg, id % procs_left, 1, &outgoing_edges[0],
outgoing_edges.size());
}
synchronize(pg);
}
// Return a process subgroup containing the p/D parent processes
return process_subgroup(pg,
make_counting_iterator(process_id_type(0)),
make_counting_iterator(procs_left));
}
} // end namespace detail
// ---------------------------------------------------------------------
// Dense Boruvka MSF algorithm
// ---------------------------------------------------------------------
template<typename Graph, typename WeightMap, typename OutputIterator,
typename VertexIndexMap, typename RankMap, typename ParentMap,
typename SupervertexMap>
OutputIterator
dense_boruvka_minimum_spanning_tree(const Graph& g, WeightMap weight_map,
OutputIterator out,
VertexIndexMap index_map,
RankMap rank_map, ParentMap parent_map,
SupervertexMap supervertex_map)
{
using boost::graph::parallel::process_group;
typedef typename graph_traits<Graph>::traversal_category traversal_category;
BOOST_STATIC_ASSERT((is_convertible<traversal_category*,
vertex_list_graph_tag*>::value));
typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
// Don't throw away cached edge weights
weight_map.set_max_ghost_cells(0);
// Initialize the disjoint sets structures
disjoint_sets<RankMap, ParentMap> dset(rank_map, parent_map);
vertex_iterator vi, vi_end;
for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
dset.make_set(*vi);
std::vector<vertex_descriptor> supervertices;
supervertices.assign(vertices(g).first, vertices(g).second);
// Use Kruskal's algorithm to find the minimum spanning forest
// considering only the local edges. The resulting edges are not
// necessarily going to be in the final minimum spanning
// forest. However, any edge not part of the local MSF cannot be a
// part of the global MSF, so we should have eliminated some edges
// from consideration.
std::vector<edge_descriptor> edge_list;
kruskal_minimum_spanning_tree
(make_vertex_and_edge_range(g, vertices(g).first, vertices(g).second,
edges(g).first, edges(g).second),
std::back_inserter(edge_list),
boost::weight_map(weight_map).
vertex_index_map(index_map));
// While the number of supervertices is decreasing, keep executing
// Boruvka steps to identify additional MSF edges. This loop will
// execute log |V| times.
vertices_size_type old_num_supervertices;
do {
old_num_supervertices = supervertices.size();
out = detail::boruvka_merge_step(process_group(g), g,
weight_map, out,
dset, supervertex_map, supervertices,
edge_list);
} while (supervertices.size() < old_num_supervertices);
return out;
}
template<typename Graph, typename WeightMap, typename OutputIterator,
typename VertexIndex>
OutputIterator
dense_boruvka_minimum_spanning_tree(const Graph& g, WeightMap weight_map,
OutputIterator out, VertexIndex i_map)
{
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
std::vector<std::size_t> ranks(num_vertices(g));
std::vector<vertex_descriptor> parents(num_vertices(g));
std::vector<std::size_t> supervertices(num_vertices(g));
return dense_boruvka_minimum_spanning_tree
(g, weight_map, out, i_map,
make_iterator_property_map(ranks.begin(), i_map),
make_iterator_property_map(parents.begin(), i_map),
make_iterator_property_map(supervertices.begin(), i_map));
}
template<typename Graph, typename WeightMap, typename OutputIterator>
OutputIterator
dense_boruvka_minimum_spanning_tree(const Graph& g, WeightMap weight_map,
OutputIterator out)
{
return dense_boruvka_minimum_spanning_tree(g, weight_map, out,
get(vertex_index, g));
}
// ---------------------------------------------------------------------
// Merge local MSFs MSF algorithm
// ---------------------------------------------------------------------
template<typename Graph, typename WeightMap, typename OutputIterator,
typename GlobalIndexMap>
OutputIterator
merge_local_minimum_spanning_trees(const Graph& g, WeightMap weight,
OutputIterator out,
GlobalIndexMap global_index)
{
using boost::graph::parallel::process_group_type;
using boost::graph::parallel::process_group;
typedef typename graph_traits<Graph>::traversal_category traversal_category;
BOOST_STATIC_ASSERT((is_convertible<traversal_category*,
vertex_list_graph_tag*>::value));
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
// Don't throw away cached edge weights
weight.set_max_ghost_cells(0);
// Compute the initial local minimum spanning forests
std::vector<edge_descriptor> edge_list;
kruskal_minimum_spanning_tree
(make_vertex_and_edge_range(g, vertices(g).first, vertices(g).second,
edges(g).first, edges(g).second),
std::back_inserter(edge_list),
boost::weight_map(weight).vertex_index_map(global_index));
// Merge the local MSFs from p processes into p/D processes,
// reducing the number of processes in each step. Continue looping
// until either (a) the current process drops out or (b) only one
// process remains in the group. This loop will execute log_D p
// times.
typename process_group_type<Graph>::type pg = process_group(g);
while (pg && num_processes(pg) > 1) {
pg = detail::merge_local_minimum_spanning_trees_step
(pg, g, vertices(g).first, vertices(g).second,
edge_list, weight, global_index,
detail::identity_function<edge_descriptor>(), true);
}
// Only process 0 has the entire edge list, so emit it to the output
// iterator.
if (pg && process_id(pg) == 0) {
out = std::copy(edge_list.begin(), edge_list.end(), out);
}
synchronize(process_group(g));
return out;
}
template<typename Graph, typename WeightMap, typename OutputIterator>
inline OutputIterator
merge_local_minimum_spanning_trees(const Graph& g, WeightMap weight,
OutputIterator out)
{
return merge_local_minimum_spanning_trees(g, weight, out,
get(vertex_index, g));
}
// ---------------------------------------------------------------------
// Boruvka-then-merge MSF algorithm
// ---------------------------------------------------------------------
template<typename Graph, typename WeightMap, typename OutputIterator,
typename GlobalIndexMap, typename RankMap, typename ParentMap,
typename SupervertexMap>
OutputIterator
boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out,
GlobalIndexMap index, RankMap rank_map,
ParentMap parent_map, SupervertexMap supervertex_map)
{
using std::log;
using boost::graph::parallel::process_group_type;
using boost::graph::parallel::process_group;
typedef typename graph_traits<Graph>::traversal_category traversal_category;
BOOST_STATIC_ASSERT((is_convertible<traversal_category*,
vertex_list_graph_tag*>::value));
typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
// Don't throw away cached edge weights
weight.set_max_ghost_cells(0);
// Compute the initial local minimum spanning forests
std::vector<edge_descriptor> edge_list;
kruskal_minimum_spanning_tree
(make_vertex_and_edge_range(g, vertices(g).first, vertices(g).second,
edges(g).first, edges(g).second),
std::back_inserter(edge_list),
boost::weight_map(weight).
vertex_index_map(index));
// Initialize the disjoint sets structures for Boruvka steps
disjoint_sets<RankMap, ParentMap> dset(rank_map, parent_map);
vertex_iterator vi, vi_end;
for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
dset.make_set(*vi);
// Construct the initial set of supervertices (all vertices)
std::vector<vertex_descriptor> supervertices;
supervertices.assign(vertices(g).first, vertices(g).second);
// Continue performing Boruvka merge steps until the number of
// supervertices reaches |V| / (log_D p)^2.
const std::size_t tree_factor = 3; // TBD: same as above! should be param
double log_d_p = log((double)num_processes(process_group(g)))
/ log((double)tree_factor);
vertices_size_type target_supervertices =
vertices_size_type(num_vertices(g) / (log_d_p * log_d_p));
vertices_size_type old_num_supervertices;
while (supervertices.size() > target_supervertices) {
old_num_supervertices = supervertices.size();
out = detail::boruvka_merge_step(process_group(g), g,
weight, out, dset,
supervertex_map, supervertices,
edge_list);
if (supervertices.size() == old_num_supervertices)
return out;
}
// Renumber the supervertices
for (std::size_t i = 0; i < supervertices.size(); ++i)
put(supervertex_map, supervertices[i], i);
// Merge local MSFs on the supervertices. (D-1)p/D processors drop
// out each iteration, so this loop executes log_D p times.
typename process_group_type<Graph>::type pg = process_group(g);
bool have_msf = false;
while (pg && num_processes(pg) > 1) {
pg = detail::merge_local_minimum_spanning_trees_step
(pg, g, supervertices.begin(), supervertices.end(),
edge_list, weight, supervertex_map,
detail::make_supervertex_edge_descriptor(g, dset),
have_msf);
have_msf = true;
}
// Only process 0 has the complete list of _supervertex_ MST edges,
// so emit those to the output iterator. This is not the complete
// list of edges in the MSF, however: the Boruvka steps in the
// beginning of the algorithm emitted any edges used to merge
// supervertices.
if (pg && process_id(pg) == 0)
out = std::copy(edge_list.begin(), edge_list.end(), out);
synchronize(process_group(g));
return out;
}
template<typename Graph, typename WeightMap, typename OutputIterator,
typename GlobalIndexMap>
inline OutputIterator
boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out,
GlobalIndexMap index)
{
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
std::vector<vertices_size_type> ranks(num_vertices(g));
std::vector<vertex_descriptor> parents(num_vertices(g));
std::vector<vertices_size_type> supervertex_indices(num_vertices(g));
return boruvka_then_merge
(g, weight, out, index,
make_iterator_property_map(ranks.begin(), index),
make_iterator_property_map(parents.begin(), index),
make_iterator_property_map(supervertex_indices.begin(), index));
}
template<typename Graph, typename WeightMap, typename OutputIterator>
inline OutputIterator
boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out)
{ return boruvka_then_merge(g, weight, out, get(vertex_index, g)); }
// ---------------------------------------------------------------------
// Boruvka-mixed-merge MSF algorithm
// ---------------------------------------------------------------------
template<typename Graph, typename WeightMap, typename OutputIterator,
typename GlobalIndexMap, typename RankMap, typename ParentMap,
typename SupervertexMap>
OutputIterator
boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out,
GlobalIndexMap index, RankMap rank_map,
ParentMap parent_map, SupervertexMap supervertex_map)
{
using boost::graph::parallel::process_group_type;
using boost::graph::parallel::process_group;
typedef typename graph_traits<Graph>::traversal_category traversal_category;
BOOST_STATIC_ASSERT((is_convertible<traversal_category*,
vertex_list_graph_tag*>::value));
typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
// Don't throw away cached edge weights
weight.set_max_ghost_cells(0);
// Initialize the disjoint sets structures for Boruvka steps
disjoint_sets<RankMap, ParentMap> dset(rank_map, parent_map);
vertex_iterator vi, vi_end;
for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
dset.make_set(*vi);
// Construct the initial set of supervertices (all vertices)
std::vector<vertex_descriptor> supervertices;
supervertices.assign(vertices(g).first, vertices(g).second);
// Compute the initial local minimum spanning forests
std::vector<edge_descriptor> edge_list;
kruskal_minimum_spanning_tree
(make_vertex_and_edge_range(g, vertices(g).first, vertices(g).second,
edges(g).first, edges(g).second),
std::back_inserter(edge_list),
boost::weight_map(weight).
vertex_index_map(index));
if (num_processes(process_group(g)) == 1) {
return std::copy(edge_list.begin(), edge_list.end(), out);
}
// Like the merging local MSFs algorithm and the Boruvka-then-merge
// algorithm, each iteration of this loop reduces the number of
// processes by a constant factor D, and therefore we require log_D
// p iterations. Note also that the number of edges in the edge list
// decreases geometrically, giving us an efficient distributed MSF
// algorithm.
typename process_group_type<Graph>::type pg = process_group(g);
vertices_size_type old_num_supervertices;
while (pg && num_processes(pg) > 1) {
// A single Boruvka step. If this doesn't change anything, we're done
old_num_supervertices = supervertices.size();
out = detail::boruvka_merge_step(pg, g, weight, out, dset,
supervertex_map, supervertices,
edge_list);
if (old_num_supervertices == supervertices.size()) {
edge_list.clear();
break;
}
// Renumber the supervertices
for (std::size_t i = 0; i < supervertices.size(); ++i)
put(supervertex_map, supervertices[i], i);
// A single merging of local MSTs, which reduces the number of
// processes we're using by a constant factor D.
pg = detail::merge_local_minimum_spanning_trees_step
(pg, g, supervertices.begin(), supervertices.end(),
edge_list, weight, supervertex_map,
detail::make_supervertex_edge_descriptor(g, dset),
true);
}
// Only process 0 has the complete edge list, so emit it for the
// user. Note that list edge list only contains the MSF edges in the
// final supervertex graph: all of the other edges were used to
// merge supervertices and have been emitted by the Boruvka steps,
// although only process 0 has received the complete set.
if (pg && process_id(pg) == 0)
out = std::copy(edge_list.begin(), edge_list.end(), out);
synchronize(process_group(g));
return out;
}
template<typename Graph, typename WeightMap, typename OutputIterator,
typename GlobalIndexMap>
inline OutputIterator
boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out,
GlobalIndexMap index)
{
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
std::vector<vertices_size_type> ranks(num_vertices(g));
std::vector<vertex_descriptor> parents(num_vertices(g));
std::vector<vertices_size_type> supervertex_indices(num_vertices(g));
return boruvka_mixed_merge
(g, weight, out, index,
make_iterator_property_map(ranks.begin(), index),
make_iterator_property_map(parents.begin(), index),
make_iterator_property_map(supervertex_indices.begin(), index));
}
template<typename Graph, typename WeightMap, typename OutputIterator>
inline OutputIterator
boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out)
{ return boruvka_mixed_merge(g, weight, out, get(vertex_index, g)); }
} // end namespace distributed
using distributed::dense_boruvka_minimum_spanning_tree;
using distributed::merge_local_minimum_spanning_trees;
using distributed::boruvka_then_merge;
using distributed::boruvka_mixed_merge;
} } // end namespace boost::graph
#endif // BOOST_DEHNE_GOTZ_MIN_SPANNING_TREE_HPP
Reference in New Issue View Git Blame Copy Permalink