1 //=======================================================================
2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
8 #include <boost/config.hpp>
9 #include <fstream>
10 #include <iostream>
11 #include <numeric>
12 #include <string>
13 #include <boost/graph/adjacency_list.hpp>
14 #include <boost/graph/graph_utility.hpp>
15 #include <boost/graph/property_iter_range.hpp>
16 #include <boost/graph/depth_first_search.hpp> // for default_dfs_visitor
17
18 namespace std
19 {
20 template < typename T >
operator >>(std::istream & in,std::pair<T,T> & p)21 std::istream& operator>>(std::istream& in, std::pair< T, T >& p)
22 {
23 in >> p.first >> p.second;
24 return in;
25 }
26 }
27
28 namespace boost
29 {
30 enum vertex_compile_cost_t
31 {
32 vertex_compile_cost
33 };
34 BOOST_INSTALL_PROPERTY(vertex, compile_cost);
35 }
36
37 using namespace boost;
38
39 typedef adjacency_list< listS, // Store out-edges of each vertex in a std::list
40 listS, // Store vertex set in a std::list
41 directedS, // The file dependency graph is directed
42 // vertex properties
43 property< vertex_name_t, std::string,
44 property< vertex_compile_cost_t, float,
45 property< vertex_distance_t, float,
46 property< vertex_color_t, default_color_type > > > >,
47 // an edge property
48 property< edge_weight_t, float > >
49 file_dep_graph2;
50
51 typedef graph_traits< file_dep_graph2 >::vertex_descriptor vertex_t;
52 typedef graph_traits< file_dep_graph2 >::edge_descriptor edge_t;
53
54 template < typename Graph, typename ColorMap, typename Visitor >
dfs_v2(const Graph & g,typename graph_traits<Graph>::vertex_descriptor u,ColorMap color,Visitor vis)55 void dfs_v2(const Graph& g, typename graph_traits< Graph >::vertex_descriptor u,
56 ColorMap color, Visitor vis)
57 {
58 typedef typename property_traits< ColorMap >::value_type color_type;
59 typedef color_traits< color_type > ColorT;
60 color[u] = ColorT::gray();
61 vis.discover_vertex(u, g);
62 typename graph_traits< Graph >::out_edge_iterator ei, ei_end;
63 for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei)
64 if (color[target(*ei, g)] == ColorT::white())
65 {
66 vis.tree_edge(*ei, g);
67 dfs_v2(g, target(*ei, g), color, vis);
68 }
69 else if (color[target(*ei, g)] == ColorT::gray())
70 vis.back_edge(*ei, g);
71 else
72 vis.forward_or_cross_edge(*ei, g);
73 color[u] = ColorT::black();
74 vis.finish_vertex(u, g);
75 }
76
77 template < typename Graph, typename Visitor, typename ColorMap >
generic_dfs_v2(const Graph & g,Visitor vis,ColorMap color)78 void generic_dfs_v2(const Graph& g, Visitor vis, ColorMap color)
79 {
80 typedef typename property_traits< ColorMap >::value_type ColorValue;
81 typedef color_traits< ColorValue > ColorT;
82 typename graph_traits< Graph >::vertex_iterator vi, vi_end;
83 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
84 color[*vi] = ColorT::white();
85 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
86 if (color[*vi] == ColorT::white())
87 dfs_v2(g, *vi, color, vis);
88 }
89
90 template < typename OutputIterator >
91 struct topo_visitor : public default_dfs_visitor
92 {
topo_visitortopo_visitor93 topo_visitor(OutputIterator& order) : topo_order(order) {}
94 template < typename Graph >
finish_vertextopo_visitor95 void finish_vertex(
96 typename graph_traits< Graph >::vertex_descriptor u, const Graph&)
97 {
98 *topo_order++ = u;
99 }
100 OutputIterator& topo_order;
101 };
102
103 template < typename Graph, typename OutputIterator, typename ColorMap >
topo_sort(const Graph & g,OutputIterator topo_order,ColorMap color)104 void topo_sort(const Graph& g, OutputIterator topo_order, ColorMap color)
105 {
106 topo_visitor< OutputIterator > vis(topo_order);
107 generic_dfs_v2(g, vis, color);
108 }
109
110 typedef property_map< file_dep_graph2, vertex_name_t >::type name_map_t;
111 typedef property_map< file_dep_graph2, vertex_compile_cost_t >::type
112 compile_cost_map_t;
113 typedef property_map< file_dep_graph2, vertex_distance_t >::type distance_map_t;
114 typedef property_map< file_dep_graph2, vertex_color_t >::type color_map_t;
115
main(int argc,const char ** argv)116 int main(int argc, const char** argv)
117 {
118 std::ifstream file_in(argc >= 2 ? argv[1] : "makefile-dependencies.dat");
119 typedef graph_traits< file_dep_graph2 >::vertices_size_type size_type;
120 size_type n_vertices;
121 file_in >> n_vertices; // read in number of vertices
122 std::istream_iterator< std::pair< size_type, size_type > > input_begin(
123 file_in),
124 input_end;
125 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
126 // VC++ can't handle the iterator constructor
127 file_dep_graph2 g;
128 typedef graph_traits< file_dep_graph2 >::vertex_descriptor vertex_t;
129 std::vector< vertex_t > id2vertex;
130 for (std::size_t v = 0; v < n_vertices; ++v)
131 id2vertex.push_back(add_vertex(g));
132 while (input_begin != input_end)
133 {
134 size_type i, j;
135 boost::tie(i, j) = *input_begin++;
136 add_edge(id2vertex[i], id2vertex[j], g);
137 }
138 #else
139 file_dep_graph2 g(input_begin, input_end, n_vertices);
140 #endif
141
142 name_map_t name_map = get(vertex_name, g);
143 compile_cost_map_t compile_cost_map = get(vertex_compile_cost, g);
144 distance_map_t distance_map = get(vertex_distance, g);
145 color_map_t color_map = get(vertex_color, g);
146
147 {
148 std::ifstream name_in(
149 argc >= 3 ? argv[2] : "makefile-target-names.dat");
150 std::ifstream compile_cost_in(
151 argc >= 4 ? argv[3] : "target-compile-costs.dat");
152 graph_traits< file_dep_graph2 >::vertex_iterator vi, vi_end;
153 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
154 {
155 name_in >> name_map[*vi];
156 compile_cost_in >> compile_cost_map[*vi];
157 }
158 }
159 std::vector< vertex_t > topo_order(num_vertices(g));
160 topo_sort(g, topo_order.rbegin(), color_map);
161
162 graph_traits< file_dep_graph2 >::vertex_iterator i, i_end;
163 graph_traits< file_dep_graph2 >::adjacency_iterator vi, vi_end;
164
165 // find source vertices with zero in-degree by marking all vertices with
166 // incoming edges
167 for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i)
168 color_map[*i] = white_color;
169 for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i)
170 for (boost::tie(vi, vi_end) = adjacent_vertices(*i, g); vi != vi_end;
171 ++vi)
172 color_map[*vi] = black_color;
173
174 // initialize distances to zero, or for source vertices, to the compile cost
175 for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i)
176 if (color_map[*i] == white_color)
177 distance_map[*i] = compile_cost_map[*i];
178 else
179 distance_map[*i] = 0;
180
181 std::vector< vertex_t >::iterator ui;
182 for (ui = topo_order.begin(); ui != topo_order.end(); ++ui)
183 {
184 vertex_t u = *ui;
185 for (boost::tie(vi, vi_end) = adjacent_vertices(u, g); vi != vi_end;
186 ++vi)
187 if (distance_map[*vi] < distance_map[u] + compile_cost_map[*vi])
188 distance_map[*vi] = distance_map[u] + compile_cost_map[*vi];
189 }
190
191 graph_property_iter_range< file_dep_graph2, vertex_distance_t >::iterator
192 ci,
193 ci_end;
194 boost::tie(ci, ci_end) = get_property_iter_range(g, vertex_distance);
195 std::cout << "total (parallel) compile time: "
196 << *std::max_element(ci, ci_end) << std::endl;
197
198 return 0;
199 }
200