[ceph.git] / ceph / src / boost / libs / graph_parallel / doc / html / dijkstra_example.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&lt;listS, vecS, directedS,
                       no_property,                 // Vertex properties
                       property&lt;edge_weight_t, int&gt; // Edge properties
                       &gt; graph_t;
typedef graph_traits &lt; graph_t &gt;::vertex_descriptor vertex_descriptor;
typedef graph_traits &lt; graph_t &gt;::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&lt;int, int&gt; Edge;
const int num_nodes = 5;
enum nodes { A, B, C, D, E };
char name[] = &quot;ABCDE&quot;;
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&lt;vertex_descriptor&gt; p(num_vertices(g));
// Keeps track of the distance to each vertex
std::vector&lt;int&gt; 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&lt;mpi::immediateS&gt; 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&lt;listS,
                       distributedS&lt;process_group_type, vecS&gt;,
                       directedS,
                       no_property,                 // Vertex properties
                       property&lt;edge_weight_t, int&gt; // Edge properties
                       &gt; graph_t;
typedef graph_traits &lt; graph_t &gt;::vertex_descriptor vertex_descriptor;
typedef graph_traits &lt; graph_t &gt;::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>
Commit	Line	Data
7c673cae FG	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.
	15	Use, modification and distribution is subject to the Boost Software
	16	License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	17	http://www.boost.org/LICENSE_1_0.txt) -->
	18	<p>To illustrate the use of the Parallel Boost Graph Library, we
	19	illustrate the use of both the sequential and parallel BGL to find
	20	the shortest paths from vertex A to every other vertex in the
	21	following 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
	24	three stages. Readers familiar with the BGL may wish to skip ahead to
	25	the 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,
	36	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>
	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
	39	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
	40	of the edges we attach an integral weight.</p>
	41	<pre class="literal-block">
	42	typedef adjacency_list<listS, vecS, directedS,
	43	no_property, // Vertex properties
	44	property<edge_weight_t, int> // Edge properties
	45	> graph_t;
	46	typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
	47	typedef 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
	53	names (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
	55	the second, <tt class="docutils literal"><span class="pre">weights</span></tt>, contains the integral weight of each
	56	edge. We pass the contents of the arrays via pointers (used here as
	57	iterators) to the graph constructor to build our graph:</p>
	58	<pre class="literal-block">
	59	typedef std::pair<int, int> Edge;
	60	const int num_nodes = 5;
	61	enum nodes { A, B, C, D, E };
	62	char name[] = "ABCDE";
	63	Edge 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	};
66	int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
67	int num_arcs = sizeof(edge_array) / sizeof(Edge);
68
69	graph_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
75	to receive the results of the algorithm, namely the distance to each
76	vertex and the predecessor of each vertex (allowing reconstruction of
77	the shortest paths themselves). In our case, we will create two
78	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>
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>
80	operation 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>
84	vector. The algorithm automatically uses the edge weights stored
85	within the graph, although this capability can be overridden.</p>
86	<pre class="literal-block">
87	// Keeps track of the predecessor of each vertex
88	std::vector<vertex_descriptor> p(num_vertices(g));
89	// Keeps track of the distance to each vertex
90	std::vector<int> d(num_vertices(g));
91
92	vertex_descriptor s = vertex(A, g);
93	dijkstra_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
105	within a single address space. To distribute the graph across several
106	processors without a shared address space, we need to represent the
107	processors and communication among them and alter the graph type.</p>
108	<p>Processors and their interactions are abstracted via a <em>process
109	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
110	inter-processor messages sent immediately:</p>
111	<pre class="literal-block">
112	typedef 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
115	to distribute the vertices of the graph across our process group,
116	storing the local vertices in an <tt class="docutils literal"><span class="pre">std::vector</span></tt>:</p>
117	<pre class="literal-block">
118	typedef 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;
124	typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
125	typedef 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
128	the <tt class="docutils literal"><span class="pre">distributedS</span></tt> selector, which identifies a distributed
129	graph. The vertices of the graph will be distributed among the
130	various processors, and the processor that owns a vertex also stores
131	the edges outgoing from that vertex and any properties associated
132	with that vertex or its edges. With three processors and the default
133	block 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
136	from those vertices, processor 1 (green) owns vertices C and D (and
137	their edges), and processor 2 (blue) owns vertex E. Constructing this
138	graph 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
141	the sequential call, but the mechanisms used are very different. The
142	property 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
144	or vertices and perform implicit communication to access properties
145	of remote edges or vertices when needed. The formulation of Dijkstra's
146	algorithm is also slightly different, because each processor can
147	only attempt to relax edges outgoing from local vertices: as shorter
148	paths to a vertex are discovered, messages to the processor owning
149	that 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" />
156	Generated on: 2009-05-31 00:22 UTC.
157	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.
158
159	</div>
160	</body>
161	</html>