1 //=======================================================================
2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
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>
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
20 template < typename T
>
21 std::istream
& operator>>(std::istream
& in
, std::pair
< T
, T
>& p
)
23 in
>> p
.first
>> p
.second
;
30 enum vertex_compile_cost_t
34 BOOST_INSTALL_PROPERTY(vertex
, compile_cost
);
37 using namespace boost
;
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
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
> > > >,
48 property
< edge_weight_t
, float > >
51 typedef graph_traits
< file_dep_graph2
>::vertex_descriptor vertex_t
;
52 typedef graph_traits
< file_dep_graph2
>::edge_descriptor edge_t
;
54 template < typename Graph
, typename ColorMap
, typename Visitor
>
55 void dfs_v2(const Graph
& g
, typename graph_traits
< Graph
>::vertex_descriptor u
,
56 ColorMap color
, Visitor vis
)
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())
66 vis
.tree_edge(*ei
, g
);
67 dfs_v2(g
, target(*ei
, g
), color
, vis
);
69 else if (color
[target(*ei
, g
)] == ColorT::gray())
70 vis
.back_edge(*ei
, g
);
72 vis
.forward_or_cross_edge(*ei
, g
);
73 color
[u
] = ColorT::black();
74 vis
.finish_vertex(u
, g
);
77 template < typename Graph
, typename Visitor
, typename ColorMap
>
78 void generic_dfs_v2(const Graph
& g
, Visitor vis
, ColorMap color
)
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
);
90 template < typename OutputIterator
>
91 struct topo_visitor
: public default_dfs_visitor
93 topo_visitor(OutputIterator
& order
) : topo_order(order
) {}
94 template < typename Graph
>
96 typename graph_traits
< Graph
>::vertex_descriptor u
, const Graph
&)
100 OutputIterator
& topo_order
;
103 template < typename Graph
, typename OutputIterator
, typename ColorMap
>
104 void topo_sort(const Graph
& g
, OutputIterator topo_order
, ColorMap color
)
106 topo_visitor
< OutputIterator
> vis(topo_order
);
107 generic_dfs_v2(g
, vis
, color
);
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
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
;
116 int main(int argc
, const char** argv
)
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(
125 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
126 // VC++ can't handle the iterator constructor
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
)
135 boost::tie(i
, j
) = *input_begin
++;
136 add_edge(id2vertex
[i
], id2vertex
[j
], g
);
139 file_dep_graph2
g(input_begin
, input_end
, n_vertices
);
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
);
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
)
155 name_in
>> name_map
[*vi
];
156 compile_cost_in
>> compile_cost_map
[*vi
];
159 std::vector
< vertex_t
> topo_order(num_vertices(g
));
160 topo_sort(g
, topo_order
.rbegin(), color_map
);
162 graph_traits
< file_dep_graph2
>::vertex_iterator i
, i_end
;
163 graph_traits
< file_dep_graph2
>::adjacency_iterator vi
, vi_end
;
165 // find source vertices with zero in-degree by marking all vertices with
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
;
172 color_map
[*vi
] = black_color
;
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
];
179 distance_map
[*i
] = 0;
181 std::vector
< vertex_t
>::iterator ui
;
182 for (ui
= topo_order
.begin(); ui
!= topo_order
.end(); ++ui
)
185 for (boost::tie(vi
, vi_end
) = adjacent_vertices(u
, g
); vi
!= vi_end
;
187 if (distance_map
[*vi
] < distance_map
[u
] + compile_cost_map
[*vi
])
188 distance_map
[*vi
] = distance_map
[u
] + compile_cost_map
[*vi
];
191 graph_property_iter_range
< file_dep_graph2
, vertex_distance_t
>::iterator
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
;