ceph/src/boost/libs/graph_parallel/doc/dijkstra_example.rst

   1 .. Copyright (C) 2004-2008 The Trustees of Indiana University.
   2    Use, modification and distribution is subject to the Boost Software
   3    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   4    http://www.boost.org/LICENSE_1_0.txt)
   5
   6 =======================
   7 Parallel Shortest Paths
   8 =======================
   9 To illustrate the use of the Parallel Boost Graph Library, we
  10 illustrate the use of both the sequential and parallel BGL to find
  11 the shortest paths from vertex A to every other vertex in the
  12 following simple graph:
  13
  14 .. image:: ../dijkstra_seq_graph.png
  15
  16 With the sequential BGL_, the program to calculate shortest paths has
  17 three stages. Readers familiar with the BGL may wish to skip ahead to
  18 the section `Distributing the graph`_.
  19
  20
  21   - `Define the graph type`_
  22   - `Construct the graph`_
  23   - `Invoke Dijkstra's algorithm`_
  24
  25 Define the graph type
  26 ~~~~~~~~~~~~~~~~~~~~~
  27
  28 For this problem we use an adjacency list representation of the graph,
  29 using the BGL ``adjacency_list``_ class template. It will be a directed
  30 graph (``directedS`` parameter ) whose vertices are stored in an
  31 ``std::vector`` (``vecS`` parameter) where the outgoing edges of each
  32 vertex are stored in an ``std::list`` (``listS`` parameter). To each
  33 of the edges we attach an integral weight.
  34
  35 ::
  36
  37   typedef adjacency_list<listS, vecS, directedS,
  38                          no_property,                 // Vertex properties
  39                          property<edge_weight_t, int> // Edge properties
  40                          > graph_t;
  41   typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
  42   typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
  43
  44 Construct the graph
  45 ~~~~~~~~~~~~~~~~~~~
  46 To build the graph, we declare an enumeration containing the node
  47 names (for our own use) and create two arrays: the first,
  48 ``edge_array``, contains the source and target of each edge, whereas
  49 the second, ``weights``, contains the integral weight of each
  50 edge. We pass the contents of the arrays via pointers (used here as
  51 iterators) to the graph constructor to build our graph:
  52
  53 ::
  54
  55   typedef std::pair<int, int> Edge;
  56   const int num_nodes = 5;
  57   enum nodes { A, B, C, D, E };
  58   char name[] = "ABCDE";
  59   Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
  60     Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B)
  61   };
  62   int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
  63   int num_arcs = sizeof(edge_array) / sizeof(Edge);
  64
  65   graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
  66
  67
  68 Invoke Dijkstra's algorithm
  69 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
  70 To invoke Dijkstra's algorithm, we need to first decide how we want
  71 to receive the results of the algorithm, namely the distance to each
  72 vertex and the predecessor of each vertex (allowing reconstruction of
  73 the shortest paths themselves). In our case, we will create two
  74 vectors, ``p`` for predecessors and ``d`` for distances.
  75
  76 Next, we determine our starting vertex ``s`` using the ``vertex``
  77 operation on the ``adjacency_list``_ and call
  78 ``dijkstra_shortest_paths``_ with the graph ``g``, starting vertex
  79 ``s``, and two ``property maps``_ that instruct the algorithm to
  80 store predecessors in the ``p`` vector and distances in the ``d``
  81 vector. The algorithm automatically uses the edge weights stored
  82 within the graph, although this capability can be overridden.
  83
  84 ::
  85
  86   // Keeps track of the predecessor of each vertex
  87   std::vector<vertex_descriptor> p(num_vertices(g));
  88   // Keeps track of the distance to each vertex
  89   std::vector<int> d(num_vertices(g));
  90
  91   vertex_descriptor s = vertex(A, g);
  92   dijkstra_shortest_paths
  93     (g, s,
  94      predecessor_map(
  95        make_iterator_property_map(p.begin(), get(vertex_index, g))).
  96      distance_map(
  97        make_iterator_property_map(d.begin(), get(vertex_index, g)))
  98      );
  99
 100 Distributing the graph
 101 ~~~~~~~~~~~~~~~~~~~~~~
 102 The prior computation is entirely sequential, with the graph stored
 103 within a single address space. To distribute the graph across several
 104 processors without a shared address space, we need to represent the
 105 processors and communication among them and alter the graph type.
 106
 107 Processors and their interactions are abstracted via a *process
 108 group*. In our case, we will use MPI_ for communication with
 109 inter-processor messages sent immediately:
 110
 111 ::
 112
 113   typedef mpi::process_group<mpi::immediateS> process_group_type;
 114
 115 Next, we instruct the ``adjacency_list`` template
 116 to distribute the vertices of the graph across our process group,
 117 storing the local vertices in an ``std::vector``::
 118
 119   typedef adjacency_list<listS,
 120                          distributedS<process_group_type, vecS>,
 121                          directedS,
 122                          no_property,                 // Vertex properties
 123                          property<edge_weight_t, int> // Edge properties
 124                          > graph_t;
 125   typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
 126   typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
 127
 128 Note that the only difference from the sequential BGL is the use of
 129 the ``distributedS`` selector, which identifies a distributed
 130 graph. The vertices of the graph will be distributed among the
 131 various processors, and the processor that owns a vertex also stores
 132 the edges outgoing from that vertex and any properties associated
 133 with that vertex or its edges. With three processors and the default
 134 block distribution, the graph would be distributed in this manner:
 135
 136 .. image:: ../dijkstra_dist3_graph.png
 137
 138 Processor 0 (red) owns vertices A and B, including all edges outoing
 139 from those vertices, processor 1 (green) owns vertices C and D (and
 140 their edges), and processor 2 (blue) owns vertex E. Constructing this
 141 graph uses the same syntax is the sequential graph, as in the section
 142 `Construct the graph`_.
 143
 144 The call to ``dijkstra_shortest_paths`` is syntactically equivalent to
 145 the sequential call, but the mechanisms used are very different. The
 146 property maps passed to ``dijkstra_shortest_paths`` are actually
 147 *distributed* property maps, which store properties for local edges
 148 or vertices and perform implicit communication to access properties
 149 of remote edges or vertices when needed. The formulation of Dijkstra's
 150 algorithm is also slightly different, because each processor can
 151 only attempt to relax edges outgoing from local vertices: as shorter
 152 paths to a vertex are discovered, messages to the processor owning
 153 that vertex indicate that the vertex may require reprocessing.
 154
 155 ----------------------------------------------------------------------
 156
 157 Return to the `Parallel BGL home page`_
 158
 159 .. _Parallel BGL home page: index.html
 160 .. _dijkstra_shortest_paths: http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
 161 .. _property maps: http://www.boost.org/libs/graph/doc/using_property_maps.html
 162 .. _adjacency_list: http://www.boost.org/libs/graph/doc/adjacency_list.html
 163 .. _MPI: http://www-unix.mcs.anl.gov/mpi/
 164 .. _BGL: http://www.boost.org/libs/graph/doc