2 //=======================================================================
3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
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 //=======================================================================
11 #ifndef BOOST_GRAPH_UNDIRECTED_DFS_HPP
12 #define BOOST_GRAPH_UNDIRECTED_DFS_HPP
14 #include <boost/graph/depth_first_search.hpp>
21 // Define BOOST_RECURSIVE_DFS to use older, recursive version.
22 // It is retained for a while in order to perform performance
24 #ifndef BOOST_RECURSIVE_DFS
26 template <typename IncidenceGraph, typename DFSVisitor,
27 typename VertexColorMap, typename EdgeColorMap>
29 (const IncidenceGraph& g,
30 typename graph_traits<IncidenceGraph>::vertex_descriptor u,
32 VertexColorMap vertex_color,
33 EdgeColorMap edge_color)
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;
50 std::vector<VertexInfo> stack;
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();
59 tie(ei, ei_end) = back.second;
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)));
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);
77 } else { // if (v_color == Color::black())
81 put(vertex_color, u, Color::black());
82 vis.finish_vertex(u, g);
86 #else // BOOST_RECURSIVE_DFS
88 template <typename IncidenceGraph, typename DFSVisitor,
89 typename VertexColorMap, typename EdgeColorMap>
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)
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;
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);
122 put(vertex_color, u, Color::black()); vis.finish_vertex(u, g);
125 #endif // ! BOOST_RECURSIVE_DFS
127 } // namespace detail
129 template <typename Graph, typename DFSVisitor,
130 typename VertexColorMap, typename EdgeColorMap,
133 undirected_dfs(const Graph& g, DFSVisitor vis,
134 VertexColorMap vertex_color, EdgeColorMap edge_color,
137 function_requires<DFSVisitorConcept<DFSVisitor, Graph> >();
138 function_requires<EdgeListGraphConcept<Graph> >();
140 typedef typename property_traits<VertexColorMap>::value_type ColorValue;
141 typedef color_traits<ColorValue> Color;
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);
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());
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);
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);
163 template <typename Graph, typename DFSVisitor, typename VertexColorMap,
164 typename EdgeColorMap>
166 undirected_dfs(const Graph& g, DFSVisitor vis,
167 VertexColorMap vertex_color, EdgeColorMap edge_color)
169 undirected_dfs(g, vis, vertex_color, edge_color, *vertices(g).first);
173 template <typename VertexColorMap>
174 struct udfs_dispatch {
176 template <typename Graph, typename Vertex,
177 typename DFSVisitor, typename EdgeColorMap,
178 typename P, typename T, typename R>
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)
185 undirected_dfs(g, vis, vertex_color, edge_color, start_vertex);
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>
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)
200 std::vector<default_color_type> color_vec(num_vertices(g));
201 default_color_type c = white_color; // avoid warning about un-init
203 (g, vis, make_iterator_property_map
205 choose_const_pmap(get_param(params, vertex_index),
206 g, vertex_index), c),
212 } // namespace detail
215 // Named Parameter Variant
216 template <typename Graph, typename P, typename T, typename R>
218 undirected_dfs(const Graph& g,
219 const bgl_named_params<P, T, R>& params)
221 typedef typename property_value< bgl_named_params<P, T, R>,
222 vertex_color_t>::type C;
223 detail::udfs_dispatch<C>::apply
225 choose_param(get_param(params, graph_visitor),
226 make_dfs_visitor(null_visitor())),
227 choose_param(get_param(params, root_vertex_t()),
230 get_param(params, edge_color),
231 get_param(params, vertex_color)
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)
243 detail::undir_dfv_impl(g, u, vis, vertex_color, edge_color);