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> undir_dfv_impl(const IncidenceGraph & g,typename graph_traits<IncidenceGraph>::vertex_descriptor u,DFSVisitor & vis,VertexColorMap vertex_color,EdgeColorMap edge_color)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 undirected_dfs(const Graph & g,DFSVisitor vis,VertexColorMap vertex_color,EdgeColorMap edge_color,Vertex start_vertex)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 undirected_dfs(const Graph & g,DFSVisitor vis,VertexColorMap vertex_color,EdgeColorMap edge_color)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 applyboost::detail::udfs_dispatch186 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 applyboost::detail::udfs_dispatch201 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 undirected_dfs(const Graph & g,const bgl_named_params<P,T,R> & params)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> undirected_depth_first_visit(const IncidenceGraph & g,typename graph_traits<IncidenceGraph>::vertex_descriptor u,DFSVisitor vis,VertexColorMap vertex_color,EdgeColorMap edge_color)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