 • Print
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;
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))
return true;
return false;
} ```