123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164 |
- .. 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
|