| 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
|
|---|
![(please configure the [header_logo] section in trac.ini)](/trac/gametools/chrome/site/your_project_logo.png){kind=logo}
