Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Graph Setup
Before addressing the questions regarding the build system, you must first find a way to represent the file-dependency graph of Figure 1 in memory. That is, you need to construct a BGL graph object. The BGL contains several graph classes, but the adjacency_list class is a good choice for most situations and is used here. The other BGL graph classes have the same interface as the adjacency_list class, so when you have learned how to use one, you have learned them all.
){kind=link}
The basic idea of an adjacency list is that for each vertex in the graph, you maintain a linked list of all the vertices that are adjacent to it. Figure 2 shows a simple graph and the adjacency list representation of it. The implementation of the adjacency_list class uses containers from the C++ Standard Library to store the lists of adjacent vertices and to store the "backbone" list of vertices.
){kind=link}
Figure 2 A graph stored using the adjacency list data structure.
The adjacency_list class is really more than one graph class; it is a family of graph classes, each with different time and space trade-offs and with different characteristics, such as being directed or undirected. The user picks the kind of adjacency_list by choosing particular arguments for the template parameters. The following typedef shows the kind of adjacency_list you will use to represent file dependencies:
·Dependency graph typedefÒ∫ #include <boost/graph/adjacency_list.hpp> using namespace boost; typedef adjacency_list< listS, // Store out-edges of each vertex in a std::list vecS, // Store vertex set in a std::vector directedS // The file dependency graph is directed > file_dep_graph;
Now suppose that your build system stores the file dependencies in an auxiliary file. On each line in the file is an edge in the graph, recorded by listing the names of the two files that the edge connects—for example:
zig.cpp zig.o boz.h zig.o boz.h zag.o ...
You will create a graph object based on this file. You will use the add_edge function to insert each edge into the graph. There is also a way to add many edges into the graph all at once using a constructor, but the simpler add_edge suits your purposes here. The prototype for the add_edge function is as follows:
std::pair<edge_descriptor, bool> add_edge(vertex_descriptor u, vertex_descriptor v, adjacency_list& g);
What are these descriptor types? They are opaque handle objects provided by the graph type to make it possible for the user to inspect and modify vertices and edges in the graph. Each graph type has its own descriptor types, which you can access via a graph_traits class.
·Vertex and edge descriptor typedefsÒ∫ typedef graph_traits<file_dep_graph>::vertex_descriptorvertex_descriptor;
Why was the BGL designed with this extra level of indirection? As with the STL, you want to write generic algorithms that work with many different types of containers. You want to be as flexible as possible about what kinds of graph classes can be used with your algorithms, so the BGL allows different graph classes to use different types for the descriptors. The BGL generic algorithms are function templates parameterized on the graph type; from within the templates, the algorithm needs to discover the descriptor types—hence the need for the graph_traits class.
Let's get back to adding edges to the graph. First, we create an empty graph object; then open the file-dependencies.dat auxiliary file using std::ifstream. Then read in the edges, storing the name of the source and target vertex in std::strings. To add the edge to the graph, you first must obtain vertex descriptors for the source and target, which means that you first need to make sure that these two vertices have been added to the graph. This is describe more later. The code for what you have described so far is as follows:
·Construct the graph from a fileÒ∫
file_dep_graph G;
std::ifstream file_in("file-dependencies.dat");
std::map<std::string, vertex_descriptor> name2vertex;
std::string source_name, target_name;
while (file_in >> source_name >> target_name) {
·Make sure a vertex for the source has been added to the graphÒ
·Make sure a vertex for the target has been added to the graphÒ
add_edge(s, t, G)
}
You can add vertices to the graph using the add_vertex function, which returns a vertex descriptor for the new vertex. However, you will encounter the same vertex multiple times when reading the file. Therefore, you need to first check to see if the vertex has already been added to the graph and then retrieve it by name. A std::map from vertex names to vertex descriptors fits this need.
·Make sure a vertex for the source has been added to the graphÒ∫
vertex_descriptor s;
if (name2vertex.find(source_name) == name2vertex.end()) {
s = add_vertex(G);
name2vertex.insert(make_pair(source_name, s));
} else
s = name2vertex[source_name];
Do the same thing for the target vertex:
·Make sure a vertex for the target has been added to the graphÒ∫
vertex_descriptor t;
if (name2vertex.find(target_name) == name2vertex.end()) {
s = add_vertex(G);
name2vertex.insert(make_pair(target_name, t));
} else
t = name2vertex[target_name];