Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Compilation Order
The first question to address is in what order to build all of the files. The primary consideration here is to ensure that, before building a given file, all the files that it depends on are already built. This idea of finding an ordering of files (vertices) that respects the dependencies (edges) is called a topological order. The BGL includes a function template named topological_sort that computes a topological ordering. The declaration for this function is as follows:
template <typename Graph, typename OutputIterator,
typename P, typename T, typename R>
void topological_sort(Graph& g, OutputIterator result,
const bgl_named_params<P,T,R>& params = all defaults);
Here you can start to see the generic nature of the BGL. The graph type is parameterized so that this function will work with many different graph classes. However, there are some limits to what kinds of types can be passed in for the parameter Graph. In the documentation for topological_sort, you can see that the graph type must be a model of the VertexListGraph and the IncidenceGraph concepts. Note that in generic programming, the concept is used as a technical term. A concept is a set of requirements that a type must fulfill for a generic algorithm to work properly. A type that meets the requirements is said to model the concept.
The requirements consist of valid expressions, associated types, invariants, and complexity guarantees. The valid expressions define the syntax of the concept's interface. For example, the VertexListGraph requires vertices(g) to be a valid expression that returns the type std::pair<vertex_iterator, vertex_iterator>. The pair of iterators is a begin-end range that provides access to all the vertices in the graph. You have already seen associated types; they are types such as the vertex and edge descriptors that are accessed via traits classes. Invariants describe and place restrictions on the runtime behavior of the valid expressions. The complexity guarantees provide information about how much time or space a valid expression is allowed to use to execute. For example, the vertices(g) expression must return the pair of iterators in constant time.
An important question is whether the graph class that you are using, adjacency_list, can be used with topological_sort. That is, is adjacency_list a model of IncidenceGraph and VertexListGraph? If you go to the "Model Of" section of the documentation for adjacency_list, you will see that adjacency_list does indeed model IncidenceGraph and VertexListGraph.
The IncidenceGraph concept is a central one to the BGL. It defines the main interface for traversing the adjacency structure of the graph. It requires the valid expression out_edges(u, g) (where u is a vertex and g is a graph), which returns the type std::pair<out_edge_iterator, out_edge_iterator>. The out-edge iterator pair is used to access all of the out edges of vertex u. The expression out_degee(u, g) returns the number of out-edges for vertex u. For each out edge e, you can use the valid expressions source(e, g) and target(e, g) to obtain the vertices incident on the edge.
The result of the topological sort is a sequence of vertices that are written to the output iterator supplied by the user (the result parameter). The vertices are output in reverse topological order (it is more efficient that way), and the user must flip the ordering, if so desired. In the code that follows, this is accomplished by using the reverse iterator of the vector as the output iterator.
For now, you will ignore the params parameter of topological_sort and just use the defaults. The following few lines of code perform the topological sort and output the results:
·Compute the compilation orderÒ∫
std::vector<vertex_descriptor> topo_order(num_vertices(G));
topological_sort(G, topo_order.rbegin());
std::cout << "topological order:\n";
for (std::vector<vertex_descriptor>::iterator i = topo_order.begin();
i != topo_order.end(); ++i)
std::cout << name[*i] << "\n";
The output is as follows:
zag.cpp zig.cpp foo.cpp bar.cpp zow.h boz.h zig.o yow.h dax.h zag.o foo.o bar.o libfoobar.a libzigzag.a killerapp