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======================= 7Parallel Shortest Paths 8======================= 9To illustrate the use of the Parallel Boost Graph Library, we 10illustrate the use of both the sequential and parallel BGL to find 11the shortest paths from vertex A to every other vertex in the 12following simple graph: 13 14.. image:: ../dijkstra_seq_graph.png 15 16With the sequential BGL_, the program to calculate shortest paths has 17three stages. Readers familiar with the BGL may wish to skip ahead to 18the section `Distributing the graph`_. 19 20 21 - `Define the graph type`_ 22 - `Construct the graph`_ 23 - `Invoke Dijkstra's algorithm`_ 24 25Define the graph type 26~~~~~~~~~~~~~~~~~~~~~ 27 28For this problem we use an adjacency list representation of the graph, 29using the BGL ``adjacency_list``_ class template. It will be a directed 30graph (``directedS`` parameter ) whose vertices are stored in an 31``std::vector`` (``vecS`` parameter) where the outgoing edges of each 32vertex are stored in an ``std::list`` (``listS`` parameter). To each 33of 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 44Construct the graph 45~~~~~~~~~~~~~~~~~~~ 46To build the graph, we declare an enumeration containing the node 47names (for our own use) and create two arrays: the first, 48``edge_array``, contains the source and target of each edge, whereas 49the second, ``weights``, contains the integral weight of each 50edge. We pass the contents of the arrays via pointers (used here as 51iterators) 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 68Invoke Dijkstra's algorithm 69~~~~~~~~~~~~~~~~~~~~~~~~~~~ 70To invoke Dijkstra's algorithm, we need to first decide how we want 71to receive the results of the algorithm, namely the distance to each 72vertex and the predecessor of each vertex (allowing reconstruction of 73the shortest paths themselves). In our case, we will create two 74vectors, ``p`` for predecessors and ``d`` for distances. 75 76Next, we determine our starting vertex ``s`` using the ``vertex`` 77operation 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 80store predecessors in the ``p`` vector and distances in the ``d`` 81vector. The algorithm automatically uses the edge weights stored 82within 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 100Distributing the graph 101~~~~~~~~~~~~~~~~~~~~~~ 102The prior computation is entirely sequential, with the graph stored 103within a single address space. To distribute the graph across several 104processors without a shared address space, we need to represent the 105processors and communication among them and alter the graph type. 106 107Processors and their interactions are abstracted via a *process 108group*. In our case, we will use MPI_ for communication with 109inter-processor messages sent immediately: 110 111:: 112 113 typedef mpi::process_group<mpi::immediateS> process_group_type; 114 115Next, we instruct the ``adjacency_list`` template 116to distribute the vertices of the graph across our process group, 117storing 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 128Note that the only difference from the sequential BGL is the use of 129the ``distributedS`` selector, which identifies a distributed 130graph. The vertices of the graph will be distributed among the 131various processors, and the processor that owns a vertex also stores 132the edges outgoing from that vertex and any properties associated 133with that vertex or its edges. With three processors and the default 134block distribution, the graph would be distributed in this manner: 135 136.. image:: ../dijkstra_dist3_graph.png 137 138Processor 0 (red) owns vertices A and B, including all edges outoing 139from those vertices, processor 1 (green) owns vertices C and D (and 140their edges), and processor 2 (blue) owns vertex E. Constructing this 141graph uses the same syntax is the sequential graph, as in the section 142`Construct the graph`_. 143 144The call to ``dijkstra_shortest_paths`` is syntactically equivalent to 145the sequential call, but the mechanisms used are very different. The 146property maps passed to ``dijkstra_shortest_paths`` are actually 147*distributed* property maps, which store properties for local edges 148or vertices and perform implicit communication to access properties 149of remote edges or vertices when needed. The formulation of Dijkstra's 150algorithm is also slightly different, because each processor can 151only attempt to relax edges outgoing from local vertices: as shorter 152paths to a vertex are discovered, messages to the processor owning 153that vertex indicate that the vertex may require reprocessing. 154 155---------------------------------------------------------------------- 156 157Return 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 165
