]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | //======================================================================= |
f67539c2 | 2 | // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, |
7c673cae FG |
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 | // can't do using namespace boost because then | |
16 | // we get conflict with boost::default_dfs_visitor. | |
17 | using namespace boost; | |
18 | ||
f67539c2 TL |
19 | namespace std |
20 | { | |
21 | template < typename T > | |
22 | std::istream& operator>>(std::istream& in, std::pair< T, T >& p) | |
23 | { | |
7c673cae | 24 | in >> p.first >> p.second; |
f67539c2 TL |
25 | return in; |
26 | } | |
7c673cae FG |
27 | } |
28 | ||
f67539c2 TL |
29 | typedef adjacency_list< listS, // Store out-edges of each vertex in a std::list |
30 | vecS, // Store vertex set in a std::vector | |
31 | directedS // The file dependency graph is directed | |
32 | > | |
33 | file_dep_graph; | |
7c673cae | 34 | |
f67539c2 TL |
35 | typedef graph_traits< file_dep_graph >::vertex_descriptor vertex_t; |
36 | typedef graph_traits< file_dep_graph >::edge_descriptor edge_t; | |
7c673cae | 37 | |
f67539c2 TL |
38 | template < typename Visitor > |
39 | void dfs_v1( | |
40 | const file_dep_graph& g, vertex_t u, default_color_type* color, Visitor vis) | |
7c673cae | 41 | { |
f67539c2 TL |
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 | { | |
47 | if (color[target(*ei, g)] == white_color) | |
48 | { | |
49 | vis.tree_edge(*ei, g); | |
50 | dfs_v1(g, target(*ei, g), color, vis); | |
51 | } | |
52 | else if (color[target(*ei, g)] == gray_color) | |
53 | vis.back_edge(*ei, g); | |
54 | else | |
55 | vis.forward_or_cross_edge(*ei, g); | |
56 | } | |
57 | color[u] = black_color; | |
58 | vis.finish_vertex(u, g); | |
7c673cae FG |
59 | } |
60 | ||
f67539c2 TL |
61 | template < typename Visitor > |
62 | void generic_dfs_v1(const file_dep_graph& g, Visitor vis) | |
7c673cae | 63 | { |
f67539c2 TL |
64 | std::vector< default_color_type > color(num_vertices(g), white_color); |
65 | graph_traits< file_dep_graph >::vertex_iterator vi, vi_end; | |
66 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) | |
67 | { | |
68 | if (color[*vi] == white_color) | |
69 | dfs_v1(g, *vi, &color[0], vis); | |
70 | } | |
7c673cae FG |
71 | } |
72 | ||
73 | struct dfs_visitor_default | |
74 | { | |
f67539c2 TL |
75 | template < typename V, typename G > void discover_vertex(V, const G&) {} |
76 | ||
77 | template < typename E, typename G > void tree_edge(E, const G&) {} | |
78 | ||
79 | template < typename E, typename G > void back_edge(E, const G&) {} | |
80 | ||
81 | template < typename E, typename G > void forward_or_cross_edge(E, const G&) | |
82 | { | |
83 | } | |
84 | ||
85 | template < typename V, typename G > void finish_vertex(V, const G&) {} | |
7c673cae FG |
86 | }; |
87 | ||
88 | struct cycle_detector : public dfs_visitor_default | |
89 | { | |
f67539c2 TL |
90 | cycle_detector(bool& cycle) : has_cycle(cycle) {} |
91 | void back_edge(edge_t, const file_dep_graph&) { has_cycle = true; } | |
92 | bool& has_cycle; | |
7c673cae FG |
93 | }; |
94 | ||
f67539c2 | 95 | bool has_cycle(const file_dep_graph& g) |
7c673cae | 96 | { |
f67539c2 TL |
97 | bool has_cycle = false; |
98 | cycle_detector vis(has_cycle); | |
99 | generic_dfs_v1(g, vis); | |
100 | return has_cycle; | |
7c673cae FG |
101 | } |
102 | ||
f67539c2 | 103 | int main(int argc, const char** argv) |
7c673cae | 104 | { |
f67539c2 TL |
105 | std::ifstream file_in(argc >= 2 ? argv[1] : "makefile-dependencies.dat"); |
106 | typedef graph_traits< file_dep_graph >::vertices_size_type size_type; | |
107 | size_type n_vertices; | |
108 | file_in >> n_vertices; // read in number of vertices | |
109 | std::istream_iterator< std::pair< size_type, size_type > > input_begin( | |
110 | file_in), | |
111 | input_end; | |
7c673cae | 112 | #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 |
f67539c2 TL |
113 | // VC++ has trouble with the edge iterator constructor |
114 | file_dep_graph g(n_vertices); | |
115 | while (input_begin != input_end) | |
116 | { | |
117 | size_type i, j; | |
118 | boost::tie(i, j) = *input_begin++; | |
119 | add_edge(i, j, g); | |
120 | } | |
7c673cae | 121 | #else |
f67539c2 | 122 | file_dep_graph g(input_begin, input_end, n_vertices); |
7c673cae FG |
123 | #endif |
124 | ||
f67539c2 TL |
125 | std::vector< std::string > name(num_vertices(g)); |
126 | std::ifstream name_in(argc >= 3 ? argv[2] : "makefile-target-names.dat"); | |
127 | graph_traits< file_dep_graph >::vertex_iterator vi, vi_end; | |
128 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) | |
129 | name_in >> name[*vi]; | |
7c673cae | 130 | |
f67539c2 TL |
131 | assert(has_cycle(g) == false); |
132 | return 0; | |
7c673cae | 133 | } |