## 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 *x*4.2, and the
documentation for `depth_first_search()` is in §13.2.3. The
documentation for `topological_sort()` is in §13.2.5.