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
topo_sort_dfs(const file_dep_graph & g,vertex_t u,vertex_t * & topo_order,int * mark)36 void topo_sort_dfs(
37 const file_dep_graph& g, vertex_t u, vertex_t*& topo_order, int* mark)
38 {
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)
42 if (mark[*vi] == 0)
43 topo_sort_dfs(g, *vi, topo_order, mark);
44
45 *--topo_order = u;
46 }
47
topo_sort(const file_dep_graph & g,vertex_t * topo_order)48 void topo_sort(const file_dep_graph& g, vertex_t* topo_order)
49 {
50 std::vector< int > mark(num_vertices(g), 0);
51 graph_traits< file_dep_graph >::vertex_iterator vi, vi_end;
52 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
53 if (mark[*vi] == 0)
54 topo_sort_dfs(g, *vi, topo_order, &mark[0]);
55 }
56
main(int argc,const char ** argv)57 int main(int argc, const char** argv)
58 {
59 std::ifstream file_in(argc >= 2 ? argv[1] : "makefile-dependencies.dat");
60 typedef graph_traits< file_dep_graph >::vertices_size_type size_type;
61 size_type n_vertices;
62 file_in >> n_vertices; // read in number of vertices
63 std::istream_iterator< std::pair< size_type, size_type > > input_begin(
64 file_in),
65 input_end;
66 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
67 // VC++ can't handle the iterator constructor
68 file_dep_graph g(n_vertices);
69 while (input_begin != input_end)
70 {
71 size_type i, j;
72 boost::tie(i, j) = *input_begin++;
73 add_edge(i, j, g);
74 }
75 #else
76 file_dep_graph g(input_begin, input_end, n_vertices);
77 #endif
78
79 std::vector< std::string > name(num_vertices(g));
80 std::ifstream name_in(argc >= 3 ? argv[2] : "makefile-target-names.dat");
81 graph_traits< file_dep_graph >::vertex_iterator vi, vi_end;
82 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
83 name_in >> name[*vi];
84
85 std::vector< vertex_t > order(num_vertices(g));
86 topo_sort(g, &order[0] + num_vertices(g));
87 for (size_type i = 0; i < num_vertices(g); ++i)
88 std::cout << name[order[i]] << std::endl;
89
90 return 0;
91 }
92