- What is Boost?
- Implementing a Make-Like Build System
- Graph Setup
- Compilation Order
- Property Maps
- Cyclic Dependencies
- Conclusion
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Implementing a Make-Like Build System
Figure 1 shows a graph that depicts the compilation dependencies between some source files, object files, libraries, and an executable. Each file corresponds to a vertex in the graph. When one file is used in the build of another file, there is an edge connecting the corresponding vertices, called the source vertex and the target vertex. In this graph, the edges are drawn as arrows because the dependency relationship goes one way but not the other—that is, it is a directed graph. Vertex v is said to be adjacent to vertex u when there is an edge connecting u to v.
){kind=link}
Answers to many of the questions that arise when creating a build system such as make can be formulated in terms of this dependency graph. You might ask these questions:
If all the makefile targets need to be built, in what order should that be accomplished?
Are there any cycles in the dependencies? A cycle in the dependencies is an error, and an appropriate message should be emitted.
Figure 1 A graph representing file dependencies.
In the following sections, these questions are posed in graph terms, and BGL algorithms are used to obtain solutions. The graph in Figure 1 is used in all the examples. The following is the overview of the program you will be constructing. I use the notation of literate programming:
·Compilation order and cycle detector programÒ∫
·Dependency graph typedefÒ
·Vertex and edge descriptor typedefsÒ
·Cycle detector DFS visitorÒ
int main(int, char*[])
{
·Construct the graph from a fileÒ
·Construct the name property mapÒ
·Compute the compilation orderÒ
·Check whether the graph has a cycleÒ
return EXIT_SUCCESS;
}