devn00b
/
EQ2EMu


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627
							<html>

<!--
     Copyright (c) Jeremy Siek 2000
    
     Distributed under the Boost Software License, Version 1.0.
     (See accompanying file LICENSE_1_0.txt or copy at
     http://www.boost.org/LICENSE_1_0.txt)
  -->

<head>
<title>Quick Tour of Boost Graph Library</title>
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
</head>

<body bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b" alink="#ff0000">

<img src="../../../boost.png" alt="C++ Boost" width="277" height="86"><br clear>
<h1>A Quick Tour of the Boost Graph Library</h1>
<p>The domain of graph data structures and algorithms is in some respects more
complicated than that of containers. The abstract iterator interface used by STL
is not sufficiently rich to encompass the numerous ways that graph algorithms
may traverse a graph. Instead, we formulate an abstract interface that serves
the same purpose for graphs that iterators do for basic containers (though
iterators still play a large role). <a href="#fig:analogy">Figure 1</a> depicts
the analogy between the STL and the BGL.
<p>&nbsp;</p>
<div align="CENTER">
  <a name="fig:analogy"></a><a name="752"></a>
  <table>
    <caption valign="bottom"><strong>Figure 1:</strong> The analogy between the
      STL and the BGL.</caption>
    <tr>
      <td><img src="figs/analogy.gif" width="518" height="335"></td>
    </tr>
  </table>
</div>
<p>&nbsp;</p>
The graph abstraction consists of a set of vertices (or nodes), and a set of
edges (or arcs) that connect the vertices. <a href="#fig:quick-start">Figure 2</a>
depicts a directed graph with five vertices (labeled 0 through 4) and 11 edges.
The edges leaving a vertex are called the <i>out-edges</i> of the vertex. The
edges <tt>{(0,1),(0,2),(0,3),(0,4)}</tt> are all out-edges of vertex 0. The
edges entering a vertex are called the <i>in-edges</i> of the vertex. The edges <tt>{(0,4),(2,4),(3,4)}</tt>
are all in-edges of vertex 4.
<p>&nbsp;</p>
<div align="CENTER">
  <a name="fig:quick-start"></a>
  <table>
    <caption valign="bottom"><strong>Figure 2:</strong> An example of a directed
      graph.</caption>
    <tr>
      <td><img src="figs/quick_start.gif" width="103" height="124"></td>
    </tr>
  </table>
</div>
<p>&nbsp;</p>
<p>In the following sections we will use the BGL to construct this example graph
and manipulate it in various ways. The complete source code for this example can
be found in <a href="../example/quick_tour.cpp"><tt>examples/quick_tour.cpp</tt></a>.
Each of the following sections discusses a &quot;slice&quot; of this example
file. Excerpts from the output of the example program will also be listed.
<p>&nbsp;
<h2>Constructing a Graph</h2>
<p>In this example we will use the BGL <a href="adjacency_list.html"><tt>adjacency_list</tt></a>
class to demonstrate the main ideas in the BGL interface. The <tt>adjacency_list</tt>
class provides a generalized version of the classic &quot;adjacency list&quot;
data structure. The <tt>adjacency_list</tt> is a template class with six
template parameters, though here we only fill in the first three parameters and
use the defaults for the remaining three. The first two template arguments (<tt>vecS,
vecS</tt>) determine the data structure used to represent the out-edges for each
vertex in the graph and the data structure used to represent the graph's vertex
set (see section <a href="using_adjacency_list.html#sec:choosing-graph-type">Choosing
the <tt>Edgelist</tt> and <tt>VertexList</tt></a> for information about the
tradeoffs of the different data structures). The third argument, <tt>bidirectionalS</tt>,
selects a directed graph that provides access to both out and in-edges. The
other options for the third argument are <tt>directedS</tt> which selects a
directed graph with only out-edges, and <tt>undirectedS</tt> which selects an
undirected graph.
<p>Once we have the graph type selected, we can create the graph in <a href="#fig:quick-start">Figure
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>
function of the <a href="MutableGraph.html">MutableGraph</a> interface (which <tt>adjacency_list</tt>
implements). We use the array of pairs <tt>edge_array</tt> merely as a
convenient way to explicitly create the edges for this example.
<p>&nbsp;
<pre>
  #include &lt;iostream&gt;                  // for std::cout
  #include &lt;utility&gt;                   // for std::pair
  #include &lt;algorithm&gt;                 // for std::for_each
  #include &lt;boost/graph/graph_traits.hpp&gt;
  #include &lt;boost/graph/adjacency_list.hpp&gt;
  #include &lt;boost/graph/dijkstra_shortest_paths.hpp&gt;

  using namespace boost;
  
  int main(int,char*[])
  {
    // create a typedef for the Graph type
    typedef adjacency_list&lt;vecS, vecS, bidirectionalS&gt; Graph;

    // Make convenient labels for the vertices
    enum { A, B, C, D, E, N };
    const int num_vertices = N;
    const char* name = "ABCDE";

    // writing out the edges in the graph
    typedef std::pair&lt;int, int&gt; Edge;
    Edge edge_array[] = 
    { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
      Edge(C,E), Edge(B,D), Edge(D,E) };
    const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);

    // declare a graph object
    Graph g(num_vertices);

    // add the edges to the graph object
    for (int i = 0; i &lt; num_edges; ++i)
      add_edge(edge_array[i].first, edge_array[i].second, g);
    ...
    return 0;
  }
