1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/neighbor_bfs.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,323 @@
1.4 +//
1.5 +//=======================================================================
1.6 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
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 +#ifndef BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP
1.15 +#define BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP
1.16 +
1.17 +/*
1.18 + Neighbor Breadth First Search
1.19 + Like BFS, but traverses in-edges as well as out-edges.
1.20 + (for directed graphs only. use normal BFS for undirected graphs)
1.21 +*/
1.22 +#include <boost/config.hpp>
1.23 +#include <vector>
1.24 +#include <boost/pending/queue.hpp>
1.25 +#include <boost/graph/graph_traits.hpp>
1.26 +#include <boost/graph/graph_concepts.hpp>
1.27 +#include <boost/graph/visitors.hpp>
1.28 +#include <boost/graph/named_function_params.hpp>
1.29 +
1.30 +namespace boost {
1.31 +
1.32 + template <class Visitor, class Graph>
1.33 + struct NeighborBFSVisitorConcept {
1.34 + void constraints() {
1.35 + function_requires< CopyConstructibleConcept<Visitor> >();
1.36 + vis.initialize_vertex(u, g);
1.37 + vis.discover_vertex(u, g);
1.38 + vis.examine_vertex(u, g);
1.39 + vis.examine_out_edge(e, g);
1.40 + vis.examine_in_edge(e, g);
1.41 + vis.tree_out_edge(e, g);
1.42 + vis.tree_in_edge(e, g);
1.43 + vis.non_tree_out_edge(e, g);
1.44 + vis.non_tree_in_edge(e, g);
1.45 + vis.gray_target(e, g);
1.46 + vis.black_target(e, g);
1.47 + vis.gray_source(e, g);
1.48 + vis.black_source(e, g);
1.49 + vis.finish_vertex(u, g);
1.50 + }
1.51 + Visitor vis;
1.52 + Graph g;
1.53 + typename graph_traits<Graph>::vertex_descriptor u;
1.54 + typename graph_traits<Graph>::edge_descriptor e;
1.55 + };
1.56 +
1.57 + template <class Visitors = null_visitor>
1.58 + class neighbor_bfs_visitor {
1.59 + public:
1.60 + neighbor_bfs_visitor(Visitors vis = Visitors()) : m_vis(vis) { }
1.61 +
1.62 + template <class Vertex, class Graph>
1.63 + void initialize_vertex(Vertex u, Graph& g) {
1.64 + invoke_visitors(m_vis, u, g, on_initialize_vertex());
1.65 + }
1.66 + template <class Vertex, class Graph>
1.67 + void discover_vertex(Vertex u, Graph& g) {
1.68 + invoke_visitors(m_vis, u, g, on_discover_vertex());
1.69 + }
1.70 + template <class Vertex, class Graph>
1.71 + void examine_vertex(Vertex u, Graph& g) {
1.72 + invoke_visitors(m_vis, u, g, on_examine_vertex());
1.73 + }
1.74 + template <class Edge, class Graph>
1.75 + void examine_out_edge(Edge e, Graph& g) {
1.76 + invoke_visitors(m_vis, e, g, on_examine_edge());
1.77 + }
1.78 + template <class Edge, class Graph>
1.79 + void tree_out_edge(Edge e, Graph& g) {
1.80 + invoke_visitors(m_vis, e, g, on_tree_edge());
1.81 + }
1.82 + template <class Edge, class Graph>
1.83 + void non_tree_out_edge(Edge e, Graph& g) {
1.84 + invoke_visitors(m_vis, e, g, on_non_tree_edge());
1.85 + }
1.86 + template <class Edge, class Graph>
1.87 + void gray_target(Edge e, Graph& g) {
1.88 + invoke_visitors(m_vis, e, g, on_gray_target());
1.89 + }
1.90 + template <class Edge, class Graph>
1.91 + void black_target(Edge e, Graph& g) {
1.92 + invoke_visitors(m_vis, e, g, on_black_target());
1.93 + }
1.94 + template <class Edge, class Graph>
1.95 + void examine_in_edge(Edge e, Graph& g) {
1.96 + invoke_visitors(m_vis, e, g, on_examine_edge());
1.97 + }
1.98 + template <class Edge, class Graph>
1.99 + void tree_in_edge(Edge e, Graph& g) {
1.100 + invoke_visitors(m_vis, e, g, on_tree_edge());
1.101 + }
1.102 + template <class Edge, class Graph>
1.103 + void non_tree_in_edge(Edge e, Graph& g) {
1.104 + invoke_visitors(m_vis, e, g, on_non_tree_edge());
1.105 + }
1.106 + template <class Edge, class Graph>
1.107 + void gray_source(Edge e, Graph& g) {
1.108 + invoke_visitors(m_vis, e, g, on_gray_target());
1.109 + }
1.110 + template <class Edge, class Graph>
1.111 + void black_source(Edge e, Graph& g) {
1.112 + invoke_visitors(m_vis, e, g, on_black_target());
1.113 + }
1.114 + template <class Vertex, class Graph>
1.115 + void finish_vertex(Vertex u, Graph& g) {
1.116 + invoke_visitors(m_vis, u, g, on_finish_vertex());
1.117 + }
1.118 + protected:
1.119 + Visitors m_vis;
1.120 + };
1.121 +
1.122 + template <class Visitors>
1.123 + neighbor_bfs_visitor<Visitors>
1.124 + make_neighbor_bfs_visitor(Visitors vis) {
1.125 + return neighbor_bfs_visitor<Visitors>(vis);
1.126 + }
1.127 +
1.128 + namespace detail {
1.129 +
1.130 + template <class BidirectionalGraph, class Buffer, class BFSVisitor,
1.131 + class ColorMap>
1.132 + void neighbor_bfs_impl
1.133 + (const BidirectionalGraph& g,
1.134 + typename graph_traits<BidirectionalGraph>::vertex_descriptor s,
1.135 + Buffer& Q, BFSVisitor vis, ColorMap color)
1.136 +
1.137 + {
1.138 + function_requires< BidirectionalGraphConcept<BidirectionalGraph> >();
1.139 + typedef graph_traits<BidirectionalGraph> GTraits;
1.140 + typedef typename GTraits::vertex_descriptor Vertex;
1.141 + typedef typename GTraits::edge_descriptor Edge;
1.142 + function_requires<
1.143 + NeighborBFSVisitorConcept<BFSVisitor, BidirectionalGraph> >();
1.144 + function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >();
1.145 + typedef typename property_traits<ColorMap>::value_type ColorValue;
1.146 + typedef color_traits<ColorValue> Color;
1.147 +
1.148 + put(color, s, Color::gray());
1.149 + vis.discover_vertex(s, g);
1.150 + Q.push(s);
1.151 + while (! Q.empty()) {
1.152 + Vertex u = Q.top();
1.153 + Q.pop(); // pop before push to avoid problem if Q is priority_queue.
1.154 + vis.examine_vertex(u, g);
1.155 +
1.156 + typename GTraits::out_edge_iterator ei, ei_end;
1.157 + for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
1.158 + Edge e = *ei;
1.159 + vis.examine_out_edge(e, g);
1.160 + Vertex v = target(e, g);
1.161 + ColorValue v_color = get(color, v);
1.162 + if (v_color == Color::white()) {
1.163 + vis.tree_out_edge(e, g);
1.164 + put(color, v, Color::gray());
1.165 + vis.discover_vertex(v, g);
1.166 + Q.push(v);
1.167 + } else {
1.168 + vis.non_tree_out_edge(e, g);
1.169 + if (v_color == Color::gray())
1.170 + vis.gray_target(e, g);
1.171 + else
1.172 + vis.black_target(e, g);
1.173 + }
1.174 + } // for out-edges
1.175 +
1.176 + typename GTraits::in_edge_iterator in_ei, in_ei_end;
1.177 + for (tie(in_ei, in_ei_end) = in_edges(u, g);
1.178 + in_ei != in_ei_end; ++in_ei) {
1.179 + Edge e = *in_ei;
1.180 + vis.examine_in_edge(e, g);
1.181 + Vertex v = source(e, g);
1.182 + ColorValue v_color = get(color, v);
1.183 + if (v_color == Color::white()) {
1.184 + vis.tree_in_edge(e, g);
1.185 + put(color, v, Color::gray());
1.186 + vis.discover_vertex(v, g);
1.187 + Q.push(v);
1.188 + } else {
1.189 + vis.non_tree_in_edge(e, g);
1.190 + if (v_color == Color::gray())
1.191 + vis.gray_source(e, g);
1.192 + else
1.193 + vis.black_source(e, g);
1.194 + }
1.195 + } // for in-edges
1.196 +
1.197 + put(color, u, Color::black());
1.198 + vis.finish_vertex(u, g);
1.199 + } // while
1.200 + }
1.201 +
1.202 +
1.203 + template <class VertexListGraph, class ColorMap, class BFSVisitor,
1.204 + class P, class T, class R>
1.205 + void neighbor_bfs_helper
1.206 + (VertexListGraph& g,
1.207 + typename graph_traits<VertexListGraph>::vertex_descriptor s,
1.208 + ColorMap color,
1.209 + BFSVisitor vis,
1.210 + const bgl_named_params<P, T, R>& params)
1.211 + {
1.212 + typedef graph_traits<VertexListGraph> Traits;
1.213 + // Buffer default
1.214 + typedef typename Traits::vertex_descriptor Vertex;
1.215 + typedef boost::queue<Vertex> queue_t;
1.216 + queue_t Q;
1.217 + detail::wrap_ref<queue_t> Qref(Q);
1.218 + // Initialization
1.219 + typedef typename property_traits<ColorMap>::value_type ColorValue;
1.220 + typedef color_traits<ColorValue> Color;
1.221 + typename boost::graph_traits<VertexListGraph>::vertex_iterator i, i_end;
1.222 + for (tie(i, i_end) = vertices(g); i != i_end; ++i) {
1.223 + put(color, *i, Color::white());
1.224 + vis.initialize_vertex(*i, g);
1.225 + }
1.226 + neighbor_bfs_impl
1.227 + (g, s,
1.228 + choose_param(get_param(params, buffer_param_t()), Qref).ref,
1.229 + vis, color);
1.230 + }
1.231 +
1.232 + //-------------------------------------------------------------------------
1.233 + // Choose between default color and color parameters. Using
1.234 + // function dispatching so that we don't require vertex index if
1.235 + // the color default is not being used.
1.236 +
1.237 + template <class ColorMap>
1.238 + struct neighbor_bfs_dispatch {
1.239 + template <class VertexListGraph, class P, class T, class R>
1.240 + static void apply
1.241 + (VertexListGraph& g,
1.242 + typename graph_traits<VertexListGraph>::vertex_descriptor s,
1.243 + const bgl_named_params<P, T, R>& params,
1.244 + ColorMap color)
1.245 + {
1.246 + neighbor_bfs_helper
1.247 + (g, s, color,
1.248 + choose_param(get_param(params, graph_visitor),
1.249 + make_neighbor_bfs_visitor(null_visitor())),
1.250 + params);
1.251 + }
1.252 + };
1.253 +
1.254 + template <>
1.255 + struct neighbor_bfs_dispatch<detail::error_property_not_found> {
1.256 + template <class VertexListGraph, class P, class T, class R>
1.257 + static void apply
1.258 + (VertexListGraph& g,
1.259 + typename graph_traits<VertexListGraph>::vertex_descriptor s,
1.260 + const bgl_named_params<P, T, R>& params,
1.261 + detail::error_property_not_found)
1.262 + {
1.263 + std::vector<default_color_type> color_vec(num_vertices(g));
1.264 + null_visitor null_vis;
1.265 +
1.266 + neighbor_bfs_helper
1.267 + (g, s,
1.268 + make_iterator_property_map
1.269 + (color_vec.begin(),
1.270 + choose_const_pmap(get_param(params, vertex_index),
1.271 + g, vertex_index), color_vec[0]),
1.272 + choose_param(get_param(params, graph_visitor),
1.273 + make_neighbor_bfs_visitor(null_vis)),
1.274 + params);
1.275 + }
1.276 + };
1.277 +
1.278 + } // namespace detail
1.279 +
1.280 +
1.281 + // Named Parameter Variant
1.282 + template <class VertexListGraph, class P, class T, class R>
1.283 + void neighbor_breadth_first_search
1.284 + (const VertexListGraph& g,
1.285 + typename graph_traits<VertexListGraph>::vertex_descriptor s,
1.286 + const bgl_named_params<P, T, R>& params)
1.287 + {
1.288 + // The graph is passed by *const* reference so that graph adaptors
1.289 + // (temporaries) can be passed into this function. However, the
1.290 + // graph is not really const since we may write to property maps
1.291 + // of the graph.
1.292 + VertexListGraph& ng = const_cast<VertexListGraph&>(g);
1.293 + typedef typename property_value< bgl_named_params<P,T,R>,
1.294 + vertex_color_t>::type C;
1.295 + detail::neighbor_bfs_dispatch<C>::apply(ng, s, params,
1.296 + get_param(params, vertex_color));
1.297 + }
1.298 +
1.299 +
1.300 + // This version does not initialize colors, user has to.
1.301 +
1.302 + template <class IncidenceGraph, class P, class T, class R>
1.303 + void neighbor_breadth_first_visit
1.304 + (IncidenceGraph& g,
1.305 + typename graph_traits<IncidenceGraph>::vertex_descriptor s,
1.306 + const bgl_named_params<P, T, R>& params)
1.307 + {
1.308 + typedef graph_traits<IncidenceGraph> Traits;
1.309 + // Buffer default
1.310 + typedef boost::queue<typename Traits::vertex_descriptor> queue_t;
1.311 + queue_t Q;
1.312 + detail::wrap_ref<queue_t> Qref(Q);
1.313 +
1.314 + detail::neighbor_bfs_impl
1.315 + (g, s,
1.316 + choose_param(get_param(params, buffer_param_t()), Qref).ref,
1.317 + choose_param(get_param(params, graph_visitor),
1.318 + make_neighbor_bfs_visitor(null_visitor())),
1.319 + choose_pmap(get_param(params, vertex_color), g, vertex_color)
1.320 + );
1.321 + }
1.322 +
1.323 +} // namespace boost
1.324 +
1.325 +#endif // BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP
1.326 +