ceph/src/boost/libs/graph_parallel/doc/html/dijkstra_example.html

   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&lt;listS, vecS, directedS,
  43                        no_property,                 // Vertex properties
  44                        property&lt;edge_weight_t, int&gt; // Edge properties
  45                        &gt; graph_t;
  46 typedef graph_traits &lt; graph_t &gt;::vertex_descriptor vertex_descriptor;
  47 typedef graph_traits &lt; graph_t &gt;::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&lt;int, int&gt; Edge;
  60 const int num_nodes = 5;
  61 enum nodes { A, B, C, D, E };
  62 char name[] = &quot;ABCDE&quot;;
  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&lt;vertex_descriptor&gt; p(num_vertices(g));
  89 // Keeps track of the distance to each vertex
  90 std::vector&lt;int&gt; 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&lt;mpi::immediateS&gt; 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&lt;listS,
 119                        distributedS&lt;process_group_type, vecS&gt;,
 120                        directedS,
 121                        no_property,                 // Vertex properties
 122                        property&lt;edge_weight_t, int&gt; // Edge properties
 123                        &gt; graph_t;
 124 typedef graph_traits &lt; graph_t &gt;::vertex_descriptor vertex_descriptor;
 125 typedef graph_traits &lt; graph_t &gt;::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>