</pre>
<p>Instead of calling the <tt>add_edge()</tt> function for each edge, we could
use the <a href="adjacency_list.html#sec:iterator-constructor">edge iterator
constructor</a> of the graph. This is typically more efficient than using <tt>add_edge()</tt>.
Pointers to the <tt>edge_array</tt> can be viewed as iterators, so we can call
the iterator constructor by passing pointers to the beginning and end of the
array.
<pre>
    Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(Edge), num_vertices);
</pre>
<p>Instead of creating a graph with a certain number of vertices to begin with,
it is also possible to add and remove vertices with the <a href="MutableGraph.html#sec:add-vertex"><tt>add_vertex()</tt></a>
and <a href="MutableGraph.html#sec:remove-vertex"><tt>remove_vertex()</tt></a>
functions, also of the <a href="MutableGraph.html">MutableGraph</a> interface.
<h2>Accessing the Vertex Set</h2>
<p>Now that we have created a graph, we can use the graph interface to access
the graph data in different ways. First we can access all of the vertices in the
graph using the <a href="VertexListGraph.html#sec:vertices"><tt>vertices()</tt></a>
function of the <a href="VertexListGraph.html">VertexListGraph</a> interface.
This function returns a <tt>std::pair</tt> of <i>vertex iterators</i> (the <tt>first</tt>
iterator points to the &quot;beginning&quot; of the vertices and the <tt>second</tt>
iterator points &quot;past the end&quot;). Dereferencing a vertex iterator gives
a vertex object. The type of the vertex iterator is given by the <a href="graph_traits.html"><tt>graph_traits</tt></a>
class. Note that different graph classes can have different associated vertex
iterator types, which is why we need the <tt>graph_traits</tt> class. Given some
graph type, the <tt>graph_traits</tt> class will provide access to the <tt>vertex_iterator</tt>
type.
<p>The following example prints out the index for each of the vertices in the
graph. All vertex and edge properties, including index, are accessed via
property map objects. The <a href="property_map.html"><tt>property_map</tt></a>
class is used to obtain the property map type for a specific property (specified
by <tt>vertex_index_t</tt>, one of the BGL predefined properties) and function
call <tt>get(vertex_index, g)</tt> returns the actual property map object.
<p>&nbsp;
<pre>
  // ...
  int main(int,char*[])
  {
    // ...

    typedef graph_traits&lt;Graph&gt;::vertex_descriptor Vertex;

    // get the property map for vertex indices
    typedef property_map&lt;Graph, vertex_index_t&gt;::type IndexMap;
    IndexMap index = get(vertex_index, g);

    std::cout &lt;&lt; &quot;vertices(g) = &quot;;
    typedef graph_traits&lt;Graph&gt;::vertex_iterator vertex_iter;
    std::pair&lt;vertex_iter, vertex_iter&gt; vp;
    for (vp = vertices(g); vp.first != vp.second; ++vp.first) {
      Vertex v = *vp.first;
      std::cout &lt;&lt; index[v] &lt;&lt;  &quot; &quot;;
    }
    std::cout &lt;&lt; std::endl;
    // ...
    return 0;
  }
</pre>
The output is:
<pre>
  vertices(g) = 0 1 2 3 4
