## 3.2 Graph Setup

Before addressing these questions directly, we must first find a way to represent the file-dependency graph of Figure 3.1 in memory. That is, we need to construct a BGL graph object.

#### Deciding Which Graph Class To Use

There are several BGL graph classes from which to choose. Since BGL
algorithms are generic, they can also be used with any conforming user-defined
graph class, but in this chapter we restrict our discussion to BGL graph
classes. The principle BGL graph classes are the `adjacency_list `and
`adjacency_matrix `classes. The `adjacency_list `class is a good
choice for most situations, particularly for representing sparse graphs. The
file-dependencies graph has only a few edges per vertex, so it is sparse. The
`adjacency_matrix `class is a good choice for representing dense graphs,
but a very bad choice for sparse graphs.

The `adjacency_list `class is used
exclusively in this chapter. However, most of what is presented here also
applies directly to the `adjacency_matrix `class because its interface is
almost identical to that of the `adjacency_list `class. Here we use the
same variant of `adjacency_list `as was used in §1.4.1.

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;

#### Constructing a Graph Using Edge Iterators

In *x*1.2.4 we showed how the `add_vertex()` and
`add_edge()` functions can be used to create a graph. Those
functions add vertices and edges one at a time, but in many cases one would like
to add them all at once. To meet this need the `adjacency_list `graph
class has a constructor that takes two iterators that define a range of edges.
The edge iterators can be any InputIterator that dereference to a `std::pair
`of integers (*i; j*) that represent an edge in the graph. The two
integers *i *and *j *represent vertices where 0≤* i < |V |
*and 0 ≤* j < |V |*. The `n `and `m `parameters
say how many vertices and edges will be in the graph. These parameters are
optional, but providing them improves the speed of graph construction. The graph
properties parameter `p `is attached to the graph object. The function
prototype for the constructor that uses edge iterators is as follows:

template <typename EdgeIterator> adjacency_list(EdgeIterator first, EdgeIterator last, vertices_size_type n = 0, edges_size_type m = 0, const GraphProperties& p = GraphProperties())

The following code demonstrates the use of the
edge iterator constructor to create a graph. The `std::istream_iterator
`is used to make an input iterator that reads the edges in from the file.
The file contains the number of vertices in the graph, followed by pairs of
numbers that specify the edges. The second default-constructed input iterator is
a placeholder for the end of the input. The `std::istream_iterator `is
passed directly into the constructor for the graph.

std::ifstream file in("makefile-dependencies.dat"); typedef graph_traits<file dep_graph>::vertices size_type size_type; size_type n_vertices; file in >> n_vertices; // read in number of vertices std::istream_iterator<std::pair<size_type, size_type> > input_begin(file_in), input_end; file_dep_graph g(input_begin, input_end, n_vertices);

Since the value type of the `std::istream_iterator `is
`std::pair`, an input operator needs to be de-fined for
`std::pair`.

namespace std { template <typename T> std::istream& operator>>(std::istream& in, std::pair<T,T>& p) { in >> p.first >> p.second; return in; } }