This chapter is from the book
This chapter is from the book
This chapter is from the book
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.
){kind=link}
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 x1.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;
}
}