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