## 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.

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.

**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_descriptor vertex_descriptor; typedef graph_traits<file_dep_graph>::edge_descriptor edge_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::string`s. 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];