1 //=======================================================================
2 // Copyright 2001 University of Notre Dame.
3 // Author: Jeremy G. Siek
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9
10 #include <boost/config.hpp>
11 #include <boost/core/lightweight_test.hpp>
12 #include <stdlib.h>
13
14 #include <boost/graph/depth_first_search.hpp>
15 #include <boost/graph/adjacency_list.hpp>
16 #include <boost/graph/graph_archetypes.hpp>
17 #include <boost/graph/graph_utility.hpp>
18 #include <boost/graph/random.hpp>
19
20 #include <boost/random/mersenne_twister.hpp>
21
22 template < typename ColorMap, typename ParentMap, typename DiscoverTimeMap,
23 typename FinishTimeMap >
24 class dfs_test_visitor
25 {
26 typedef typename boost::property_traits< ColorMap >::value_type ColorValue;
27 typedef typename boost::color_traits< ColorValue > Color;
28
29 public:
dfs_test_visitor(ColorMap color,ParentMap p,DiscoverTimeMap d,FinishTimeMap f)30 dfs_test_visitor(
31 ColorMap color, ParentMap p, DiscoverTimeMap d, FinishTimeMap f)
32 : m_color(color)
33 , m_parent(p)
34 , m_discover_time(d)
35 , m_finish_time(f)
36 , m_time(0)
37 {
38 }
39
40 template < class Vertex, class Graph >
initialize_vertex(Vertex u,Graph &)41 void initialize_vertex(Vertex u, Graph&)
42 {
43 BOOST_TEST(boost::get(m_color, u) == Color::white());
44 }
start_vertex(Vertex u,Graph &)45 template < class Vertex, class Graph > void start_vertex(Vertex u, Graph&)
46 {
47 BOOST_TEST(boost::get(m_color, u) == Color::white());
48 }
49 template < class Vertex, class Graph >
discover_vertex(Vertex u,Graph &)50 void discover_vertex(Vertex u, Graph&)
51 {
52 using namespace boost;
53 BOOST_TEST(get(m_color, u) == Color::gray());
54 BOOST_TEST(get(m_color, get(m_parent, u)) == Color::gray());
55
56 put(m_discover_time, u, m_time++);
57 }
examine_edge(Edge e,Graph & g)58 template < class Edge, class Graph > void examine_edge(Edge e, Graph& g)
59 {
60 using namespace boost;
61 BOOST_TEST(get(m_color, source(e, g)) == Color::gray());
62 }
tree_edge(Edge e,Graph & g)63 template < class Edge, class Graph > void tree_edge(Edge e, Graph& g)
64 {
65 using namespace boost;
66 BOOST_TEST(get(m_color, target(e, g)) == Color::white());
67
68 put(m_parent, target(e, g), source(e, g));
69 }
back_edge(Edge e,Graph & g)70 template < class Edge, class Graph > void back_edge(Edge e, Graph& g)
71 {
72 using namespace boost;
73 BOOST_TEST(get(m_color, target(e, g)) == Color::gray());
74 }
75 template < class Edge, class Graph >
forward_or_cross_edge(Edge e,Graph & g)76 void forward_or_cross_edge(Edge e, Graph& g)
77 {
78 using namespace boost;
79 BOOST_TEST(get(m_color, target(e, g)) == Color::black());
80 }
finish_edge(Edge e,Graph & g)81 template < class Edge, class Graph > void finish_edge(Edge e, Graph& g)
82 {
83 using namespace boost;
84 BOOST_TEST(get(m_color, target(e, g)) == Color::gray()
85 || get(m_color, target(e, g)) == Color::black());
86 }
finish_vertex(Vertex u,Graph &)87 template < class Vertex, class Graph > void finish_vertex(Vertex u, Graph&)
88 {
89 using namespace boost;
90 BOOST_TEST(get(m_color, u) == Color::black());
91
92 put(m_finish_time, u, m_time++);
93 }
94
95 private:
96 ColorMap m_color;
97 ParentMap m_parent;
98 DiscoverTimeMap m_discover_time;
99 FinishTimeMap m_finish_time;
100 typename boost::property_traits< DiscoverTimeMap >::value_type m_time;
101 };
102
103 template < typename Graph > struct dfs_test
104 {
105 typedef boost::graph_traits< Graph > Traits;
106 typedef typename Traits::vertices_size_type vertices_size_type;
107
godfs_test108 static void go(vertices_size_type max_V)
109 {
110 using namespace boost;
111 typedef typename Traits::vertex_descriptor vertex_descriptor;
112 typedef
113 typename boost::property_map< Graph, boost::vertex_color_t >::type
114 ColorMap;
115 typedef
116 typename boost::property_traits< ColorMap >::value_type ColorValue;
117 typedef typename boost::color_traits< ColorValue > Color;
118
119 vertices_size_type i, k;
120 typename Traits::edges_size_type j;
121 typename Traits::vertex_iterator vi, vi_end, ui, ui_end;
122
123 boost::mt19937 gen;
124
125 for (i = 0; i < max_V; ++i)
126 for (j = 0; j < i * i; ++j)
127 {
128 Graph g;
129 generate_random_graph(g, i, j, gen);
130
131 ColorMap color = get(boost::vertex_color, g);
132 std::vector< vertex_descriptor > parent(num_vertices(g));
133 for (k = 0; k < num_vertices(g); ++k)
134 parent[k] = k;
135 std::vector< int > discover_time(num_vertices(g)),
136 finish_time(num_vertices(g));
137
138 // Get vertex index map
139 typedef typename boost::property_map< Graph,
140 boost::vertex_index_t >::const_type idx_type;
141 idx_type idx = get(boost::vertex_index, g);
142
143 typedef boost::iterator_property_map<
144 typename std::vector< vertex_descriptor >::iterator,
145 idx_type >
146 parent_pm_type;
147 parent_pm_type parent_pm(parent.begin(), idx);
148 typedef boost::iterator_property_map<
149 std::vector< int >::iterator, idx_type >
150 time_pm_type;
151 time_pm_type discover_time_pm(discover_time.begin(), idx);
152 time_pm_type finish_time_pm(finish_time.begin(), idx);
153
154 dfs_test_visitor< ColorMap, parent_pm_type, time_pm_type,
155 time_pm_type >
156 vis(color, parent_pm, discover_time_pm, finish_time_pm);
157
158 boost::depth_first_search(g, visitor(vis).color_map(color));
159
160 // all vertices should be black
161 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
162 BOOST_TEST(get(color, *vi) == Color::black());
163
164 // check parenthesis structure of discover/finish times
165 // See CLR p.480
166 for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
167 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end;
168 ++vi)
169 {
170 vertex_descriptor u = *ui, v = *vi;
171 if (u != v)
172 {
173 BOOST_TEST(finish_time[u] < discover_time[v]
174 || finish_time[v] < discover_time[u]
175 || (discover_time[v] < discover_time[u]
176 && finish_time[u] < finish_time[v]
177 && boost::is_descendant(u, v, parent_pm))
178 || (discover_time[u] < discover_time[v]
179 && finish_time[v] < finish_time[u]
180 && boost::is_descendant(v, u, parent_pm)));
181 }
182 }
183 }
184 }
185 };
186
187 // usage: dfs.exe [max-vertices=15]
188
main(int argc,char * argv[])189 int main(int argc, char* argv[])
190 {
191 int max_V = 7;
192 if (argc > 1)
193 max_V = atoi(argv[1]);
194
195 // Test directed graphs.
196 dfs_test< boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS,
197 boost::property< boost::vertex_color_t,
198 boost::default_color_type > > >::go(max_V);
199 // Test undirected graphs.
200 dfs_test<
201 boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS,
202 boost::property< boost::vertex_color_t,
203 boost::default_color_type > > >::go(max_V);
204
205 return boost::report_errors();
206 }
207