diff -r 666f914201fb -r 2fe1408b6811 epoc32/include/stdapis/boost/graph/neighbor_bfs.hpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/epoc32/include/stdapis/boost/graph/neighbor_bfs.hpp Tue Mar 16 16:12:26 2010 +0000 @@ -0,0 +1,323 @@ +// +//======================================================================= +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame. +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek +// +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +//======================================================================= +// +#ifndef BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP +#define BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP + +/* + Neighbor Breadth First Search + Like BFS, but traverses in-edges as well as out-edges. + (for directed graphs only. use normal BFS for undirected graphs) +*/ +#include +#include +#include +#include +#include +#include +#include + +namespace boost { + + template + struct NeighborBFSVisitorConcept { + void constraints() { + function_requires< CopyConstructibleConcept >(); + vis.initialize_vertex(u, g); + vis.discover_vertex(u, g); + vis.examine_vertex(u, g); + vis.examine_out_edge(e, g); + vis.examine_in_edge(e, g); + vis.tree_out_edge(e, g); + vis.tree_in_edge(e, g); + vis.non_tree_out_edge(e, g); + vis.non_tree_in_edge(e, g); + vis.gray_target(e, g); + vis.black_target(e, g); + vis.gray_source(e, g); + vis.black_source(e, g); + vis.finish_vertex(u, g); + } + Visitor vis; + Graph g; + typename graph_traits::vertex_descriptor u; + typename graph_traits::edge_descriptor e; + }; + + template + class neighbor_bfs_visitor { + public: + neighbor_bfs_visitor(Visitors vis = Visitors()) : m_vis(vis) { } + + template + void initialize_vertex(Vertex u, Graph& g) { + invoke_visitors(m_vis, u, g, on_initialize_vertex()); + } + template + void discover_vertex(Vertex u, Graph& g) { + invoke_visitors(m_vis, u, g, on_discover_vertex()); + } + template + void examine_vertex(Vertex u, Graph& g) { + invoke_visitors(m_vis, u, g, on_examine_vertex()); + } + template + void examine_out_edge(Edge e, Graph& g) { + invoke_visitors(m_vis, e, g, on_examine_edge()); + } + template + void tree_out_edge(Edge e, Graph& g) { + invoke_visitors(m_vis, e, g, on_tree_edge()); + } + template + void non_tree_out_edge(Edge e, Graph& g) { + invoke_visitors(m_vis, e, g, on_non_tree_edge()); + } + template + void gray_target(Edge e, Graph& g) { + invoke_visitors(m_vis, e, g, on_gray_target()); + } + template + void black_target(Edge e, Graph& g) { + invoke_visitors(m_vis, e, g, on_black_target()); + } + template + void examine_in_edge(Edge e, Graph& g) { + invoke_visitors(m_vis, e, g, on_examine_edge()); + } + template + void tree_in_edge(Edge e, Graph& g) { + invoke_visitors(m_vis, e, g, on_tree_edge()); + } + template + void non_tree_in_edge(Edge e, Graph& g) { + invoke_visitors(m_vis, e, g, on_non_tree_edge()); + } + template + void gray_source(Edge e, Graph& g) { + invoke_visitors(m_vis, e, g, on_gray_target()); + } + template + void black_source(Edge e, Graph& g) { + invoke_visitors(m_vis, e, g, on_black_target()); + } + template + void finish_vertex(Vertex u, Graph& g) { + invoke_visitors(m_vis, u, g, on_finish_vertex()); + } + protected: + Visitors m_vis; + }; + + template + neighbor_bfs_visitor + make_neighbor_bfs_visitor(Visitors vis) { + return neighbor_bfs_visitor(vis); + } + + namespace detail { + + template + void neighbor_bfs_impl + (const BidirectionalGraph& g, + typename graph_traits::vertex_descriptor s, + Buffer& Q, BFSVisitor vis, ColorMap color) + + { + function_requires< BidirectionalGraphConcept >(); + typedef graph_traits GTraits; + typedef typename GTraits::vertex_descriptor Vertex; + typedef typename GTraits::edge_descriptor Edge; + function_requires< + NeighborBFSVisitorConcept >(); + function_requires< ReadWritePropertyMapConcept >(); + typedef typename property_traits::value_type ColorValue; + typedef color_traits Color; + + put(color, s, Color::gray()); + vis.discover_vertex(s, g); + Q.push(s); + while (! Q.empty()) { + Vertex u = Q.top(); + Q.pop(); // pop before push to avoid problem if Q is priority_queue. + vis.examine_vertex(u, g); + + typename GTraits::out_edge_iterator ei, ei_end; + for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) { + Edge e = *ei; + vis.examine_out_edge(e, g); + Vertex v = target(e, g); + ColorValue v_color = get(color, v); + if (v_color == Color::white()) { + vis.tree_out_edge(e, g); + put(color, v, Color::gray()); + vis.discover_vertex(v, g); + Q.push(v); + } else { + vis.non_tree_out_edge(e, g); + if (v_color == Color::gray()) + vis.gray_target(e, g); + else + vis.black_target(e, g); + } + } // for out-edges + + typename GTraits::in_edge_iterator in_ei, in_ei_end; + for (tie(in_ei, in_ei_end) = in_edges(u, g); + in_ei != in_ei_end; ++in_ei) { + Edge e = *in_ei; + vis.examine_in_edge(e, g); + Vertex v = source(e, g); + ColorValue v_color = get(color, v); + if (v_color == Color::white()) { + vis.tree_in_edge(e, g); + put(color, v, Color::gray()); + vis.discover_vertex(v, g); + Q.push(v); + } else { + vis.non_tree_in_edge(e, g); + if (v_color == Color::gray()) + vis.gray_source(e, g); + else + vis.black_source(e, g); + } + } // for in-edges + + put(color, u, Color::black()); + vis.finish_vertex(u, g); + } // while + } + + + template + void neighbor_bfs_helper + (VertexListGraph& g, + typename graph_traits::vertex_descriptor s, + ColorMap color, + BFSVisitor vis, + const bgl_named_params& params) + { + typedef graph_traits Traits; + // Buffer default + typedef typename Traits::vertex_descriptor Vertex; + typedef boost::queue queue_t; + queue_t Q; + detail::wrap_ref Qref(Q); + // Initialization + typedef typename property_traits::value_type ColorValue; + typedef color_traits Color; + typename boost::graph_traits::vertex_iterator i, i_end; + for (tie(i, i_end) = vertices(g); i != i_end; ++i) { + put(color, *i, Color::white()); + vis.initialize_vertex(*i, g); + } + neighbor_bfs_impl + (g, s, + choose_param(get_param(params, buffer_param_t()), Qref).ref, + vis, color); + } + + //------------------------------------------------------------------------- + // Choose between default color and color parameters. Using + // function dispatching so that we don't require vertex index if + // the color default is not being used. + + template + struct neighbor_bfs_dispatch { + template + static void apply + (VertexListGraph& g, + typename graph_traits::vertex_descriptor s, + const bgl_named_params& params, + ColorMap color) + { + neighbor_bfs_helper + (g, s, color, + choose_param(get_param(params, graph_visitor), + make_neighbor_bfs_visitor(null_visitor())), + params); + } + }; + + template <> + struct neighbor_bfs_dispatch { + template + static void apply + (VertexListGraph& g, + typename graph_traits::vertex_descriptor s, + const bgl_named_params& params, + detail::error_property_not_found) + { + std::vector color_vec(num_vertices(g)); + null_visitor null_vis; + + neighbor_bfs_helper + (g, s, + make_iterator_property_map + (color_vec.begin(), + choose_const_pmap(get_param(params, vertex_index), + g, vertex_index), color_vec[0]), + choose_param(get_param(params, graph_visitor), + make_neighbor_bfs_visitor(null_vis)), + params); + } + }; + + } // namespace detail + + + // Named Parameter Variant + template + void neighbor_breadth_first_search + (const VertexListGraph& g, + typename graph_traits::vertex_descriptor s, + const bgl_named_params& params) + { + // The graph is passed by *const* reference so that graph adaptors + // (temporaries) can be passed into this function. However, the + // graph is not really const since we may write to property maps + // of the graph. + VertexListGraph& ng = const_cast(g); + typedef typename property_value< bgl_named_params, + vertex_color_t>::type C; + detail::neighbor_bfs_dispatch::apply(ng, s, params, + get_param(params, vertex_color)); + } + + + // This version does not initialize colors, user has to. + + template + void neighbor_breadth_first_visit + (IncidenceGraph& g, + typename graph_traits::vertex_descriptor s, + const bgl_named_params& params) + { + typedef graph_traits Traits; + // Buffer default + typedef boost::queue queue_t; + queue_t Q; + detail::wrap_ref Qref(Q); + + detail::neighbor_bfs_impl + (g, s, + choose_param(get_param(params, buffer_param_t()), Qref).ref, + choose_param(get_param(params, graph_visitor), + make_neighbor_bfs_visitor(null_visitor())), + choose_pmap(get_param(params, vertex_color), g, vertex_color) + ); + } + +} // namespace boost + +#endif // BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP +