Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Cyclic Dependencies
One important assumption in the last section is that the file-dependency graph does not have any cycles. The reason for this assumption is that a graph with cycles does not have a topological ordering, so there will be no valid order in which you can build the makefile targets. A well-formed makefile must not have cycles, but human errors do occur and the build system should be able to catch and report such errors.
The problem of detecting cycles can be solved using a depth-first search (DFS). A DFS follows along edges to visit all the vertices in the graph exactly once. A DFS chooses to go "deeper" into the graph when possible, backtracking and exploring other paths only when it comes to a dead end. The edges traversed by a DFS form a tree (actually, there can be multiple trees if one part of the graph is unreachable from other parts). It turns out that if DFS is applied to a graph that has a cycle, one of the branches of the 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. Therefore, you will use DFS to identify whether any back edges exist and, correspondingly, whether there are any cycles.
The BGL contains a generic algorithm for performing a DFS: the depth_first_search function template. The declaration for this function is as follows:
template <typename Graph, typename P, typename T, typename R> void depth_first_search(const Graph& g,pconst bgl_named_params<P, T, R>& params);
The graph parameter is straightforward, but params deserves some explanation. This parameter provides a mechanism for named parameters. The DFS has three named parameters: visitor, color_map, and vertex_index_map. The user can supply them in any order; the arguments are matched to parameters by name. All of the parameters have a default, and for current purposes you want to supply only the visitor argument.
The visitor argument is like a callback that allows you to customize the behavior of the DFS a certain event points. Interestingly enough, one of the event points occurs when the DFS encounters a back edge. Therefore, to detect cycles, you simply need to create a visitor object that notifies you when a back edge is encountered and then use this visitor in a call to depth_first_search. The notification mechanism you will use is an exception; you will throw a has_cycle exception when a back edge is encountered. The following is the code for the cycle_detector DFS visitor. You inherit from default_dfs_visitor to get the default empty member functions for the other event points.
·Cycle detector DFS visitorÒ∫
struct has_cycle { };
struct cycle_detector : public default_dfs_visitor {
void back_edge(edge_t, const file_dep_graph&) {
throw has_cycle();
}
};
Now you compute whether the graph has a cycle. To pass the visitor as a named parameter, pass the visitor object vis to the visitor function which you then pass to depth_first_search:
·Check whether the graph has a cycleÒ∫
cycle_detector vis;
try {
depth_first_search(G, visitor(vis));
} catch (has_cycle) {
std::cout << "Error: cycle detected" << std::endl;
}