This chapter is from the book
This chapter is from the book
This chapter is from the book
3.8 A Generic Topological Sort and DFS
Due to the change in graph type (from file dep graph to file dep graph2) we can no longer use the topo_sort() function that we developed in §3.4. Not only does the graph type not match, but also the color array used inside of generic_dfs_v1() relies on the fact that vertex descriptors are integers (which is not true for file_dep_graph2). These problems give us an opportunity to create an even more generic version of topological sort and the underlying DFS. We parameterize the topo_sort() function in the following way.
The specific type file_dep_graph is replaced by the template parameter Graph. Merely changing to a template parameter does not help us unless there is a standard interface shared by all the graph types that we wish to use with the algorithm. This is where the BGL graph traversal concepts come in. For topo_sort() we need a graph type that models the VertexListGraph and IncidenceGraph concepts.
Using a vertex_t* for the ordering output is overly restrictive. A more generalized way to output a sequence of elements is to use an output iterator, just as the algorithms in the C++ Standard Library do. This gives the user much more options in terms of where to store the results.
We need to add a parameter for the color map. To make this as general as possible, we only want to require what is essential. In this case, the topo_sort() function needs to be able to map from a vertex descriptor to a marker object for that vertex. The Boost Property Map Library (see Chapter 15) defines a minimalistic interface for performing this mapping. Here we use the LvaluePropertyMap interface. The internal color_map that we obtained from the graph in §3.6 implements the LvaluePropertyMap interface, as does the color array we used in §3.3.4. A pointer to an array of color markers can be used as a property map because there are function overloads in boost/property_map_hpp that adapt pointers to satisfy the LvaluePropertyMap interface.
The following is the implementation of our generic topo_sort() . The topo_visitor and generic_dfs_v2() are discussed next.
template <typename Graph, typename OutputIterator, typename ColorMap> void topo_sort(const Graph& g, OutputIterator topo_order,ColorMap color) { topo_visitor<OutputIterator> vis(topo_order); generic dfs v2(g, vis, color); }
The topo_visitor class is now a class template to accommodate the output iterator. Instead of decrementing, we now increment the output iterator (decrementing an output iterator is not allowed). To get the same reversal behavior as in the first version of topo_sort() , the user can pass in a reverse iterator or something like a front insert iterator for a list.
template <typename OutputIterator>
struct topo_visitor : public default_dfs_visitor {
topo_visitor(OutputIterator& order) : topo_order(order) { }
template <typename Graph>
void finish_vertex(typename graph_traits<Graph>::
vertex_descriptor u, const Graph&)
{ *topo_order++ = u; }
OutputIterator& topo order;
};
The generic DFS changes in a similar fashion, with the graph type and color map becoming parameterized. In addition, we do not a priori know the color type, so we must get the color type by asking the ColorMap for its value type (though the property_traits class). Instead of using constants such as white_color, we use the color functions defined in color_traits.
template <typename Graph, typename Visitor, typename ColorMap>
void generic_dfs_v2(const Graph& g, Visitor vis, ColorMap color)
{
typedef color_traits<typename property_traits<ColorMap>::
value_type> ColorT;
typename graph_traits<Graph>::vertex_iterator vi, vi_end;
for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
color[*vi] = ColorT::white();
for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
if (color[*vi] == ColorT::white())
dfs_v2(g, *vi, color, vis);
}
The logic from the dfs_v1 does not need to change; however, there are a few small changes required due to making the graph type parameterized. Instead of hard-coding vertex_t as the vertex descriptor type, we extract the appropriate vertex descriptor from the graph type using graph_traits. The fully generic DFS function follows. This function is essentially the same as the BGL depth_first_visit() .
template <typename Graph, typename ColorMap, typename Visitor>
void dfs v2(const Graph& g,
typename graph_traits<Graph>::vertex_descriptor u,
ColorMap color, Visitor vis)
{
typedef typename property_traits<ColorMap>::value_type color_type;
typedef color_traits<color_type> ColorT;
color[u] = ColorT::gray();
vis.discover vertex(u, g);
typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei)
if (color[target(*ei, g)] == ColorT::white()) {
vis.tree_edge(*ei, g);
dfs_v2(g, target(*ei, g), color, vis);
} else if (color[target(*ei, g)] == ColorT::gray())
vis.back_edge(*ei, g);
else
vis.forward_or_cross_edge(*ei, g);
color[u] = ColorT::black();
vis.finish vertex(u, g);
}
The real BGL depth_first_search() and topological_sort() functions are quite similar to the generic functions that we developed in this section. We give a detailed example of using the BGL depth_first_search() function in x4.2, and the documentation for depth_first_search() is in §13.2.3. The documentation for topological_sort() is in §13.2.5.