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

     1 //=======================================================================

     2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

     3 // Copyright 2003 Bruce Barr

     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 //=======================================================================

    11 // Nonrecursive implementation of depth_first_visit_impl submitted by

    12 // Bruce Barr, schmoost <at> yahoo.com, May/June 2003.

    13 #ifndef BOOST_GRAPH_RECURSIVE_DFS_HPP

    14 #define BOOST_GRAPH_RECURSIVE_DFS_HPP

    16 #include <boost/config.hpp>

    17 #include <boost/graph/graph_traits.hpp>

    18 #include <boost/graph/graph_concepts.hpp>

    19 #include <boost/graph/properties.hpp>

    20 #include <boost/graph/visitors.hpp>

    21 #include <boost/graph/named_function_params.hpp>

    23 #include <boost/ref.hpp>

    24 #include <boost/implicit_cast.hpp>

    26 #include <vector>

    27 #include <utility>

    29 namespace boost {

    31   template <class Visitor, class Graph>

    32   class DFSVisitorConcept {

    33   public:

    34     void constraints() {

    35       function_requires< CopyConstructibleConcept<Visitor> >();

    36       vis.initialize_vertex(u, g);

    37       vis.start_vertex(u, g);

    38       vis.discover_vertex(u, g);

    39       vis.examine_edge(e, g);

    40       vis.tree_edge(e, g);

    41       vis.back_edge(e, g);

    42       vis.forward_or_cross_edge(e, g);

    43       vis.finish_vertex(u, g);

    44     }

    45   private:

    46     Visitor vis;

    47     Graph g;

    48     typename graph_traits<Graph>::vertex_descriptor u;

    49     typename graph_traits<Graph>::edge_descriptor e;

    50   };

    52   namespace detail {

    54     struct nontruth2 {

    55       template<class T, class T2>

    56       bool operator()(const T&, const T2&) const { return false; }

    57     };

    60 // Define BOOST_RECURSIVE_DFS to use older, recursive version.

    61 // It is retained for a while in order to perform performance

    62 // comparison.

    63 #ifndef BOOST_RECURSIVE_DFS

    65     // If the vertex u and the iterators ei and ei_end are thought of as the

    66     // context of the algorithm, each push and pop from the stack could

    67     // be thought of as a context shift.

    68     // Each pass through "while (ei != ei_end)" may refer to the out-edges of

    69     // an entirely different vertex, because the context of the algorithm

    70     // shifts every time a white adjacent vertex is discovered.

    71     // The corresponding context shift back from the adjacent vertex occurs

    72     // after all of its out-edges have been examined.

    73     //

    74     // See http://lists.boost.org/MailArchives/boost/msg48752.php for FAQ.

    76     template <class IncidenceGraph, class DFSVisitor, class ColorMap,

    77             class TerminatorFunc>

    78     void depth_first_visit_impl

    79       (const IncidenceGraph& g,

    80        typename graph_traits<IncidenceGraph>::vertex_descriptor u,

    81        DFSVisitor& vis,

    82        ColorMap color, TerminatorFunc func = TerminatorFunc())

    83     {

    84       function_requires<IncidenceGraphConcept<IncidenceGraph> >();

    85       function_requires<DFSVisitorConcept<DFSVisitor, IncidenceGraph> >();

    86       typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;

    87       function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >();

    88       typedef typename property_traits<ColorMap>::value_type ColorValue;

    89       function_requires< ColorValueConcept<ColorValue> >();

    90       typedef color_traits<ColorValue> Color;

    91       typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter;

    92       typedef std::pair<Vertex, std::pair<Iter, Iter> > VertexInfo;

    94       Iter ei, ei_end;

    95       std::vector<VertexInfo> stack;

    97       // Possible optimization for vector

    98       //stack.reserve(num_vertices(g));

   100       typedef typename unwrap_reference<TerminatorFunc>::type TF;

   102       put(color, u, Color::gray());

   103       vis.discover_vertex(u, g);

   104       tie(ei, ei_end) = out_edges(u, g);

   105       // Variable is needed to workaround a borland bug.

   106       TF& fn = static_cast<TF&>(func);

   107       if (fn(u, g)) {

   108           // If this vertex terminates the search, we push empty range

   109           stack.push_back(std::make_pair(u, std::make_pair(ei_end, ei_end)));

   110       } else {

   111           stack.push_back(std::make_pair(u, std::make_pair(ei, ei_end)));

   112       }

   113       while (!stack.empty()) {

   114         VertexInfo& back = stack.back();

   115         u = back.first;

   116         tie(ei, ei_end) = back.second;

   117         stack.pop_back();

   118         while (ei != ei_end) {

   119           Vertex v = target(*ei, g);

   120           vis.examine_edge(*ei, g);

   121           ColorValue v_color = get(color, v);

   122           if (v_color == Color::white()) {

   123             vis.tree_edge(*ei, g);

   124             stack.push_back(std::make_pair(u, std::make_pair(++ei, ei_end)));

   125             u = v;

   126             put(color, u, Color::gray());

   127             vis.discover_vertex(u, g);

   128             tie(ei, ei_end) = out_edges(u, g);

   129             if (fn(u, g)) {

   130                 ei = ei_end;

   131             }

   132           } else if (v_color == Color::gray()) {

   133             vis.back_edge(*ei, g);

   134             ++ei;

   135           } else {

   136             vis.forward_or_cross_edge(*ei, g);

   137             ++ei;

   138           }

   139         }

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

   141         vis.finish_vertex(u, g);

   142       }

   143     }

   145 #else // BOOST_RECURSIVE_DFS is defined

   147     template <class IncidenceGraph, class DFSVisitor, class ColorMap,

   148               class TerminatorFunc>

   149     void depth_first_visit_impl

   150       (const IncidenceGraph& g,

   151        typename graph_traits<IncidenceGraph>::vertex_descriptor u,

   152        DFSVisitor& vis,  // pass-by-reference here, important!

   153        ColorMap color, TerminatorFunc func)

   154     {

   155       function_requires<IncidenceGraphConcept<IncidenceGraph> >();

   156       function_requires<DFSVisitorConcept<DFSVisitor, IncidenceGraph> >();

   157       typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;

   158       function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >();

   159       typedef typename property_traits<ColorMap>::value_type ColorValue;

   160       function_requires< ColorValueConcept<ColorValue> >();

   161       typedef color_traits<ColorValue> Color;

   162       typename graph_traits<IncidenceGraph>::out_edge_iterator ei, ei_end;

   164       put(color, u, Color::gray());          vis.discover_vertex(u, g);

   166       typedef typename unwrap_reference<TerminatorFunc>::type TF;

   167       // Variable is needed to workaround a borland bug.

   168       TF& fn = static_cast<TF&>(func);

   169       if (!fn(u, g))

   170         for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {

   171           Vertex v = target(*ei, g);           vis.examine_edge(*ei, g);

   172           ColorValue v_color = get(color, v);

   173           if (v_color == Color::white()) {     vis.tree_edge(*ei, g);

   174           depth_first_visit_impl(g, v, vis, color, func);

   175           } else if (v_color == Color::gray()) vis.back_edge(*ei, g);

   176           else                                 vis.forward_or_cross_edge(*ei, g);

   177         }

   178       put(color, u, Color::black());         vis.finish_vertex(u, g);

   179     }

   181 #endif

   183   } // namespace detail

   185   template <class VertexListGraph, class DFSVisitor, class ColorMap>

   186   void

   187   depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color,

   188                      typename graph_traits<VertexListGraph>::vertex_descriptor start_vertex)

   189   {

   190     typedef typename graph_traits<VertexListGraph>::vertex_descriptor Vertex;

   191     function_requires<DFSVisitorConcept<DFSVisitor, VertexListGraph> >();

   192     typedef typename property_traits<ColorMap>::value_type ColorValue;

   193     typedef color_traits<ColorValue> Color;

   195     typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;

   196     for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {

   197       put(color, *ui, Color::white());       vis.initialize_vertex(*ui, g);

   198     }

   200     if (start_vertex != implicit_cast<Vertex>(*vertices(g).first)){ vis.start_vertex(start_vertex, g);

   201       detail::depth_first_visit_impl(g, start_vertex, vis, color,

   202                                      detail::nontruth2());

   203     }

   205     for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {

   206       ColorValue u_color = get(color, *ui);

   207       if (u_color == Color::white()) {       vis.start_vertex(*ui, g);

   208         detail::depth_first_visit_impl(g, *ui, vis, color, detail::nontruth2());

   209       }

   210     }

   211   }

   213   template <class VertexListGraph, class DFSVisitor, class ColorMap>

   214   void

   215   depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color)

   216   {

   217     if (vertices(g).first == vertices(g).second)

   218       return;

   220     depth_first_search(g, vis, color, *vertices(g).first);

   221   }

   223   namespace detail {

   224     template <class ColorMap>

   225     struct dfs_dispatch {

   227       template <class VertexListGraph, class Vertex, class DFSVisitor,

   228                 class P, class T, class R>

   229       static void

   230       apply(const VertexListGraph& g, DFSVisitor vis, Vertex start_vertex,

   231             const bgl_named_params<P, T, R>&,

   232             ColorMap color)

   233       {

   234         depth_first_search(g, vis, color, start_vertex);

   235       }

   236     };

   238     template <>

   239     struct dfs_dispatch<detail::error_property_not_found> {

   240       template <class VertexListGraph, class Vertex, class DFSVisitor,

   241                 class P, class T, class R>

   242       static void

   243       apply(const VertexListGraph& g, DFSVisitor vis, Vertex start_vertex,

   244             const bgl_named_params<P, T, R>& params,

   245             detail::error_property_not_found)

   246       {

   247         std::vector<default_color_type> color_vec(num_vertices(g));

   248         default_color_type c = white_color; // avoid warning about un-init

   249         depth_first_search

   250           (g, vis, make_iterator_property_map

   251            (color_vec.begin(),

   252             choose_const_pmap(get_param(params, vertex_index),

   253                               g, vertex_index), c),

   254            start_vertex);

   255       }

   256     };

   257   } // namespace detail

   260   template <class Visitors = null_visitor>

   261   class dfs_visitor {

   262   public:

   263     dfs_visitor() { }

   264     dfs_visitor(Visitors vis) : m_vis(vis) { }

   266     template <class Vertex, class Graph>

   267     void initialize_vertex(Vertex u, const Graph& g) {

   268       invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());

   269     }

   270     template <class Vertex, class Graph>

   271     void start_vertex(Vertex u, const Graph& g) {

   272       invoke_visitors(m_vis, u, g, ::boost::on_start_vertex());

   273     }

   274     template <class Vertex, class Graph>

   275     void discover_vertex(Vertex u, const Graph& g) {

   276       invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex());

   277     }

   278     template <class Edge, class Graph>

   279     void examine_edge(Edge u, const Graph& g) {

   280       invoke_visitors(m_vis, u, g, ::boost::on_examine_edge());

   281     }

   282     template <class Edge, class Graph>

   283     void tree_edge(Edge u, const Graph& g) {

   284       invoke_visitors(m_vis, u, g, ::boost::on_tree_edge());

   285     }

   286     template <class Edge, class Graph>

   287     void back_edge(Edge u, const Graph& g) {

   288       invoke_visitors(m_vis, u, g, ::boost::on_back_edge());

   289     }

   290     template <class Edge, class Graph>

   291     void forward_or_cross_edge(Edge u, const Graph& g) {

   292       invoke_visitors(m_vis, u, g, ::boost::on_forward_or_cross_edge());

   293     }

   294     template <class Vertex, class Graph>

   295     void finish_vertex(Vertex u, const Graph& g) {

   296       invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());

   297     }

   299     BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,dfs)

   300     BOOST_GRAPH_EVENT_STUB(on_start_vertex,dfs)

   301     BOOST_GRAPH_EVENT_STUB(on_discover_vertex,dfs)

   302     BOOST_GRAPH_EVENT_STUB(on_examine_edge,dfs)

   303     BOOST_GRAPH_EVENT_STUB(on_tree_edge,dfs)

   304     BOOST_GRAPH_EVENT_STUB(on_back_edge,dfs)

   305     BOOST_GRAPH_EVENT_STUB(on_forward_or_cross_edge,dfs)

   306     BOOST_GRAPH_EVENT_STUB(on_finish_vertex,dfs)

   308   protected:

   309     Visitors m_vis;

   310   };

   311   template <class Visitors>

   312   dfs_visitor<Visitors>

   313   make_dfs_visitor(Visitors vis) {

   314     return dfs_visitor<Visitors>(vis);

   315   }

   316   typedef dfs_visitor<> default_dfs_visitor;

   319   // Named Parameter Variant

   320   template <class VertexListGraph, class P, class T, class R>

   321   void

   322   depth_first_search(const VertexListGraph& g,

   323                      const bgl_named_params<P, T, R>& params)

   324   {

   325     typedef typename property_value< bgl_named_params<P, T, R>,

   326       vertex_color_t>::type C;

   327     if (vertices(g).first == vertices(g).second)

   328       return;

   329     detail::dfs_dispatch<C>::apply

   330       (g,

   331        choose_param(get_param(params, graph_visitor),

   332                     make_dfs_visitor(null_visitor())),

   333        choose_param(get_param(params, root_vertex_t()),

   334                     *vertices(g).first),

   335        params,

   336        get_param(params, vertex_color)

   337        );

   338   }

   340   template <class IncidenceGraph, class DFSVisitor, class ColorMap>

   341   void depth_first_visit

   342     (const IncidenceGraph& g,

   343      typename graph_traits<IncidenceGraph>::vertex_descriptor u,

   344      DFSVisitor vis, ColorMap color)

   345   {

   346     vis.start_vertex(u, g);

   347     detail::depth_first_visit_impl(g, u, vis, color, detail::nontruth2());

   348   }

   350   template <class IncidenceGraph, class DFSVisitor, class ColorMap,

   351             class TerminatorFunc>

   352   void depth_first_visit

   353     (const IncidenceGraph& g,

   354      typename graph_traits<IncidenceGraph>::vertex_descriptor u,

   355      DFSVisitor vis, ColorMap color, TerminatorFunc func = TerminatorFunc())

   356   {

   357     vis.start_vertex(u, g);

   358     detail::depth_first_visit_impl(g, u, vis, color, func);

   359   }

   362 } // namespace boost

   365 #endif

author	William Roberts <williamr@symbian.org>
	Tue, 16 Mar 2010 16:12:26 +0000
branch	Symbian2
changeset 2	2fe1408b6811
permissions	-rw-r--r--