</pre>
<p>&nbsp;
<h2>Accessing the Edge Set</h2>
<p>The set of edges for a graph can be accessed with the <a href="EdgeListGraph.html#sec:edges"><tt>edges()</tt></a>
function of the <a href="EdgeListGraph.html">EdgeListGraph</a> interface.
Similar to the <tt>vertices()</tt> function, this returns a pair of iterators,
but in this case the iterators are <i>edge iterators</i>. Dereferencing an edge
iterator gives an edge object. The <tt>source()</tt> and <tt>target()</tt>
functions return the two vertices that are connected by the edge. Instead of
explicitly creating a <tt>std::pair</tt> for the iterators, this time we will
use the <a href="../../tuple/doc/tuple_users_guide.html#tiers"><tt>boost::tie()</tt></a> helper function.
This handy function can be used to assign the parts of a <tt>std::pair</tt> into
two separate variables, in this case <tt>ei</tt> and <tt>ei_end</tt>. This is
usually more convenient than creating a <tt>std::pair</tt> and is our method of
choice for the BGL.
<p>&nbsp;
<pre>
  // ...
  int main(int,char*[])
  {
    // ...
    std::cout &lt;&lt; &quot;edges(g) = &quot;;
    graph_traits&lt;Graph&gt;::edge_iterator ei, ei_end;
    for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
        std::cout &lt;&lt; &quot;(&quot; &lt;&lt; index[source(*ei, g)] 
                  &lt;&lt; &quot;,&quot; &lt;&lt; index[target(*ei, g)] &lt;&lt; &quot;) &quot;;
    std::cout &lt;&lt; std::endl;
    // ...
    return 0;
  }
</pre>
The output is:
<pre>
  edges(g) = (0,1) (0,3) (2,0) (3,2) (2,4) (1,3) (3,4)
</pre>
<p>&nbsp;
<h2>The Adjacency Structure</h2>
<p>In the next few examples we will explore the adjacency structure of the graph
from the point of view of a particular vertex. We will look at the vertices'
in-edges, out-edges, and its adjacent vertices. We will encapsulate this in an
&quot;exercise vertex&quot; function, and apply it to each vertex in the graph.
To demonstrate the STL-interoperability of BGL, we will use the STL <tt>for_each()</tt>
function to iterate through the vertices and apply the function.
<p>&nbsp;
<pre>
  //...
  int main(int,char*[])
  {
    //...
    std::for_each(vertices(g).first, vertices(g).second,
                  exercise_vertex&lt;Graph&gt;(g));
    return 0;
  }
</pre>
<p>We use a functor for <tt>exercise_vertex</tt> instead of just a function
because the graph object will be needed when we access information about each
vertex; using a functor gives us a place to keep a reference to the graph object
during the execution of the <tt>std::for_each()</tt>. Also we template the
functor on the graph type so that it is reusable with different graph classes.
Here is the start of the <tt>exercise_vertex</tt> functor:
<p>&nbsp;
<pre>
  template &lt;class Graph&gt; struct exercise_vertex {
    exercise_vertex(Graph&amp; g_) : g(g_) {}
    //...
    Graph&amp; g;
  };
</pre>
<p>&nbsp;
<h3>Vertex Descriptors</h3>
<p>The first thing we need to know in order to write the <tt>operator()</tt>
method of the functor is the type for the vertex objects of the graph. The
vertex type will be the parameter to the <tt>operator()</tt> method. To be
precise, we do not deal with actual vertex objects, but rather with <i>vertex
descriptors</i>. Many graph representations (such as adjacency lists) do not
store actual vertex objects, while others do (e.g., pointer-linked graphs). This
difference is hidden underneath the &quot;black-box&quot; of the vertex
descriptor object. The vertex descriptor is something provided by each graph
type that can be used to access information about the graph via the <tt>out_edges()</tt>,
<tt>in_edges()</tt>, <tt>adjacent_vertices()</tt>, and property map functions
that are described in the following sections. The <tt>vertex_descriptor</tt>
type is obtained through the <tt>graph_traits</tt> class. The <tt>typename</tt>
keyword used below is necessary because the type on the left hand side of the
scope <tt>::</tt> operator (the <tt>graph_traits&lt;Graph&gt;</tt> type) is
dependent on a template parameter (the <tt>Graph</tt> type). Here is how we
define the functor's apply method:
<p>&nbsp;
<pre>
  template &lt;class Graph&gt; struct exercise_vertex {
    //...
    typedef typename graph_traits&lt;Graph&gt;
      ::vertex_descriptor Vertex;

    void operator()(const Vertex&amp; v) const
    {
      //...
    }
    //...
  };
