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 | |
18 | namespace 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 | |