test: epoc32/include/stdapis/boost/graph/neighbor

     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

    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>

    27 namespace boost {

    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   };

    54   template <class Visitors = null_visitor>

    55   class neighbor_bfs_visitor {

    56   public:

    57     neighbor_bfs_visitor(Visitors vis = Visitors()) : m_vis(vis) { }

    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   };

   119   template <class Visitors>

   120   neighbor_bfs_visitor<Visitors>

   121   make_neighbor_bfs_visitor(Visitors vis) {

   122     return neighbor_bfs_visitor<Visitors>(vis);

   123   }

   125   namespace detail {

   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)

   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;

   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);

   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

   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

   194         put(color, u, Color::black());

   195         vis.finish_vertex(u, g);

   196       } // while

   197     }

   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     }

   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.

   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     };

   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;

   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     };

   275   } // namespace detail

   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   }

   297   // This version does not initialize colors, user has to.

   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);

   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   }

   320 } // namespace boost

   322 #endif // BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP

author	William Roberts <williamr@symbian.org>
	Wed, 31 Mar 2010 12:33:34 +0100
branch	Symbian3
changeset 4	837f303aceeb
permissions	-rw-r--r--