| //======================================================================= |
| // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
| // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
| // |
| // 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) |
| //======================================================================= |
| |
| // Some small modifications are done by Alexander Holler |
| |
| /* |
| |
| Paul Moore's request: |
| |
| As an example of a practical problem which is not restricted to graph |
| "experts", consider file dependencies. It's basically graph construction, |
| plus topological sort, but it might make a nice "tutorial" example. Build a |
| dependency graph of files, then use the algorithms to do things like |
| |
| 1. Produce a full recompilation order (topological sort, by modified date) |
| 2. Produce a "parallel" recompilation order (same as above, but group files |
| which can be built in parallel) |
| 3. Change analysis (if I change file x, which others need recompiling) |
| 4. Dependency changes (if I add a dependency between file x and file y, what |
| are the effects) |
| |
| */ |
| |
| #include <boost/config.hpp> // put this first to suppress some VC++ warnings |
| |
| #include <iostream> |
| #include <iterator> |
| #include <algorithm> |
| #include <time.h> |
| |
| #include <boost/utility.hpp> |
| #include <boost/graph/adjacency_list.hpp> |
| #include <boost/graph/topological_sort.hpp> |
| #include <boost/graph/depth_first_search.hpp> |
| #include <boost/graph/dijkstra_shortest_paths.hpp> |
| #include <boost/graph/visitors.hpp> |
| |
| using namespace std; |
| using namespace boost; |
| |
| 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" }; |
| |
| |
| struct print_visitor : public bfs_visitor<> { |
| template <class Vertex, class Graph> |
| void discover_vertex(Vertex v, Graph&) { |
| cout << name[v] << " "; |
| } |
| }; |
| |
| |
| struct cycle_detector : public dfs_visitor<> |
| { |
| cycle_detector(bool& has_cycle) |
| : m_has_cycle(has_cycle) { } |
| |
| template <class Edge, class Graph> |
| void back_edge(Edge, Graph&) { m_has_cycle = true; } |
| protected: |
| bool& m_has_cycle; |
| }; |
| |
| |
| |
| |
| int main(int,char*[]) |
| { |
| |
| typedef 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) |
| }; |
| const std::size_t nedges = sizeof(used_by)/sizeof(Edge); |
| |
| typedef adjacency_list<vecS, vecS, bidirectionalS> Graph; |
| #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 |
| // VC++ can't handle the iterator constructor |
| Graph g(N); |
| for (std::size_t j = 0; j < nedges; ++j) { |
| graph_traits<Graph>::edge_descriptor e; bool inserted; |
| boost::tie(e, inserted) = add_edge(used_by[j].first, used_by[j].second, g); |
| } |
| #else |
| Graph g(used_by, used_by + nedges, N); |
| #endif |
| typedef graph_traits<Graph>::vertex_descriptor Vertex; |
| |
| // Determine ordering for a full recompilation |
| // and the order with files that can be compiled in parallel |
| { |
| typedef list<Vertex> MakeOrder; |
| MakeOrder::iterator i; |
| MakeOrder make_order; |
| |
| topological_sort(g, std::front_inserter(make_order)); |
| cout << "make ordering: "; |
| for (i = make_order.begin(); |
| i != make_order.end(); ++i) |
| cout << name[*i] << " "; |
| |
| cout << endl << endl; |
| |
| // Parallel compilation ordering |
| std::vector<int> time(N, 0); |
| for (i = make_order.begin(); i != make_order.end(); ++i) { |
| // Walk through the in_edges an calculate the maximum time. |
| if (in_degree (*i, g) > 0) { |
| Graph::in_edge_iterator j, j_end; |
| int maxdist=0; |
| // Through the order from topological sort, we are sure that every |
| // time we are using here is already initialized. |
| 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; |
| } |
| } |
| |
| cout << "parallel make ordering, " << endl |
| << "vertices with same group number can be made in parallel" << endl; |
| { |
| graph_traits<Graph>::vertex_iterator i, iend; |
| for (boost::tie(i,iend) = vertices(g); i != iend; ++i) |
| cout << "time_slot[" << name[*i] << "] = " << time[*i] << endl; |
| } |
| |
| } |
| cout << endl; |
| |
| // if I change yow.h what files need to be re-made? |
| { |
| cout << "A change to yow.h will cause what to be re-made?" << endl; |
| print_visitor vis; |
| breadth_first_search(g, vertex(yow_h, g), visitor(vis)); |
| cout << endl; |
| } |
| cout << endl; |
| |
| // are there any cycles in the graph? |
| { |
| bool has_cycle = false; |
| cycle_detector vis(has_cycle); |
| depth_first_search(g, visitor(vis)); |
| cout << "The graph has a cycle? " << has_cycle << endl; |
| } |
| cout << endl; |
| |
| // add a dependency going from bar.cpp to dax.h |
| { |
| cout << "adding edge bar_cpp -> dax_h" << endl; |
| add_edge(bar_cpp, dax_h, g); |
| } |
| cout << endl; |
| |
| // are there any cycles in the graph? |
| { |
| bool has_cycle = false; |
| cycle_detector vis(has_cycle); |
| depth_first_search(g, visitor(vis)); |
| cout << "The graph has a cycle now? " << has_cycle << endl; |
| } |
| |
| return 0; |
| } |