628 lines
29 KiB
HTML
628 lines
29 KiB
HTML
<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> </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> </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> </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> </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 "slice" of this example
|
||
file. Excerpts from the output of the example program will also be listed.
|
||
<p>
|
||
<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 "adjacency list"
|
||
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>
|
||
<pre>
|
||
#include <iostream> // for std::cout
|
||
#include <utility> // for std::pair
|
||
#include <algorithm> // for std::for_each
|
||
#include <boost/graph/graph_traits.hpp>
|
||
#include <boost/graph/adjacency_list.hpp>
|
||
#include <boost/graph/dijkstra_shortest_paths.hpp>
|
||
|
||
using namespace boost;
|
||
|
||
int main(int,char*[])
|
||
{
|
||
// create a typedef for the Graph type
|
||
typedef adjacency_list<vecS, vecS, bidirectionalS> 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<int, int> 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 < 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 "beginning" of the vertices and the <tt>second</tt>
|
||
iterator points "past the end"). 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>
|
||
<pre>
|
||
// ...
|
||
int main(int,char*[])
|
||
{
|
||
// ...
|
||
|
||
typedef graph_traits<Graph>::vertex_descriptor Vertex;
|
||
|
||
// get the property map for vertex indices
|
||
typedef property_map<Graph, vertex_index_t>::type IndexMap;
|
||
IndexMap index = get(vertex_index, g);
|
||
|
||
std::cout << "vertices(g) = ";
|
||
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
|
||
std::pair<vertex_iter, vertex_iter> vp;
|
||
for (vp = vertices(g); vp.first != vp.second; ++vp.first) {
|
||
Vertex v = *vp.first;
|
||
std::cout << index[v] << " ";
|
||
}
|
||
std::cout << std::endl;
|
||
// ...
|
||
return 0;
|
||
}
|
||
</pre>
|
||
The output is:
|
||
<pre>
|
||
vertices(g) = 0 1 2 3 4
|
||
</pre>
|
||
<p>
|
||
<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>
|
||
<pre>
|
||
// ...
|
||
int main(int,char*[])
|
||
{
|
||
// ...
|
||
std::cout << "edges(g) = ";
|
||
graph_traits<Graph>::edge_iterator ei, ei_end;
|
||
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
|
||
std::cout << "(" << index[source(*ei, g)]
|
||
<< "," << index[target(*ei, g)] << ") ";
|
||
std::cout << 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>
|
||
<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
|
||
"exercise vertex" 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>
|
||
<pre>
|
||
//...
|
||
int main(int,char*[])
|
||
{
|
||
//...
|
||
std::for_each(vertices(g).first, vertices(g).second,
|
||
exercise_vertex<Graph>(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>
|
||
<pre>
|
||
template <class Graph> struct exercise_vertex {
|
||
exercise_vertex(Graph& g_) : g(g_) {}
|
||
//...
|
||
Graph& g;
|
||
};
|
||
</pre>
|
||
<p>
|
||
<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 "black-box" 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<Graph></tt> type) is
|
||
dependent on a template parameter (the <tt>Graph</tt> type). Here is how we
|
||
define the functor's apply method:
|
||
<p>
|
||
<pre>
|
||
template <class Graph> struct exercise_vertex {
|
||
//...
|
||
typedef typename graph_traits<Graph>
|
||
::vertex_descriptor Vertex;
|
||
|
||
void operator()(const Vertex& v) const
|
||
{
|
||
//...
|
||
}
|
||
//...
|
||
};
|
||
</pre>
|
||
<p>
|
||
<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 "black box" provided by the graph
|
||
type. The following code snippet prints the source-target pairs for each
|
||
out-edge of vertex <tt>v</tt>.
|
||
<p>
|
||
<pre>
|
||
template <class Graph> struct exercise_vertex {
|
||
//...
|
||
void operator()(const Vertex& v) const
|
||
{
|
||
typedef graph_traits<Graph> GraphTraits;
|
||
typename property_map<Graph, vertex_index_t>::type
|
||
index = get(vertex_index, g);
|
||
|
||
std::cout << "out-edges: ";
|
||
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 << "(" << index[src] << ","
|
||
<< index[targ] << ") ";
|
||
}
|
||
std::cout << 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>
|
||
<pre>
|
||
template <class Graph> struct exercise_vertex {
|
||
//...
|
||
void operator()(const Vertex& v) const
|
||
{
|
||
//...
|
||
std::cout << "in-edges: ";
|
||
typedef typename graph_traits<Graph> 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 << "(" << index[src] << "," << index[targ] << ") ";
|
||
}
|
||
std::cout << std::endl;
|
||
//...
|
||
}
|
||
//...
|
||
};
|
||
</pre>
|
||
For vertex 0 the output is:
|
||
<pre>
|
||
in-edges: (2,0) (3,0) (4,0)
|
||
</pre>
|
||
<p>
|
||
<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>
|
||
<pre>
|
||
template <class Graph> struct exercise_vertex {
|
||
//...
|
||
void operator()(Vertex v) const
|
||
{
|
||
//...
|
||
std::cout << "adjacent vertices: ";
|
||
typename graph_traits<Graph>::adjacency_iterator ai;
|
||
typename graph_traits<Graph>::adjacency_iterator ai_end;
|
||
for (boost::tie(ai, ai_end) = adjacent_vertices(v, g);
|
||
ai != ai_end; ++ai)
|
||
std::cout << index[*ai] << " ";
|
||
std::cout << std::endl;
|
||
}
|
||
//...
|
||
};
|
||
</pre>
|
||
For vertex 4 the output is:
|
||
<pre>
|
||
adjacent vertices: 0 1
|
||
</pre>
|
||
<p>
|
||
<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>
|
||
<pre>
|
||
typedef adjacency_list<listS, vecS, directedS,
|
||
no_property, property<edge_weight_t, int> > Graph;
|
||
typedef graph_traits<Graph>::vertex_descriptor Vertex;
|
||
typedef std::pair<int,int> 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>
|
||
<pre>
|
||
// vector for storing distance property
|
||
std::vector<int> 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(&d[0]));
|
||
|
||
std::cout << "distances from start vertex:" << std::endl;
|
||
graph_traits<Graph>::vertex_iterator vi;
|
||
for(vi = vertices(G).first; vi != vertices(G).second; ++vi)
|
||
std::cout << "distance(" << index(*vi) << ") = "
|
||
<< d[*vi] << std::endl;
|
||
std::cout << 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>
|
||
<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 "apply"
|
||
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>
|
||
<pre>
|
||
template <class PredecessorMap>
|
||
class record_predecessors : public dijkstra_visitor<>
|
||
{
|
||
public:
|
||
record_predecessors(PredecessorMap p)
|
||
: m_predecessor(p) { }
|
||
|
||
template <class Edge, class Graph>
|
||
void edge_relaxed(Edge e, Graph& 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>
|
||
<pre>
|
||
template <class PredecessorMap>
|
||
record_predecessors<PredecessorMap>
|
||
make_predecessor_recorder(PredecessorMap p) {
|
||
return record_predecessors<PredecessorMap>(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>
|
||
<pre>
|
||
using std::vector;
|
||
using std::cout;
|
||
using std::endl;
|
||
vector<Vertex> p(num_vertices(G), graph_traits<G>::null_vertex()); //the predecessor array
|
||
dijkstra_shortest_paths(G, s, distance_map(&d[0]).
|
||
visitor(make_predecessor_recorder(&p[0])));
|
||
|
||
cout << "parents in the tree of shortest paths:" << endl;
|
||
for(vi = vertices(G).first; vi != vertices(G).second; ++vi) {
|
||
cout << "parent(" << *vi;
|
||
if (p[*vi] == graph_traits<G>::null_vertex())
|
||
cout << ") = no parent" << endl;
|
||
else
|
||
cout << ") = " << p[*vi] << 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 <20> 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
|
||
-->
|