| <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*[]) |
| { |
| // ... |
| |
| // 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) |
| std::cout << index[*vp.first] << " "; |
| 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>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 (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 (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 (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 (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.sgi.com/tech/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 |
| --> |
