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