123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408 |
- .. 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| Dijkstra's Single-Source Shortest Paths
- ==============================================
- ::
- // named parameter version
- template <typename Graph, typename P, typename T, typename R>
- void
- dijkstra_shortest_paths(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor s,
- const bgl_named_params<P, T, R>& params);
- // non-named parameter version
- template <typename Graph, typename DijkstraVisitor,
- typename PredecessorMap, typename DistanceMap,
- typename WeightMap, typename VertexIndexMap, typename CompareFunction, typename CombineFunction,
- typename DistInf, typename DistZero>
- void dijkstra_shortest_paths
- (const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
- VertexIndexMap index_map,
- CompareFunction compare, CombineFunction combine, DistInf inf, DistZero zero,
- DijkstraVisitor vis);
- The ``dijkstra_shortest_paths()`` function solves the single-source
- shortest paths problem on a weighted, undirected or directed
- distributed graph. There are two implementations of distributed
- Dijkstra's algorithm, which offer different performance
- tradeoffs. Both are accessible via the ``dijkstra_shortest_paths()``
- function (for compatibility with sequential BGL programs). The
- distributed Dijkstra algorithms are very similar to their sequential
- counterparts. Only the differences are highlighted here; please refer
- to the `sequential Dijkstra implementation`_ for additional
- details. The best-performing implementation for most cases is the
- `Delta-Stepping algorithm`_; however, one can also employ the more
- conservative `Crauser et al.'s algorithm`_ or the simlistic `Eager
- Dijkstra's algorithm`_.
- .. contents::
- Where Defined
- -------------
- <``boost/graph/dijkstra_shortest_paths.hpp``>
- Parameters
- ----------
- All parameters of the `sequential Dijkstra implementation`_ are
- supported and have essentially the same meaning. The distributed
- Dijkstra implementations introduce a new parameter that allows one to
- select `Eager Dijkstra's algorithm`_ and control the amount of work it
- performs. Only differences and new parameters are documented here.
- IN: ``Graph& g``
- The graph type must be a model of `Distributed Graph`_.
- IN: ``vertex_descriptor s``
- The start vertex must be the same in every process.
- OUT: ``predecessor_map(PredecessorMap p_map)``
- The predecessor map must be a `Distributed Property Map`_ or
- ``dummy_property_map``, although only the local portions of the map
- will be written.
- **Default:** ``dummy_property_map``
- UTIL/OUT: ``distance_map(DistanceMap d_map)``
- The distance map must be either a `Distributed Property Map`_ or
- ``dummy_property_map``. It will be given the ``vertex_distance``
- role.
- IN: ``visitor(DijkstraVisitor vis)``
- The visitor must be a distributed Dijkstra visitor. The suble differences
- between sequential and distributed Dijkstra visitors are discussed in the
- section `Visitor Event Points`_.
- UTIL/OUT: ``color_map(ColorMap color)``
- The color map must be a `Distributed Property Map`_ with the same
- process group as the graph ``g`` whose colors must monotonically
- darken (white -> gray -> black). The default value is a distributed
- ``iterator_property_map`` created from a ``std::vector`` of
- ``default_color_type``.
- IN: ``lookahead(distance_type look)``
- When this parameter is supplied, the implementation will use the
- `Eager Dijkstra's algorithm`_ with the given lookahead value.
- Lookahead permits distributed Dijkstra's algorithm to speculatively
- process vertices whose shortest distance from the source may not
- have been found yet. When the distance found is the shortest
- distance, parallelism is improved and the algorithm may terminate
- more quickly. However, if the distance is not the shortest distance,
- the vertex will need to be reprocessed later, resulting in more
- work.
- The type ``distance_type`` is the value type of the ``DistanceMap``
- property map. It is a nonnegative value specifying how far ahead
- Dijkstra's algorithm may process values.
- **Default:** no value (lookahead is not employed; uses `Crauser et
- al.'s algorithm`_).
- Visitor Event Points
- --------------------
- The `Dijkstra Visitor`_ concept defines 7 event points that will be
- triggered by the `sequential Dijkstra implementation`_. The distributed
- Dijkstra retains these event points, but the sequence of events
- triggered and the process in which each event occurs will change
- depending on the distribution of the graph, lookahead, and edge
- weights.
- ``initialize_vertex(s, g)``
- This will be invoked by every process for each local vertex.
- ``discover_vertex(u, g)``
- This will be invoked each type a process discovers a new vertex
- ``u``. Due to incomplete information in distributed property maps,
- this event may be triggered many times for the same vertex ``u``.
- ``examine_vertex(u, g)``
- This will be invoked by the process owning the vertex ``u``. This
- event may be invoked multiple times for the same vertex when the
- graph contains negative edges or lookahead is employed.
- ``examine_edge(e, g)``
- This will be invoked by the process owning the source vertex of
- ``e``. As with ``examine_vertex``, this event may be invoked
- multiple times for the same edge.
- ``edge_relaxed(e, g)``
- Similar to ``examine_edge``, this will be invoked by the process
- owning the source vertex and may be invoked multiple times (even
- without lookahead or negative edges).
- ``edge_not_relaxed(e, g)``
- Similar to ``edge_relaxed``. Some ``edge_not_relaxed`` events that
- would be triggered by sequential Dijkstra's will become
- ``edge_relaxed`` events in distributed Dijkstra's algorithm.
- ``finish_vertex(e, g)``
- See documentation for ``examine_vertex``. Note that a "finished"
- vertex is not necessarily finished if lookahead is permitted or
- negative edges exist in the graph.
- Crauser et al.'s algorithm
- --------------------------
- ::
- namespace graph {
- template<typename DistributedGraph, typename DijkstraVisitor,
- typename PredecessorMap, typename DistanceMap, typename WeightMap,
- typename IndexMap, typename ColorMap, typename Compare,
- typename Combine, typename DistInf, typename DistZero>
- void
- crauser_et_al_shortest_paths
- (const DistributedGraph& g,
- typename graph_traits<DistributedGraph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
- IndexMap index_map, ColorMap color_map,
- Compare compare, Combine combine, DistInf inf, DistZero zero,
- DijkstraVisitor vis);
- template<typename DistributedGraph, typename DijkstraVisitor,
- typename PredecessorMap, typename DistanceMap, typename WeightMap>
- void
- crauser_et_al_shortest_paths
- (const DistributedGraph& g,
- typename graph_traits<DistributedGraph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance, WeightMap weight);
- template<typename DistributedGraph, typename DijkstraVisitor,
- typename PredecessorMap, typename DistanceMap>
- void
- crauser_et_al_shortest_paths
- (const DistributedGraph& g,
- typename graph_traits<DistributedGraph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance);
- }
- The formulation of Dijkstra's algorithm by Crauser, Mehlhorn, Meyer,
- and Sanders [CMMS98a]_ improves the scalability of parallel Dijkstra's
- algorithm by increasing the number of vertices that can be processed
- in a given superstep. This algorithm adapts well to various graph
- types, and is a simple algorithm to use, requiring no additional user
- input to achieve reasonable performance. The disadvantage of this
- algorithm is that the implementation is required to manage three
- priority queues, which creates a large amount of work at each node.
- This algorithm is used by default in distributed
- ``dijkstra_shortest_paths()``.
- Where Defined
- ~~~~~~~~~~~~~
- <``boost/graph/distributed/crauser_et_al_shortest_paths.hpp``>
- Complexity
- ~~~~~~~~~~
- This algorithm performs *O(V log V)* work in *d + 1* BSP supersteps,
- where *d* is at most *O(V)* but is generally much smaller. On directed
- Erdos-Renyi graphs with edge weights in [0, 1), the expected number of
- supersteps *d* is *O(n^(1/3))* with high probability.
- Performance
- ~~~~~~~~~~~
- The following charts illustrate the performance of the Parallel BGL implementation of Crauser et al.'s
- algorithm on graphs with edge weights uniformly selected from the
- range *[0, 1)*.
- .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=4
- :align: left
- .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=4&speedup=1
- .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=4
- :align: left
- .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=4&speedup=1
- Eager Dijkstra's algorithm
- --------------------------
- ::
- namespace graph {
- template<typename DistributedGraph, typename DijkstraVisitor,
- typename PredecessorMap, typename DistanceMap, typename WeightMap,
- typename IndexMap, typename ColorMap, typename Compare,
- typename Combine, typename DistInf, typename DistZero>
- void
- eager_dijkstra_shortest_paths
- (const DistributedGraph& g,
- typename graph_traits<DistributedGraph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance,
- typename property_traits<DistanceMap>::value_type lookahead,
- WeightMap weight, IndexMap index_map, ColorMap color_map,
- Compare compare, Combine combine, DistInf inf, DistZero zero,
- DijkstraVisitor vis);
- template<typename DistributedGraph, typename DijkstraVisitor,
- typename PredecessorMap, typename DistanceMap, typename WeightMap>
- void
- eager_dijkstra_shortest_paths
- (const DistributedGraph& g,
- typename graph_traits<DistributedGraph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance,
- typename property_traits<DistanceMap>::value_type lookahead,
- WeightMap weight);
- template<typename DistributedGraph, typename DijkstraVisitor,
- typename PredecessorMap, typename DistanceMap>
- void
- eager_dijkstra_shortest_paths
- (const DistributedGraph& g,
- typename graph_traits<DistributedGraph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance,
- typename property_traits<DistanceMap>::value_type lookahead);
- }
- In each superstep, parallel Dijkstra's algorithm typically only
- processes nodes whose distances equivalent to the global minimum
- distance, because these distances are guaranteed to be correct. This
- variation on the algorithm allows the algorithm to process all
- vertices whose distances are within some constant value of the
- minimum distance. The value is called the "lookahead" value and is
- provided by the user as the fifth parameter to the function. Small
- values of the lookahead parameter will likely result in limited
- parallelization opportunities, whereas large values will expose more
- parallelism but may introduce (non-infinite) looping and result in
- extra work. The optimal value for the lookahead parameter depends on
- the input graph; see [CMMS98b]_ and [MS98]_.
- This algorithm will be used by ``dijkstra_shortest_paths()`` when it
- is provided with a lookahead value.
- Where Defined
- ~~~~~~~~~~~~~
- <``boost/graph/distributed/eager_dijkstra_shortest_paths.hpp``>
- Complexity
- ~~~~~~~~~~
- This algorithm performs *O(V log V)* work in *d
- + 1* BSP supersteps, where *d* is at most *O(V)* but may be smaller
- depending on the lookahead value. the algorithm may perform more work
- when a large lookahead is provided, because vertices will be
- reprocessed.
- Performance
- ~~~~~~~~~~~
- The performance of the eager Dijkstra's algorithm varies greatly
- depending on the lookahead value. The following charts illustrate the
- performance of the Parallel BGL on graphs with edge weights uniformly
- selected from the range *[0, 1)* and a constant lookahead of 0.1.
- .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=5
- :align: left
- .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=5&speedup=1
- .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=5
- :align: left
- .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=5&speedup=1
- Delta-Stepping algorithm
- --------------------------
- ::
- namespace boost { namespace graph { namespace distributed {
- template <typename Graph, typename PredecessorMap,
- typename DistanceMap, typename WeightMap>
- void delta_stepping_shortest_paths
- (const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
- typename property_traits<WeightMap>::value_type delta)
- template <typename Graph, typename PredecessorMap,
- typename DistanceMap, typename WeightMap>
- void delta_stepping_shortest_paths
- (const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance, WeightMap weight)
- }
- } } }
- The delta-stepping algorithm [MS98]_ is another variant of the parallel
- Dijkstra algorithm. Like the eager Dijkstra algorithm, it employs a
- lookahead (``delta``) value that allows processors to process vertices
- before we are guaranteed to find their minimum distances, permitting
- more parallelism than a conservative strategy. Delta-stepping also
- introduces a multi-level bucket data structure that provides more
- relaxed ordering constraints than the priority queues employed by the
- other Dijkstra variants, reducing the complexity of insertions,
- relaxations, and removals from the central data structure. The
- delta-stepping algorithm is the best-performing of the Dijkstra
- variants.
- The lookahead value ``delta`` determines how large each of the
- "buckets" within the delta-stepping queue will be, where the ith
- bucket contains edges within tentative distances between ``delta``*i
- and ``delta``*(i+1). ``delta`` must be a positive value. When omitted,
- ``delta`` will be set to the maximum edge weight divided by the
- maximum degree.
- Where Defined
- ~~~~~~~~~~~~~
- <``boost/graph/distributed/delta_stepping_shortest_paths.hpp``>
- Example
- -------
- See the separate `Dijkstra example`_.
- Bibliography
- ------------
- .. [CMMS98a] Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter Sanders. A
- Parallelization of Dijkstra's Shortest Path Algorithm. In
- *Mathematical Foundations of Computer Science (MFCS)*, volume 1450 of
- Lecture Notes in Computer Science, pages 722--731, 1998. Springer.
- .. [CMMS98b] Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter
- Sanders. Parallelizing Dijkstra's shortest path algorithm. Technical
- report, MPI-Informatik, 1998.
- .. [MS98] Ulrich Meyer and Peter Sanders. Delta-stepping: A parallel
- shortest path algorithm. In *6th ESA*, LNCS. Springer, 1998.
- -----------------------------------------------------------------------------
- Copyright (C) 2004, 2005, 2006, 2007, 2008 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
- .. _sequential Dijkstra implementation: http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
- .. _distributed breadth-first search: breadth_first_search.html
- .. _Distributed Graph: DistributedGraph.html
- .. _Distributed Property Map: distributed_property_map.html
- .. _Dijkstra Visitor: http://www.boost.org/libs/graph/doc/DijkstraVisitor.html
- .. _Dijkstra example: dijkstra_example.html
|