| <?xml version="1.0" encoding="utf-8" ?> |
| <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
| <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> |
| <head> |
| <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> |
| <meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" /> |
| <title>Parallel Shortest Paths</title> |
| <link rel="stylesheet" href="../../../../rst.css" type="text/css" /> |
| </head> |
| <body> |
| <div class="document" id="parallel-shortest-paths"> |
| <h1 class="title">Parallel Shortest Paths</h1> |
| |
| <!-- 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) --> |
| <p>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:</p> |
| <img alt="../dijkstra_seq_graph.png" src="../dijkstra_seq_graph.png" /> |
| <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 |
| three stages. Readers familiar with the BGL may wish to skip ahead to |
| the section <a class="reference internal" href="#distributing-the-graph">Distributing the graph</a>.</p> |
| <blockquote> |
| <ul class="simple"> |
| <li><a class="reference internal" href="#define-the-graph-type">Define the graph type</a></li> |
| <li><a class="reference internal" href="#construct-the-graph">Construct the graph</a></li> |
| <li><a class="reference internal" href="#invoke-dijkstra-s-algorithm">Invoke Dijkstra's algorithm</a></li> |
| </ul> |
| </blockquote> |
| <div class="section" id="define-the-graph-type"> |
| <h1>Define the graph type</h1> |
| <p>For this problem we use an adjacency list representation of the graph, |
| using 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> |
| <span class="pre">graph</span> <span class="pre">(``directedS</span></tt> parameter ) whose vertices are stored in an |
| <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 |
| vertex 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 |
| of the edges we attach an integral weight.</p> |
| <pre class="literal-block"> |
| 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; |
| </pre> |
| </div> |
| <div class="section" id="construct-the-graph"> |
| <h1>Construct the graph</h1> |
| <p>To build the graph, we declare an enumeration containing the node |
| names (for our own use) and create two arrays: the first, |
| <tt class="docutils literal"><span class="pre">edge_array</span></tt>, contains the source and target of each edge, whereas |
| the second, <tt class="docutils literal"><span class="pre">weights</span></tt>, 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:</p> |
| <pre class="literal-block"> |
| 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); |
| </pre> |
| </div> |
| <div class="section" id="invoke-dijkstra-s-algorithm"> |
| <h1>Invoke Dijkstra's algorithm</h1> |
| <p>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, <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> |
| <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> |
| operation on the <tt class="docutils literal"><span class="pre">adjacency_list``_</span> <span class="pre">and</span> <span class="pre">call</span> |
| <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 |
| <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> |
| <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> |
| vector. The algorithm automatically uses the edge weights stored |
| within the graph, although this capability can be overridden.</p> |
| <pre class="literal-block"> |
| // 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))) |
| ); |
| </pre> |
| </div> |
| <div class="section" id="distributing-the-graph"> |
| <h1>Distributing the graph</h1> |
| <p>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.</p> |
| <p>Processors and their interactions are abstracted via a <em>process |
| group</em>. In our case, we will use <a class="reference external" href="http://www-unix.mcs.anl.gov/mpi/">MPI</a> for communication with |
| inter-processor messages sent immediately:</p> |
| <pre class="literal-block"> |
| typedef mpi::process_group<mpi::immediateS> process_group_type; |
| </pre> |
| <p>Next, we instruct the <tt class="docutils literal"><span class="pre">adjacency_list</span></tt> template |
| to distribute the vertices of the graph across our process group, |
| storing the local vertices in an <tt class="docutils literal"><span class="pre">std::vector</span></tt>:</p> |
| <pre class="literal-block"> |
| 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; |
| </pre> |
| <p>Note that the only difference from the sequential BGL is the use of |
| the <tt class="docutils literal"><span class="pre">distributedS</span></tt> 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:</p> |
| <img alt="../dijkstra_dist3_graph.png" src="../dijkstra_dist3_graph.png" /> |
| <p>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 |
| <a class="reference internal" href="#construct-the-graph">Construct the graph</a>.</p> |
| <p>The call to <tt class="docutils literal"><span class="pre">dijkstra_shortest_paths</span></tt> is syntactically equivalent to |
| the sequential call, but the mechanisms used are very different. The |
| property maps passed to <tt class="docutils literal"><span class="pre">dijkstra_shortest_paths</span></tt> are actually |
| <em>distributed</em> 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.</p> |
| <hr class="docutils" /> |
| <p>Return to the <a class="reference external" href="index.html">Parallel BGL home page</a></p> |
| </div> |
| </div> |
| <div class="footer"> |
| <hr class="footer" /> |
| Generated on: 2009-05-31 00:22 UTC. |
| Generated 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. |
| |
| </div> |
| </body> |
| </html> |