364 lines
12 KiB
HTML
364 lines
12 KiB
HTML
<HTML>
|
|
<!--
|
|
Copyright (c) Jeremy Siek 2000
|
|
|
|
Distributed under the Boost Software License, Version 1.0.
|
|
(See accompanying file LICENSE_1_0.txt or copy at
|
|
http://www.boost.org/LICENSE_1_0.txt)
|
|
-->
|
|
<Head>
|
|
<Title>File Dependency Example</Title>
|
|
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
|
|
ALINK="#ff0000">
|
|
<IMG SRC="../../../boost.png"
|
|
ALT="C++ Boost" width="277" height="86">
|
|
|
|
<BR Clear>
|
|
|
|
|
|
<H1><A NAME="sec:file-depend-eg"></A>
|
|
File Dependency Example
|
|
</H1>
|
|
|
|
<P>
|
|
One of the most common uses of the graph abstraction in computer
|
|
science is to track dependencies. An example of dependency tracking
|
|
that we deal with on a day to day basis is the compilation
|
|
dependencies for files in programs that we write. These dependencies
|
|
are used inside programs such as <TT>make</TT> or in an IDE such as
|
|
Visual C++ to minimize the number of files that must be recompiled
|
|
after some changes have been made.
|
|
|
|
<P>
|
|
<A HREF="#fig:file-dep">Figure 1</A> shows a graph that has a vertex
|
|
for each source file, object file, and library that is used in the
|
|
<TT>killerapp</TT> program. The edges in the graph show which files
|
|
are used in creating other files. The choice of which direction to
|
|
point the arrows is somewhat arbitrary. As long as we are consistent
|
|
in remembering that the arrows mean ``used by'' then things will work
|
|
out. The opposite direction would mean ``depends on''.
|
|
|
|
<P>
|
|
|
|
<P></P>
|
|
<DIV ALIGN="CENTER"><A NAME="fig:file-dep"></A>
|
|
<TABLE>
|
|
<CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG>
|
|
A graph representing file dependencies.</CAPTION>
|
|
<TR><TD><IMG SRC="./figs/file_dep.gif" width="331" height="351"></TD></TR>
|
|
</TABLE>
|
|
</DIV><P></P>
|
|
|
|
<P>
|
|
A compilation system such as <TT>make</TT> has to be able to answer a
|
|
number of questions:
|
|
|
|
<P>
|
|
|
|
<OL>
|
|
<LI>If we need to compile (or recompile) all of the files, what order
|
|
should that be done it?
|
|
</LI>
|
|
<LI>What files can be compiled in parallel?
|
|
</LI>
|
|
<LI>If a file is changed, which files must be recompiled?
|
|
</LI>
|
|
<LI>Are there any cycles in the dependencies? (which means the user
|
|
has made a mistake and an error should be emitted)
|
|
</LI>
|
|
</OL>
|
|
|
|
<P>
|
|
In the following examples we will formulate each of these questions in
|
|
terms of the dependency graph, and then find a graph algorithm to
|
|
provide the solution. The graph in <A HREF="#fig:file-dep">Figure
|
|
1</A> will be used in all of the following examples. The source code
|
|
for this example can be found in the file <a
|
|
href="../example/file_dependencies.cpp"><TT>examples/file_dependencies.cpp</TT></a>.
|
|
|
|
<P>
|
|
|
|
<H2>Graph Setup</H2>
|
|
|
|
<P>
|
|
Here we show the construction of the graph. First, these are the required
|
|
header files:
|
|
|
|
<P>
|
|
<PRE>
|
|
#include <iostream> // std::cout
|
|
#include <utility> // std::pair
|
|
#include <boost/graph/graph_traits.hpp>
|
|
#include <boost/graph/adjacency_list.hpp>
|
|
#include <boost/graph/topological_sort.hpp>
|
|
</PRE>
|
|
|
|
<P>
|
|
For simplicity we have
|
|
constructed the graph "by-hand". A compilation system such
|
|
as <TT>make</TT> would instead parse a <TT>Makefile</TT> to get the
|
|
list of files and to set-up the dependencies. We use the
|
|
<TT>adjacency_list</TT> class to represent the graph. The
|
|
<TT>vecS</TT> selector means that a <TT>std::vector</TT> will be used
|
|
to represent each edge-list, which provides efficient traversal. The
|
|
<TT>bidirectionalS</TT> selector means we want a directed graph with access to both the edges outgoing from each vertex and the edges incoming to each vertex, and the
|
|
<TT>color_property</TT> attaches a color property to each vertex of the
|
|
graph. The color property will be used in several of the algorithms in
|
|
the following sections.
|
|
|
|
<P>
|
|
<PRE>
|
|
enum files_e { dax_h, yow_h, boz_h, zow_h, foo_cpp,
|
|
foo_o, bar_cpp, bar_o, libfoobar_a,
|
|
zig_cpp, zig_o, zag_cpp, zag_o,
|
|
libzigzag_a, killerapp, N };
|
|
const char* name[] = { "dax.h", "yow.h", "boz.h", "zow.h", "foo.cpp",
|
|
"foo.o", "bar.cpp", "bar.o", "libfoobar.a",
|
|
"zig.cpp", "zig.o", "zag.cpp", "zag.o",
|
|
"libzigzag.a", "killerapp" };
|
|
|
|
typedef std::pair<int, int> Edge;
|
|
Edge used_by[] = {
|
|
Edge(dax_h, foo_cpp), Edge(dax_h, bar_cpp), Edge(dax_h, yow_h),
|
|
Edge(yow_h, bar_cpp), Edge(yow_h, zag_cpp),
|
|
Edge(boz_h, bar_cpp), Edge(boz_h, zig_cpp), Edge(boz_h, zag_cpp),
|
|
Edge(zow_h, foo_cpp),
|
|
Edge(foo_cpp, foo_o),
|
|
Edge(foo_o, libfoobar_a),
|
|
Edge(bar_cpp, bar_o),
|
|
Edge(bar_o, libfoobar_a),
|
|
Edge(libfoobar_a, libzigzag_a),
|
|
Edge(zig_cpp, zig_o),
|
|
Edge(zig_o, libzigzag_a),
|
|
Edge(zag_cpp, zag_o),
|
|
Edge(zag_o, libzigzag_a),
|
|
Edge(libzigzag_a, killerapp)
|
|
};
|
|
|
|
using namespace boost;
|
|
typedef adjacency_list<vecS, vecS, bidirectionalS,
|
|
property<vertex_color_t, default_color_type>
|
|
> Graph;
|
|
Graph g(used_by, used_by + sizeof(used_by) / sizeof(Edge), N);
|
|
typedef graph_traits<Graph>::vertex_descriptor Vertex;
|
|
</PRE>
|
|
|
|
<P>
|
|
|
|
<H2>Compilation Order (All Files)</H2>
|
|
|
|
<P>
|
|
On the first invocation of <TT>make</TT> for a particular project, all
|
|
of the files must be compiled. Given the dependencies between the
|
|
various files, what is the correct order in which to compile and link
|
|
them? First we need to formulate this in terms of a graph. Finding a
|
|
compilation order is the same as ordering the vertices in the graph.
|
|
The constraint on the ordering is the file dependencies which we have
|
|
represented as edges. So if there is an edge <i>(u,v)</i> in the graph
|
|
then <i>v</i> better not come before <i>u</i> in the ordering. It
|
|
turns out that this kind of constrained ordering is called a
|
|
<I>topological sort</I>. Therefore, answering the question of
|
|
compilation order is as easy as calling the BGL algorithm <a
|
|
href="./topological_sort.html"><TT>topological_sort()</TT></a>. The
|
|
traditional form of the output for topological sort is a linked-list
|
|
of the sorted vertices. The BGL algorithm instead puts the sorted
|
|
vertices into any <a
|
|
href="http://www.boost.org/sgi/stl/OutputIterator.html">OutputIterator</a>,
|
|
which allows for much more flexibility. Here we use the
|
|
<TT>std::front_insert_iterator</TT> to create an output iterator that
|
|
inserts the vertices on the front of a linked list. Other possible
|
|
options are writing the output to a file or inserting into a different
|
|
STL or custom-made container.
|
|
|
|
<P>
|
|
<PRE>
|
|
typedef std::list<Vertex> MakeOrder;
|
|
MakeOrder make_order;
|
|
boost::topological_sort(g, std::front_inserter(make_order));
|
|
|
|
std::cout << "make ordering: ";
|
|
for (MakeOrder::iterator i = make_order.begin();
|
|
i != make_order.end(); ++i)
|
|
std::cout << name[*i] << " ";
|
|
std::cout << std::endl;
|
|
</PRE>
|
|
The output of this is:
|
|
<PRE>
|
|
make ordering: zow.h boz.h zig.cpp zig.o dax.h yow.h zag.cpp \
|
|
zag.o bar.cpp bar.o foo.cpp foo.o libfoobar.a libzigzag.a killerapp
|
|
</PRE>
|
|
|
|
<P>
|
|
|
|
<H2><A NAME="sec:parallel-compilation"></A>
|
|
Parallel Compilation
|
|
</H2>
|
|
|
|
<P>
|
|
Another question the compilation system might need to answer is: what
|
|
files can be compiled simultaneously? This would allow the system to
|
|
spawn threads and utilize multiple processors to speed up the build.
|
|
This question can also be put in a slightly different way: what is the
|
|
earliest time that a file can be built assuming that an unlimited
|
|
number of files can be built at the same time? The main criteria for
|
|
when a file can be built is that all of the files it depends on must
|
|
already be built. To simplify things for this example, we'll assume
|
|
that each file takes 1 time unit to build (even header files). For
|
|
parallel compilation, we can build all of the files corresponding to
|
|
vertices with no dependencies, e.g., those that have
|
|
an <i>in-degree</i> of 0, in the first step. For all other files, the
|
|
main observation for determining the ``time slot'' for a file is that
|
|
the time slot must be one more than the maximum time-slot of the files
|
|
it depends on.
|
|
|
|
<P>We start by creating a vector <code>time</code> that will store the
|
|
time step at which each file can be built. We initialize every value
|
|
with time step zero.</p>
|
|
|
|
<P>
|
|
<PRE>
|
|
std::vector<int> time(N, 0);
|
|
</PRE>
|
|
|
|
<p>Now, we want to visit the vertices against in topological order,
|
|
from those files that need to be built first until those that need
|
|
to be built last. However, instead of printing out the order
|
|
immediately, we will compute the time step in which each file should
|
|
be built based on the time steps of the files it depends on. We
|
|
only need to consider those files whose in-degree is greater than
|
|
zero.</p>
|
|
|
|
<pre>
|
|
for (i = make_order.begin(); i != make_order.end(); ++i) {
|
|
if (in_degree (*i, g) > 0) {
|
|
Graph::in_edge_iterator j, j_end;
|
|
int maxdist = 0;
|
|
for (boost::tie(j, j_end) = in_edges(*i, g); j != j_end; ++j)
|
|
maxdist = std::max(time[source(*j, g)], maxdist);
|
|
time[*i]=maxdist+1;
|
|
}
|
|
}
|
|
</pre>
|
|
|
|
<P>
|
|
Last, we output the time-slot that we've calculated for each vertex.
|
|
|
|
<P>
|
|
<PRE>
|
|
std::cout << "parallel make ordering, " << std::endl
|
|
<< " vertices with same group number" << std::endl
|
|
<< " can be made in parallel" << std::endl << std::endl;
|
|
for (boost::tie(i, iend) = vertices(g); i != iend; ++i)
|
|
std::cout << "time_slot[" << name[*i] << "] = " << time[*i] << std::endl;
|
|
</PRE>
|
|
The output is:
|
|
<PRE>
|
|
parallel make ordering,
|
|
vertices with same group number
|
|
can be made in parallel
|
|
time_slot[dax.h] = 0
|
|
time_slot[yow.h] = 1
|
|
time_slot[boz.h] = 0
|
|
time_slot[zow.h] = 0
|
|
time_slot[foo.cpp] = 1
|
|
time_slot[foo.o] = 2
|
|
time_slot[bar.cpp] = 2
|
|
time_slot[bar.o] = 3
|
|
time_slot[libfoobar.a] = 4
|
|
time_slot[zig.cpp] = 1
|
|
time_slot[zig.o] = 2
|
|
time_slot[zag.cpp] = 2
|
|
time_slot[zag.o] = 3
|
|
time_slot[libzigzag.a] = 5
|
|
time_slot[killerapp] = 6
|
|
</PRE>
|
|
|
|
<P>
|
|
|
|
<H2><A NAME="SECTION001014000000000000000"></A>
|
|
<A NAME="sec:cycles"></A>
|
|
<BR>
|
|
Cyclic Dependencies
|
|
</H2>
|
|
|
|
<P>
|
|
Another question the compilation system needs to be able to answer is
|
|
whether there are any cycles in the dependencies. If there are cycles,
|
|
the system will need to report an error to the user so that the cycles
|
|
can be removed. One easy way to detect a cycle is to run a <a
|
|
href="./depth_first_search.html">depth-first search</a>, and if the
|
|
search runs into an already discovered vertex (of the current search
|
|
tree), then there is a cycle. The BGL graph search algorithms (which
|
|
includes
|
|
<TT>depth_first_search()</TT>) are all extensible via the
|
|
<I>visitor</I> mechanism. A visitor is similar to a function object,
|
|
but it has several methods instead of just the one
|
|
<TT>operator()</TT>. The visitor's methods are called at certain
|
|
points within the algorithm, thereby giving the user a way to extend
|
|
the functionality of the graph search algorithms. See Section <A
|
|
HREF="visitor_concepts.html">Visitor Concepts</A>
|
|
for a detailed description of visitors.
|
|
|
|
<P>
|
|
We will create a visitor class and fill in the <TT>back_edge()</TT>
|
|
method, which is the <a href="./DFSVisitor.html">DFSVisitor</a> method
|
|
that is called when DFS explores an edge to an already discovered
|
|
vertex. A call to this method indicates the existence of a
|
|
cycle. Inheriting from <TT>dfs_visitor<></TT>
|
|
provides the visitor with empty versions of the other visitor methods.
|
|
Once our visitor is created, we can construct and object and pass it
|
|
to the BGL algorithm. Visitor objects are passed by value inside of
|
|
the BGL algorithms, so the <TT>has_cycle</TT> flag is stored by
|
|
reference in this visitor.
|
|
|
|
<P>
|
|
<PRE>
|
|
struct cycle_detector : public dfs_visitor<>
|
|
{
|
|
cycle_detector( bool& has_cycle)
|
|
: _has_cycle(has_cycle) { }
|
|
|
|
template <class Edge, class Graph>
|
|
void back_edge(Edge, Graph&) {
|
|
_has_cycle = true;
|
|
}
|
|
protected:
|
|
bool& _has_cycle;
|
|
};
|
|
</PRE>
|
|
|
|
<P>
|
|
We can now invoke the BGL <TT>depth_first_search()</TT>
|
|
algorithm and pass in the cycle detector visitor.
|
|
|
|
<P>
|
|
<PRE>
|
|
bool has_cycle = false;
|
|
cycle_detector vis(has_cycle);
|
|
boost::depth_first_search(g, visitor(vis));
|
|
std::cout << "The graph has a cycle? " << has_cycle << std::endl;
|
|
</PRE>
|
|
|
|
<P>
|
|
The graph in <A HREF="#fig:file-dep">Figure 1</A> (ignoring the dotted
|
|
line) did not have any cycles, but if we add a dependency between
|
|
<TT>bar.cpp</TT> and <TT>dax.h</TT> there there will be. Such a
|
|
dependency would be flagged as a user error.
|
|
|
|
<P>
|
|
<PRE>
|
|
add_edge(bar_cpp, dax_h, g);
|
|
</PRE>
|
|
|
|
|
|
<br>
|
|
<HR>
|
|
<TABLE>
|
|
<TR valign=top>
|
|
<TD nowrap>Copyright © 2000-2001</TD><TD>
|
|
<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
|
|
</TD></TR></TABLE>
|
|
|
|
</BODY>
|
|
</HTML>
|