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