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>
12 #include <boost/graph/adjacency_list.hpp>
13 #include <boost/graph/graph_utility.hpp>
15 using namespace boost
;
19 template < typename T
>
20 std::istream
& operator >> (std::istream
& in
, std::pair
< T
, T
> &p
)
22 in
>> p
.first
>> p
.second
;
27 typedef adjacency_list
< listS
, // Store out-edges of each vertex in a std::list
28 vecS
, // Store vertex set in a std::vector
29 directedS
// The file dependency graph is directed
32 typedef graph_traits
< file_dep_graph
>::vertex_descriptor vertex_t
;
33 typedef graph_traits
< file_dep_graph
>::edge_descriptor edge_t
;
36 topo_sort_dfs(const file_dep_graph
& g
, vertex_t u
, vertex_t
* &topo_order
,
39 mark
[u
] = 1; // 1 means visited, 0 means not yet visited
40 graph_traits
< file_dep_graph
>::adjacency_iterator vi
, vi_end
;
41 for (boost::tie(vi
, vi_end
) = adjacent_vertices(u
, g
); vi
!= vi_end
; ++vi
)
43 topo_sort_dfs(g
, *vi
, topo_order
, mark
);
49 topo_sort(const file_dep_graph
& g
, vertex_t
* topo_order
)
51 std::vector
< int >mark(num_vertices(g
), 0);
52 graph_traits
< file_dep_graph
>::vertex_iterator vi
, vi_end
;
53 for (boost::tie(vi
, vi_end
) = vertices(g
); vi
!= vi_end
; ++vi
)
55 topo_sort_dfs(g
, *vi
, topo_order
, &mark
[0]);
62 std::ifstream
file_in("makefile-dependencies.dat");
63 typedef graph_traits
< file_dep_graph
>::vertices_size_type size_type
;
65 file_in
>> n_vertices
; // read in number of vertices
66 std::istream_iterator
< std::pair
< size_type
, size_type
> >
67 input_begin(file_in
), input_end
;
68 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
69 // VC++ can't handle the iterator constructor
70 file_dep_graph
g(n_vertices
);
71 while (input_begin
!= input_end
) {
73 boost::tie(i
, j
) = *input_begin
++;
77 file_dep_graph
g(input_begin
, input_end
, n_vertices
);
80 std::vector
< std::string
> name(num_vertices(g
));
81 std::ifstream
name_in("makefile-target-names.dat");
82 graph_traits
< file_dep_graph
>::vertex_iterator vi
, vi_end
;
83 for (boost::tie(vi
, vi_end
) = vertices(g
); vi
!= vi_end
; ++vi
)
86 std::vector
< vertex_t
> order(num_vertices(g
));
87 topo_sort(g
, &order
[0] + num_vertices(g
));
88 for (size_type i
= 0; i
< num_vertices(g
); ++i
)
89 std::cout
<< name
[order
[i
]] << std::endl
;