.. Copyright (C) 2004-2008 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) ============================ |Logo| Minimum Spanning Tree ============================ The Parallel BGL contains four `minimum spanning tree`_ (MST) algorithms [DG98]_ for use on undirected, weighted, distributed graphs. The graphs need not be connected: each algorithm will compute a minimum spanning forest (MSF) when provided with a disconnected graph. The interface to each of the four algorithms is similar to the implementation of 'Kruskal's algorithm'_ in the sequential BGL. Each accepts, at a minimum, a graph, a weight map, and an output iterator. The edges of the MST (or MSF) will be output via the output iterator on process 0: other processes may receive edges on their output iterators, but the set may not be complete, depending on the algorithm. The algorithm parameters are documented together, because they do not vary greatly. See the section `Selecting an MST algorithm`_ for advice on algorithm selection. The graph itself must model the `Vertex List Graph`_ concept and the Distributed Edge List Graph concept. Since the most common distributed graph structure, the `distributed adjacency list`_, only models the Distributed Vertex List Graph concept, it may only be used with these algorithms when wrapped in a suitable adaptor, such as the `vertex_list_adaptor`_. .. contents:: Where Defined ------------- <``boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp``> Parameters ---------- IN: ``Graph& g`` The graph type must be a model of `Vertex List Graph`_ and `Distributed Edge List Graph`_. IN/OUT: ``WeightMap weight`` The weight map must be a `Distributed Property Map`_ and a `Readable Property Map`_ whose key type is the edge descriptor of the graph and whose value type is numerical. IN/OUT: ``OutputIterator out`` The output iterator through which the edges of the MSF will be written. Must be capable of accepting edge descriptors for output. IN: ``VertexIndexMap index`` A mapping from vertex descriptors to indices in the range *[0, num_vertices(g))*. This must be a `Readable Property Map`_ whose key type is a vertex descriptor and whose value type is an integral type, typically the ``vertices_size_type`` of the graph. **Default:** ``get(vertex_index, g)`` IN/UTIL: ``RankMap rank_map`` Stores the rank of each vertex, which is used for maintaining union-find data structures. This must be a `Read/Write Property Map`_ whose key type is a vertex descriptor and whose value type is an integral type. **Default:** An ``iterator_property_map`` built from an STL vector of the ``vertices_size_type`` of the graph and the vertex index map. IN/UTIL: ``ParentMap parent_map`` Stores the parent (representative) of each vertex, which is used for maintaining union-find data structures. This must be a `Read/Write Property Map`_ whose key type is a vertex descriptor and whose value type is also a vertex descriptor. **Default:** An ``iterator_property_map`` built from an STL vector of the ``vertex_descriptor`` of the graph and the vertex index map. IN/UTIL: ``SupervertexMap supervertex_map`` Stores the supervertex index of each vertex, which is used for maintaining the supervertex list data structures. This must be a `Read/Write Property Map`_ whose key type is a vertex descriptor and whose value type is an integral type. **Default:** An ``iterator_property_map`` built from an STL vector of the ``vertices_size_type`` of the graph and the vertex index map. ``dense_boruvka_minimum_spanning_tree`` --------------------------------------- :: namespace graph { template OutputIterator dense_boruvka_minimum_spanning_tree(const Graph& g, WeightMap weight_map, OutputIterator out, VertexIndexMap index, RankMap rank_map, ParentMap parent_map, SupervertexMap supervertex_map); template OutputIterator dense_boruvka_minimum_spanning_tree(const Graph& g, WeightMap weight_map, OutputIterator out, VertexIndex index); template OutputIterator dense_boruvka_minimum_spanning_tree(const Graph& g, WeightMap weight_map, OutputIterator out); } Description ~~~~~~~~~~~ The dense Boruvka distributed minimum spanning tree algorithm is a direct parallelization of the sequential MST algorithm by Boruvka. The algorithm first creates a *supervertex* out of each vertex. Then, in each iteration, it finds the smallest-weight edge incident to each vertex, collapses supervertices along these edges, and removals all self loops. The only difference between the sequential and parallel algorithms is that the parallel algorithm performs an all-reduce operation so that all processes have the global minimum set of edges. Unlike the other three algorithms, this algorithm emits the complete list of edges in the minimum spanning forest via the output iterator on all processes. It may therefore be more useful than the others when parallelizing sequential BGL programs. Complexity ~~~~~~~~~~ The distributed algorithm requires *O(log n)* BSP supersteps, each of which requires *O(m/p + n)* time and *O(n)* communication per process. Performance ~~~~~~~~~~~ The following charts illustrate the performance of this algorithm on various random graphs. We see that the algorithm scales well up to 64 or 128 processors, depending on the type of graph, for dense graphs. However, for sparse graphs performance tapers off as the number of processors surpases *m/n*, i.e., the average degree (which is 30 for this graph). This behavior is expected from the algorithm. .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=5 :align: left .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=5&speedup=1 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=5 :align: left .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=5&speedup=1 ``merge_local_minimum_spanning_trees`` -------------------------------------- :: namespace graph { template OutputIterator merge_local_minimum_spanning_trees(const Graph& g, WeightMap weight, OutputIterator out, VertexIndexMap index); template inline OutputIterator merge_local_minimum_spanning_trees(const Graph& g, WeightMap weight, OutputIterator out); } Description ~~~~~~~~~~~ The merging local MSTs algorithm operates by computing minimum spanning forests from the edges stored on each process. Then the processes merge their edge lists along a tree. The child nodes cease participating in the computation, but the parent nodes recompute MSFs from the newly acquired edges. In the final round, the root of the tree computes the global MSFs, having received candidate edges from every other process via the tree. Complexity ~~~~~~~~~~ This algorithm requires *O(log_D p)* BSP supersteps (where *D* is the number of children in the tree, and is currently fixed at 3). Each superstep requires *O((m/p) log (m/p) + n)* time and *O(m/p)* communication per process. Performance ~~~~~~~~~~~ The following charts illustrate the performance of this algorithm on various random graphs. The algorithm only scales well for very dense graphs, where most of the work is performed in the initial stage and there is very little work in the later stages. .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=6 :align: left .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=6&speedup=1 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=6 :align: left .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=6&speedup=1 ``boruvka_then_merge`` ---------------------- :: namespace graph { template OutputIterator boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out, VertexIndexMap index, RankMap rank_map, ParentMap parent_map, SupervertexMap supervertex_map); template inline OutputIterator boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out, VertexIndexMap index); template inline OutputIterator boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out); } Description ~~~~~~~~~~~ This algorithm applies both Boruvka steps and local MSF merging steps together to achieve better asymptotic performance than either algorithm alone. It first executes Boruvka steps until only *n/(log_d p)^2* supervertices remain, then completes the MSF computation by performing local MSF merging on the remaining edges and supervertices. Complexity ~~~~~~~~~~ This algorithm requires *log_D p* + *log log_D p* BSP supersteps. The time required by each superstep depends on the type of superstep being performed; see the distributed Boruvka or merging local MSFS algorithms for details. Performance ~~~~~~~~~~~ The following charts illustrate the performance of this algorithm on various random graphs. We see that the algorithm scales well up to 64 or 128 processors, depending on the type of graph, for dense graphs. However, for sparse graphs performance tapers off as the number of processors surpases *m/n*, i.e., the average degree (which is 30 for this graph). This behavior is expected from the algorithm. .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=7 :align: left .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=7&speedup=1 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=7 :align: left .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=7&speedup=1 ``boruvka_mixed_merge`` ----------------------- :: namespace { template OutputIterator boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out, VertexIndexMap index, RankMap rank_map, ParentMap parent_map, SupervertexMap supervertex_map); template inline OutputIterator boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out, VertexIndexMap index); template inline OutputIterator boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out); } Description ~~~~~~~~~~~ This algorithm applies both Boruvka steps and local MSF merging steps together to achieve better asymptotic performance than either method alone. In each iteration, the algorithm first performs a Boruvka step and then merges the local MSFs computed based on the supervertex graph. Complexity ~~~~~~~~~~ This algorithm requires *log_D p* BSP supersteps. The time required by each superstep depends on the type of superstep being performed; see the distributed Boruvka or merging local MSFS algorithms for details. However, the algorithm is communication-optional (requiring *O(n)* communication overall) when the graph is sufficiently dense, i.e., *m/n >= p*. Performance ~~~~~~~~~~~ The following charts illustrate the performance of this algorithm on various random graphs. We see that the algorithm scales well up to 64 or 128 processors, depending on the type of graph, for dense graphs. However, for sparse graphs performance tapers off as the number of processors surpases *m/n*, i.e., the average degree (which is 30 for this graph). This behavior is expected from the algorithm. .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=8 :align: left .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=8&speedup=1 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=8 :align: left .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=8&speedup=1 Selecting an MST algorithm -------------------------- Dehne and Gotz reported [DG98]_ mixed results when evaluating these four algorithms. No particular algorithm was clearly better than the others in all cases. However, the asymptotically best algorithm (``boruvka_mixed_merge``) seemed to perform more poorly in their tests than the other merging-based algorithms. The following performance charts illustrate the performance of these four minimum spanning tree implementations. Overall, ``dense_boruvka_minimum_spanning_tree`` gives the most consistent performance and scalability for the graphs we tested. Additionally, it may be more suitable for sequential programs that are being parallelized, because it emits complete MSF edge lists via the output iterators in every process. Performance on Sparse Graphs ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER&dataset=TimeSparse&columns=5,6,7,8 :align: left .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER&dataset=TimeSparse&columns=5,6,7,8&speedup=1 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=SF&dataset=TimeSparse&columns=5,6,7,8 :align: left .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=SF&dataset=TimeSparse&columns=5,6,7,8&speedup=1 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=SW&dataset=TimeSparse&columns=5,6,7,8 :align: left .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=SW&dataset=TimeSparse&columns=5,6,7,8&speedup=1 Performance on Dense Graphs ~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER&dataset=TimeDense&columns=5,6,7,8 :align: left .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER&dataset=TimeDense&columns=5,6,7,8&speedup=1 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=SF&dataset=TimeDense&columns=5,6,7,8 :align: left .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=SF&dataset=TimeDense&columns=5,6,7,8&speedup=1 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=SW&dataset=TimeDense&columns=5,6,7,8 :align: left .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=SW&dataset=TimeDense&columns=5,6,7,8&speedup=1 ----------------------------------------------------------------------------- Copyright (C) 2004 The Trustees of Indiana University. Authors: Douglas Gregor and Andrew Lumsdaine .. |Logo| image:: pbgl-logo.png :align: middle :alt: Parallel BGL :target: http://www.osl.iu.edu/research/pbgl .. _minimum spanning tree: http://www.boost.org/libs/graph/doc/graph_theory_review.html#sec:minimum-spanning-tree .. _Kruskal's algorithm: http://www.boost.org/libs/graph/doc/kruskal_min_spanning_tree.html .. _Vertex list graph: http://www.boost.org/libs/graph/doc/VertexListGraph.html .. _distributed adjacency list: distributed_adjacency_list.html .. _vertex_list_adaptor: vertex_list_adaptor.html .. _Distributed Edge List Graph: DistributedEdgeListGraph.html .. _Distributed property map: distributed_property_map.html .. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html .. _Read/Write Property Map: http://www.boost.org/libs/property_map/ReadWritePropertyMap.html .. [DG98] Frank Dehne and Silvia Gotz. *Practical Parallel Algorithms for Minimum Spanning Trees*. In Symposium on Reliable Distributed Systems, pages 366--371, 1998.