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 <string>
12 #include <boost/graph/adjacency_list.hpp>
13 #include <boost/graph/graph_utility.hpp>
14
15 using namespace boost;
16
17 namespace std
18 {
19 template < typename T >
operator >>(std::istream & in,std::pair<T,T> & p)20 std::istream& operator>>(std::istream& in, std::pair< T, T >& p)
21 {
22 in >> p.first >> p.second;
23 return in;
24 }
25 }
26
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
30 >
31 file_dep_graph;
32
33 typedef graph_traits< file_dep_graph >::vertex_descriptor vertex_t;
34 typedef graph_traits< file_dep_graph >::edge_descriptor edge_t;
35
36 template < typename Visitor >
dfs_v1(const file_dep_graph & g,vertex_t u,default_color_type * color,Visitor vis)37 void dfs_v1(
38 const file_dep_graph& g, vertex_t u, default_color_type* color, Visitor vis)
39 {
40 color[u] = gray_color;
41 vis.discover_vertex(u, g);
42 graph_traits< file_dep_graph >::out_edge_iterator ei, ei_end;
43 for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei)
44 {
45 if (color[target(*ei, g)] == white_color)
46 {
47 vis.tree_edge(*ei, g);
48 dfs_v1(g, target(*ei, g), color, vis);
49 }
50 else if (color[target(*ei, g)] == gray_color)
51 vis.back_edge(*ei, g);
52 else
53 vis.forward_or_cross_edge(*ei, g);
54 }
55 color[u] = black_color;
56 vis.finish_vertex(u, g);
57 }
58
59 template < typename Visitor >
generic_dfs_v1(const file_dep_graph & g,Visitor vis)60 void generic_dfs_v1(const file_dep_graph& g, Visitor vis)
61 {
62 std::vector< default_color_type > color(num_vertices(g), white_color);
63 graph_traits< file_dep_graph >::vertex_iterator vi, vi_end;
64 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
65 {
66 if (color[*vi] == white_color)
67 dfs_v1(g, *vi, &color[0], vis);
68 }
69 }
70
71 struct dfs_visitor_default
72 {
discover_vertexdfs_visitor_default73 template < typename V, typename G > void discover_vertex(V, const G&) {}
74
tree_edgedfs_visitor_default75 template < typename E, typename G > void tree_edge(E, const G&) {}
76
back_edgedfs_visitor_default77 template < typename E, typename G > void back_edge(E, const G&) {}
78
forward_or_cross_edgedfs_visitor_default79 template < typename E, typename G > void forward_or_cross_edge(E, const G&)
80 {
81 }
82
finish_vertexdfs_visitor_default83 template < typename V, typename G > void finish_vertex(V, const G&) {}
84 };
85
86 struct topo_visitor : public dfs_visitor_default
87 {
topo_visitortopo_visitor88 topo_visitor(vertex_t*& order) : topo_order(order) {}
finish_vertextopo_visitor89 void finish_vertex(vertex_t u, const file_dep_graph&) { *--topo_order = u; }
90 vertex_t*& topo_order;
91 };
92
topo_sort(const file_dep_graph & g,vertex_t * topo_order)93 void topo_sort(const file_dep_graph& g, vertex_t* topo_order)
94 {
95 topo_visitor vis(topo_order);
96 generic_dfs_v1(g, vis);
97 }
98
main(int argc,const char ** argv)99 int main(int argc, const char** argv)
100 {
101 std::ifstream file_in(argc >= 2 ? argv[1] : "makefile-dependencies.dat");
102 typedef graph_traits< file_dep_graph >::vertices_size_type size_type;
103 size_type n_vertices;
104 file_in >> n_vertices; // read in number of vertices
105 std::istream_iterator< std::pair< size_type, size_type > > input_begin(
106 file_in),
107 input_end;
108
109 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
110 // VC++ can't handle the iterator constructor
111 file_dep_graph g(n_vertices);
112 while (input_begin != input_end)
113 {
114 size_type i, j;
115 boost::tie(i, j) = *input_begin++;
116 add_edge(i, j, g);
117 }
118 #else
119 file_dep_graph g(input_begin, input_end, n_vertices);
120 #endif
121
122 std::vector< std::string > name(num_vertices(g));
123 std::ifstream name_in(argc >= 2 ? argv[1] : "makefile-target-names.dat");
124 graph_traits< file_dep_graph >::vertex_iterator vi, vi_end;
125 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
126 name_in >> name[*vi];
127
128 std::vector< vertex_t > order(num_vertices(g));
129 topo_sort(g, &order[0] + num_vertices(g));
130 for (size_type i = 0; i < num_vertices(g); ++i)
131 std::cout << name[order[i]] << std::endl;
132
133 return 0;
134 }
135