| 1 | <html> |
|---|
| 2 | |
|---|
| 3 | <!-- |
|---|
| 4 | -- Copyright (c) Jeremy Siek 2000 |
|---|
| 5 | -- |
|---|
| 6 | -- Permission to use, copy, modify, distribute and sell this software |
|---|
| 7 | -- and its documentation for any purpose is hereby granted without fee, |
|---|
| 8 | -- provided that the above copyright notice appears in all copies and |
|---|
| 9 | -- that both that copyright notice and this permission notice appear |
|---|
| 10 | -- in supporting documentation. Silicon Graphics makes no |
|---|
| 11 | -- representations about the suitability of this software for any |
|---|
| 12 | -- purpose. It is provided "as is" without express or implied warranty. |
|---|
| 13 | --> |
|---|
| 14 | |
|---|
| 15 | <head> |
|---|
| 16 | <title>Quick Tour of Boost Graph Library</title> |
|---|
| 17 | <meta name="GENERATOR" content="Microsoft FrontPage 4.0"> |
|---|
| 18 | <meta name="ProgId" content="FrontPage.Editor.Document"> |
|---|
| 19 | </head> |
|---|
| 20 | |
|---|
| 21 | <body bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b" alink="#ff0000"> |
|---|
| 22 | |
|---|
| 23 | <img src="../../../boost.png" alt="C++ Boost" width="277" height="86"><br clear> |
|---|
| 24 | <h1>A Quick Tour of the Boost Graph Library</h1> |
|---|
| 25 | <p>The domain of graph data structures and algorithms is in some respects more |
|---|
| 26 | complicated than that of containers. The abstract iterator interface used by STL |
|---|
| 27 | is not sufficiently rich to encompass the numerous ways that graph algorithms |
|---|
| 28 | may traverse a graph. Instead, we formulate an abstract interface that serves |
|---|
| 29 | the same purpose for graphs that iterators do for basic containers (though |
|---|
| 30 | iterators still play a large role). <a href="#fig:analogy">Figure 1</a> depicts |
|---|
| 31 | the analogy between the STL and the BGL. |
|---|
| 32 | <p> </p> |
|---|
| 33 | <div align="CENTER"> |
|---|
| 34 | <a name="fig:analogy"></a><a name="752"></a> |
|---|
| 35 | <table> |
|---|
| 36 | <caption valign="bottom"><strong>Figure 1:</strong> The analogy between the |
|---|
| 37 | STL and the BGL.</caption> |
|---|
| 38 | <tr> |
|---|
| 39 | <td><img src="figs/analogy.gif" width="518" height="335"></td> |
|---|
| 40 | </tr> |
|---|
| 41 | </table> |
|---|
| 42 | </div> |
|---|
| 43 | <p> </p> |
|---|
| 44 | The graph abstraction consists of a set of vertices (or nodes), and a set of |
|---|
| 45 | edges (or arcs) that connect the vertices. <a href="#fig:quick-start">Figure 2</a> |
|---|
| 46 | depicts a directed graph with five vertices (labeled 0 through 4) and 11 edges. |
|---|
| 47 | The edges leaving a vertex are called the <i>out-edges</i> of the vertex. The |
|---|
| 48 | edges <tt>{(0,1),(0,2),(0,3),(0,4)}</tt> are all out-edges of vertex 0. The |
|---|
| 49 | edges entering a vertex are called the <i>in-edges</i> of the vertex. The edges <tt>{(0,4),(2,4),(3,4)}</tt> |
|---|
| 50 | are all in-edges of vertex 4. |
|---|
| 51 | <p> </p> |
|---|
| 52 | <div align="CENTER"> |
|---|
| 53 | <a name="fig:quick-start"></a> |
|---|
| 54 | <table> |
|---|
| 55 | <caption valign="bottom"><strong>Figure 2:</strong> An example of a directed |
|---|
| 56 | graph.</caption> |
|---|
| 57 | <tr> |
|---|
| 58 | <td><img src="figs/quick_start.gif" width="103" height="124"></td> |
|---|
| 59 | </tr> |
|---|
| 60 | </table> |
|---|
| 61 | </div> |
|---|
| 62 | <p> </p> |
|---|
| 63 | <p>In the following sections we will use the BGL to construct this example graph |
|---|
| 64 | and manipulate it in various ways. The complete source code for this example can |
|---|
| 65 | be found in <a href="../example/quick_tour.cpp"><tt>examples/quick_tour.cpp</tt></a>. |
|---|
| 66 | Each of the following sections discusses a "slice" of this example |
|---|
| 67 | file. Excerpts from the output of the example program will also be listed. |
|---|
| 68 | <p> |
|---|
| 69 | <h2>Constructing a Graph</h2> |
|---|
| 70 | <p>In this example we will use the BGL <a href="adjacency_list.html"><tt>adjacency_list</tt></a> |
|---|
| 71 | class to demonstrate the main ideas in the BGL interface. The <tt>adjacency_list</tt> |
|---|
| 72 | class provides a generalized version of the classic "adjacency list" |
|---|
| 73 | data structure. The <tt>adjacency_list</tt> is a template class with six |
|---|
| 74 | template parameters, though here we only fill in the first three parameters and |
|---|
| 75 | use the defaults for the remaining three. The first two template arguments (<tt>vecS, |
|---|
| 76 | vecS</tt>) determine the data structure used to represent the out-edges for each |
|---|
| 77 | vertex in the graph and the data structure used to represent the graph's vertex |
|---|
| 78 | set (see section <a href="using_adjacency_list.html#sec:choosing-graph-type">Choosing |
|---|
| 79 | the <tt>Edgelist</tt> and <tt>VertexList</tt></a> for information about the |
|---|
| 80 | tradeoffs of the different data structures). The third argument, <tt>bidirectionalS</tt>, |
|---|
| 81 | selects a directed graph that provides access to both out and in-edges. The |
|---|
| 82 | other options for the third argument are <tt>directedS</tt> which selects a |
|---|
| 83 | directed graph with only out-edges, and <tt>undirectedS</tt> which selects an |
|---|
| 84 | undirected graph. |
|---|
| 85 | <p>Once we have the graph type selected, we can create the graph in <a href="#fig:quick-start">Figure |
|---|
| 86 | 2</a> by declaring a graph object and filling in edges using the <a href="MutableGraph.html#sec:add-edge"><tt>add_edge()</tt></a> |
|---|
| 87 | function of the <a href="MutableGraph.html">MutableGraph</a> interface (which <tt>adjacency_list</tt> |
|---|
| 88 | implements). We use the array of pairs <tt>edge_array</tt> merely as a |
|---|
| 89 | convenient way to explicitly create the edges for this example. |
|---|
| 90 | <p> |
|---|
| 91 | <pre> |
|---|
| 92 | #include <iostream> // for std::cout |
|---|
| 93 | #include <utility> // for std::pair |
|---|
| 94 | #include <algorithm> // for std::for_each |
|---|
| 95 | #include <boost/graph/graph_traits.hpp> |
|---|
| 96 | #include <boost/graph/adjacency_list.hpp> |
|---|
| 97 | #include <boost/graph/dijkstra_shortest_paths.hpp> |
|---|
| 98 | |
|---|
| 99 | using namespace boost; |
|---|
| 100 | |
|---|
| 101 | int main(int,char*[]) |
|---|
| 102 | { |
|---|
| 103 | // create a typedef for the Graph type |
|---|
| 104 | typedef adjacency_list<vecS, vecS, bidirectionalS> Graph; |
|---|
| 105 | |
|---|
| 106 | // Make convenient labels for the vertices |
|---|
| 107 | enum { A, B, C, D, E, N }; |
|---|
| 108 | const int num_vertices = N; |
|---|
| 109 | const char* name = "ABCDE"; |
|---|
| 110 | |
|---|
| 111 | // writing out the edges in the graph |
|---|
| 112 | typedef std::pair<int, int> Edge; |
|---|
| 113 | Edge edge_array[] = |
|---|
| 114 | { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C), |
|---|
| 115 | Edge(C,E), Edge(B,D), Edge(D,E) }; |
|---|
| 116 | const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]); |
|---|
| 117 | |
|---|
| 118 | // declare a graph object |
|---|
| 119 | Graph g(num_vertices); |
|---|
| 120 | |
|---|
| 121 | // add the edges to the graph object |
|---|
| 122 | for (int i = 0; i < num_edges; ++i) |
|---|
| 123 | add_edge(edge_array[i].first, edge_array[i].second, g); |
|---|
| 124 | ... |
|---|
| 125 | return 0; |
|---|
| 126 | } |
|---|
| 127 | </pre> |
|---|
| 128 | <p>Instead of calling the <tt>add_edge()</tt> function for each edge, we could |
|---|
| 129 | use the <a href="adjacency_list.html#sec:iterator-constructor">edge iterator |
|---|
| 130 | constructor</a> of the graph. This is typically more efficient than using <tt>add_edge()</tt>. |
|---|
| 131 | Pointers to the <tt>edge_array</tt> can be viewed as iterators, so we can call |
|---|
| 132 | the iterator constructor by passing pointers to the beginning and end of the |
|---|
| 133 | array. |
|---|
| 134 | <pre> |
|---|
| 135 | Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(Edge), num_vertices); |
|---|
| 136 | </pre> |
|---|
| 137 | <p>Instead of creating a graph with a certain number of vertices to begin with, |
|---|
| 138 | it is also possible to add and remove vertices with the <a href="MutableGraph.html#sec:add-vertex"><tt>add_vertex()</tt></a> |
|---|
| 139 | and <a href="MutableGraph.html#sec:remove-vertex"><tt>remove_vertex()</tt></a> |
|---|
| 140 | functions, also of the <a href="MutableGraph.html">MutableGraph</a> interface. |
|---|
| 141 | <h2>Accessing the Vertex Set</h2> |
|---|
| 142 | <p>Now that we have created a graph, we can use the graph interface to access |
|---|
| 143 | the graph data in different ways. First we can access all of the vertices in the |
|---|
| 144 | graph using the <a href="VertexListGraph.html#sec:vertices"><tt>vertices()</tt></a> |
|---|
| 145 | function of the <a href="VertexListGraph.html">VertexListGraph</a> interface. |
|---|
| 146 | This function returns a <tt>std::pair</tt> of <i>vertex iterators</i> (the <tt>first</tt> |
|---|
| 147 | iterator points to the "beginning" of the vertices and the <tt>second</tt> |
|---|
| 148 | iterator points "past the end"). Dereferencing a vertex iterator gives |
|---|
| 149 | a vertex object. The type of the vertex iterator is given by the <a href="graph_traits.html"><tt>graph_traits</tt></a> |
|---|
| 150 | class. Note that different graph classes can have different associated vertex |
|---|
| 151 | iterator types, which is why we need the <tt>graph_traits</tt> class. Given some |
|---|
| 152 | graph type, the <tt>graph_traits</tt> class will provide access to the <tt>vertex_iterator</tt> |
|---|
| 153 | type. |
|---|
| 154 | <p>The following example prints out the index for each of the vertices in the |
|---|
| 155 | graph. All vertex and edge properties, including index, are accessed via |
|---|
| 156 | property map objects. The <a href="property_map.html"><tt>property_map</tt></a> |
|---|
| 157 | class is used to obtain the property map type for a specific property (specified |
|---|
| 158 | by <tt>vertex_index_t</tt>, one of the BGL predefined properties) and function |
|---|
| 159 | call <tt>get(vertex_index, g)</tt> returns the actual property map object. |
|---|
| 160 | <p> |
|---|
| 161 | <pre> |
|---|
| 162 | // ... |
|---|
| 163 | int main(int,char*[]) |
|---|
| 164 | { |
|---|
| 165 | // ... |
|---|
| 166 | |
|---|
| 167 | // get the property map for vertex indices |
|---|
| 168 | typedef property_map<Graph, vertex_index_t>::type IndexMap; |
|---|
| 169 | IndexMap index = get(vertex_index, g); |
|---|
| 170 | |
|---|
| 171 | std::cout << "vertices(g) = "; |
|---|
| 172 | typedef graph_traits<Graph>::vertex_iterator vertex_iter; |
|---|
| 173 | std::pair<vertex_iter, vertex_iter> vp; |
|---|
| 174 | for (vp = vertices(g); vp.first != vp.second; ++vp.first) |
|---|
| 175 | std::cout << index[*vp.first] << " "; |
|---|
| 176 | std::cout << std::endl; |
|---|
| 177 | // ... |
|---|
| 178 | return 0; |
|---|
| 179 | } |
|---|
| 180 | </pre> |
|---|
| 181 | The output is: |
|---|
| 182 | <pre> |
|---|
| 183 | vertices(g) = 0 1 2 3 4 |
|---|
| 184 | </pre> |
|---|
| 185 | <p> |
|---|
| 186 | <h2>Accessing the Edge Set</h2> |
|---|
| 187 | <p>The set of edges for a graph can be accessed with the <a href="EdgeListGraph.html#sec:edges"><tt>edges()</tt></a> |
|---|
| 188 | function of the <a href="EdgeListGraph.html">EdgeListGraph</a> interface. |
|---|
| 189 | Similar to the <tt>vertices()</tt> function, this returns a pair of iterators, |
|---|
| 190 | but in this case the iterators are <i>edge iterators</i>. Dereferencing an edge |
|---|
| 191 | iterator gives an edge object. The <tt>source()</tt> and <tt>target()</tt> |
|---|
| 192 | functions return the two vertices that are connected by the edge. Instead of |
|---|
| 193 | explicitly creating a <tt>std::pair</tt> for the iterators, this time we will |
|---|
| 194 | use the <a href="../../tuple/doc/tuple_users_guide.html#tiers"><tt>tie()</tt></a> helper function. |
|---|
| 195 | This handy function can be used to assign the parts of a <tt>std::pair</tt> into |
|---|
| 196 | two separate variables, in this case <tt>ei</tt> and <tt>ei_end</tt>. This is |
|---|
| 197 | usually more convenient than creating a <tt>std::pair</tt> and is our method of |
|---|
| 198 | choice for the BGL. |
|---|
| 199 | <p> |
|---|
| 200 | <pre> |
|---|
| 201 | // ... |
|---|
| 202 | int main(int,char*[]) |
|---|
| 203 | { |
|---|
| 204 | // ... |
|---|
| 205 | std::cout << "edges(g) = "; |
|---|
| 206 | graph_traits<Graph>::edge_iterator ei, ei_end; |
|---|
| 207 | for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) |
|---|
| 208 | std::cout << "(" << index[source(*ei, g)] |
|---|
| 209 | << "," << index[target(*ei, g)] << ") "; |
|---|
| 210 | std::cout << std::endl; |
|---|
| 211 | // ... |
|---|
| 212 | return 0; |
|---|
| 213 | } |
|---|
| 214 | </pre> |
|---|
| 215 | The output is: |
|---|
| 216 | <pre> |
|---|
| 217 | edges(g) = (0,1) (0,2) (0,3) (0,4) (2,0) (2,4) (3,0) |
|---|
| 218 | (3,1) (3,4) (4,0) (4,1) |
|---|
| 219 | </pre> |
|---|
| 220 | <p> |
|---|
| 221 | <h2>The Adjacency Structure</h2> |
|---|
| 222 | <p>In the next few examples we will explore the adjacency structure of the graph |
|---|
| 223 | from the point of view of a particular vertex. We will look at the vertices' |
|---|
| 224 | in-edges, out-edges, and its adjacent vertices. We will encapsulate this in an |
|---|
| 225 | "exercise vertex" function, and apply it to each vertex in the graph. |
|---|
| 226 | To demonstrate the STL-interoperability of BGL, we will use the STL <tt>for_each()</tt> |
|---|
| 227 | function to iterate through the vertices and apply the function. |
|---|
| 228 | <p> |
|---|
| 229 | <pre> |
|---|
| 230 | //... |
|---|
| 231 | int main(int,char*[]) |
|---|
| 232 | { |
|---|
| 233 | //... |
|---|
| 234 | std::for_each(vertices(g).first, vertices(g).second, |
|---|
| 235 | exercise_vertex<Graph>(g)); |
|---|
| 236 | return 0; |
|---|
| 237 | } |
|---|
| 238 | </pre> |
|---|
| 239 | <p>We use a functor for <tt>exercise_vertex</tt> instead of just a function |
|---|
| 240 | because the graph object will be needed when we access information about each |
|---|
| 241 | vertex; using a functor gives us a place to keep a reference to the graph object |
|---|
| 242 | during the execution of the <tt>std::for_each()</tt>. Also we template the |
|---|
| 243 | functor on the graph type so that it is reusable with different graph classes. |
|---|
| 244 | Here is the start of the <tt>exercise_vertex</tt> functor: |
|---|
| 245 | <p> |
|---|
| 246 | <pre> |
|---|
| 247 | template <class Graph> struct exercise_vertex { |
|---|
| 248 | exercise_vertex(Graph& g_) : g(g_) {} |
|---|
| 249 | //... |
|---|
| 250 | Graph& g; |
|---|
| 251 | }; |
|---|
| 252 | </pre> |
|---|
| 253 | <p> |
|---|
| 254 | <h3>Vertex Descriptors</h3> |
|---|
| 255 | <p>The first thing we need to know in order to write the <tt>operator()</tt> |
|---|
| 256 | method of the functor is the type for the vertex objects of the graph. The |
|---|
| 257 | vertex type will be the parameter to the <tt>operator()</tt> method. To be |
|---|
| 258 | precise, we do not deal with actual vertex objects, but rather with <i>vertex |
|---|
| 259 | descriptors</i>. Many graph representations (such as adjacency lists) do not |
|---|
| 260 | store actual vertex objects, while others do (e.g., pointer-linked graphs). This |
|---|
| 261 | difference is hidden underneath the "black-box" of the vertex |
|---|
| 262 | descriptor object. The vertex descriptor is something provided by each graph |
|---|
| 263 | type that can be used to access information about the graph via the <tt>out_edges()</tt>, |
|---|
| 264 | <tt>in_edges()</tt>, <tt>adjacent_vertices()</tt>, and property map functions |
|---|
| 265 | that are described in the following sections. The <tt>vertex_descriptor</tt> |
|---|
| 266 | type is obtained through the <tt>graph_traits</tt> class. The <tt>typename</tt> |
|---|
| 267 | keyword used below is necessary because the type on the left hand side of the |
|---|
| 268 | scope <tt>::</tt> operator (the <tt>graph_traits<Graph></tt> type) is |
|---|
| 269 | dependent on a template parameter (the <tt>Graph</tt> type). Here is how we |
|---|
| 270 | define the functor's apply method: |
|---|
| 271 | <p> |
|---|
| 272 | <pre> |
|---|
| 273 | template <class Graph> struct exercise_vertex { |
|---|
| 274 | //... |
|---|
| 275 | typedef typename graph_traits<Graph> |
|---|
| 276 | ::vertex_descriptor Vertex; |
|---|
| 277 | |
|---|
| 278 | void operator()(const Vertex& v) const |
|---|
| 279 | { |
|---|
| 280 | //... |
|---|
| 281 | } |
|---|
| 282 | //... |
|---|
| 283 | }; |
|---|
| 284 | </pre> |
|---|
| 285 | <p> |
|---|
| 286 | <h3>Out-Edges, In-Edges, and Edge Descriptors</h3> |
|---|
| 287 | <p>The out-edges of a vertex are accessed with the <a href="IncidenceGraph.html#sec:out-edges"><tt>out_edges()</tt></a> |
|---|
| 288 | function of the <a href="IncidenceGraph.html">IncidenceGraph</a> interface. The <tt>out_edges()</tt> |
|---|
| 289 | function takes two arguments: the first argument is the vertex and the second is |
|---|
| 290 | the graph object. The function returns a pair of iterators which provide access |
|---|
| 291 | to all of the out-edges of a vertex (similar to how the <tt>vertices()</tt> |
|---|
| 292 | function returned a pair of iterators). The iterators are called <i>out-edge |
|---|
| 293 | iterators</i> and dereferencing one of these iterators gives an <i>edge |
|---|
| 294 | descriptor</i> object. An edge descriptor plays the same kind of role as the |
|---|
| 295 | vertex descriptor object, it is a "black box" provided by the graph |
|---|
| 296 | type. The following code snippet prints the source-target pairs for each |
|---|
| 297 | out-edge of vertex <tt>v</tt>. |
|---|
| 298 | <p> |
|---|
| 299 | <pre> |
|---|
| 300 | template <class Graph> struct exercise_vertex { |
|---|
| 301 | //... |
|---|
| 302 | void operator()(const Vertex& v) const |
|---|
| 303 | { |
|---|
| 304 | typedef graph_traits<Graph> GraphTraits; |
|---|
| 305 | typename property_map<Graph, vertex_index_t>::type |
|---|
| 306 | index = get(vertex_index, g); |
|---|
| 307 | |
|---|
| 308 | std::cout << "out-edges: "; |
|---|
| 309 | typename GraphTraits::out_edge_iterator out_i, out_end; |
|---|
| 310 | typename GraphTraits::edge_descriptor e; |
|---|
| 311 | for (tie(out_i, out_end) = out_edges(v, g); |
|---|
| 312 | out_i != out_end; ++out_i) { |
|---|
| 313 | e = *out_i; |
|---|
| 314 | Vertex src = source(e, g), targ = target(e, g); |
|---|
| 315 | std::cout << "(" << index[src] << "," |
|---|
| 316 | << index[targ] << ") "; |
|---|
| 317 | } |
|---|
| 318 | std::cout << std::endl; |
|---|
| 319 | //... |
|---|
| 320 | } |
|---|
| 321 | //... |
|---|
| 322 | }; |
|---|
| 323 | </pre> |
|---|
| 324 | For vertex 0 the output is: |
|---|
| 325 | <pre> |
|---|
| 326 | out-edges: (0,1) (0,2) (0,3) (0,4) |
|---|
| 327 | </pre> |
|---|
| 328 | <p>The <a href="BidirectionalGraph.html#sec:in-edges"><tt>in_edges()</tt></a> |
|---|
| 329 | function of the <a href="BidirectionalGraph.html">BidirectionalGraph</a> |
|---|
| 330 | interface provides access to all the in-edges of a vertex through <i>in-edge |
|---|
| 331 | iterators</i>. The <tt>in_edges()</tt> function is only available for the <tt>adjacency_list</tt> |
|---|
| 332 | if <tt>bidirectionalS</tt> is supplied for the <tt>Directed</tt> template |
|---|
| 333 | parameter. There is an extra cost in space when <tt>bidirectionalS</tt> is |
|---|
| 334 | specified instead of <tt>directedS</tt>. |
|---|
| 335 | <p> |
|---|
| 336 | <pre> |
|---|
| 337 | template <class Graph> struct exercise_vertex { |
|---|
| 338 | //... |
|---|
| 339 | void operator()(const Vertex& v) const |
|---|
| 340 | { |
|---|
| 341 | //... |
|---|
| 342 | std::cout << "in-edges: "; |
|---|
| 343 | typedef typename graph_traits<Graph> GraphTraits; |
|---|
| 344 | typename GraphTraits::in_edge_iterator in_i, in_end; |
|---|
| 345 | for (tie(in_i, in_end) = in_edges(v,g); |
|---|
| 346 | in_i != in_end; ++in_i) { |
|---|
| 347 | e = *in_i; |
|---|
| 348 | Vertex src = source(e, g), targ = target(e, g); |
|---|
| 349 | std::cout << "(" << index[src] << "," << index[targ] << ") "; |
|---|
| 350 | } |
|---|
| 351 | std::cout << std::endl; |
|---|
| 352 | //... |
|---|
| 353 | } |
|---|
| 354 | //... |
|---|
| 355 | }; |
|---|
| 356 | </pre> |
|---|
| 357 | For vertex 0 the output is: |
|---|
| 358 | <pre> |
|---|
| 359 | in-edges: (2,0) (3,0) (4,0) |
|---|
| 360 | </pre> |
|---|
| 361 | <p> |
|---|
| 362 | <h3>Adjacent Vertices</h3> |
|---|
| 363 | <p>Given the out-edges of a vertex, the target vertices of these edges are <i>adjacent</i> |
|---|
| 364 | to the source vertex. Sometimes an algorithm does not need to look at the edges |
|---|
| 365 | of the graph and only cares about the vertices. Therefore the graph interface |
|---|
| 366 | also includes the <a href="AdjacencyGraph.html#sec:adjacent-vertices"><tt>adjacent_vertices()</tt></a> |
|---|
| 367 | function of the <a href="AdjacencyGraph.html">AdjacencyGraph</a> interface which |
|---|
| 368 | provides direct access to the adjacent vertices. This function returns a pair of |
|---|
| 369 | <i>adjacency iterators</i>. Dereferencing an adjacency iterator gives a vertex |
|---|
| 370 | descriptor for an adjacent vertex. |
|---|
| 371 | <p> |
|---|
| 372 | <pre> |
|---|
| 373 | template <class Graph> struct exercise_vertex { |
|---|
| 374 | //... |
|---|
| 375 | void operator()(Vertex v) const |
|---|
| 376 | { |
|---|
| 377 | //... |
|---|
| 378 | std::cout << "adjacent vertices: "; |
|---|
| 379 | typename graph_traits<Graph>::adjacency_iterator ai; |
|---|
| 380 | typename graph_traits<Graph>::adjacency_iterator ai_end; |
|---|
| 381 | for (tie(ai, ai_end) = adjacent_vertices(v, g); |
|---|
| 382 | ai != ai_end; ++ai) |
|---|
| 383 | std::cout << index[*ai] << " "; |
|---|
| 384 | std::cout << std::endl; |
|---|
| 385 | } |
|---|
| 386 | //... |
|---|
| 387 | }; |
|---|
| 388 | </pre> |
|---|
| 389 | For vertex 4 the output is: |
|---|
| 390 | <pre> |
|---|
| 391 | adjacent vertices: 0 1 |
|---|
| 392 | </pre> |
|---|
| 393 | <p> |
|---|
| 394 | <h2>Adding Some Color to your Graph</h2> |
|---|
| 395 | <p>BGL attempts to be as flexible as possible in terms of accommodating how |
|---|
| 396 | properties are attached to a graph. For instance, a property such as edge weight |
|---|
| 397 | may need to be used throughout a graph object's lifespan and therefore it would |
|---|
| 398 | be convenient to have the graph object also manage the property storage. On the |
|---|
| 399 | other hand, a property like vertex color may only be needed for the duration of |
|---|
| 400 | a single algorithm, and it would be better to have the property stored |
|---|
| 401 | separately from the graph object. The first kind of property is called an <i>internally |
|---|
| 402 | stored property</i> while the second kind is called an <i>externally stored |
|---|
| 403 | property</i>. BGL uses a uniform mechanism to access both kinds of properties |
|---|
| 404 | inside its graph algorithms called the <i>property map</i> interface, described |
|---|
| 405 | in Section <a href="property_map.html">Property Map Concepts</a>. In addition, |
|---|
| 406 | the <a href="PropertyGraph.html">PropertyGraph</a> concept defines the interface |
|---|
| 407 | for obtaining a property map object for an internally stored property. |
|---|
| 408 | <p>The BGL <tt>adjacency_list</tt> class allows users to specify internally |
|---|
| 409 | stored properties through plug-in template parameters of the graph class. How to |
|---|
| 410 | do this is discussed in detail in Section <a href="using_adjacency_list.html#sec:adjacency-list-properties">Internal |
|---|
| 411 | Properties</a>. Externally stored properties can be created in many different |
|---|
| 412 | ways, although they are ultimately passed as separate arguments to the graph |
|---|
| 413 | algorithms. One straightforward way to store properties is to create an array |
|---|
| 414 | indexed by vertex or edge index. In the <tt>adjacency_list</tt> with <tt>vecS</tt> |
|---|
| 415 | specified for the <tt>VertexList</tt> template parameter, vertices are |
|---|
| 416 | automatically assigned indices, which can be accessed via the property map for |
|---|
| 417 | the <tt>vertex_index_t</tt>. Edges are not automatically assigned indices. |
|---|
| 418 | However the property mechanism can be used to attach indices to the edges which |
|---|
| 419 | can be used to index into other externally stored properties. |
|---|
| 420 | <p>In the following example, we construct a graph and apply <a href="dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths()</tt></a>. |
|---|
| 421 | The complete source code for the example is in <a href="../example/dijkstra-example.cpp"><tt>examples/dijkstra-example.cpp</tt></a>. |
|---|
| 422 | Dijkstra's algorithm computes the shortest distance from the starting vertex to |
|---|
| 423 | every other vertex in the graph. |
|---|
| 424 | <p>Dijkstra's algorithm requires that a weight property is associated with each |
|---|
| 425 | edge and a distance property with each vertex. Here we use an internal property |
|---|
| 426 | for the weight and an external property for the distance. For the weight |
|---|
| 427 | property we use the <tt>property</tt> class and specify <tt>int</tt> as the type |
|---|
| 428 | used to represent weight values and <tt>edge_weight_t</tt> for the property tag |
|---|
| 429 | (which is one of the BGL predefined property tags). The weight property is then |
|---|
| 430 | used as a template argument for <tt>adjacency_list</tt>. |
|---|
| 431 | <p>The <tt>listS</tt> and <tt>vecS</tt> types are selectors that determine the |
|---|
| 432 | data structure used inside the <tt>adjacency_list</tt> (see Section <a href="using_adjacency_list.html#sec:choosing-graph-type">Choosing |
|---|
| 433 | the <tt>Edgelist</tt> and <tt>VertexList</tt></a>). The <tt>directedS</tt> type |
|---|
| 434 | specifies that the graph should be directed (versus undirected). The following |
|---|
| 435 | code shows the specification of the graph type and then the initialization of |
|---|
| 436 | the graph. The edges and weights are passed to the graph constructor in the form |
|---|
| 437 | of iterators (a pointer qualifies as a <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>). |
|---|
| 438 | <p> |
|---|
| 439 | <pre> |
|---|
| 440 | typedef adjacency_list<listS, vecS, directedS, |
|---|
| 441 | no_property, property<edge_weight_t, int> > Graph; |
|---|
| 442 | typedef graph_traits<Graph>::vertex_descriptor Vertex; |
|---|
| 443 | typedef std::pair<int,int> E; |
|---|
| 444 | |
|---|
| 445 | const int num_nodes = 5; |
|---|
| 446 | E edges[] = { E(0,2), |
|---|
| 447 | E(1,1), E(1,3), E(1,4), |
|---|
| 448 | E(2,1), E(2,3), |
|---|
| 449 | E(3,4), |
|---|
| 450 | E(4,0), E(4,1) }; |
|---|
| 451 | int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1}; |
|---|
| 452 | |
|---|
| 453 | Graph G(edges + sizeof(edges) / sizeof(E), weights, num_nodes); |
|---|
| 454 | </pre> |
|---|
| 455 | <p>For the external distance property we will use a <tt>std::vector</tt> for |
|---|
| 456 | storage. BGL algorithms treat random access iterators as property maps, so we |
|---|
| 457 | can just pass the beginning iterator of the distance vector to Dijkstra's |
|---|
| 458 | algorithm. Continuing the above example, the following code shows the creation |
|---|
| 459 | of the distance vector, the call to Dijkstra's algorithm (implicitly using the |
|---|
| 460 | internal edge weight property), and then the output of the results. |
|---|
| 461 | <p> |
|---|
| 462 | <pre> |
|---|
| 463 | // vector for storing distance property |
|---|
| 464 | std::vector<int> d(num_vertices(G)); |
|---|
| 465 | |
|---|
| 466 | // get the first vertex |
|---|
| 467 | Vertex s = *(vertices(G).first); |
|---|
| 468 | // invoke variant 2 of Dijkstra's algorithm |
|---|
| 469 | dijkstra_shortest_paths(G, s, distance_map(&d[0])); |
|---|
| 470 | |
|---|
| 471 | std::cout << "distances from start vertex:" << std::endl; |
|---|
| 472 | graph_traits<Graph>::vertex_iterator vi; |
|---|
| 473 | for(vi = vertices(G).first; vi != vertices(G).second; ++vi) |
|---|
| 474 | std::cout << "distance(" << index(*vi) << ") = " |
|---|
| 475 | << d[*vi] << std::endl; |
|---|
| 476 | std::cout << std::endl; |
|---|
| 477 | </pre> |
|---|
| 478 | The output is: |
|---|
| 479 | <pre> |
|---|
| 480 | distances from start vertex: |
|---|
| 481 | distance(0) = 0 |
|---|
| 482 | distance(1) = 6 |
|---|
| 483 | distance(2) = 1 |
|---|
| 484 | distance(3) = 4 |
|---|
| 485 | distance(4) = 5 |
|---|
| 486 | </pre> |
|---|
| 487 | <p> |
|---|
| 488 | <h2>Extending Algorithms with Visitors</h2> |
|---|
| 489 | <p>Often times an algorithm in a library <i>almost</i> does what you need, but |
|---|
| 490 | not quite. For example, in the previous section we used Dijkstra's algorithm to |
|---|
| 491 | calculate the shortest distances to each vertex, but perhaps we also wanted to |
|---|
| 492 | record the tree of shortest paths. One way to do this is to record the |
|---|
| 493 | predecessor (parent) for each node in the shortest-paths tree. |
|---|
| 494 | <p>It would be nice if we could avoid rewriting Dijkstra's algorithm, and just |
|---|
| 495 | add that little bit extra needed to record the predecessors <a href="#1">[1]</a>. In the STL, this |
|---|
| 496 | kind of extensibility is provided by functors, which are optional parameters to |
|---|
| 497 | each algorithm. In the BGL this role is fulfilled by <i>visitors</i>. |
|---|
| 498 | <p>A visitor is like a functor, but instead of having just one "apply" |
|---|
| 499 | method, it has several. Each of these methods get invoked at certain |
|---|
| 500 | well-defined points within the algorithm. The visitor methods are explained in |
|---|
| 501 | detail in Section <a href="visitor_concepts.html">Visitor Concepts</a>. The BGL |
|---|
| 502 | provides a number of visitors for some common tasks including a predecessor |
|---|
| 503 | recording visitor. The user is encouraged to write his or her own visitors as a |
|---|
| 504 | way of extending the BGL. Here we will take a quick look at the implementation |
|---|
| 505 | and use of the predecessor recorder. Since we will be using the <a href="dijkstra_shortest_paths.html">dijkstra_shortest_paths()</a> |
|---|
| 506 | algorithm, the visitor we create must be a <a href="DijkstraVisitor.html">Dijkstra Visitor</a>. |
|---|
| 507 | <p>The functionality of the <tt>record_predecessors</tt> visitor is separated |
|---|
| 508 | into two parts. For the storage and access of the predecessor property, we will |
|---|
| 509 | use a <a href="../../property_map/property_map.html">property map</a>. The |
|---|
| 510 | predecessor visitor will then only be responsible for what parent to record. To |
|---|
| 511 | implement this, we create a <tt>record_predecessors</tt> class and template it |
|---|
| 512 | on the predecessor property map <tt>PredecessorMap</tt>. Since this visitor will |
|---|
| 513 | only be filling in one of the visitor methods, we will inherit from <a href="dijkstra_visitor.html"><tt>dijkstra_visitor</tt></a> |
|---|
| 514 | which will provide empty methods for the rest. The constructor of the <tt>predecessor_recorder</tt> |
|---|
| 515 | will take the property map object and save it away in a data member. |
|---|
| 516 | <p> |
|---|
| 517 | <pre> |
|---|
| 518 | template <class PredecessorMap> |
|---|
| 519 | class record_predecessors : public dijkstra_visitor<> |
|---|
| 520 | { |
|---|
| 521 | public: |
|---|
| 522 | record_predecessors(PredecessorMap p) |
|---|
| 523 | : m_predecessor(p) { } |
|---|
| 524 | |
|---|
| 525 | template <class Edge, class Graph> |
|---|
| 526 | void edge_relaxed(Edge e, Graph& g) { |
|---|
| 527 | // set the parent of the target(e) to source(e) |
|---|
| 528 | put(m_predecessor, target(e, g), source(e, g)); |
|---|
| 529 | } |
|---|
| 530 | protected: |
|---|
| 531 | PredecessorMap m_predecessor; |
|---|
| 532 | }; |
|---|
| 533 | </pre> |
|---|
| 534 | <p>The job of recording the predecessors is quite simple. When Dijkstra's |
|---|
| 535 | algorithm relaxes an edge (potentially adding it to the shortest-paths tree) we |
|---|
| 536 | record the source vertex as the predecessor of the target vertex. Later, if the |
|---|
| 537 | edge is relaxed again the predecessor property will be overwritten by the new |
|---|
| 538 | predecessor. Here we use the <tt>put()</tt> function associated with the |
|---|
| 539 | property map to record the predecessor. The <tt>edge_filter</tt> of the visitor |
|---|
| 540 | tells the algorithm when to invoke the <tt>explore()</tt> method. In this case |
|---|
| 541 | we only want to be notified about edges in the shortest-paths tree so we specify |
|---|
| 542 | <tt>tree_edge_tag</tt>. |
|---|
| 543 | <p>As a finishing touch, we create a helper function to make it more convenient |
|---|
| 544 | to create predecessor visitors. All BGL visitors have a helper function like |
|---|
| 545 | this. |
|---|
| 546 | <p> |
|---|
| 547 | <pre> |
|---|
| 548 | template <class PredecessorMap> |
|---|
| 549 | record_predecessors<PredecessorMap> |
|---|
| 550 | make_predecessor_recorder(PredecessorMap p) { |
|---|
| 551 | return record_predecessors<PredecessorMap>(p); |
|---|
| 552 | } |
|---|
| 553 | </pre> |
|---|
| 554 | <p>We are now ready to use the <tt>record_predecessors</tt> in |
|---|
| 555 | Dijkstra's algorithm. Luckily, BGL's Dijkstra's algorithm is already |
|---|
| 556 | equipped to handle visitors, so we just pass in our new visitor. In |
|---|
| 557 | this example we only need to use one visitor, but the BGL is also |
|---|
| 558 | equipped to handle the use of multiple visitors in the same algorithm |
|---|
| 559 | (see Section <a href="visitor_concepts.html">Visitor Concepts</a>). |
|---|
| 560 | <p> |
|---|
| 561 | <pre> |
|---|
| 562 | using std::vector; |
|---|
| 563 | using std::cout; |
|---|
| 564 | using std::endl; |
|---|
| 565 | vector<Vertex> p(num_vertices(G)); //the predecessor array |
|---|
| 566 | dijkstra_shortest_paths(G, s, distance_map(&d[0]). |
|---|
| 567 | visitor(make_predecessor_recorder(&p[0]))); |
|---|
| 568 | |
|---|
| 569 | cout << "parents in the tree of shortest paths:" << endl; |
|---|
| 570 | for(vi = vertices(G).first; vi != vertices(G).second; ++vi) { |
|---|
| 571 | cout << "parent(" << *vi; |
|---|
| 572 | if (p[*vi] == Vertex()) |
|---|
| 573 | cout << ") = no parent" << endl; |
|---|
| 574 | else |
|---|
| 575 | cout << ") = " << p[*vi] << endl; |
|---|
| 576 | } |
|---|
| 577 | </pre> |
|---|
| 578 | The output is: |
|---|
| 579 | <pre> |
|---|
| 580 | parents in the tree of shortest paths: |
|---|
| 581 | parent(0) = no parent |
|---|
| 582 | parent(1) = 4 |
|---|
| 583 | parent(2) = 0 |
|---|
| 584 | parent(3) = 2 |
|---|
| 585 | parent(4) = 3 |
|---|
| 586 | </pre> |
|---|
| 587 | |
|---|
| 588 | <br> |
|---|
| 589 | |
|---|
| 590 | <h3>Notes</h3> |
|---|
| 591 | |
|---|
| 592 | <a name="1">[1]</a> The new version of Dijkstra's algorithm now includes |
|---|
| 593 | a named parameter for recording predecessors, so a predecessor visitor |
|---|
| 594 | is no long necessary, though this still makes for a good example. |
|---|
| 595 | |
|---|
| 596 | <br> |
|---|
| 597 | <hr> |
|---|
| 598 | <table> |
|---|
| 599 | <tr valign="top"> |
|---|
| 600 | <td nowrap>Copyright © 2000</td> |
|---|
| 601 | <td><a href="../../../people/jeremy_siek.htm">Jeremy Siek</a>, |
|---|
| 602 | Indiana University (<a href="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>)</td> |
|---|
| 603 | </tr> |
|---|
| 604 | </table> |
|---|
| 605 | |
|---|
| 606 | </body> |
|---|
| 607 | |
|---|
| 608 | </html> |
|---|
| 609 | <!-- LocalWords: STL BGL cpp vecS bidirectionalS directedS undirectedS hpp vp |
|---|
| 610 | --> |
|---|
| 611 | <!-- LocalWords: iostream namespace int const num sizeof map ID's gif typedef |
|---|
| 612 | --> |
|---|
| 613 | <!-- LocalWords: iter ei interoperability struct typename GraphTraits src ai |
|---|
| 614 | --> |
|---|
| 615 | <!-- LocalWords: targ PropertyGraph Properties property iterator iterators |
|---|
| 616 | --> |
|---|
| 617 | <!-- LocalWords: VertexList dijkstra listS Edgelist RandomAccessIterator cout |
|---|
| 618 | --> |
|---|
| 619 | <!-- LocalWords: weightp adjacency tradeoffs undirected MutableGraph indices |
|---|
| 620 | --> |
|---|
| 621 | <!-- LocalWords: VertexListGraph Dereferencing IndexMap EdgeListGraph functor |
|---|
| 622 | --> |
|---|
| 623 | <!-- LocalWords: functor's IncidenceGraph dereferencing BidirectionalGraph |
|---|
| 624 | --> |
|---|
| 625 | <!-- LocalWords: AdjacencyGraph Dijkstra's extensibility functors BGL's endl |
|---|
| 626 | --> |
|---|
| 627 | <!-- LocalWords: DijkstraVisitor PredecessorMap siek htm Univ Notre |
|---|
| 628 | --> |
|---|
