1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9
10 // Some small modifications are done by Alexander Holler
11
12 /*
13
14 Paul Moore's request:
15
16 As an example of a practical problem which is not restricted to graph
17 "experts", consider file dependencies. It's basically graph construction,
18 plus topological sort, but it might make a nice "tutorial" example. Build a
19 dependency graph of files, then use the algorithms to do things like
20
21 1. Produce a full recompilation order (topological sort, by modified date)
22 2. Produce a "parallel" recompilation order (same as above, but group files
23 which can be built in parallel)
24 3. Change analysis (if I change file x, which others need recompiling)
25 4. Dependency changes (if I add a dependency between file x and file y, what
26 are the effects)
27
28 */
29
30 #include <boost/config.hpp> // put this first to suppress some VC++ warnings
31
32 #include <iostream>
33 #include <iterator>
34 #include <algorithm>
35 #include <time.h>
36
37 #include <boost/utility.hpp>
38 #include <boost/graph/adjacency_list.hpp>
39 #include <boost/graph/topological_sort.hpp>
40 #include <boost/graph/depth_first_search.hpp>
41 #include <boost/graph/dijkstra_shortest_paths.hpp>
42 #include <boost/graph/visitors.hpp>
43
44 using namespace std;
45 using namespace boost;
46
47 enum files_e
48 {
49 dax_h,
50 yow_h,
51 boz_h,
52 zow_h,
53 foo_cpp,
54 foo_o,
55 bar_cpp,
56 bar_o,
57 libfoobar_a,
58 zig_cpp,
59 zig_o,
60 zag_cpp,
61 zag_o,
62 libzigzag_a,
63 killerapp,
64 N
65 };
66 const char* name[] = { "dax.h", "yow.h", "boz.h", "zow.h", "foo.cpp", "foo.o",
67 "bar.cpp", "bar.o", "libfoobar.a", "zig.cpp", "zig.o", "zag.cpp", "zag.o",
68 "libzigzag.a", "killerapp" };
69
70 struct print_visitor : public bfs_visitor<>
71 {
72 template < class Vertex, class Graph >
discover_vertexprint_visitor73 void discover_vertex(Vertex v, Graph&)
74 {
75 cout << name[v] << " ";
76 }
77 };
78
79 struct cycle_detector : public dfs_visitor<>
80 {
cycle_detectorcycle_detector81 cycle_detector(bool& has_cycle) : m_has_cycle(has_cycle) {}
82
back_edgecycle_detector83 template < class Edge, class Graph > void back_edge(Edge, Graph&)
84 {
85 m_has_cycle = true;
86 }
87
88 protected:
89 bool& m_has_cycle;
90 };
91
main(int,char * [])92 int main(int, char*[])
93 {
94
95 typedef pair< int, int > Edge;
96 Edge used_by[] = { Edge(dax_h, foo_cpp), Edge(dax_h, bar_cpp),
97 Edge(dax_h, yow_h), Edge(yow_h, bar_cpp), Edge(yow_h, zag_cpp),
98 Edge(boz_h, bar_cpp), Edge(boz_h, zig_cpp), Edge(boz_h, zag_cpp),
99 Edge(zow_h, foo_cpp), Edge(foo_cpp, foo_o), Edge(foo_o, libfoobar_a),
100 Edge(bar_cpp, bar_o), Edge(bar_o, libfoobar_a),
101 Edge(libfoobar_a, libzigzag_a), Edge(zig_cpp, zig_o),
102 Edge(zig_o, libzigzag_a), Edge(zag_cpp, zag_o),
103 Edge(zag_o, libzigzag_a), Edge(libzigzag_a, killerapp) };
104 const std::size_t nedges = sizeof(used_by) / sizeof(Edge);
105
106 typedef adjacency_list< vecS, vecS, bidirectionalS > Graph;
107 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
108 // VC++ can't handle the iterator constructor
109 Graph g(N);
110 for (std::size_t j = 0; j < nedges; ++j)
111 {
112 graph_traits< Graph >::edge_descriptor e;
113 bool inserted;
114 boost::tie(e, inserted)
115 = add_edge(used_by[j].first, used_by[j].second, g);
116 }
117 #else
118 Graph g(used_by, used_by + nedges, N);
119 #endif
120 typedef graph_traits< Graph >::vertex_descriptor Vertex;
121
122 // Determine ordering for a full recompilation
123 // and the order with files that can be compiled in parallel
124 {
125 typedef list< Vertex > MakeOrder;
126 MakeOrder::iterator i;
127 MakeOrder make_order;
128
129 topological_sort(g, std::front_inserter(make_order));
130 cout << "make ordering: ";
131 for (i = make_order.begin(); i != make_order.end(); ++i)
132 cout << name[*i] << " ";
133
134 cout << endl << endl;
135
136 // Parallel compilation ordering
137 std::vector< int > time(N, 0);
138 for (i = make_order.begin(); i != make_order.end(); ++i)
139 {
140 // Walk through the in_edges an calculate the maximum time.
141 if (in_degree(*i, g) > 0)
142 {
143 Graph::in_edge_iterator j, j_end;
144 int maxdist = 0;
145 // Through the order from topological sort, we are sure that
146 // every time we are using here is already initialized.
147 for (boost::tie(j, j_end) = in_edges(*i, g); j != j_end; ++j)
148 maxdist = (std::max)(time[source(*j, g)], maxdist);
149 time[*i] = maxdist + 1;
150 }
151 }
152
153 cout << "parallel make ordering, " << endl
154 << "vertices with same group number can be made in parallel"
155 << endl;
156 {
157 graph_traits< Graph >::vertex_iterator i, iend;
158 for (boost::tie(i, iend) = vertices(g); i != iend; ++i)
159 cout << "time_slot[" << name[*i] << "] = " << time[*i] << endl;
160 }
161 }
162 cout << endl;
163
164 // if I change yow.h what files need to be re-made?
165 {
166 cout << "A change to yow.h will cause what to be re-made?" << endl;
167 print_visitor vis;
168 breadth_first_search(g, vertex(yow_h, g), visitor(vis));
169 cout << endl;
170 }
171 cout << endl;
172
173 // are there any cycles in the graph?
174 {
175 bool has_cycle = false;
176 cycle_detector vis(has_cycle);
177 depth_first_search(g, visitor(vis));
178 cout << "The graph has a cycle? " << has_cycle << endl;
179 }
180 cout << endl;
181
182 // add a dependency going from bar.cpp to dax.h
183 {
184 cout << "adding edge bar_cpp -> dax_h" << endl;
185 add_edge(bar_cpp, dax_h, g);
186 }
187 cout << endl;
188
189 // are there any cycles in the graph?
190 {
191 bool has_cycle = false;
192 cycle_detector vis(has_cycle);
193 depth_first_search(g, visitor(vis));
194 cout << "The graph has a cycle now? " << has_cycle << endl;
195 }
196
197 return 0;
198 }
199