</pre>
<p>&nbsp;
<h3>Out-Edges, In-Edges, and Edge Descriptors</h3>
<p>The out-edges of a vertex are accessed with the <a href="IncidenceGraph.html#sec:out-edges"><tt>out_edges()</tt></a>
function of the <a href="IncidenceGraph.html">IncidenceGraph</a> interface. The <tt>out_edges()</tt>
function takes two arguments: the first argument is the vertex and the second is
the graph object. The function returns a pair of iterators which provide access
to all of the out-edges of a vertex (similar to how the <tt>vertices()</tt>
function returned a pair of iterators). The iterators are called <i>out-edge
iterators</i> and dereferencing one of these iterators gives an <i>edge
descriptor</i> object. An edge descriptor plays the same kind of role as the
vertex descriptor object, it is a &quot;black box&quot; provided by the graph
type. The following code snippet prints the source-target pairs for each
out-edge of vertex <tt>v</tt>.
<p>&nbsp;
<pre>
  template &lt;class Graph&gt; struct exercise_vertex {
    //...
    void operator()(const Vertex&amp; v) const
    {
      typedef graph_traits&lt;Graph&gt; GraphTraits;
      typename property_map&lt;Graph, vertex_index_t&gt;::type 
        index = get(vertex_index, g);

      std::cout &lt;&lt; &quot;out-edges: &quot;;
      typename GraphTraits::out_edge_iterator out_i, out_end;
      typename GraphTraits::edge_descriptor e;
      for (boost::tie(out_i, out_end) = out_edges(v, g); 
           out_i != out_end; ++out_i) {
        e = *out_i;
        Vertex src = source(e, g), targ = target(e, g);
        std::cout &lt;&lt; &quot;(&quot; &lt;&lt; index[src] &lt;&lt; &quot;,&quot; 
                  &lt;&lt; index[targ] &lt;&lt; &quot;) &quot;;
      }
      std::cout &lt;&lt; std::endl;
      //...
    }
    //...
  };
</pre>
For vertex 0 the output is:
<pre>
  out-edges: (0,1) (0,2) (0,3) (0,4)
</pre>
<p>The <a href="BidirectionalGraph.html#sec:in-edges"><tt>in_edges()</tt></a>
function of the <a href="BidirectionalGraph.html">BidirectionalGraph</a>
interface provides access to all the in-edges of a vertex through <i>in-edge
iterators</i>. The <tt>in_edges()</tt> function is only available for the <tt>adjacency_list</tt>
if <tt>bidirectionalS</tt> is supplied for the <tt>Directed</tt> template
parameter. There is an extra cost in space when <tt>bidirectionalS</tt> is
specified instead of <tt>directedS</tt>.
<p>&nbsp;
<pre>
  template &lt;class Graph&gt; struct exercise_vertex {
    //...
    void operator()(const Vertex&amp; v) const
    {
      //...
      std::cout &lt;&lt; &quot;in-edges: &quot;;
      typedef typename graph_traits&lt;Graph&gt; GraphTraits;
      typename GraphTraits::in_edge_iterator in_i, in_end;
      for (boost::tie(in_i, in_end) = in_edges(v,g); 
           in_i != in_end; ++in_i) {
        e = *in_i;
        Vertex src = source(e, g), targ = target(e, g);
        std::cout &lt;&lt; &quot;(&quot; &lt;&lt; index[src] &lt;&lt; &quot;,&quot; &lt;&lt; index[targ] &lt;&lt; &quot;) &quot;;
      }
      std::cout &lt;&lt; std::endl;
      //...
    }
    //...
  };
</pre>
For vertex 0 the output is:
<pre>
  in-edges: (2,0) (3,0) (4,0)
