ceph/src/boost/libs/graph/doc/quick_tour.html

   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
  22 complicated than that of containers. The abstract iterator interface used by STL
  23 is not sufficiently rich to encompass the numerous ways that graph algorithms
  24 may traverse a graph. Instead, we formulate an abstract interface that serves
  25 the same purpose for graphs that iterators do for basic containers (though
  26 iterators still play a large role). <a href="#fig:analogy">Figure 1</a> depicts
  27 the analogy between the STL and the BGL.
  28 <p>&nbsp;</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>&nbsp;</p>
  40 The graph abstraction consists of a set of vertices (or nodes), and a set of
  41 edges (or arcs) that connect the vertices. <a href="#fig:quick-start">Figure 2</a>
  42 depicts a directed graph with five vertices (labeled 0 through 4) and 11 edges.
  43 The edges leaving a vertex are called the <i>out-edges</i> of the vertex. The
  44 edges <tt>{(0,1),(0,2),(0,3),(0,4)}</tt> are all out-edges of vertex 0. The
  45 edges entering a vertex are called the <i>in-edges</i> of the vertex. The edges <tt>{(0,4),(2,4),(3,4)}</tt>
  46 are all in-edges of vertex 4.
  47 <p>&nbsp;</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>&nbsp;</p>
  59 <p>In the following sections we will use the BGL to construct this example graph
  60 and manipulate it in various ways. The complete source code for this example can
  61 be found in <a href="../example/quick_tour.cpp"><tt>examples/quick_tour.cpp</tt></a>.
  62 Each of the following sections discusses a &quot;slice&quot; of this example
  63 file. Excerpts from the output of the example program will also be listed.
  64 <p>&nbsp;
  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>
  67 class to demonstrate the main ideas in the BGL interface. The <tt>adjacency_list</tt>
  68 class provides a generalized version of the classic &quot;adjacency list&quot;
  69 data structure. The <tt>adjacency_list</tt> is a template class with six
  70 template parameters, though here we only fill in the first three parameters and
  71 use the defaults for the remaining three. The first two template arguments (<tt>vecS,
  72 vecS</tt>) determine the data structure used to represent the out-edges for each
  73 vertex in the graph and the data structure used to represent the graph's vertex
  74 set (see section <a href="using_adjacency_list.html#sec:choosing-graph-type">Choosing
  75 the <tt>Edgelist</tt> and <tt>VertexList</tt></a> for information about the
  76 tradeoffs of the different data structures). The third argument, <tt>bidirectionalS</tt>,
  77 selects a directed graph that provides access to both out and in-edges. The
  78 other options for the third argument are <tt>directedS</tt> which selects a
  79 directed graph with only out-edges, and <tt>undirectedS</tt> which selects an
  80 undirected graph.
  81 <p>Once we have the graph type selected, we can create the graph in <a href="#fig:quick-start">Figure
  82 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>
  83 function of the <a href="MutableGraph.html">MutableGraph</a> interface (which <tt>adjacency_list</tt>
  84 implements). We use the array of pairs <tt>edge_array</tt> merely as a
  85 convenient way to explicitly create the edges for this example.
  86 <p>&nbsp;
  87 <pre>
  88   #include &lt;iostream&gt;                  // for std::cout
  89   #include &lt;utility&gt;                   // for std::pair
  90   #include &lt;algorithm&gt;                 // for std::for_each
  91   #include &lt;boost/graph/graph_traits.hpp&gt;
  92   #include &lt;boost/graph/adjacency_list.hpp&gt;
  93   #include &lt;boost/graph/dijkstra_shortest_paths.hpp&gt;
  94
  95   using namespace boost;
  96
  97   int main(int,char*[])
  98   {
  99     // create a typedef for the Graph type
 100     typedef adjacency_list&lt;vecS, vecS, bidirectionalS&gt; 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&lt;int, int&gt; 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 &lt; 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
 125 use the <a href="adjacency_list.html#sec:iterator-constructor">edge iterator
 126 constructor</a> of the graph. This is typically more efficient than using <tt>add_edge()</tt>.
 127 Pointers to the <tt>edge_array</tt> can be viewed as iterators, so we can call
 128 the iterator constructor by passing pointers to the beginning and end of the
 129 array.
 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,
 134 it is also possible to add and remove vertices with the <a href="MutableGraph.html#sec:add-vertex"><tt>add_vertex()</tt></a>
 135 and <a href="MutableGraph.html#sec:remove-vertex"><tt>remove_vertex()</tt></a>
 136 functions, 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
 139 the graph data in different ways. First we can access all of the vertices in the
 140 graph using the <a href="VertexListGraph.html#sec:vertices"><tt>vertices()</tt></a>
 141 function of the <a href="VertexListGraph.html">VertexListGraph</a> interface.
 142 This function returns a <tt>std::pair</tt> of <i>vertex iterators</i> (the <tt>first</tt>
 143 iterator points to the &quot;beginning&quot; of the vertices and the <tt>second</tt>
 144 iterator points &quot;past the end&quot;). Dereferencing a vertex iterator gives
 145 a vertex object. The type of the vertex iterator is given by the <a href="graph_traits.html"><tt>graph_traits</tt></a>
 146 class. Note that different graph classes can have different associated vertex
 147 iterator types, which is why we need the <tt>graph_traits</tt> class. Given some
 148 graph type, the <tt>graph_traits</tt> class will provide access to the <tt>vertex_iterator</tt>
 149 type.
 150 <p>The following example prints out the index for each of the vertices in the
 151 graph. All vertex and edge properties, including index, are accessed via
 152 property map objects. The <a href="property_map.html"><tt>property_map</tt></a>
 153 class is used to obtain the property map type for a specific property (specified
 154 by <tt>vertex_index_t</tt>, one of the BGL predefined properties) and function
 155 call <tt>get(vertex_index, g)</tt> returns the actual property map object.
 156 <p>&nbsp;
 157 <pre>
 158   // ...
 159   int main(int,char*[])
 160   {
 161     // ...
 162
 163     typedef graph_traits&lt;Graph&gt;::vertex_descriptor Vertex;
 164
 165     // get the property map for vertex indices
 166     typedef property_map&lt;Graph, vertex_index_t&gt;::type IndexMap;
 167     IndexMap index = get(vertex_index, g);
 168
 169     std::cout &lt;&lt; &quot;vertices(g) = &quot;;
 170     typedef graph_traits&lt;Graph&gt;::vertex_iterator vertex_iter;
 171     std::pair&lt;vertex_iter, vertex_iter&gt; vp;
 172     for (vp = vertices(g); vp.first != vp.second; ++vp.first) {
 173       Vertex v = *vp.first;
 174       std::cout &lt;&lt; index[v] &lt;&lt;  &quot; &quot;;
 175     }
 176     std::cout &lt;&lt; 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>&nbsp;
 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>boost::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>&nbsp;
 200 <pre>
 201   // ...
 202   int main(int,char*[])
 203   {
 204     // ...
 205     std::cout &lt;&lt; &quot;edges(g) = &quot;;
 206     graph_traits&lt;Graph&gt;::edge_iterator ei, ei_end;
 207     for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
 208         std::cout &lt;&lt; &quot;(&quot; &lt;&lt; index[source(*ei, g)]
 209                   &lt;&lt; &quot;,&quot; &lt;&lt; index[target(*ei, g)] &lt;&lt; &quot;) &quot;;
 210     std::cout &lt;&lt; std::endl;
 211     // ...
 212     return 0;
 213   }
 214 </pre>
 215 The 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>&nbsp;
 220 <h2>The Adjacency Structure</h2>
 221 <p>In the next few examples we will explore the adjacency structure of the graph
 222 from the point of view of a particular vertex. We will look at the vertices'
 223 in-edges, out-edges, and its adjacent vertices. We will encapsulate this in an
 224 &quot;exercise vertex&quot; function, and apply it to each vertex in the graph.
 225 To demonstrate the STL-interoperability of BGL, we will use the STL <tt>for_each()</tt>
 226 function to iterate through the vertices and apply the function.
 227 <p>&nbsp;
 228 <pre>
 229   //...
 230   int main(int,char*[])
 231   {
 232     //...
 233     std::for_each(vertices(g).first, vertices(g).second,
 234                   exercise_vertex&lt;Graph&gt;(g));
 235     return 0;
 236   }
 237 </pre>
 238 <p>We use a functor for <tt>exercise_vertex</tt> instead of just a function
 239 because the graph object will be needed when we access information about each
 240 vertex; using a functor gives us a place to keep a reference to the graph object
 241 during the execution of the <tt>std::for_each()</tt>. Also we template the
 242 functor on the graph type so that it is reusable with different graph classes.
 243 Here is the start of the <tt>exercise_vertex</tt> functor:
 244 <p>&nbsp;
 245 <pre>
 246   template &lt;class Graph&gt; struct exercise_vertex {
 247     exercise_vertex(Graph&amp; g_) : g(g_) {}
 248     //...
 249     Graph&amp; g;
 250   };
 251 </pre>
 252 <p>&nbsp;
 253 <h3>Vertex Descriptors</h3>
 254 <p>The first thing we need to know in order to write the <tt>operator()</tt>
 255 method of the functor is the type for the vertex objects of the graph. The
 256 vertex type will be the parameter to the <tt>operator()</tt> method. To be
 257 precise, we do not deal with actual vertex objects, but rather with <i>vertex
 258 descriptors</i>. Many graph representations (such as adjacency lists) do not
 259 store actual vertex objects, while others do (e.g., pointer-linked graphs). This
 260 difference is hidden underneath the &quot;black-box&quot; of the vertex
 261 descriptor object. The vertex descriptor is something provided by each graph
 262 type 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
 264 that are described in the following sections. The <tt>vertex_descriptor</tt>
 265 type is obtained through the <tt>graph_traits</tt> class. The <tt>typename</tt>
 266 keyword used below is necessary because the type on the left hand side of the
 267 scope <tt>::</tt> operator (the <tt>graph_traits&lt;Graph&gt;</tt> type) is
 268 dependent on a template parameter (the <tt>Graph</tt> type). Here is how we
 269 define the functor's apply method:
 270 <p>&nbsp;
 271 <pre>
 272   template &lt;class Graph&gt; struct exercise_vertex {
 273     //...
 274     typedef typename graph_traits&lt;Graph&gt;
 275       ::vertex_descriptor Vertex;
 276
 277     void operator()(const Vertex&amp; v) const
 278     {
 279       //...
 280     }
 281     //...
 282   };
 283 </pre>
 284 <p>&nbsp;
 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>
 287 function of the <a href="IncidenceGraph.html">IncidenceGraph</a> interface. The <tt>out_edges()</tt>
 288 function takes two arguments: the first argument is the vertex and the second is
 289 the graph object. The function returns a pair of iterators which provide access
 290 to all of the out-edges of a vertex (similar to how the <tt>vertices()</tt>
 291 function returned a pair of iterators). The iterators are called <i>out-edge
 292 iterators</i> and dereferencing one of these iterators gives an <i>edge
 293 descriptor</i> object. An edge descriptor plays the same kind of role as the
 294 vertex descriptor object, it is a &quot;black box&quot; provided by the graph
 295 type. The following code snippet prints the source-target pairs for each
 296 out-edge of vertex <tt>v</tt>.
 297 <p>&nbsp;
 298 <pre>
 299   template &lt;class Graph&gt; struct exercise_vertex {
 300     //...
 301     void operator()(const Vertex&amp; v) const
 302     {
 303       typedef graph_traits&lt;Graph&gt; GraphTraits;
 304       typename property_map&lt;Graph, vertex_index_t&gt;::type
 305         index = get(vertex_index, g);
 306
 307       std::cout &lt;&lt; &quot;out-edges: &quot;;
 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 &lt;&lt; &quot;(&quot; &lt;&lt; index[src] &lt;&lt; &quot;,&quot;
 315                   &lt;&lt; index[targ] &lt;&lt; &quot;) &quot;;
 316       }
 317       std::cout &lt;&lt; std::endl;
 318       //...
 319     }
 320     //...
 321   };
 322 </pre>
 323 For 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>
 328 function of the <a href="BidirectionalGraph.html">BidirectionalGraph</a>
 329 interface provides access to all the in-edges of a vertex through <i>in-edge
 330 iterators</i>. The <tt>in_edges()</tt> function is only available for the <tt>adjacency_list</tt>
 331 if <tt>bidirectionalS</tt> is supplied for the <tt>Directed</tt> template
 332 parameter. There is an extra cost in space when <tt>bidirectionalS</tt> is
 333 specified instead of <tt>directedS</tt>.
 334 <p>&nbsp;
 335 <pre>
 336   template &lt;class Graph&gt; struct exercise_vertex {
 337     //...
 338     void operator()(const Vertex&amp; v) const
 339     {
 340       //...
 341       std::cout &lt;&lt; &quot;in-edges: &quot;;
 342       typedef typename graph_traits&lt;Graph&gt; 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 &lt;&lt; &quot;(&quot; &lt;&lt; index[src] &lt;&lt; &quot;,&quot; &lt;&lt; index[targ] &lt;&lt; &quot;) &quot;;
 349       }
 350       std::cout &lt;&lt; std::endl;
 351       //...
 352     }
 353     //...
 354   };
 355 </pre>
 356 For vertex 0 the output is:
 357 <pre>
 358   in-edges: (2,0) (3,0) (4,0)
 359 </pre>
 360 <p>&nbsp;
 361 <h3>Adjacent Vertices</h3>
 362 <p>Given the out-edges of a vertex, the target vertices of these edges are <i>adjacent</i>
 363 to the source vertex. Sometimes an algorithm does not need to look at the edges
 364 of the graph and only cares about the vertices. Therefore the graph interface
 365 also includes the <a href="AdjacencyGraph.html#sec:adjacent-vertices"><tt>adjacent_vertices()</tt></a>
 366 function of the <a href="AdjacencyGraph.html">AdjacencyGraph</a> interface which
 367 provides direct access to the adjacent vertices. This function returns a pair of
 368 <i>adjacency iterators</i>. Dereferencing an adjacency iterator gives a vertex
 369 descriptor for an adjacent vertex.
 370 <p>&nbsp;
 371 <pre>
 372   template &lt;class Graph&gt; struct exercise_vertex {
 373     //...
 374     void operator()(Vertex v) const
 375     {
 376       //...
 377       std::cout &lt;&lt; &quot;adjacent vertices: &quot;;
 378       typename graph_traits&lt;Graph&gt;::adjacency_iterator ai;
 379       typename graph_traits&lt;Graph&gt;::adjacency_iterator ai_end;
 380       for (boost::tie(ai, ai_end) = adjacent_vertices(v, g);
 381            ai != ai_end; ++ai)
 382         std::cout &lt;&lt; index[*ai] &lt;&lt;  &quot; &quot;;
 383       std::cout &lt;&lt; std::endl;
 384     }
 385     //...
 386   };
 387 </pre>
 388 For vertex 4 the output is:
 389 <pre>
 390   adjacent vertices: 0 1
 391 </pre>
 392 <p>&nbsp;
 393 <h2>Adding Some Color to your Graph</h2>
 394 <p>BGL attempts to be as flexible as possible in terms of accommodating how
 395 properties are attached to a graph. For instance, a property such as edge weight
 396 may need to be used throughout a graph object's lifespan and therefore it would
 397 be convenient to have the graph object also manage the property storage. On the
 398 other hand, a property like vertex color may only be needed for the duration of
 399 a single algorithm, and it would be better to have the property stored
 400 separately from the graph object. The first kind of property is called an <i>internally
 401 stored property</i> while the second kind is called an <i>externally stored
 402 property</i>. BGL uses a uniform mechanism to access both kinds of properties
 403 inside its graph algorithms called the <i>property map</i> interface, described
 404 in Section <a href="property_map.html">Property Map Concepts</a>. In addition,
 405 the <a href="PropertyGraph.html">PropertyGraph</a> concept defines the interface
 406 for obtaining a property map object for an internally stored property.
 407 <p>The BGL <tt>adjacency_list</tt> class allows users to specify internally
 408 stored properties through plug-in template parameters of the graph class. How to
 409 do this is discussed in detail in Section <a href="using_adjacency_list.html#sec:adjacency-list-properties">Internal
 410 Properties</a>. Externally stored properties can be created in many different
 411 ways, although they are ultimately passed as separate arguments to the graph
 412 algorithms. One straightforward way to store properties is to create an array
 413 indexed by vertex or edge index. In the <tt>adjacency_list</tt> with <tt>vecS</tt>
 414 specified for the <tt>VertexList</tt> template parameter, vertices are
 415 automatically assigned indices, which can be accessed via the property map for
 416 the <tt>vertex_index_t</tt>. Edges are not automatically assigned indices.
 417 However the property mechanism can be used to attach indices to the edges which
 418 can 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>.
 420 The complete source code for the example is in <a href="../example/dijkstra-example.cpp"><tt>examples/dijkstra-example.cpp</tt></a>.
 421 Dijkstra's algorithm computes the shortest distance from the starting vertex to
 422 every other vertex in the graph.
 423 <p>Dijkstra's algorithm requires that a weight property is associated with each
 424 edge and a distance property with each vertex. Here we use an internal property
 425 for the weight and an external property for the distance. For the weight
 426 property we use the <tt>property</tt> class and specify <tt>int</tt> as the type
 427 used 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
 429 used 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
 431 data structure used inside the <tt>adjacency_list</tt> (see Section <a href="using_adjacency_list.html#sec:choosing-graph-type">Choosing
 432 the <tt>Edgelist</tt> and <tt>VertexList</tt></a>). The <tt>directedS</tt> type
 433 specifies that the graph should be directed (versus undirected). The following
 434 code shows the specification of the graph type and then the initialization of
 435 the graph. The edges and weights are passed to the graph constructor in the form
 436 of iterators (a pointer qualifies as a <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
 437 <p>&nbsp;
 438 <pre>
 439   typedef adjacency_list&lt;listS, vecS, directedS,
 440                          no_property, property&lt;edge_weight_t, int&gt; &gt; Graph;
 441   typedef graph_traits&lt;Graph&gt;::vertex_descriptor Vertex;
 442   typedef std::pair&lt;int,int&gt; 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
 455 storage. BGL algorithms treat random access iterators as property maps, so we
 456 can just pass the beginning iterator of the distance vector to Dijkstra's
 457 algorithm. Continuing the above example, the following code shows the creation
 458 of the distance vector, the call to Dijkstra's algorithm (implicitly using the
 459 internal edge weight property), and then the output of the results.
 460 <p>&nbsp;
 461 <pre>
 462   // vector for storing distance property
 463   std::vector&lt;int&gt; 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(&amp;d[0]));
 469
 470   std::cout &lt;&lt; &quot;distances from start vertex:&quot; &lt;&lt; std::endl;
 471   graph_traits&lt;Graph&gt;::vertex_iterator vi;
 472   for(vi = vertices(G).first; vi != vertices(G).second; ++vi)
 473     std::cout &lt;&lt; &quot;distance(&quot; &lt;&lt; index(*vi) &lt;&lt; &quot;) = &quot;
 474               &lt;&lt; d[*vi] &lt;&lt; std::endl;
 475   std::cout &lt;&lt; std::endl;
 476 </pre>
 477 The 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>&nbsp;
 487 <h2>Extending Algorithms with Visitors</h2>
 488 <p>Often times an algorithm in a library <i>almost</i> does what you need, but
 489 not quite. For example, in the previous section we used Dijkstra's algorithm to
 490 calculate the shortest distances to each vertex, but perhaps we also wanted to
 491 record the tree of shortest paths. One way to do this is to record the
 492 predecessor (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
 494 add that little bit extra needed to record the predecessors <a href="#1">[1]</a>. In the STL, this
 495 kind of extensibility is provided by functors, which are optional parameters to
 496 each 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 &quot;apply&quot;
 498 method, it has several. Each of these methods get invoked at certain
 499 well-defined points within the algorithm. The visitor methods are explained in
 500 detail in Section <a href="visitor_concepts.html">Visitor Concepts</a>. The BGL
 501 provides a number of visitors for some common tasks including a predecessor
 502 recording visitor. The user is encouraged to write his or her own visitors as a
 503 way of extending the BGL. Here we will take a quick look at the implementation
 504 and use of the predecessor recorder. Since we will be using the <a href="dijkstra_shortest_paths.html">dijkstra_shortest_paths()</a>
 505 algorithm, 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
 507 into two parts. For the storage and access of the predecessor property, we will
 508 use a <a href="../../property_map/doc/property_map.html">property map</a>. The
 509 predecessor visitor will then only be responsible for what parent to record. To
 510 implement this, we create a <tt>record_predecessors</tt> class and template it
 511 on the predecessor property map <tt>PredecessorMap</tt>. Since this visitor will
 512 only be filling in one of the visitor methods, we will inherit from <a href="dijkstra_visitor.html"><tt>dijkstra_visitor</tt></a>
 513 which will provide empty methods for the rest. The constructor of the <tt>predecessor_recorder</tt>
 514 will take the property map object and save it away in a data member.
 515 <p>&nbsp;
 516 <pre>
 517   template &lt;class PredecessorMap&gt;
 518   class record_predecessors : public dijkstra_visitor&lt;&gt;
 519   {
 520   public:
 521     record_predecessors(PredecessorMap p)
 522       : m_predecessor(p) { }
 523
 524     template &lt;class Edge, class Graph&gt;
 525     void edge_relaxed(Edge e, Graph&amp; 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
 534 algorithm relaxes an edge (potentially adding it to the shortest-paths tree) we
 535 record the source vertex as the predecessor of the target vertex. Later, if the
 536 edge is relaxed again the predecessor property will be overwritten by the new
 537 predecessor. Here we use the <tt>put()</tt> function associated with the
 538 property map to record the predecessor. The <tt>edge_filter</tt> of the visitor
 539 tells the algorithm when to invoke the <tt>explore()</tt> method. In this case
 540 we 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
 543 to create predecessor visitors. All BGL visitors have a helper function like
 544 this.
 545 <p>&nbsp;
 546 <pre>
 547   template &lt;class PredecessorMap&gt;
 548   record_predecessors&lt;PredecessorMap&gt;
 549   make_predecessor_recorder(PredecessorMap p) {
 550     return record_predecessors&lt;PredecessorMap&gt;(p);
 551   }
 552 </pre>
 553 <p>We are now ready to use the <tt>record_predecessors</tt> in
 554 Dijkstra's algorithm. Luckily, BGL's Dijkstra's algorithm is already
 555 equipped to handle visitors, so we just pass in our new visitor. In
 556 this example we only need to use one visitor, but the BGL is also
 557 equipped to handle the use of multiple visitors in the same algorithm
 558 (see Section <a href="visitor_concepts.html">Visitor Concepts</a>).
 559 <p>&nbsp;
 560 <pre>
 561   using std::vector;
 562   using std::cout;
 563   using std::endl;
 564   vector&lt;Vertex&gt; p(num_vertices(G), graph_traits&lt;G&gt;::null_vertex()); //the predecessor array
 565   dijkstra_shortest_paths(G, s, distance_map(&amp;d[0]).
 566                           visitor(make_predecessor_recorder(&amp;p[0])));
 567
 568   cout &lt;&lt; &quot;parents in the tree of shortest paths:&quot; &lt;&lt; endl;
 569   for(vi = vertices(G).first; vi != vertices(G).second; ++vi) {
 570     cout &lt;&lt; &quot;parent(&quot; &lt;&lt; *vi;
 571     if (p[*vi] == graph_traits&lt;G&gt;::null_vertex())
 572       cout &lt;&lt; &quot;) = no parent&quot; &lt;&lt; endl;
 573     else
 574       cout &lt;&lt; &quot;) = &quot; &lt;&lt; p[*vi] &lt;&lt; endl;
 575   }
 576 </pre>
 577 The 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
 592 a named parameter for recording predecessors, so a predecessor visitor
 593 is 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  -->