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> </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 © 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
- -->
|