123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423 |
- .. 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<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,
- RankMap rank_map, ParentMap parent_map,
- SupervertexMap supervertex_map);
- template<typename Graph, typename WeightMap, typename OutputIterator,
- typename VertexIndex>
- OutputIterator
- dense_boruvka_minimum_spanning_tree(const Graph& g, WeightMap weight_map,
- OutputIterator out, VertexIndex index);
- template<typename Graph, typename WeightMap, typename OutputIterator>
- 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<typename Graph, typename WeightMap, typename OutputIterator,
- typename VertexIndexMap>
- OutputIterator
- merge_local_minimum_spanning_trees(const Graph& g, WeightMap weight,
- OutputIterator out,
- VertexIndexMap index);
- template<typename Graph, typename WeightMap, typename OutputIterator>
- 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<typename Graph, typename WeightMap, typename OutputIterator,
- typename VertexIndexMap, typename RankMap, typename ParentMap,
- typename SupervertexMap>
- OutputIterator
- boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out,
- VertexIndexMap index, RankMap rank_map,
- ParentMap parent_map, SupervertexMap
- supervertex_map);
- template<typename Graph, typename WeightMap, typename OutputIterator,
- typename VertexIndexMap>
- inline OutputIterator
- boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out,
- VertexIndexMap index);
- template<typename Graph, typename WeightMap, typename OutputIterator>
- 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<typename Graph, typename WeightMap, typename OutputIterator,
- typename VertexIndexMap, typename RankMap, typename ParentMap,
- typename SupervertexMap>
- OutputIterator
- boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out,
- VertexIndexMap index, RankMap rank_map,
- ParentMap parent_map, SupervertexMap
- supervertex_map);
- template<typename Graph, typename WeightMap, typename OutputIterator,
- typename VertexIndexMap>
- inline OutputIterator
- boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out,
- VertexIndexMap index);
- template<typename Graph, typename WeightMap, typename OutputIterator>
- 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.
|