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
has_cycle_dfs(const file_dep_graph & g,vertex_t u,default_color_type * color)36 bool has_cycle_dfs(
37 const file_dep_graph& g, vertex_t u, default_color_type* color)
38 {
39 color[u] = gray_color;
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 (color[*vi] == white_color)
43 {
44 if (has_cycle_dfs(g, *vi, color))
45 return true; // cycle detected, return immediately
46 }
47 else if (color[*vi] == gray_color) // *vi is an ancestor!
48 return true;
49 color[u] = black_color;
50 return false;
51 }
52
has_cycle(const file_dep_graph & g)53 bool has_cycle(const file_dep_graph& g)
54 {
55 std::vector< default_color_type > color(num_vertices(g), white_color);
56 graph_traits< file_dep_graph >::vertex_iterator vi, vi_end;
57 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
58 if (color[*vi] == white_color)
59 if (has_cycle_dfs(g, *vi, &color[0]))
60 return true;
61 return false;
62 }
63
main(int argc,const char ** argv)64 int main(int argc, const char** argv)
65 {
66 std::ifstream file_in(argc >= 2 ? argv[1] : "makefile-dependencies.dat");
67 typedef graph_traits< file_dep_graph >::vertices_size_type size_type;
68 size_type n_vertices;
69 file_in >> n_vertices; // read in number of vertices
70 std::istream_iterator< std::pair< size_type, size_type > > input_begin(
71 file_in),
72 input_end;
73 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
74 // VC++ has trouble with the edge iterator constructor
75 file_dep_graph g(n_vertices);
76 while (input_begin != input_end)
77 {
78 size_type i, j;
79 boost::tie(i, j) = *input_begin++;
80 add_edge(i, j, g);
81 }
82 #else
83 file_dep_graph g(input_begin, input_end, n_vertices);
84 #endif
85
86 std::vector< std::string > name(num_vertices(g));
87 std::ifstream name_in(argc >= 3 ? argv[2] : "makefile-target-names.dat");
88 graph_traits< file_dep_graph >::vertex_iterator vi, vi_end;
89 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
90 name_in >> name[*vi];
91
92 assert(has_cycle(g) == false);
93 return 0;
94 }
95