1//
2//=======================================================================
3// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
5//
6// Distributed under the Boost Software License, Version 1.0. (See
7// accompanying file LICENSE_1_0.txt or copy at
8// http://www.boost.org/LICENSE_1_0.txt)
9//=======================================================================
10//
11#ifndef BOOST_GRAPH_UNDIRECTED_DFS_HPP
12#define BOOST_GRAPH_UNDIRECTED_DFS_HPP
13
14#include <boost/graph/depth_first_search.hpp>
15#include <vector>
16#include <boost/concept/assert.hpp>
17
18namespace boost {
19
20 namespace detail {
21
22// Define BOOST_RECURSIVE_DFS to use older, recursive version.
23// It is retained for a while in order to perform performance
24// comparison.
25#ifndef BOOST_RECURSIVE_DFS
26
27 template <typename IncidenceGraph, typename DFSVisitor,
28 typename VertexColorMap, typename EdgeColorMap>
29 void undir_dfv_impl
30 (const IncidenceGraph& g,
31 typename graph_traits<IncidenceGraph>::vertex_descriptor u,
32 DFSVisitor& vis,
33 VertexColorMap vertex_color,
34 EdgeColorMap edge_color)
35 {
36 BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> ));
37 BOOST_CONCEPT_ASSERT(( DFSVisitorConcept<DFSVisitor, IncidenceGraph> ));
38 typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
39 typedef typename graph_traits<IncidenceGraph>::edge_descriptor Edge;
40 BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<VertexColorMap,Vertex> ));
41 BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<EdgeColorMap,Edge> ));
42 typedef typename property_traits<VertexColorMap>::value_type ColorValue;
43 typedef typename property_traits<EdgeColorMap>::value_type EColorValue;
44 BOOST_CONCEPT_ASSERT(( ColorValueConcept<ColorValue> ));
45 BOOST_CONCEPT_ASSERT(( ColorValueConcept<EColorValue> ));
46 typedef color_traits<ColorValue> Color;
47 typedef color_traits<EColorValue> EColor;
48 typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter;
49 typedef std::pair<Vertex, std::pair<boost::optional<Edge>, std::pair<Iter, Iter> > > VertexInfo;
50
51 std::vector<VertexInfo> stack;
52
53 put(vertex_color, u, Color::gray());
54 vis.discover_vertex(u, g);
55 stack.push_back(std::make_pair(u, std::make_pair(boost::optional<Edge>(), out_edges(u, g))));
56 while (!stack.empty()) {
57 VertexInfo& back = stack.back();
58 u = back.first;
59 boost::optional<Edge> src_e = back.second.first;
60 Iter ei = back.second.second.first, ei_end = back.second.second.second;
61 stack.pop_back();
62 while (ei != ei_end) {
63 Vertex v = target(*ei, g);
64 vis.examine_edge(*ei, g);
65 ColorValue v_color = get(vertex_color, v);
66 EColorValue uv_color = get(edge_color, *ei);
67 put(edge_color, *ei, EColor::black());
68 if (v_color == Color::white()) {
69 vis.tree_edge(*ei, g);
70 src_e = *ei;
71 stack.push_back(std::make_pair(u, std::make_pair(src_e, std::make_pair(++ei, ei_end))));
72 u = v;
73 put(vertex_color, u, Color::gray());
74 vis.discover_vertex(u, g);
75 boost::tie(ei, ei_end) = out_edges(u, g);
76 } else if (v_color == Color::gray()) {
77 if (uv_color == EColor::white()) vis.back_edge(*ei, g);
78 call_finish_edge(vis, *ei, g);
79 ++ei;
80 } else { // if (v_color == Color::black())
81 call_finish_edge(vis, *ei, g);
82 ++ei;
83 }
84 }
85 put(vertex_color, u, Color::black());
86 vis.finish_vertex(u, g);
87 if (src_e) call_finish_edge(vis, src_e.get(), g);
88 }
89 }
90
91#else // BOOST_RECURSIVE_DFS
92
93 template <typename IncidenceGraph, typename DFSVisitor,
94 typename VertexColorMap, typename EdgeColorMap>
95 void undir_dfv_impl
96 (const IncidenceGraph& g,
97 typename graph_traits<IncidenceGraph>::vertex_descriptor u,
98 DFSVisitor& vis, // pass-by-reference here, important!
99 VertexColorMap vertex_color,
100 EdgeColorMap edge_color)
101 {
102 BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> ));
103 BOOST_CONCEPT_ASSERT(( DFSVisitorConcept<DFSVisitor, IncidenceGraph> ));
104 typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
105 typedef typename graph_traits<IncidenceGraph>::edge_descriptor Edge;
106 BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<VertexColorMap,Vertex> ));
107 BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<EdgeColorMap,Edge> ));
108 typedef typename property_traits<VertexColorMap>::value_type ColorValue;
109 typedef typename property_traits<EdgeColorMap>::value_type EColorValue;
110 BOOST_CONCEPT_ASSERT(( ColorValueConcept<ColorValue> ));
111 BOOST_CONCEPT_ASSERT(( ColorValueConcept<EColorValue> ));
112 typedef color_traits<ColorValue> Color;
113 typedef color_traits<EColorValue> EColor;
114 typename graph_traits<IncidenceGraph>::out_edge_iterator ei, ei_end;
115
116 put(vertex_color, u, Color::gray()); vis.discover_vertex(u, g);
117 for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
118 Vertex v = target(*ei, g); vis.examine_edge(*ei, g);
119 ColorValue v_color = get(vertex_color, v);
120 EColorValue uv_color = get(edge_color, *ei);
121 put(edge_color, *ei, EColor::black());
122 if (v_color == Color::white()) { vis.tree_edge(*ei, g);
123 undir_dfv_impl(g, v, vis, vertex_color, edge_color);
124 } else if (v_color == Color::gray() && uv_color == EColor::white())
125 vis.back_edge(*ei, g);
126 call_finish_edge(vis, *ei, g);
127 }
128 put(vertex_color, u, Color::black()); vis.finish_vertex(u, g);
129 }
130
131#endif // ! BOOST_RECURSIVE_DFS
132
133 } // namespace detail
134
135 template <typename Graph, typename DFSVisitor,
136 typename VertexColorMap, typename EdgeColorMap,
137 typename Vertex>
138 void
139 undirected_dfs(const Graph& g, DFSVisitor vis,
140 VertexColorMap vertex_color, EdgeColorMap edge_color,
141 Vertex start_vertex)
142 {
143 BOOST_CONCEPT_ASSERT(( DFSVisitorConcept<DFSVisitor, Graph> ));
144 BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph> ));
145
146 typedef typename property_traits<VertexColorMap>::value_type ColorValue;
147 typedef color_traits<ColorValue> Color;
148
149 typename graph_traits<Graph>::vertex_iterator ui, ui_end;
150 for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
151 put(vertex_color, *ui, Color::white()); vis.initialize_vertex(*ui, g);
152 }
153 typename graph_traits<Graph>::edge_iterator ei, ei_end;
154 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
155 put(edge_color, *ei, Color::white());
156
157 if (start_vertex != *vertices(g).first){ vis.start_vertex(start_vertex, g);
158 detail::undir_dfv_impl(g, start_vertex, vis, vertex_color, edge_color);
159 }
160
161 for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
162 ColorValue u_color = get(vertex_color, *ui);
163 if (u_color == Color::white()) { vis.start_vertex(*ui, g);
164 detail::undir_dfv_impl(g, *ui, vis, vertex_color, edge_color);
165 }
166 }
167 }
168
169 template <typename Graph, typename DFSVisitor, typename VertexColorMap,
170 typename EdgeColorMap>
171 void
172 undirected_dfs(const Graph& g, DFSVisitor vis,
173 VertexColorMap vertex_color, EdgeColorMap edge_color)
174 {
175 undirected_dfs(g, vis, vertex_color, edge_color, *vertices(g).first);
176 }
177
178 namespace detail {
179 template <typename VertexColorMap>
180 struct udfs_dispatch {
181
182 template <typename Graph, typename Vertex,
183 typename DFSVisitor, typename EdgeColorMap,
184 typename P, typename T, typename R>
185 static void
186 apply(const Graph& g, DFSVisitor vis, Vertex start_vertex,
187 const bgl_named_params<P, T, R>&,
188 EdgeColorMap edge_color,
189 VertexColorMap vertex_color)
190 {
191 undirected_dfs(g, vis, vertex_color, edge_color, start_vertex);
192 }
193 };
194
195 template <>
196 struct udfs_dispatch<param_not_found> {
197 template <typename Graph, typename Vertex, typename DFSVisitor,
198 typename EdgeColorMap,
199 typename P, typename T, typename R>
200 static void
201 apply(const Graph& g, DFSVisitor vis, Vertex start_vertex,
202 const bgl_named_params<P, T, R>& params,
203 EdgeColorMap edge_color,
204 param_not_found)
205 {
206 std::vector<default_color_type> color_vec(num_vertices(g));
207 default_color_type c = white_color; // avoid warning about un-init
208 undirected_dfs
209 (g, vis, make_iterator_property_map
210 (color_vec.begin(),
211 choose_const_pmap(get_param(params, vertex_index),
212 g, vertex_index), c),
213 edge_color,
214 start_vertex);
215 }
216 };
217
218 } // namespace detail
219
220
221 // Named Parameter Variant
222 template <typename Graph, typename P, typename T, typename R>
223 void
224 undirected_dfs(const Graph& g,
225 const bgl_named_params<P, T, R>& params)
226 {
227 typedef typename get_param_type< vertex_color_t, bgl_named_params<P, T, R> >::type C;
228 detail::udfs_dispatch<C>::apply
229 (g,
230 choose_param(get_param(params, graph_visitor),
231 make_dfs_visitor(vis: null_visitor())),
232 choose_param(get_param(params, root_vertex_t()),
233 *vertices(g).first),
234 params,
235 get_param(params, edge_color),
236 get_param(params, vertex_color)
237 );
238 }
239
240
241 template <typename IncidenceGraph, typename DFSVisitor,
242 typename VertexColorMap, typename EdgeColorMap>
243 void undirected_depth_first_visit
244 (const IncidenceGraph& g,
245 typename graph_traits<IncidenceGraph>::vertex_descriptor u,
246 DFSVisitor vis, VertexColorMap vertex_color, EdgeColorMap edge_color)
247 {
248 detail::undir_dfv_impl(g, u, vis, vertex_color, edge_color);
249 }
250
251
252} // namespace boost
253
254
255#endif
256

source code of boost/boost/graph/undirected_dfs.hpp