This chapter is from the book
This chapter is from the book
This chapter is from the book
3.4 Cyclic Dependencies
One important assumption in the last section is that the file dependency graph does not have any cycles. As stated in §3.3.1, a graph with cycles does not have a topological ordering. A well-formed makefile will have no cycles, but errors do occur, and our build system should be able to catch and report such errors.
Depth-first search can also be used for the problem of detecting cycles. If DFS is applied to a graph that has a cycle, then one of the branches of a DFS tree will loop back on itself. That is, there will be an edge from a vertex to one of its ancestors in the tree. This kind of edge is called a back edge. This occurrence can be detected if we change how we mark vertices. Instead of marking each vertex as visited or not visited, we use a three-way coloring scheme: white means undiscovered, gray means discovered but still searching descendants, and black means the vertex and all of its descendants have been discovered. Three-way coloring is useful for several graph algorithms, so the header file boost/graph/properties.hpp defines the following enumerated type.
enum default_color_type { white_color, gray_color, black_color };
A cycle in the graph is identified by an adjacent vertex that is gray, meaning that an edge loops back to an ancestor. The following code is a version of DFS instrumented to detect cycles.
bool has_cycle dfs(const file_dep graph& g, vertex_t u,default_color_type* color) { color[u] = gray_color; graph_traits<file_dep_graph>::adjacency_iterator vi, vi_end; for (tie(vi, vi_end) = adjacent_vertices(u, g); vi != vi_end; ++vi) if (color[*vi] == white_color) if (has_cycle_dfs(g, *vi, color)) return true; // cycle detected, return immediately else if (color[*vi] == gray_color) // *vi is an ancestor! return true; color[u] = black_color; return false; }
As with the topological sort, in the has_cycle() function the recursive DFS function call is placed inside of a loop through all of the vertices so that we catch all of the DFS trees in the graph.
bool has_cycle(const file_dep_graph& g)
{
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)
if (has_cycle_dfs(g, *vi, &color[0]))
return true;
return false;
}