1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/depth_first_search.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,365 @@
1.4 +//=======================================================================
1.5 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
1.6 +// Copyright 2003 Bruce Barr
1.7 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
1.8 +//
1.9 +// Distributed under the Boost Software License, Version 1.0. (See
1.10 +// accompanying file LICENSE_1_0.txt or copy at
1.11 +// http://www.boost.org/LICENSE_1_0.txt)
1.12 +//=======================================================================
1.13 +
1.14 +// Nonrecursive implementation of depth_first_visit_impl submitted by
1.15 +// Bruce Barr, schmoost <at> yahoo.com, May/June 2003.
1.16 +#ifndef BOOST_GRAPH_RECURSIVE_DFS_HPP
1.17 +#define BOOST_GRAPH_RECURSIVE_DFS_HPP
1.18 +
1.19 +#include <boost/config.hpp>
1.20 +#include <boost/graph/graph_traits.hpp>
1.21 +#include <boost/graph/graph_concepts.hpp>
1.22 +#include <boost/graph/properties.hpp>
1.23 +#include <boost/graph/visitors.hpp>
1.24 +#include <boost/graph/named_function_params.hpp>
1.25 +
1.26 +#include <boost/ref.hpp>
1.27 +#include <boost/implicit_cast.hpp>
1.28 +
1.29 +#include <vector>
1.30 +#include <utility>
1.31 +
1.32 +namespace boost {
1.33 +
1.34 + template <class Visitor, class Graph>
1.35 + class DFSVisitorConcept {
1.36 + public:
1.37 + void constraints() {
1.38 + function_requires< CopyConstructibleConcept<Visitor> >();
1.39 + vis.initialize_vertex(u, g);
1.40 + vis.start_vertex(u, g);
1.41 + vis.discover_vertex(u, g);
1.42 + vis.examine_edge(e, g);
1.43 + vis.tree_edge(e, g);
1.44 + vis.back_edge(e, g);
1.45 + vis.forward_or_cross_edge(e, g);
1.46 + vis.finish_vertex(u, g);
1.47 + }
1.48 + private:
1.49 + Visitor vis;
1.50 + Graph g;
1.51 + typename graph_traits<Graph>::vertex_descriptor u;
1.52 + typename graph_traits<Graph>::edge_descriptor e;
1.53 + };
1.54 +
1.55 + namespace detail {
1.56 +
1.57 + struct nontruth2 {
1.58 + template<class T, class T2>
1.59 + bool operator()(const T&, const T2&) const { return false; }
1.60 + };
1.61 +
1.62 +
1.63 +// Define BOOST_RECURSIVE_DFS to use older, recursive version.
1.64 +// It is retained for a while in order to perform performance
1.65 +// comparison.
1.66 +#ifndef BOOST_RECURSIVE_DFS
1.67 +
1.68 + // If the vertex u and the iterators ei and ei_end are thought of as the
1.69 + // context of the algorithm, each push and pop from the stack could
1.70 + // be thought of as a context shift.
1.71 + // Each pass through "while (ei != ei_end)" may refer to the out-edges of
1.72 + // an entirely different vertex, because the context of the algorithm
1.73 + // shifts every time a white adjacent vertex is discovered.
1.74 + // The corresponding context shift back from the adjacent vertex occurs
1.75 + // after all of its out-edges have been examined.
1.76 + //
1.77 + // See http://lists.boost.org/MailArchives/boost/msg48752.php for FAQ.
1.78 +
1.79 + template <class IncidenceGraph, class DFSVisitor, class ColorMap,
1.80 + class TerminatorFunc>
1.81 + void depth_first_visit_impl
1.82 + (const IncidenceGraph& g,
1.83 + typename graph_traits<IncidenceGraph>::vertex_descriptor u,
1.84 + DFSVisitor& vis,
1.85 + ColorMap color, TerminatorFunc func = TerminatorFunc())
1.86 + {
1.87 + function_requires<IncidenceGraphConcept<IncidenceGraph> >();
1.88 + function_requires<DFSVisitorConcept<DFSVisitor, IncidenceGraph> >();
1.89 + typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
1.90 + function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >();
1.91 + typedef typename property_traits<ColorMap>::value_type ColorValue;
1.92 + function_requires< ColorValueConcept<ColorValue> >();
1.93 + typedef color_traits<ColorValue> Color;
1.94 + typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter;
1.95 + typedef std::pair<Vertex, std::pair<Iter, Iter> > VertexInfo;
1.96 +
1.97 + Iter ei, ei_end;
1.98 + std::vector<VertexInfo> stack;
1.99 +
1.100 + // Possible optimization for vector
1.101 + //stack.reserve(num_vertices(g));
1.102 +
1.103 + typedef typename unwrap_reference<TerminatorFunc>::type TF;
1.104 +
1.105 + put(color, u, Color::gray());
1.106 + vis.discover_vertex(u, g);
1.107 + tie(ei, ei_end) = out_edges(u, g);
1.108 + // Variable is needed to workaround a borland bug.
1.109 + TF& fn = static_cast<TF&>(func);
1.110 + if (fn(u, g)) {
1.111 + // If this vertex terminates the search, we push empty range
1.112 + stack.push_back(std::make_pair(u, std::make_pair(ei_end, ei_end)));
1.113 + } else {
1.114 + stack.push_back(std::make_pair(u, std::make_pair(ei, ei_end)));
1.115 + }
1.116 + while (!stack.empty()) {
1.117 + VertexInfo& back = stack.back();
1.118 + u = back.first;
1.119 + tie(ei, ei_end) = back.second;
1.120 + stack.pop_back();
1.121 + while (ei != ei_end) {
1.122 + Vertex v = target(*ei, g);
1.123 + vis.examine_edge(*ei, g);
1.124 + ColorValue v_color = get(color, v);
1.125 + if (v_color == Color::white()) {
1.126 + vis.tree_edge(*ei, g);
1.127 + stack.push_back(std::make_pair(u, std::make_pair(++ei, ei_end)));
1.128 + u = v;
1.129 + put(color, u, Color::gray());
1.130 + vis.discover_vertex(u, g);
1.131 + tie(ei, ei_end) = out_edges(u, g);
1.132 + if (fn(u, g)) {
1.133 + ei = ei_end;
1.134 + }
1.135 + } else if (v_color == Color::gray()) {
1.136 + vis.back_edge(*ei, g);
1.137 + ++ei;
1.138 + } else {
1.139 + vis.forward_or_cross_edge(*ei, g);
1.140 + ++ei;
1.141 + }
1.142 + }
1.143 + put(color, u, Color::black());
1.144 + vis.finish_vertex(u, g);
1.145 + }
1.146 + }
1.147 +
1.148 +#else // BOOST_RECURSIVE_DFS is defined
1.149 +
1.150 + template <class IncidenceGraph, class DFSVisitor, class ColorMap,
1.151 + class TerminatorFunc>
1.152 + void depth_first_visit_impl
1.153 + (const IncidenceGraph& g,
1.154 + typename graph_traits<IncidenceGraph>::vertex_descriptor u,
1.155 + DFSVisitor& vis, // pass-by-reference here, important!
1.156 + ColorMap color, TerminatorFunc func)
1.157 + {
1.158 + function_requires<IncidenceGraphConcept<IncidenceGraph> >();
1.159 + function_requires<DFSVisitorConcept<DFSVisitor, IncidenceGraph> >();
1.160 + typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
1.161 + function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >();
1.162 + typedef typename property_traits<ColorMap>::value_type ColorValue;
1.163 + function_requires< ColorValueConcept<ColorValue> >();
1.164 + typedef color_traits<ColorValue> Color;
1.165 + typename graph_traits<IncidenceGraph>::out_edge_iterator ei, ei_end;
1.166 +
1.167 + put(color, u, Color::gray()); vis.discover_vertex(u, g);
1.168 +
1.169 + typedef typename unwrap_reference<TerminatorFunc>::type TF;
1.170 + // Variable is needed to workaround a borland bug.
1.171 + TF& fn = static_cast<TF&>(func);
1.172 + if (!fn(u, g))
1.173 + for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
1.174 + Vertex v = target(*ei, g); vis.examine_edge(*ei, g);
1.175 + ColorValue v_color = get(color, v);
1.176 + if (v_color == Color::white()) { vis.tree_edge(*ei, g);
1.177 + depth_first_visit_impl(g, v, vis, color, func);
1.178 + } else if (v_color == Color::gray()) vis.back_edge(*ei, g);
1.179 + else vis.forward_or_cross_edge(*ei, g);
1.180 + }
1.181 + put(color, u, Color::black()); vis.finish_vertex(u, g);
1.182 + }
1.183 +
1.184 +#endif
1.185 +
1.186 + } // namespace detail
1.187 +
1.188 + template <class VertexListGraph, class DFSVisitor, class ColorMap>
1.189 + void
1.190 + depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color,
1.191 + typename graph_traits<VertexListGraph>::vertex_descriptor start_vertex)
1.192 + {
1.193 + typedef typename graph_traits<VertexListGraph>::vertex_descriptor Vertex;
1.194 + function_requires<DFSVisitorConcept<DFSVisitor, VertexListGraph> >();
1.195 + typedef typename property_traits<ColorMap>::value_type ColorValue;
1.196 + typedef color_traits<ColorValue> Color;
1.197 +
1.198 + typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
1.199 + for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
1.200 + put(color, *ui, Color::white()); vis.initialize_vertex(*ui, g);
1.201 + }
1.202 +
1.203 + if (start_vertex != implicit_cast<Vertex>(*vertices(g).first)){ vis.start_vertex(start_vertex, g);
1.204 + detail::depth_first_visit_impl(g, start_vertex, vis, color,
1.205 + detail::nontruth2());
1.206 + }
1.207 +
1.208 + for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
1.209 + ColorValue u_color = get(color, *ui);
1.210 + if (u_color == Color::white()) { vis.start_vertex(*ui, g);
1.211 + detail::depth_first_visit_impl(g, *ui, vis, color, detail::nontruth2());
1.212 + }
1.213 + }
1.214 + }
1.215 +
1.216 + template <class VertexListGraph, class DFSVisitor, class ColorMap>
1.217 + void
1.218 + depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color)
1.219 + {
1.220 + if (vertices(g).first == vertices(g).second)
1.221 + return;
1.222 +
1.223 + depth_first_search(g, vis, color, *vertices(g).first);
1.224 + }
1.225 +
1.226 + namespace detail {
1.227 + template <class ColorMap>
1.228 + struct dfs_dispatch {
1.229 +
1.230 + template <class VertexListGraph, class Vertex, class DFSVisitor,
1.231 + class P, class T, class R>
1.232 + static void
1.233 + apply(const VertexListGraph& g, DFSVisitor vis, Vertex start_vertex,
1.234 + const bgl_named_params<P, T, R>&,
1.235 + ColorMap color)
1.236 + {
1.237 + depth_first_search(g, vis, color, start_vertex);
1.238 + }
1.239 + };
1.240 +
1.241 + template <>
1.242 + struct dfs_dispatch<detail::error_property_not_found> {
1.243 + template <class VertexListGraph, class Vertex, class DFSVisitor,
1.244 + class P, class T, class R>
1.245 + static void
1.246 + apply(const VertexListGraph& g, DFSVisitor vis, Vertex start_vertex,
1.247 + const bgl_named_params<P, T, R>& params,
1.248 + detail::error_property_not_found)
1.249 + {
1.250 + std::vector<default_color_type> color_vec(num_vertices(g));
1.251 + default_color_type c = white_color; // avoid warning about un-init
1.252 + depth_first_search
1.253 + (g, vis, make_iterator_property_map
1.254 + (color_vec.begin(),
1.255 + choose_const_pmap(get_param(params, vertex_index),
1.256 + g, vertex_index), c),
1.257 + start_vertex);
1.258 + }
1.259 + };
1.260 + } // namespace detail
1.261 +
1.262 +
1.263 + template <class Visitors = null_visitor>
1.264 + class dfs_visitor {
1.265 + public:
1.266 + dfs_visitor() { }
1.267 + dfs_visitor(Visitors vis) : m_vis(vis) { }
1.268 +
1.269 + template <class Vertex, class Graph>
1.270 + void initialize_vertex(Vertex u, const Graph& g) {
1.271 + invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
1.272 + }
1.273 + template <class Vertex, class Graph>
1.274 + void start_vertex(Vertex u, const Graph& g) {
1.275 + invoke_visitors(m_vis, u, g, ::boost::on_start_vertex());
1.276 + }
1.277 + template <class Vertex, class Graph>
1.278 + void discover_vertex(Vertex u, const Graph& g) {
1.279 + invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex());
1.280 + }
1.281 + template <class Edge, class Graph>
1.282 + void examine_edge(Edge u, const Graph& g) {
1.283 + invoke_visitors(m_vis, u, g, ::boost::on_examine_edge());
1.284 + }
1.285 + template <class Edge, class Graph>
1.286 + void tree_edge(Edge u, const Graph& g) {
1.287 + invoke_visitors(m_vis, u, g, ::boost::on_tree_edge());
1.288 + }
1.289 + template <class Edge, class Graph>
1.290 + void back_edge(Edge u, const Graph& g) {
1.291 + invoke_visitors(m_vis, u, g, ::boost::on_back_edge());
1.292 + }
1.293 + template <class Edge, class Graph>
1.294 + void forward_or_cross_edge(Edge u, const Graph& g) {
1.295 + invoke_visitors(m_vis, u, g, ::boost::on_forward_or_cross_edge());
1.296 + }
1.297 + template <class Vertex, class Graph>
1.298 + void finish_vertex(Vertex u, const Graph& g) {
1.299 + invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
1.300 + }
1.301 +
1.302 + BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,dfs)
1.303 + BOOST_GRAPH_EVENT_STUB(on_start_vertex,dfs)
1.304 + BOOST_GRAPH_EVENT_STUB(on_discover_vertex,dfs)
1.305 + BOOST_GRAPH_EVENT_STUB(on_examine_edge,dfs)
1.306 + BOOST_GRAPH_EVENT_STUB(on_tree_edge,dfs)
1.307 + BOOST_GRAPH_EVENT_STUB(on_back_edge,dfs)
1.308 + BOOST_GRAPH_EVENT_STUB(on_forward_or_cross_edge,dfs)
1.309 + BOOST_GRAPH_EVENT_STUB(on_finish_vertex,dfs)
1.310 +
1.311 + protected:
1.312 + Visitors m_vis;
1.313 + };
1.314 + template <class Visitors>
1.315 + dfs_visitor<Visitors>
1.316 + make_dfs_visitor(Visitors vis) {
1.317 + return dfs_visitor<Visitors>(vis);
1.318 + }
1.319 + typedef dfs_visitor<> default_dfs_visitor;
1.320 +
1.321 +
1.322 + // Named Parameter Variant
1.323 + template <class VertexListGraph, class P, class T, class R>
1.324 + void
1.325 + depth_first_search(const VertexListGraph& g,
1.326 + const bgl_named_params<P, T, R>& params)
1.327 + {
1.328 + typedef typename property_value< bgl_named_params<P, T, R>,
1.329 + vertex_color_t>::type C;
1.330 + if (vertices(g).first == vertices(g).second)
1.331 + return;
1.332 + detail::dfs_dispatch<C>::apply
1.333 + (g,
1.334 + choose_param(get_param(params, graph_visitor),
1.335 + make_dfs_visitor(null_visitor())),
1.336 + choose_param(get_param(params, root_vertex_t()),
1.337 + *vertices(g).first),
1.338 + params,
1.339 + get_param(params, vertex_color)
1.340 + );
1.341 + }
1.342 +
1.343 + template <class IncidenceGraph, class DFSVisitor, class ColorMap>
1.344 + void depth_first_visit
1.345 + (const IncidenceGraph& g,
1.346 + typename graph_traits<IncidenceGraph>::vertex_descriptor u,
1.347 + DFSVisitor vis, ColorMap color)
1.348 + {
1.349 + vis.start_vertex(u, g);
1.350 + detail::depth_first_visit_impl(g, u, vis, color, detail::nontruth2());
1.351 + }
1.352 +
1.353 + template <class IncidenceGraph, class DFSVisitor, class ColorMap,
1.354 + class TerminatorFunc>
1.355 + void depth_first_visit
1.356 + (const IncidenceGraph& g,
1.357 + typename graph_traits<IncidenceGraph>::vertex_descriptor u,
1.358 + DFSVisitor vis, ColorMap color, TerminatorFunc func = TerminatorFunc())
1.359 + {
1.360 + vis.start_vertex(u, g);
1.361 + detail::depth_first_visit_impl(g, u, vis, color, func);
1.362 + }
1.363 +
1.364 +
1.365 +} // namespace boost
1.366 +
1.367 +
1.368 +#endif