</pre>
<p>&nbsp;
<h3>Adjacent Vertices</h3>
<p>Given the out-edges of a vertex, the target vertices of these edges are <i>adjacent</i>
to the source vertex. Sometimes an algorithm does not need to look at the edges
of the graph and only cares about the vertices. Therefore the graph interface
also includes the <a href="AdjacencyGraph.html#sec:adjacent-vertices"><tt>adjacent_vertices()</tt></a>
function of the <a href="AdjacencyGraph.html">AdjacencyGraph</a> interface which
provides direct access to the adjacent vertices. This function returns a pair of
<i>adjacency iterators</i>. Dereferencing an adjacency iterator gives a vertex
descriptor for an adjacent vertex.
<p>&nbsp;
<pre>
  template &lt;class Graph&gt; struct exercise_vertex {
    //...
    void operator()(Vertex v) const
    {
      //...
      std::cout &lt;&lt; &quot;adjacent vertices: &quot;;
      typename graph_traits&lt;Graph&gt;::adjacency_iterator ai;
      typename graph_traits&lt;Graph&gt;::adjacency_iterator ai_end;
      for (boost::tie(ai, ai_end) = adjacent_vertices(v, g);
           ai != ai_end; ++ai)
        std::cout &lt;&lt; index[*ai] &lt;&lt;  &quot; &quot;;
      std::cout &lt;&lt; std::endl;
    }
    //...
  };
</pre>
For vertex 4 the output is:
<pre>
  adjacent vertices: 0 1
</pre>
<p>&nbsp;
<h2>Adding Some Color to your Graph</h2>
<p>BGL attempts to be as flexible as possible in terms of accommodating how
properties are attached to a graph. For instance, a property such as edge weight
may need to be used throughout a graph object's lifespan and therefore it would
be convenient to have the graph object also manage the property storage. On the
other hand, a property like vertex color may only be needed for the duration of
a single algorithm, and it would be better to have the property stored
separately from the graph object. The first kind of property is called an <i>internally
stored property</i> while the second kind is called an <i>externally stored
property</i>. BGL uses a uniform mechanism to access both kinds of properties
inside its graph algorithms called the <i>property map</i> interface, described
in Section <a href="property_map.html">Property Map Concepts</a>. In addition,
the <a href="PropertyGraph.html">PropertyGraph</a> concept defines the interface
for obtaining a property map object for an internally stored property.
<p>The BGL <tt>adjacency_list</tt> class allows users to specify internally
stored properties through plug-in template parameters of the graph class. How to
do this is discussed in detail in Section <a href="using_adjacency_list.html#sec:adjacency-list-properties">Internal
Properties</a>. Externally stored properties can be created in many different
ways, although they are ultimately passed as separate arguments to the graph
algorithms. One straightforward way to store properties is to create an array
indexed by vertex or edge index. In the <tt>adjacency_list</tt> with <tt>vecS</tt>
specified for the <tt>VertexList</tt> template parameter, vertices are
automatically assigned indices, which can be accessed via the property map for
the <tt>vertex_index_t</tt>. Edges are not automatically assigned indices.
However the property mechanism can be used to attach indices to the edges which
can be used to index into other externally stored properties.
<p>In the following example, we construct a graph and apply <a href="dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths()</tt></a>.
The complete source code for the example is in <a href="../example/dijkstra-example.cpp"><tt>examples/dijkstra-example.cpp</tt></a>.
Dijkstra's algorithm computes the shortest distance from the starting vertex to
every other vertex in the graph.
<p>Dijkstra's algorithm requires that a weight property is associated with each
edge and a distance property with each vertex. Here we use an internal property
for the weight and an external property for the distance. For the weight
property we use the <tt>property</tt> class and specify <tt>int</tt> as the type
used to represent weight values and <tt>edge_weight_t</tt> for the property tag
(which is one of the BGL predefined property tags). The weight property is then
used as a template argument for <tt>adjacency_list</tt>.
<p>The <tt>listS</tt> and <tt>vecS</tt> types are selectors that determine the
data structure used inside the <tt>adjacency_list</tt> (see Section <a href="using_adjacency_list.html#sec:choosing-graph-type">Choosing
the <tt>Edgelist</tt> and <tt>VertexList</tt></a>). The <tt>directedS</tt> type
specifies that the graph should be directed (versus undirected). The following
code shows the specification of the graph type and then the initialization of
the graph. The edges and weights are passed to the graph constructor in the form
of iterators (a pointer qualifies as a <a href="http://www.boost.org/sgi/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
<p>&nbsp;
<pre>
  typedef adjacency_list&lt;listS, vecS, directedS, 
                         no_property, property&lt;edge_weight_t, int&gt; &gt; Graph;
  typedef graph_traits&lt;Graph&gt;::vertex_descriptor Vertex;
  typedef std::pair&lt;int,int&gt; E;

  const int num_nodes = 5;
  E edges[] = { E(0,2), 
                E(1,1), E(1,3), E(1,4),
                E(2,1), E(2,3), 
                E(3,4),
                E(4,0), E(4,1) };
  int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1};

  Graph G(edges, edges + sizeof(edges) / sizeof(E), weights, num_nodes);
