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
{ vertex_compile_cost
};
31 BOOST_INSTALL_PROPERTY(vertex
, compile_cost
);
34 using namespace boost
;
36 typedef adjacency_list
< listS
, // Store out-edges of each vertex in a std::list
37 listS
, // Store vertex set in a std::list
38 directedS
, // The file dependency graph is directed
40 property
< vertex_name_t
, std::string
,
41 property
< vertex_compile_cost_t
, float,
42 property
< vertex_distance_t
, float,
43 property
< vertex_color_t
, default_color_type
> > > >,
45 property
< edge_weight_t
, float > >
48 typedef graph_traits
<file_dep_graph2
>::vertex_descriptor vertex_t
;
49 typedef graph_traits
<file_dep_graph2
>::edge_descriptor edge_t
;
52 template < typename Graph
, typename ColorMap
, typename Visitor
> void
53 dfs_v2(const Graph
& g
,
54 typename graph_traits
< Graph
>::vertex_descriptor u
,
55 ColorMap color
, Visitor vis
)
57 typedef typename property_traits
< ColorMap
>::value_type color_type
;
58 typedef color_traits
< color_type
> ColorT
;
59 color
[u
] = ColorT::gray();
60 vis
.discover_vertex(u
, g
);
61 typename graph_traits
< Graph
>::out_edge_iterator ei
, ei_end
;
62 for (boost::tie(ei
, ei_end
) = out_edges(u
, g
); ei
!= ei_end
; ++ei
)
63 if (color
[target(*ei
, g
)] == ColorT::white()) {
64 vis
.tree_edge(*ei
, g
);
65 dfs_v2(g
, target(*ei
, g
), color
, vis
);
66 } else if (color
[target(*ei
, g
)] == ColorT::gray())
67 vis
.back_edge(*ei
, g
);
69 vis
.forward_or_cross_edge(*ei
, g
);
70 color
[u
] = ColorT::black();
71 vis
.finish_vertex(u
, g
);
74 template < typename Graph
, typename Visitor
, typename ColorMap
> void
75 generic_dfs_v2(const Graph
& g
, Visitor vis
, ColorMap color
)
77 typedef typename property_traits
<ColorMap
>::value_type ColorValue
;
78 typedef color_traits
< ColorValue
> ColorT
;
79 typename graph_traits
< Graph
>::vertex_iterator vi
, vi_end
;
80 for (boost::tie(vi
, vi_end
) = vertices(g
); vi
!= vi_end
; ++vi
)
81 color
[*vi
] = ColorT::white();
82 for (boost::tie(vi
, vi_end
) = vertices(g
); vi
!= vi_end
; ++vi
)
83 if (color
[*vi
] == ColorT::white())
84 dfs_v2(g
, *vi
, color
, vis
);
88 template < typename OutputIterator
>
89 struct topo_visitor
: public default_dfs_visitor
91 topo_visitor(OutputIterator
& order
):
95 template < typename Graph
> void
96 finish_vertex(typename graph_traits
< Graph
>::vertex_descriptor u
,
101 OutputIterator
& topo_order
;
104 template < typename Graph
, typename OutputIterator
, typename ColorMap
> void
105 topo_sort(const Graph
& g
, OutputIterator topo_order
, ColorMap color
)
107 topo_visitor
< OutputIterator
> vis(topo_order
);
108 generic_dfs_v2(g
, vis
, color
);
112 typedef property_map
< file_dep_graph2
, vertex_name_t
>::type name_map_t
;
113 typedef property_map
< file_dep_graph2
, vertex_compile_cost_t
>::type
115 typedef property_map
< file_dep_graph2
, vertex_distance_t
>::type distance_map_t
;
116 typedef property_map
< file_dep_graph2
, vertex_color_t
>::type color_map_t
;
122 std::ifstream
file_in("makefile-dependencies.dat");
123 typedef graph_traits
< file_dep_graph2
>::vertices_size_type size_type
;
124 size_type n_vertices
;
125 file_in
>> n_vertices
; // read in number of vertices
126 std::istream_iterator
< std::pair
< size_type
,
127 size_type
> >input_begin(file_in
), input_end
;
128 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
129 // VC++ can't handle the iterator constructor
131 typedef graph_traits
<file_dep_graph2
>::vertex_descriptor vertex_t
;
132 std::vector
<vertex_t
> id2vertex
;
133 for (std::size_t v
= 0; v
< n_vertices
; ++v
)
134 id2vertex
.push_back(add_vertex(g
));
135 while (input_begin
!= input_end
) {
137 boost::tie(i
, j
) = *input_begin
++;
138 add_edge(id2vertex
[i
], id2vertex
[j
], g
);
141 file_dep_graph2
g(input_begin
, input_end
, n_vertices
);
149 get(vertex_compile_cost
, g
);
152 get(vertex_distance
, g
);
155 get(vertex_color
, g
);
158 std::ifstream
name_in("makefile-target-names.dat");
159 std::ifstream
compile_cost_in("target-compile-costs.dat");
160 graph_traits
< file_dep_graph2
>::vertex_iterator vi
, vi_end
;
161 for (boost::tie(vi
, vi_end
) = vertices(g
); vi
!= vi_end
; ++vi
) {
162 name_in
>> name_map
[*vi
];
163 compile_cost_in
>> compile_cost_map
[*vi
];
167 std::vector
< vertex_t
> topo_order(num_vertices(g
));
168 topo_sort(g
, topo_order
.rbegin(), color_map
);
170 graph_traits
< file_dep_graph2
>::vertex_iterator i
, i_end
;
171 graph_traits
< file_dep_graph2
>::adjacency_iterator vi
, vi_end
;
173 // find source vertices with zero in-degree by marking all vertices with incoming edges
174 for (boost::tie(i
, i_end
) = vertices(g
); i
!= i_end
; ++i
)
175 color_map
[*i
] = white_color
;
176 for (boost::tie(i
, i_end
) = vertices(g
); i
!= i_end
; ++i
)
177 for (boost::tie(vi
, vi_end
) = adjacent_vertices(*i
, g
); vi
!= vi_end
; ++vi
)
178 color_map
[*vi
] = black_color
;
180 // initialize distances to zero, or for source vertices, to the compile cost
181 for (boost::tie(i
, i_end
) = vertices(g
); i
!= i_end
; ++i
)
182 if (color_map
[*i
] == white_color
)
183 distance_map
[*i
] = compile_cost_map
[*i
];
185 distance_map
[*i
] = 0;
187 std::vector
< vertex_t
>::iterator ui
;
188 for (ui
= topo_order
.begin(); ui
!= topo_order
.end(); ++ui
) {
192 for (boost::tie(vi
, vi_end
) = adjacent_vertices(u
, g
); vi
!= vi_end
; ++vi
)
193 if (distance_map
[*vi
] < distance_map
[u
] + compile_cost_map
[*vi
])
194 distance_map
[*vi
] = distance_map
[u
] + compile_cost_map
[*vi
];
197 graph_property_iter_range
< file_dep_graph2
,
198 vertex_distance_t
>::iterator ci
, ci_end
;
199 boost::tie(ci
, ci_end
) = get_property_iter_range(g
, vertex_distance
);
200 std::cout
<< "total (parallel) compile time: "
201 << *std::max_element(ci
, ci_end
) << std::endl
;