epoc32/include/stdapis/boost/graph/neighbor_bfs.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     1 //
     2 //=======================================================================
     3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
     4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
     5 //
     6 // Distributed under the Boost Software License, Version 1.0. (See
     7 // accompanying file LICENSE_1_0.txt or copy at
     8 // http://www.boost.org/LICENSE_1_0.txt)
     9 //=======================================================================
    10 //
    11 #ifndef BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP
    12 #define BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP
    13 
    14 /*
    15   Neighbor Breadth First Search
    16   Like BFS, but traverses in-edges as well as out-edges.
    17   (for directed graphs only. use normal BFS for undirected graphs)
    18 */
    19 #include <boost/config.hpp>
    20 #include <vector>
    21 #include <boost/pending/queue.hpp>
    22 #include <boost/graph/graph_traits.hpp>
    23 #include <boost/graph/graph_concepts.hpp>
    24 #include <boost/graph/visitors.hpp>
    25 #include <boost/graph/named_function_params.hpp>
    26 
    27 namespace boost {
    28 
    29   template <class Visitor, class Graph>
    30   struct NeighborBFSVisitorConcept {
    31     void constraints() {
    32       function_requires< CopyConstructibleConcept<Visitor> >();
    33       vis.initialize_vertex(u, g);
    34       vis.discover_vertex(u, g);
    35       vis.examine_vertex(u, g);
    36       vis.examine_out_edge(e, g);
    37       vis.examine_in_edge(e, g);
    38       vis.tree_out_edge(e, g);
    39       vis.tree_in_edge(e, g);
    40       vis.non_tree_out_edge(e, g);
    41       vis.non_tree_in_edge(e, g);
    42       vis.gray_target(e, g);
    43       vis.black_target(e, g);
    44       vis.gray_source(e, g);
    45       vis.black_source(e, g);
    46       vis.finish_vertex(u, g);
    47     }
    48     Visitor vis;
    49     Graph g;
    50     typename graph_traits<Graph>::vertex_descriptor u;
    51     typename graph_traits<Graph>::edge_descriptor e;
    52   };
    53 
    54   template <class Visitors = null_visitor>
    55   class neighbor_bfs_visitor {
    56   public:
    57     neighbor_bfs_visitor(Visitors vis = Visitors()) : m_vis(vis) { }
    58 
    59     template <class Vertex, class Graph>
    60     void initialize_vertex(Vertex u, Graph& g) {
    61       invoke_visitors(m_vis, u, g, on_initialize_vertex());      
    62     }
    63     template <class Vertex, class Graph>
    64     void discover_vertex(Vertex u, Graph& g) {
    65       invoke_visitors(m_vis, u, g, on_discover_vertex());      
    66     }
    67     template <class Vertex, class Graph>
    68     void examine_vertex(Vertex u, Graph& g) {
    69       invoke_visitors(m_vis, u, g, on_examine_vertex());
    70     }
    71     template <class Edge, class Graph>
    72     void examine_out_edge(Edge e, Graph& g) {
    73       invoke_visitors(m_vis, e, g, on_examine_edge());
    74     }
    75     template <class Edge, class Graph>
    76     void tree_out_edge(Edge e, Graph& g) {
    77       invoke_visitors(m_vis, e, g, on_tree_edge());      
    78     }
    79     template <class Edge, class Graph>
    80     void non_tree_out_edge(Edge e, Graph& g) {
    81       invoke_visitors(m_vis, e, g, on_non_tree_edge());
    82     }
    83     template <class Edge, class Graph>
    84     void gray_target(Edge e, Graph& g) {
    85       invoke_visitors(m_vis, e, g, on_gray_target());
    86     }
    87     template <class Edge, class Graph>
    88     void black_target(Edge e, Graph& g) {
    89       invoke_visitors(m_vis, e, g, on_black_target());
    90     }
    91     template <class Edge, class Graph>
    92     void examine_in_edge(Edge e, Graph& g) {
    93       invoke_visitors(m_vis, e, g, on_examine_edge());
    94     }
    95     template <class Edge, class Graph>
    96     void tree_in_edge(Edge e, Graph& g) {
    97       invoke_visitors(m_vis, e, g, on_tree_edge());      
    98     }
    99     template <class Edge, class Graph>
   100     void non_tree_in_edge(Edge e, Graph& g) {
   101       invoke_visitors(m_vis, e, g, on_non_tree_edge());
   102     }
   103     template <class Edge, class Graph>
   104     void gray_source(Edge e, Graph& g) {
   105       invoke_visitors(m_vis, e, g, on_gray_target());
   106     }
   107     template <class Edge, class Graph>
   108     void black_source(Edge e, Graph& g) {
   109       invoke_visitors(m_vis, e, g, on_black_target());
   110     }
   111     template <class Vertex, class Graph>
   112     void finish_vertex(Vertex u, Graph& g) {
   113       invoke_visitors(m_vis, u, g, on_finish_vertex());      
   114     }
   115   protected:
   116     Visitors m_vis;
   117   };
   118 
   119   template <class Visitors>
   120   neighbor_bfs_visitor<Visitors>
   121   make_neighbor_bfs_visitor(Visitors vis) {
   122     return neighbor_bfs_visitor<Visitors>(vis);
   123   }
   124 
   125   namespace detail {
   126 
   127     template <class BidirectionalGraph, class Buffer, class BFSVisitor, 
   128               class ColorMap>
   129     void neighbor_bfs_impl
   130       (const BidirectionalGraph& g, 
   131        typename graph_traits<BidirectionalGraph>::vertex_descriptor s, 
   132        Buffer& Q, BFSVisitor vis, ColorMap color)
   133 
   134     {
   135       function_requires< BidirectionalGraphConcept<BidirectionalGraph> >();
   136       typedef graph_traits<BidirectionalGraph> GTraits;
   137       typedef typename GTraits::vertex_descriptor Vertex;
   138       typedef typename GTraits::edge_descriptor Edge;
   139       function_requires< 
   140         NeighborBFSVisitorConcept<BFSVisitor, BidirectionalGraph> >();
   141       function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >();
   142       typedef typename property_traits<ColorMap>::value_type ColorValue;
   143       typedef color_traits<ColorValue> Color;
   144       
   145       put(color, s, Color::gray());
   146       vis.discover_vertex(s, g);
   147       Q.push(s);
   148       while (! Q.empty()) {
   149         Vertex u = Q.top();
   150         Q.pop(); // pop before push to avoid problem if Q is priority_queue.
   151         vis.examine_vertex(u, g);
   152 
   153         typename GTraits::out_edge_iterator ei, ei_end;
   154         for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
   155           Edge e = *ei;
   156           vis.examine_out_edge(e, g);
   157           Vertex v = target(e, g);
   158           ColorValue v_color = get(color, v);
   159           if (v_color == Color::white()) {
   160             vis.tree_out_edge(e, g);
   161             put(color, v, Color::gray());
   162             vis.discover_vertex(v, g);
   163             Q.push(v);
   164           } else {
   165             vis.non_tree_out_edge(e, g);
   166             if (v_color == Color::gray())
   167               vis.gray_target(e, g);
   168             else
   169               vis.black_target(e, g);
   170           }
   171         } // for out-edges
   172 
   173         typename GTraits::in_edge_iterator in_ei, in_ei_end;
   174         for (tie(in_ei, in_ei_end) = in_edges(u, g); 
   175              in_ei != in_ei_end; ++in_ei) {
   176           Edge e = *in_ei;
   177           vis.examine_in_edge(e, g);
   178           Vertex v = source(e, g);
   179           ColorValue v_color = get(color, v);
   180           if (v_color == Color::white()) {
   181             vis.tree_in_edge(e, g);
   182             put(color, v, Color::gray());
   183             vis.discover_vertex(v, g);
   184             Q.push(v);
   185           } else {
   186             vis.non_tree_in_edge(e, g);
   187             if (v_color == Color::gray())
   188               vis.gray_source(e, g);
   189             else
   190               vis.black_source(e, g);
   191           }
   192         } // for in-edges
   193 
   194         put(color, u, Color::black());
   195         vis.finish_vertex(u, g);
   196       } // while
   197     }
   198 
   199     
   200     template <class VertexListGraph, class ColorMap, class BFSVisitor,
   201       class P, class T, class R>
   202     void neighbor_bfs_helper
   203       (VertexListGraph& g,
   204        typename graph_traits<VertexListGraph>::vertex_descriptor s,
   205        ColorMap color, 
   206        BFSVisitor vis,
   207        const bgl_named_params<P, T, R>& params)
   208     {
   209       typedef graph_traits<VertexListGraph> Traits;
   210       // Buffer default
   211       typedef typename Traits::vertex_descriptor Vertex;
   212       typedef boost::queue<Vertex> queue_t;
   213       queue_t Q;
   214       detail::wrap_ref<queue_t> Qref(Q);
   215       // Initialization
   216       typedef typename property_traits<ColorMap>::value_type ColorValue;
   217       typedef color_traits<ColorValue> Color;
   218       typename boost::graph_traits<VertexListGraph>::vertex_iterator i, i_end;
   219       for (tie(i, i_end) = vertices(g); i != i_end; ++i) {
   220         put(color, *i, Color::white());
   221         vis.initialize_vertex(*i, g);
   222       }
   223       neighbor_bfs_impl
   224         (g, s, 
   225          choose_param(get_param(params, buffer_param_t()), Qref).ref,
   226          vis, color);
   227     }
   228 
   229     //-------------------------------------------------------------------------
   230     // Choose between default color and color parameters. Using
   231     // function dispatching so that we don't require vertex index if
   232     // the color default is not being used.
   233 
   234     template <class ColorMap>
   235     struct neighbor_bfs_dispatch {
   236       template <class VertexListGraph, class P, class T, class R>
   237       static void apply
   238       (VertexListGraph& g,
   239        typename graph_traits<VertexListGraph>::vertex_descriptor s,
   240        const bgl_named_params<P, T, R>& params,
   241        ColorMap color)
   242       {
   243         neighbor_bfs_helper
   244           (g, s, color,
   245            choose_param(get_param(params, graph_visitor),
   246                         make_neighbor_bfs_visitor(null_visitor())),
   247            params);
   248       }
   249     };
   250 
   251     template <>
   252     struct neighbor_bfs_dispatch<detail::error_property_not_found> {
   253       template <class VertexListGraph, class P, class T, class R>
   254       static void apply
   255       (VertexListGraph& g,
   256        typename graph_traits<VertexListGraph>::vertex_descriptor s,
   257        const bgl_named_params<P, T, R>& params,
   258        detail::error_property_not_found)
   259       {
   260         std::vector<default_color_type> color_vec(num_vertices(g));
   261         null_visitor null_vis;
   262         
   263         neighbor_bfs_helper
   264           (g, s, 
   265            make_iterator_property_map
   266            (color_vec.begin(), 
   267             choose_const_pmap(get_param(params, vertex_index), 
   268                               g, vertex_index), color_vec[0]),
   269            choose_param(get_param(params, graph_visitor),
   270                         make_neighbor_bfs_visitor(null_vis)),
   271            params);
   272       }
   273     };
   274 
   275   } // namespace detail
   276 
   277 
   278   // Named Parameter Variant
   279   template <class VertexListGraph, class P, class T, class R>
   280   void neighbor_breadth_first_search
   281     (const VertexListGraph& g,
   282      typename graph_traits<VertexListGraph>::vertex_descriptor s,
   283      const bgl_named_params<P, T, R>& params)
   284   {
   285     // The graph is passed by *const* reference so that graph adaptors
   286     // (temporaries) can be passed into this function. However, the
   287     // graph is not really const since we may write to property maps
   288     // of the graph.
   289     VertexListGraph& ng = const_cast<VertexListGraph&>(g);
   290     typedef typename property_value< bgl_named_params<P,T,R>, 
   291       vertex_color_t>::type C;
   292     detail::neighbor_bfs_dispatch<C>::apply(ng, s, params, 
   293                                             get_param(params, vertex_color));
   294   }
   295 
   296 
   297   // This version does not initialize colors, user has to.
   298 
   299   template <class IncidenceGraph, class P, class T, class R>
   300   void neighbor_breadth_first_visit
   301     (IncidenceGraph& g,
   302      typename graph_traits<IncidenceGraph>::vertex_descriptor s,
   303      const bgl_named_params<P, T, R>& params)
   304   {
   305     typedef graph_traits<IncidenceGraph> Traits;
   306     // Buffer default
   307     typedef boost::queue<typename Traits::vertex_descriptor> queue_t;
   308     queue_t Q;
   309     detail::wrap_ref<queue_t> Qref(Q);
   310 
   311     detail::neighbor_bfs_impl
   312       (g, s,
   313        choose_param(get_param(params, buffer_param_t()), Qref).ref,
   314        choose_param(get_param(params, graph_visitor),
   315                     make_neighbor_bfs_visitor(null_visitor())),
   316        choose_pmap(get_param(params, vertex_color), g, vertex_color)
   317        );
   318   }
   319 
   320 } // namespace boost
   321 
   322 #endif // BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP
   323