]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | .. Copyright (C) 2004-2008 The Trustees of Indiana University. |
2 | Use, modification and distribution is subject to the Boost Software | |
3 | License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
4 | http://www.boost.org/LICENSE_1_0.txt) | |
5 | ||
6 | ======================= | |
7 | Parallel Shortest Paths | |
8 | ======================= | |
9 | To illustrate the use of the Parallel Boost Graph Library, we | |
10 | illustrate the use of both the sequential and parallel BGL to find | |
11 | the shortest paths from vertex A to every other vertex in the | |
12 | following simple graph: | |
13 | ||
14 | .. image:: ../dijkstra_seq_graph.png | |
15 | ||
16 | With the sequential BGL_, the program to calculate shortest paths has | |
17 | three stages. Readers familiar with the BGL may wish to skip ahead to | |
18 | the section `Distributing the graph`_. | |
19 | ||
20 | ||
21 | - `Define the graph type`_ | |
22 | - `Construct the graph`_ | |
23 | - `Invoke Dijkstra's algorithm`_ | |
24 | ||
25 | Define the graph type | |
26 | ~~~~~~~~~~~~~~~~~~~~~ | |
27 | ||
28 | For this problem we use an adjacency list representation of the graph, | |
29 | using the BGL ``adjacency_list``_ class template. It will be a directed | |
30 | graph (``directedS`` parameter ) whose vertices are stored in an | |
31 | ``std::vector`` (``vecS`` parameter) where the outgoing edges of each | |
32 | vertex are stored in an ``std::list`` (``listS`` parameter). To each | |
33 | of the edges we attach an integral weight. | |
34 | ||
35 | :: | |
36 | ||
37 | typedef adjacency_list<listS, vecS, directedS, | |
38 | no_property, // Vertex properties | |
39 | property<edge_weight_t, int> // Edge properties | |
40 | > graph_t; | |
41 | typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor; | |
42 | typedef graph_traits < graph_t >::edge_descriptor edge_descriptor; | |
43 | ||
44 | Construct the graph | |
45 | ~~~~~~~~~~~~~~~~~~~ | |
46 | To build the graph, we declare an enumeration containing the node | |
47 | names (for our own use) and create two arrays: the first, | |
48 | ``edge_array``, contains the source and target of each edge, whereas | |
49 | the second, ``weights``, contains the integral weight of each | |
50 | edge. We pass the contents of the arrays via pointers (used here as | |
51 | iterators) to the graph constructor to build our graph: | |
52 | ||
53 | :: | |
54 | ||
55 | typedef std::pair<int, int> Edge; | |
56 | const int num_nodes = 5; | |
57 | enum nodes { A, B, C, D, E }; | |
58 | char name[] = "ABCDE"; | |
59 | Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E), | |
60 | Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B) | |
61 | }; | |
62 | int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 }; | |
63 | int num_arcs = sizeof(edge_array) / sizeof(Edge); | |
64 | ||
65 | graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes); | |
66 | ||
67 | ||
68 | Invoke Dijkstra's algorithm | |
69 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~ | |
70 | To invoke Dijkstra's algorithm, we need to first decide how we want | |
71 | to receive the results of the algorithm, namely the distance to each | |
72 | vertex and the predecessor of each vertex (allowing reconstruction of | |
73 | the shortest paths themselves). In our case, we will create two | |
74 | vectors, ``p`` for predecessors and ``d`` for distances. | |
75 | ||
76 | Next, we determine our starting vertex ``s`` using the ``vertex`` | |
77 | operation on the ``adjacency_list``_ and call | |
78 | ``dijkstra_shortest_paths``_ with the graph ``g``, starting vertex | |
79 | ``s``, and two ``property maps``_ that instruct the algorithm to | |
80 | store predecessors in the ``p`` vector and distances in the ``d`` | |
81 | vector. The algorithm automatically uses the edge weights stored | |
82 | within the graph, although this capability can be overridden. | |
83 | ||
84 | :: | |
85 | ||
86 | // Keeps track of the predecessor of each vertex | |
87 | std::vector<vertex_descriptor> p(num_vertices(g)); | |
88 | // Keeps track of the distance to each vertex | |
89 | std::vector<int> d(num_vertices(g)); | |
90 | ||
91 | vertex_descriptor s = vertex(A, g); | |
92 | dijkstra_shortest_paths | |
93 | (g, s, | |
94 | predecessor_map( | |
95 | make_iterator_property_map(p.begin(), get(vertex_index, g))). | |
96 | distance_map( | |
97 | make_iterator_property_map(d.begin(), get(vertex_index, g))) | |
98 | ); | |
99 | ||
100 | Distributing the graph | |
101 | ~~~~~~~~~~~~~~~~~~~~~~ | |
102 | The prior computation is entirely sequential, with the graph stored | |
103 | within a single address space. To distribute the graph across several | |
104 | processors without a shared address space, we need to represent the | |
105 | processors and communication among them and alter the graph type. | |
106 | ||
107 | Processors and their interactions are abstracted via a *process | |
108 | group*. In our case, we will use MPI_ for communication with | |
109 | inter-processor messages sent immediately: | |
110 | ||
111 | :: | |
112 | ||
113 | typedef mpi::process_group<mpi::immediateS> process_group_type; | |
114 | ||
115 | Next, we instruct the ``adjacency_list`` template | |
116 | to distribute the vertices of the graph across our process group, | |
117 | storing the local vertices in an ``std::vector``:: | |
118 | ||
119 | typedef adjacency_list<listS, | |
120 | distributedS<process_group_type, vecS>, | |
121 | directedS, | |
122 | no_property, // Vertex properties | |
123 | property<edge_weight_t, int> // Edge properties | |
124 | > graph_t; | |
125 | typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor; | |
126 | typedef graph_traits < graph_t >::edge_descriptor edge_descriptor; | |
127 | ||
128 | Note that the only difference from the sequential BGL is the use of | |
129 | the ``distributedS`` selector, which identifies a distributed | |
130 | graph. The vertices of the graph will be distributed among the | |
131 | various processors, and the processor that owns a vertex also stores | |
132 | the edges outgoing from that vertex and any properties associated | |
133 | with that vertex or its edges. With three processors and the default | |
134 | block distribution, the graph would be distributed in this manner: | |
135 | ||
136 | .. image:: ../dijkstra_dist3_graph.png | |
137 | ||
138 | Processor 0 (red) owns vertices A and B, including all edges outoing | |
139 | from those vertices, processor 1 (green) owns vertices C and D (and | |
140 | their edges), and processor 2 (blue) owns vertex E. Constructing this | |
141 | graph uses the same syntax is the sequential graph, as in the section | |
142 | `Construct the graph`_. | |
143 | ||
144 | The call to ``dijkstra_shortest_paths`` is syntactically equivalent to | |
145 | the sequential call, but the mechanisms used are very different. The | |
146 | property maps passed to ``dijkstra_shortest_paths`` are actually | |
147 | *distributed* property maps, which store properties for local edges | |
148 | or vertices and perform implicit communication to access properties | |
149 | of remote edges or vertices when needed. The formulation of Dijkstra's | |
150 | algorithm is also slightly different, because each processor can | |
151 | only attempt to relax edges outgoing from local vertices: as shorter | |
152 | paths to a vertex are discovered, messages to the processor owning | |
153 | that vertex indicate that the vertex may require reprocessing. | |
154 | ||
155 | ---------------------------------------------------------------------- | |
156 | ||
157 | Return to the `Parallel BGL home page`_ | |
158 | ||
159 | .. _Parallel BGL home page: index.html | |
160 | .. _dijkstra_shortest_paths: http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html | |
161 | .. _property maps: http://www.boost.org/libs/graph/doc/using_property_maps.html | |
162 | .. _adjacency_list: http://www.boost.org/libs/graph/doc/adjacency_list.html | |
163 | .. _MPI: http://www-unix.mcs.anl.gov/mpi/ | |
164 | .. _BGL: http://www.boost.org/libs/graph/doc |