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