ceph/src/boost/boost/graph/undirected_dfs.hpp

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