</pre>
<p>For the external distance property we will use a <tt>std::vector</tt> for
storage. BGL algorithms treat random access iterators as property maps, so we
can just pass the beginning iterator of the distance vector to Dijkstra's
algorithm. Continuing the above example, the following code shows the creation
of the distance vector, the call to Dijkstra's algorithm (implicitly using the
internal edge weight property), and then the output of the results.
<p>&nbsp;
<pre>
  // vector for storing distance property
  std::vector&lt;int&gt; d(num_vertices(G));

  // get the first vertex
  Vertex s = *(vertices(G).first);
  // invoke variant 2 of Dijkstra's algorithm
  dijkstra_shortest_paths(G, s, distance_map(&amp;d[0]));

  std::cout &lt;&lt; &quot;distances from start vertex:&quot; &lt;&lt; std::endl;
  graph_traits&lt;Graph&gt;::vertex_iterator vi;
  for(vi = vertices(G).first; vi != vertices(G).second; ++vi)
    std::cout &lt;&lt; &quot;distance(&quot; &lt;&lt; index(*vi) &lt;&lt; &quot;) = &quot; 
              &lt;&lt; d[*vi] &lt;&lt; std::endl;
  std::cout &lt;&lt; std::endl;
</pre>
The output is:
<pre>
  distances from start vertex:
  distance(0) = 0
  distance(1) = 6
  distance(2) = 1
  distance(3) = 4
  distance(4) = 5
</pre>
<p>&nbsp;
<h2>Extending Algorithms with Visitors</h2>
<p>Often times an algorithm in a library <i>almost</i> does what you need, but
not quite. For example, in the previous section we used Dijkstra's algorithm to
calculate the shortest distances to each vertex, but perhaps we also wanted to
record the tree of shortest paths. One way to do this is to record the
predecessor (parent) for each node in the shortest-paths tree.
<p>It would be nice if we could avoid rewriting Dijkstra's algorithm, and just
add that little bit extra needed to record the predecessors <a href="#1">[1]</a>. In the STL, this
kind of extensibility is provided by functors, which are optional parameters to
each algorithm. In the BGL this role is fulfilled by <i>visitors</i>.
<p>A visitor is like a functor, but instead of having just one &quot;apply&quot;
method, it has several. Each of these methods get invoked at certain
well-defined points within the algorithm. The visitor methods are explained in
detail in Section <a href="visitor_concepts.html">Visitor Concepts</a>. The BGL
provides a number of visitors for some common tasks including a predecessor
recording visitor. The user is encouraged to write his or her own visitors as a
way of extending the BGL. Here we will take a quick look at the implementation
and use of the predecessor recorder. Since we will be using the <a href="dijkstra_shortest_paths.html">dijkstra_shortest_paths()</a>
algorithm, the visitor we create must be a <a href="DijkstraVisitor.html">Dijkstra Visitor</a>.
<p>The functionality of the <tt>record_predecessors</tt> visitor is separated
into two parts. For the storage and access of the predecessor property, we will
use a <a href="../../property_map/doc/property_map.html">property map</a>. The
predecessor visitor will then only be responsible for what parent to record. To
implement this, we create a <tt>record_predecessors</tt> class and template it
on the predecessor property map <tt>PredecessorMap</tt>. Since this visitor will
only be filling in one of the visitor methods, we will inherit from <a href="dijkstra_visitor.html"><tt>dijkstra_visitor</tt></a>
which will provide empty methods for the rest. The constructor of the <tt>predecessor_recorder</tt>
will take the property map object and save it away in a data member.
<p>&nbsp;
<pre>
  template &lt;class PredecessorMap&gt;
  class record_predecessors : public dijkstra_visitor&lt;&gt;
  {
  public:
    record_predecessors(PredecessorMap p)
      : m_predecessor(p) { }

    template &lt;class Edge, class Graph&gt;
    void edge_relaxed(Edge e, Graph&amp; g) {
      // set the parent of the target(e) to source(e)
      put(m_predecessor, target(e, g), source(e, g));
    }
  protected:
    PredecessorMap m_predecessor;
  };
