epoc32/include/stdapis/boost/graph/neighbor_bfs.hpp
branchSymbian2
changeset 2 2fe1408b6811
     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 +