165 lines
6.8 KiB
ReStructuredText
165 lines
6.8 KiB
ReStructuredText
.. 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)
|
|
|
|
=======================
|
|
Parallel Shortest Paths
|
|
=======================
|
|
To illustrate the use of the Parallel Boost Graph Library, we
|
|
illustrate the use of both the sequential and parallel BGL to find
|
|
the shortest paths from vertex A to every other vertex in the
|
|
following simple graph:
|
|
|
|
.. image:: ../dijkstra_seq_graph.png
|
|
|
|
With the sequential BGL_, the program to calculate shortest paths has
|
|
three stages. Readers familiar with the BGL may wish to skip ahead to
|
|
the section `Distributing the graph`_.
|
|
|
|
|
|
- `Define the graph type`_
|
|
- `Construct the graph`_
|
|
- `Invoke Dijkstra's algorithm`_
|
|
|
|
Define the graph type
|
|
~~~~~~~~~~~~~~~~~~~~~
|
|
|
|
For this problem we use an adjacency list representation of the graph,
|
|
using the BGL ``adjacency_list``_ class template. It will be a directed
|
|
graph (``directedS`` parameter ) whose vertices are stored in an
|
|
``std::vector`` (``vecS`` parameter) where the outgoing edges of each
|
|
vertex are stored in an ``std::list`` (``listS`` parameter). To each
|
|
of the edges we attach an integral weight.
|
|
|
|
::
|
|
|
|
typedef adjacency_list<listS, vecS, directedS,
|
|
no_property, // Vertex properties
|
|
property<edge_weight_t, int> // Edge properties
|
|
> graph_t;
|
|
typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
|
|
typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
|
|
|
|
Construct the graph
|
|
~~~~~~~~~~~~~~~~~~~
|
|
To build the graph, we declare an enumeration containing the node
|
|
names (for our own use) and create two arrays: the first,
|
|
``edge_array``, contains the source and target of each edge, whereas
|
|
the second, ``weights``, contains the integral weight of each
|
|
edge. We pass the contents of the arrays via pointers (used here as
|
|
iterators) to the graph constructor to build our graph:
|
|
|
|
::
|
|
|
|
typedef std::pair<int, int> Edge;
|
|
const int num_nodes = 5;
|
|
enum nodes { A, B, C, D, E };
|
|
char name[] = "ABCDE";
|
|
Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
|
|
Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B)
|
|
};
|
|
int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
|
|
int num_arcs = sizeof(edge_array) / sizeof(Edge);
|
|
|
|
graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
|
|
|
|
|
|
Invoke Dijkstra's algorithm
|
|
~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
|
To invoke Dijkstra's algorithm, we need to first decide how we want
|
|
to receive the results of the algorithm, namely the distance to each
|
|
vertex and the predecessor of each vertex (allowing reconstruction of
|
|
the shortest paths themselves). In our case, we will create two
|
|
vectors, ``p`` for predecessors and ``d`` for distances.
|
|
|
|
Next, we determine our starting vertex ``s`` using the ``vertex``
|
|
operation on the ``adjacency_list``_ and call
|
|
``dijkstra_shortest_paths``_ with the graph ``g``, starting vertex
|
|
``s``, and two ``property maps``_ that instruct the algorithm to
|
|
store predecessors in the ``p`` vector and distances in the ``d``
|
|
vector. The algorithm automatically uses the edge weights stored
|
|
within the graph, although this capability can be overridden.
|
|
|
|
::
|
|
|
|
// Keeps track of the predecessor of each vertex
|
|
std::vector<vertex_descriptor> p(num_vertices(g));
|
|
// Keeps track of the distance to each vertex
|
|
std::vector<int> d(num_vertices(g));
|
|
|
|
vertex_descriptor s = vertex(A, g);
|
|
dijkstra_shortest_paths
|
|
(g, s,
|
|
predecessor_map(
|
|
make_iterator_property_map(p.begin(), get(vertex_index, g))).
|
|
distance_map(
|
|
make_iterator_property_map(d.begin(), get(vertex_index, g)))
|
|
);
|
|
|
|
Distributing the graph
|
|
~~~~~~~~~~~~~~~~~~~~~~
|
|
The prior computation is entirely sequential, with the graph stored
|
|
within a single address space. To distribute the graph across several
|
|
processors without a shared address space, we need to represent the
|
|
processors and communication among them and alter the graph type.
|
|
|
|
Processors and their interactions are abstracted via a *process
|
|
group*. In our case, we will use MPI_ for communication with
|
|
inter-processor messages sent immediately:
|
|
|
|
::
|
|
|
|
typedef mpi::process_group<mpi::immediateS> process_group_type;
|
|
|
|
Next, we instruct the ``adjacency_list`` template
|
|
to distribute the vertices of the graph across our process group,
|
|
storing the local vertices in an ``std::vector``::
|
|
|
|
typedef adjacency_list<listS,
|
|
distributedS<process_group_type, vecS>,
|
|
directedS,
|
|
no_property, // Vertex properties
|
|
property<edge_weight_t, int> // Edge properties
|
|
> graph_t;
|
|
typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
|
|
typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
|
|
|
|
Note that the only difference from the sequential BGL is the use of
|
|
the ``distributedS`` selector, which identifies a distributed
|
|
graph. The vertices of the graph will be distributed among the
|
|
various processors, and the processor that owns a vertex also stores
|
|
the edges outgoing from that vertex and any properties associated
|
|
with that vertex or its edges. With three processors and the default
|
|
block distribution, the graph would be distributed in this manner:
|
|
|
|
.. image:: ../dijkstra_dist3_graph.png
|
|
|
|
Processor 0 (red) owns vertices A and B, including all edges outoing
|
|
from those vertices, processor 1 (green) owns vertices C and D (and
|
|
their edges), and processor 2 (blue) owns vertex E. Constructing this
|
|
graph uses the same syntax is the sequential graph, as in the section
|
|
`Construct the graph`_.
|
|
|
|
The call to ``dijkstra_shortest_paths`` is syntactically equivalent to
|
|
the sequential call, but the mechanisms used are very different. The
|
|
property maps passed to ``dijkstra_shortest_paths`` are actually
|
|
*distributed* property maps, which store properties for local edges
|
|
or vertices and perform implicit communication to access properties
|
|
of remote edges or vertices when needed. The formulation of Dijkstra's
|
|
algorithm is also slightly different, because each processor can
|
|
only attempt to relax edges outgoing from local vertices: as shorter
|
|
paths to a vertex are discovered, messages to the processor owning
|
|
that vertex indicate that the vertex may require reprocessing.
|
|
|
|
----------------------------------------------------------------------
|
|
|
|
Return to the `Parallel BGL home page`_
|
|
|
|
.. _Parallel BGL home page: index.html
|
|
.. _dijkstra_shortest_paths: http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
|
|
.. _property maps: http://www.boost.org/libs/graph/doc/using_property_maps.html
|
|
.. _adjacency_list: http://www.boost.org/libs/graph/doc/adjacency_list.html
|
|
.. _MPI: http://www-unix.mcs.anl.gov/mpi/
|
|
.. _BGL: http://www.boost.org/libs/graph/doc
|