162 lines
10 KiB
HTML
162 lines
10 KiB
HTML
<?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>
|