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// can't do using namespace boost because then
16// we get conflict with boost::default_dfs_visitor.
17using namespace boost;
18
19namespace std
20{
21template < typename T >
22std::istream& operator>>(std::istream& in, std::pair< T, T >& p)
23{
24 in >> p.first >> p.second;
25 return in;
26}
27}
28
29typedef 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;
34
35typedef graph_traits< file_dep_graph >::vertex_descriptor vertex_t;
36typedef graph_traits< file_dep_graph >::edge_descriptor edge_t;
37
38template < typename Visitor >
39void dfs_v1(
40 const file_dep_graph& g, vertex_t u, default_color_type* color, Visitor vis)
41{
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(t0&: ei, t1&: ei_end) = out_edges(u, g_: g); ei != ei_end; ++ei)
46 {
47 if (color[target(e: *ei, g)] == white_color)
48 {
49 vis.tree_edge(*ei, g);
50 dfs_v1(g, target(e: *ei, g), color, vis);
51 }
52 else if (color[target(e: *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);
59}
60
61template < typename Visitor >
62void generic_dfs_v1(const file_dep_graph& g, Visitor vis)
63{
64 std::vector< default_color_type > color(num_vertices(g_: g), white_color);
65 graph_traits< file_dep_graph >::vertex_iterator vi, vi_end;
66 for (boost::tie(t0&: vi, t1&: vi_end) = vertices(g_: g); vi != vi_end; ++vi)
67 {
68 if (color[*vi] == white_color)
69 dfs_v1(g, *vi, &color[0], vis);
70 }
71}
72
73struct dfs_visitor_default
74{
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&) {}
86};
87
88struct cycle_detector : public dfs_visitor_default
89{
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;
93};
94
95bool has_cycle(const file_dep_graph& g)
96{
97 bool has_cycle = false;
98 cycle_detector vis(has_cycle);
99 generic_dfs_v1(g, vis);
100 return has_cycle;
101}
102
103int main(int argc, const char** argv)
104{
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;
112#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
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 }
121#else
122 file_dep_graph g(input_begin, input_end, n_vertices);
123#endif
124
125 std::vector< std::string > name(num_vertices(g_: 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(t0&: vi, t1&: vi_end) = vertices(g_: g); vi != vi_end; ++vi)
129 name_in >> name[*vi];
130
131 assert(has_cycle(g) == false);
132 return 0;
133}
134

source code of boost/libs/graph/example/cycle-file-dep2.cpp