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