This chapter is from the book
This chapter is from the book
This chapter is from the book
3.5 Toward a Generic DFS: Visitors
At this point we have completed two functions, topo_sort() and has_cycle() , each of which is implemented using depth-first search, although in slightly different ways. However, the fundamental similarities between the two functions provide an excellent opportunity for code reuse. It would be much better if we had a single generic algorithm for depth-first search that expresses the commonality between topo_sort() and has_cycle() and then used parameters to customize the DFS for each of the different problems.
The design of the STL gives us a hint for how to create a suitably parameterized DFS algorithm. Many of the STL algorithms can be customized by providing a user-defined function object. In the same way, we would like to parameterize DFS in such a way that topo_sort() and has_cycle() can be realized by passing in a function object.
Unfortunately, the situation here is a little more complicated than in typical STL algorithms. In particular, there are several different locations in the DFS algorithm where customized actions must occur. For instance, the topo_sort() function records the ordering at the bottom of the recursive function, whereas the has cycle() function needs to insert an operation inside the loop that examines the adjacent vertices.
The solution to this problem is to use a function object with more than one callback member function. Instead of a single operator() function, we use a class with several member functions that are called at different locations (we refer to these places as event points). This kind of function object is called an algorithm visitor. The DFS visitor will have five member functions: discover_vertex() , tree_edge() , back_edge() , forward_or_cross_edge() , and finish_vertex() . Also, instead of iterating over the adjacent vertices, we iterator over out-edges to allow passing edge descriptors to the visitor functions and thereby provide more information to the user-defined visitor. This code for a DFS function has a template parameter for a visitor:
template <typename Visitor> void_dfs v1(const file_dep_graph& g, vertex_t u, default_color_type*color, Visitor vis) { color[u] = gray_color; vis.discover_vertex(u, g); graph_traits<file_dep_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)] == white_color) { vis.tree_edge(*ei, g); dfs_v1(g, target(*ei, g), color, vis); } else if (color[target(*ei, g)] == gray_color) vis.back_edge(*ei, g); else vis.forward_or_cross_edge(*ei, g); } color[u] = black_color; vis.finish vertex(u, g); }
template <typename Visitor>
void generic_dfs_v1(const file_dep_graph& g, Visitor vis)
{
std::vector<default_color_type> color(num_vertices(g), white_color);
graph_traits<file_dep_graph>::vertex_iterator vi, vi_end;
for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
if (color[*vi] == white_color)
dfs_v1(g, *vi, &color[0], vis);
}
}
The five member functions of the visitor provide the flexibility we need, but a user that only wants to add one action should not have to write four empty member functions. This is easily solved by creating a default visitor from which user-defined visitors can be derived.
struct default_dfs_visitor {
template <typename V, typename G>
void discover_vertex(V, const G&) { }
template <typename E, typename G>
void tree_edge(E, const G&) { }
template <typename E, typename G>
void back_edge(E, const G&) { }
template <typename E, typename G>
void forward_or_cross_edge(E, const G&) { }
template <typename V, typename G>
void finish_vertex(V, const G&) { }
};
To demonstrate that this generic DFS can solve our problems, we reimplement the topo_sort() and has_cycle() functions. First we need to create a visitor that records the topological ordering on the "finish vertex" event point. The code for this visitor follows.
struct topo_visitor : public default_dfs_visitor {
topo_visitor(vertex_t*& order) : topo_order(order) { }
void finish_vertex(vertex_t u, const file dep_graph&) {
*topo_order = u;
}
vertex_t*& topo order;
};
Only two lines of code are required in the body of topo_sort() when implemented using generic DFS. One line creates the visitor object and one line calls the generic DFS.
void topo_sort(const file_dep_graph& g, vertex_t* topo order)
{
topo_visitor vis(topo_order);
generic_dfs_v1(g, vis);
}
To reimplement the has_cycle() function, we use a visitor that records that the graph has a cycle whenever the back edge event point occurs.
struct cycle_detector : public default_dfs_visitor {
cycle_detector(bool& cycle) : has_cycle(cycle) { }
void back_edge(edge_t, const file_dep_graph&) {
has_cycle = true;
}
bool& has cycle;
};
The new has_cycle() function creates a cycle detector object and passes it to the generic DFS.
bool has_cycle(const file_dep_graph& g)
{
bool has_cycle = false;
cycle_detector vis(has_cycle);
generic_dfs_v1(g, vis);
return has_cycle;
}