</pre>
<p>The job of recording the predecessors is quite simple. When Dijkstra's
algorithm relaxes an edge (potentially adding it to the shortest-paths tree) we
record the source vertex as the predecessor of the target vertex. Later, if the
edge is relaxed again the predecessor property will be overwritten by the new
predecessor. Here we use the <tt>put()</tt> function associated with the
property map to record the predecessor. The <tt>edge_filter</tt> of the visitor
tells the algorithm when to invoke the <tt>explore()</tt> method. In this case
we only want to be notified about edges in the shortest-paths tree so we specify
<tt>tree_edge_tag</tt>.
<p>As a finishing touch, we create a helper function to make it more convenient
to create predecessor visitors. All BGL visitors have a helper function like
this.
<p>&nbsp;
<pre>
  template &lt;class PredecessorMap&gt;
  record_predecessors&lt;PredecessorMap&gt;
  make_predecessor_recorder(PredecessorMap p) {
    return record_predecessors&lt;PredecessorMap&gt;(p);
  }
</pre>
<p>We are now ready to use the <tt>record_predecessors</tt> in
Dijkstra's algorithm. Luckily, BGL's Dijkstra's algorithm is already
equipped to handle visitors, so we just pass in our new visitor. In
this example we only need to use one visitor, but the BGL is also
equipped to handle the use of multiple visitors in the same algorithm
(see Section <a href="visitor_concepts.html">Visitor Concepts</a>).
<p>&nbsp;
<pre>
  using std::vector;
  using std::cout;
  using std::endl;
  vector&lt;Vertex&gt; p(num_vertices(G), graph_traits&lt;G&gt;::null_vertex()); //the predecessor array
  dijkstra_shortest_paths(G, s, distance_map(&amp;d[0]). 
                          visitor(make_predecessor_recorder(&amp;p[0])));

  cout &lt;&lt; &quot;parents in the tree of shortest paths:&quot; &lt;&lt; endl;
  for(vi = vertices(G).first; vi != vertices(G).second; ++vi) {
    cout &lt;&lt; &quot;parent(&quot; &lt;&lt; *vi;
    if (p[*vi] == graph_traits&lt;G&gt;::null_vertex())
      cout &lt;&lt; &quot;) = no parent&quot; &lt;&lt; endl; 
    else 
      cout &lt;&lt; &quot;) = &quot; &lt;&lt; p[*vi] &lt;&lt; endl;
  }
</pre>
The output is:
<pre>
  parents in the tree of shortest paths:
  parent(0) = no parent
  parent(1) = 4
  parent(2) = 0
  parent(3) = 2
  parent(4) = 3
</pre>

<br>

<h3>Notes</h3>

<a name="1">[1]</a> The new version of Dijkstra's algorithm now includes
a named parameter for recording predecessors, so a predecessor visitor
is no long necessary, though this still makes for a good example.

<br>
<hr>
<table>
  <tr valign="top">
    <td nowrap>Copyright © 2000</td>
    <td><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>,
      Indiana University (<a href="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>)</td>
  </tr>
</table>

</body>

</html>
<!--  LocalWords:  STL BGL cpp vecS bidirectionalS directedS undirectedS hpp vp
 -->
<!--  LocalWords:  iostream namespace int const num sizeof map ID's gif typedef
 -->
<!--  LocalWords:  iter ei interoperability struct typename GraphTraits src ai
 -->
<!--  LocalWords:  targ PropertyGraph  Properties property iterator iterators
 -->
<!--  LocalWords:  VertexList dijkstra listS Edgelist RandomAccessIterator cout
 -->
<!--  LocalWords:  weightp  adjacency tradeoffs undirected MutableGraph indices
 -->
<!--  LocalWords:  VertexListGraph Dereferencing IndexMap EdgeListGraph functor
 -->
<!--  LocalWords:  functor's IncidenceGraph dereferencing BidirectionalGraph
 -->
<!--  LocalWords:  AdjacencyGraph Dijkstra's extensibility functors BGL's endl
 -->
<!--  LocalWords:  DijkstraVisitor PredecessorMap siek htm Univ Notre
 -->