]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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(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 |