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>
16 #include <boost/concept/assert.hpp>
22 // Define BOOST_RECURSIVE_DFS to use older, recursive version.
23 // It is retained for a while in order to perform performance
25 #ifndef BOOST_RECURSIVE_DFS
27 template <typename IncidenceGraph, typename DFSVisitor,
28 typename VertexColorMap, typename EdgeColorMap>
30 (const IncidenceGraph& g,
31 typename graph_traits<IncidenceGraph>::vertex_descriptor u,
33 VertexColorMap vertex_color,
34 EdgeColorMap edge_color)
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;
51 std::vector<VertexInfo> stack;
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();
59 boost::optional<Edge> src_e = back.second.first;
60 Iter ei = back.second.second.first, ei_end = back.second.second.second;
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);
71 stack.push_back(std::make_pair(u, std::make_pair(src_e, std::make_pair(++ei, ei_end))));
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);
80 } else { // if (v_color == Color::black())
81 call_finish_edge(vis, *ei, g);
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);
91 #else // BOOST_RECURSIVE_DFS
93 template <typename IncidenceGraph, typename DFSVisitor,
94 typename VertexColorMap, typename EdgeColorMap>
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)
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;
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);
128 put(vertex_color, u, Color::black()); vis.finish_vertex(u, g);
131 #endif // ! BOOST_RECURSIVE_DFS
133 } // namespace detail
135 template <typename Graph, typename DFSVisitor,
136 typename VertexColorMap, typename EdgeColorMap,
139 undirected_dfs(const Graph& g, DFSVisitor vis,
140 VertexColorMap vertex_color, EdgeColorMap edge_color,
143 BOOST_CONCEPT_ASSERT(( DFSVisitorConcept<DFSVisitor, Graph> ));
144 BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph> ));
146 typedef typename property_traits<VertexColorMap>::value_type ColorValue;
147 typedef color_traits<ColorValue> Color;
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);
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());
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);
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);
169 template <typename Graph, typename DFSVisitor, typename VertexColorMap,
170 typename EdgeColorMap>
172 undirected_dfs(const Graph& g, DFSVisitor vis,
173 VertexColorMap vertex_color, EdgeColorMap edge_color)
175 undirected_dfs(g, vis, vertex_color, edge_color, *vertices(g).first);
179 template <typename VertexColorMap>
180 struct udfs_dispatch {
182 template <typename Graph, typename Vertex,
183 typename DFSVisitor, typename EdgeColorMap,
184 typename P, typename T, typename R>
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)
191 undirected_dfs(g, vis, vertex_color, edge_color, start_vertex);
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>
201 apply(const Graph& g, DFSVisitor vis, Vertex start_vertex,
202 const bgl_named_params<P, T, R>& params,
203 EdgeColorMap edge_color,
206 std::vector<default_color_type> color_vec(num_vertices(g));
207 default_color_type c = white_color; // avoid warning about un-init
209 (g, vis, make_iterator_property_map
211 choose_const_pmap(get_param(params, vertex_index),
212 g, vertex_index), c),
218 } // namespace detail
221 // Named Parameter Variant
222 template <typename Graph, typename P, typename T, typename R>
224 undirected_dfs(const Graph& g,
225 const bgl_named_params<P, T, R>& params)
227 typedef typename get_param_type< vertex_color_t, bgl_named_params<P, T, R> >::type C;
228 detail::udfs_dispatch<C>::apply
230 choose_param(get_param(params, graph_visitor),
231 make_dfs_visitor(null_visitor())),
232 choose_param(get_param(params, root_vertex_t()),
235 get_param(params, edge_color),
236 get_param(params, vertex_color)
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)
248 detail::undir_dfv_impl(g, u, vis, vertex_color, edge_color);