epoc32/include/stdapis/boost/graph/undirected_dfs.hpp
author William Roberts <williamr@symbian.org>
Tue, 16 Mar 2010 16:12:26 +0000
branchSymbian2
changeset 2 2fe1408b6811
permissions -rw-r--r--
Final list of Symbian^2 public API header files
     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_UNDIRECTED_DFS_HPP
    12 #define BOOST_GRAPH_UNDIRECTED_DFS_HPP
    13 
    14 #include <boost/graph/depth_first_search.hpp>
    15 #include <vector>
    16 
    17 namespace boost {
    18 
    19   namespace detail {
    20 
    21 // Define BOOST_RECURSIVE_DFS to use older, recursive version.
    22 // It is retained for a while in order to perform performance
    23 // comparison.
    24 #ifndef BOOST_RECURSIVE_DFS
    25 
    26     template <typename IncidenceGraph, typename DFSVisitor, 
    27               typename VertexColorMap, typename EdgeColorMap>
    28     void undir_dfv_impl
    29       (const IncidenceGraph& g,
    30        typename graph_traits<IncidenceGraph>::vertex_descriptor u, 
    31        DFSVisitor& vis,
    32        VertexColorMap vertex_color,
    33        EdgeColorMap edge_color)
    34     {
    35       function_requires<IncidenceGraphConcept<IncidenceGraph> >();
    36       function_requires<DFSVisitorConcept<DFSVisitor, IncidenceGraph> >();
    37       typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
    38       typedef typename graph_traits<IncidenceGraph>::edge_descriptor Edge;
    39       function_requires<ReadWritePropertyMapConcept<VertexColorMap,Vertex> >();
    40       function_requires<ReadWritePropertyMapConcept<EdgeColorMap,Edge> >();
    41       typedef typename property_traits<VertexColorMap>::value_type ColorValue;
    42       typedef typename property_traits<EdgeColorMap>::value_type EColorValue;
    43       function_requires< ColorValueConcept<ColorValue> >();
    44       function_requires< ColorValueConcept<EColorValue> >();
    45       typedef color_traits<ColorValue> Color;
    46       typedef color_traits<EColorValue> EColor;
    47       typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter;
    48       typedef std::pair<Vertex, std::pair<Iter, Iter> > VertexInfo;
    49 
    50       std::vector<VertexInfo> stack;
    51 
    52       put(vertex_color, u, Color::gray());
    53       vis.discover_vertex(u, g);
    54       stack.push_back(std::make_pair(u, out_edges(u, g)));
    55       while (!stack.empty()) {
    56         VertexInfo& back = stack.back();
    57         u = back.first;
    58         Iter ei, ei_end;
    59         tie(ei, ei_end) = back.second;
    60         stack.pop_back();
    61         while (ei != ei_end) {
    62           Vertex v = target(*ei, g);
    63           vis.examine_edge(*ei, g);
    64           ColorValue v_color = get(vertex_color, v);
    65           EColorValue uv_color = get(edge_color, *ei);
    66           put(edge_color, *ei, EColor::black());
    67           if (v_color == Color::white()) {
    68             vis.tree_edge(*ei, g);
    69             stack.push_back(std::make_pair(u, std::make_pair(++ei, ei_end)));
    70             u = v;
    71             put(vertex_color, u, Color::gray());
    72             vis.discover_vertex(u, g);
    73             tie(ei, ei_end) = out_edges(u, g);
    74           } else if (v_color == Color::gray()) {
    75             if (uv_color == EColor::white()) vis.back_edge(*ei, g);
    76             ++ei;
    77           } else { // if (v_color == Color::black())
    78             ++ei;
    79           }
    80         }
    81         put(vertex_color, u, Color::black());
    82         vis.finish_vertex(u, g);
    83       }
    84     }
    85 
    86 #else // BOOST_RECURSIVE_DFS
    87 
    88     template <typename IncidenceGraph, typename DFSVisitor, 
    89               typename VertexColorMap, typename EdgeColorMap>
    90     void undir_dfv_impl
    91       (const IncidenceGraph& g,
    92        typename graph_traits<IncidenceGraph>::vertex_descriptor u, 
    93        DFSVisitor& vis,  // pass-by-reference here, important!
    94        VertexColorMap vertex_color,
    95        EdgeColorMap edge_color)
    96     {
    97       function_requires<IncidenceGraphConcept<IncidenceGraph> >();
    98       function_requires<DFSVisitorConcept<DFSVisitor, IncidenceGraph> >();
    99       typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
   100       typedef typename graph_traits<IncidenceGraph>::edge_descriptor Edge;
   101       function_requires<ReadWritePropertyMapConcept<VertexColorMap,Vertex> >();
   102       function_requires<ReadWritePropertyMapConcept<EdgeColorMap,Edge> >();
   103       typedef typename property_traits<VertexColorMap>::value_type ColorValue;
   104       typedef typename property_traits<EdgeColorMap>::value_type EColorValue;
   105       function_requires< ColorValueConcept<ColorValue> >();
   106       function_requires< ColorValueConcept<EColorValue> >();
   107       typedef color_traits<ColorValue> Color;
   108       typedef color_traits<EColorValue> EColor;
   109       typename graph_traits<IncidenceGraph>::out_edge_iterator ei, ei_end;
   110 
   111       put(vertex_color, u, Color::gray());   vis.discover_vertex(u, g);
   112       for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
   113         Vertex v = target(*ei, g);           vis.examine_edge(*ei, g);
   114         ColorValue v_color = get(vertex_color, v);
   115         EColorValue uv_color = get(edge_color, *ei);
   116         put(edge_color, *ei, EColor::black());
   117         if (v_color == Color::white()) {     vis.tree_edge(*ei, g);
   118           undir_dfv_impl(g, v, vis, vertex_color, edge_color);
   119         } else if (v_color == Color::gray() && uv_color == EColor::white())
   120                                              vis.back_edge(*ei, g);
   121       }
   122       put(vertex_color, u, Color::black());  vis.finish_vertex(u, g);
   123     }
   124 
   125 #endif // ! BOOST_RECURSIVE_DFS
   126 
   127   } // namespace detail
   128 
   129   template <typename Graph, typename DFSVisitor, 
   130             typename VertexColorMap, typename EdgeColorMap, 
   131             typename Vertex>
   132   void
   133   undirected_dfs(const Graph& g, DFSVisitor vis, 
   134                  VertexColorMap vertex_color, EdgeColorMap edge_color,
   135                  Vertex start_vertex)
   136   {
   137     function_requires<DFSVisitorConcept<DFSVisitor, Graph> >();
   138       function_requires<EdgeListGraphConcept<Graph> >();
   139 
   140     typedef typename property_traits<VertexColorMap>::value_type ColorValue;
   141     typedef color_traits<ColorValue> Color;
   142 
   143     typename graph_traits<Graph>::vertex_iterator ui, ui_end;
   144     for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
   145       put(vertex_color, *ui, Color::white());   vis.initialize_vertex(*ui, g);
   146     }
   147     typename graph_traits<Graph>::edge_iterator ei, ei_end;
   148     for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
   149       put(edge_color, *ei, Color::white());
   150 
   151     if (start_vertex != *vertices(g).first){ vis.start_vertex(start_vertex, g);
   152       detail::undir_dfv_impl(g, start_vertex, vis, vertex_color, edge_color);
   153     }
   154 
   155     for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
   156       ColorValue u_color = get(vertex_color, *ui);
   157       if (u_color == Color::white()) {       vis.start_vertex(*ui, g);
   158         detail::undir_dfv_impl(g, *ui, vis, vertex_color, edge_color);
   159       }
   160     }
   161   }
   162 
   163   template <typename Graph, typename DFSVisitor, typename VertexColorMap,
   164     typename EdgeColorMap>
   165   void
   166   undirected_dfs(const Graph& g, DFSVisitor vis, 
   167                  VertexColorMap vertex_color, EdgeColorMap edge_color)
   168   {
   169     undirected_dfs(g, vis, vertex_color, edge_color, *vertices(g).first);
   170   }
   171 
   172   namespace detail {
   173     template <typename VertexColorMap>
   174     struct udfs_dispatch {
   175 
   176       template <typename Graph, typename Vertex, 
   177                 typename DFSVisitor, typename EdgeColorMap,
   178                 typename P, typename T, typename R>
   179       static void
   180       apply(const Graph& g, DFSVisitor vis, Vertex start_vertex,
   181             const bgl_named_params<P, T, R>&,
   182             EdgeColorMap edge_color,
   183             VertexColorMap vertex_color)
   184       {
   185         undirected_dfs(g, vis, vertex_color, edge_color, start_vertex);
   186       }
   187     };
   188 
   189     template <>
   190     struct udfs_dispatch<detail::error_property_not_found> {
   191       template <typename Graph, typename Vertex, typename DFSVisitor,
   192                 typename EdgeColorMap,
   193                 typename P, typename T, typename R>
   194       static void
   195       apply(const Graph& g, DFSVisitor vis, Vertex start_vertex,
   196             const bgl_named_params<P, T, R>& params,
   197             EdgeColorMap edge_color,
   198             detail::error_property_not_found)
   199       {
   200         std::vector<default_color_type> color_vec(num_vertices(g));
   201         default_color_type c = white_color; // avoid warning about un-init
   202         undirected_dfs
   203           (g, vis, make_iterator_property_map
   204            (color_vec.begin(),
   205             choose_const_pmap(get_param(params, vertex_index),
   206                               g, vertex_index), c),
   207            edge_color,
   208            start_vertex);
   209       }
   210     };
   211 
   212   } // namespace detail
   213   
   214 
   215   // Named Parameter Variant
   216   template <typename Graph, typename P, typename T, typename R>
   217   void
   218   undirected_dfs(const Graph& g, 
   219                  const bgl_named_params<P, T, R>& params)
   220   {
   221     typedef typename property_value< bgl_named_params<P, T, R>, 
   222       vertex_color_t>::type C;
   223     detail::udfs_dispatch<C>::apply
   224       (g,
   225        choose_param(get_param(params, graph_visitor),
   226                     make_dfs_visitor(null_visitor())),
   227        choose_param(get_param(params, root_vertex_t()),
   228                     *vertices(g).first),
   229        params,
   230        get_param(params, edge_color),
   231        get_param(params, vertex_color)
   232        );
   233   }
   234   
   235 
   236   template <typename IncidenceGraph, typename DFSVisitor, 
   237     typename VertexColorMap, typename EdgeColorMap>
   238   void undirected_depth_first_visit
   239     (const IncidenceGraph& g,
   240      typename graph_traits<IncidenceGraph>::vertex_descriptor u, 
   241      DFSVisitor vis, VertexColorMap vertex_color, EdgeColorMap edge_color)
   242   {
   243     detail::undir_dfv_impl(g, u, vis, vertex_color, edge_color);
   244   }
   245 
   246 
   247 } // namespace boost
   248 
   249 
   250 #endif