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
>
21 operator >> (std::istream
& in
, std::pair
< T
, T
> &p
)
23 in
>> p
.first
>> p
.second
;
29 typedef adjacency_list
<
30 listS
, // Store out-edges of each vertex in a std::list
31 vecS
, // Store vertex set in a std::vector
32 directedS
// The file dependency graph is directed
35 typedef graph_traits
<file_dep_graph
>::vertex_descriptor vertex_t
;
36 typedef graph_traits
<file_dep_graph
>::edge_descriptor edge_t
;
38 template < typename Visitor
> void
39 dfs_v1(const file_dep_graph
& g
, vertex_t u
, default_color_type
* color
,
42 color
[u
] = gray_color
;
43 vis
.discover_vertex(u
, g
);
44 graph_traits
< file_dep_graph
>::out_edge_iterator ei
, ei_end
;
45 for (boost::tie(ei
, ei_end
) = out_edges(u
, g
); ei
!= ei_end
; ++ei
) {
46 if (color
[target(*ei
, g
)] == white_color
) {
47 vis
.tree_edge(*ei
, g
);
48 dfs_v1(g
, target(*ei
, g
), color
, vis
);
49 } else if (color
[target(*ei
, g
)] == gray_color
)
50 vis
.back_edge(*ei
, g
);
52 vis
.forward_or_cross_edge(*ei
, g
);
54 color
[u
] = black_color
;
55 vis
.finish_vertex(u
, g
);
58 template < typename Visitor
> void
59 generic_dfs_v1(const file_dep_graph
& g
, Visitor vis
)
61 std::vector
< default_color_type
> color(num_vertices(g
), white_color
);
62 graph_traits
< file_dep_graph
>::vertex_iterator vi
, vi_end
;
63 for (boost::tie(vi
, vi_end
) = vertices(g
); vi
!= vi_end
; ++vi
) {
64 if (color
[*vi
] == white_color
)
65 dfs_v1(g
, *vi
, &color
[0], vis
);
69 struct dfs_visitor_default
71 template < typename V
, typename G
> void
72 discover_vertex(V
, const G
&)
76 template < typename E
, typename G
> void
77 tree_edge(E
, const G
&)
81 template < typename E
, typename G
> void
82 back_edge(E
, const G
&)
86 template < typename E
, typename G
> void
87 forward_or_cross_edge(E
, const G
&)
91 template < typename V
, typename G
> void
92 finish_vertex(V
, const G
&)
97 struct topo_visitor
: public dfs_visitor_default
99 topo_visitor(vertex_t
* &order
) : topo_order(order
)
103 finish_vertex(vertex_t u
, const file_dep_graph
&)
107 vertex_t
*& topo_order
;
111 topo_sort(const file_dep_graph
& g
, vertex_t
* topo_order
)
113 topo_visitor
vis(topo_order
);
114 generic_dfs_v1(g
, vis
);
119 main(int argc
, const char** argv
)
121 std::ifstream
file_in(argc
>= 2 ? argv
[1] : "makefile-dependencies.dat");
122 typedef graph_traits
<file_dep_graph
>::vertices_size_type size_type
;
123 size_type n_vertices
;
124 file_in
>> n_vertices
; // read in number of vertices
125 std::istream_iterator
< std::pair
< size_type
,
126 size_type
> >input_begin(file_in
), input_end
;
128 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
129 // VC++ can't handle the iterator constructor
130 file_dep_graph
g(n_vertices
);
131 while (input_begin
!= input_end
) {
133 boost::tie(i
, j
) = *input_begin
++;
137 file_dep_graph
g(input_begin
, input_end
, n_vertices
);
140 std::vector
< std::string
> name(num_vertices(g
));
141 std::ifstream
name_in(argc
>= 2 ? argv
[1] : "makefile-target-names.dat");
142 graph_traits
< file_dep_graph
>::vertex_iterator vi
, vi_end
;
143 for (boost::tie(vi
, vi_end
) = vertices(g
); vi
!= vi_end
; ++vi
)
144 name_in
>> name
[*vi
];
146 std::vector
< vertex_t
> order(num_vertices(g
));
147 topo_sort(g
, &order
[0] + num_vertices(g
));
148 for (size_type i
= 0; i
< num_vertices(g
); ++i
)
149 std::cout
<< name
[order
[i
]] << std::endl
;