123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161 |
- <?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>
|