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