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