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/undirected_dfs.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 typedef typename boost::property_map< Graph, boost::edge_color_t >::type
119 EColorMap;
120 typedef typename boost::property_traits< EColorMap >::value_type
121 EColorValue;
122 typedef typename boost::color_traits< EColorValue > EColor;
123
124 vertices_size_type i, k;
125 typename Traits::edges_size_type j;
126 typename Traits::vertex_iterator vi, vi_end, ui, ui_end;
127 typename Traits::edge_iterator ei, ei_end;
128
129 boost::mt19937 gen;
130
131 for (i = 0; i < max_V; ++i)
132 for (j = 0; j < i * i; ++j)
133 {
134 Graph g;
135 generate_random_graph(g, i, j, gen);
136
137 ColorMap color = get(boost::vertex_color, g);
138 EColorMap e_color = get(boost::edge_color, g);
139 std::vector< vertex_descriptor > parent(num_vertices(g));
140 for (k = 0; k < num_vertices(g); ++k)
141 parent[k] = k;
142 std::vector< int > discover_time(num_vertices(g)),
143 finish_time(num_vertices(g));
144
145 // Get vertex index map
146 typedef typename boost::property_map< Graph,
147 boost::vertex_index_t >::const_type idx_type;
148 idx_type idx = get(boost::vertex_index, g);
149
150 typedef boost::iterator_property_map<
151 typename std::vector< vertex_descriptor >::iterator,
152 idx_type >
153 parent_pm_type;
154 parent_pm_type parent_pm(parent.begin(), idx);
155 typedef boost::iterator_property_map<
156 std::vector< int >::iterator, idx_type >
157 time_pm_type;
158 time_pm_type discover_time_pm(discover_time.begin(), idx);
159 time_pm_type finish_time_pm(finish_time.begin(), idx);
160
161 dfs_test_visitor< ColorMap, parent_pm_type, time_pm_type,
162 time_pm_type >
163 vis(color, parent_pm, discover_time_pm, finish_time_pm);
164
165 boost::undirected_dfs(
166 g, visitor(vis).color_map(color).edge_color_map(e_color));
167
168 // all vertices should be black
169 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
170 BOOST_TEST(get(color, *vi) == Color::black());
171
172 // all edges should be black
173 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
174 BOOST_TEST(get(e_color, *ei) == EColor::black());
175
176 // check parenthesis structure of discover/finish times
177 // See CLR p.480
178 for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
179 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end;
180 ++vi)
181 {
182 vertex_descriptor u = *ui, v = *vi;
183 if (u != v)
184 {
185 BOOST_TEST(finish_time[u] < discover_time[v]
186 || finish_time[v] < discover_time[u]
187 || (discover_time[v] < discover_time[u]
188 && finish_time[u] < finish_time[v]
189 && boost::is_descendant(u, v, parent_pm))
190 || (discover_time[u] < discover_time[v]
191 && finish_time[v] < finish_time[u]
192 && boost::is_descendant(v, u, parent_pm)));
193 }
194 }
195 }
196 }
197 };
198
199 // usage: undirected_dfs.exe [max-vertices=15]
200
main(int argc,char * argv[])201 int main(int argc, char* argv[])
202 {
203 int max_V = 7;
204 if (argc > 1)
205 max_V = atoi(argv[1]);
206
207 // Test undirected graphs.
208 dfs_test< boost::adjacency_list< boost::vecS, boost::vecS,
209 boost::undirectedS,
210 boost::property< boost::vertex_color_t, boost::default_color_type >,
211 boost::property< boost::edge_color_t, boost::default_color_type > > >::
212 go(max_V);
213
214 return boost::report_errors();
215 }
216