ceph/src/boost/boost/graph/depth_first_search.hpp

   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 //=======================================================================
  10
  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
  15
  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>
  22 #include <boost/graph/detail/mpi_include.hpp>
  23 #include <boost/ref.hpp>
  24 #include <boost/implicit_cast.hpp>
  25 #include <boost/optional.hpp>
  26 #include <boost/parameter.hpp>
  27 #include <boost/concept/assert.hpp>
  28 #include <boost/tti/has_member_function.hpp>
  29
  30 #include <vector>
  31 #include <utility>
  32
  33 namespace boost {
  34
  35   template <class Visitor, class Graph>
  36   class DFSVisitorConcept {
  37   public:
  38     void constraints() {
  39       BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> ));
  40       vis.initialize_vertex(u, g);
  41       vis.start_vertex(u, g);
  42       vis.discover_vertex(u, g);
  43       vis.examine_edge(e, g);
  44       vis.tree_edge(e, g);
  45       vis.back_edge(e, g);
  46       vis.forward_or_cross_edge(e, g);
  47       // vis.finish_edge(e, g); // Optional for user
  48       vis.finish_vertex(u, g);
  49     }
  50   private:
  51     Visitor vis;
  52     Graph g;
  53     typename graph_traits<Graph>::vertex_descriptor u;
  54     typename graph_traits<Graph>::edge_descriptor e;
  55   };
  56
  57   namespace detail {
  58
  59     struct nontruth2 {
  60       template<class T, class T2>
  61       bool operator()(const T&, const T2&) const { return false; }
  62     };
  63
  64     BOOST_TTI_HAS_MEMBER_FUNCTION(finish_edge)
  65
  66     template <bool IsCallable> struct do_call_finish_edge {
  67       template <typename E, typename G, typename Vis>
  68       static void call_finish_edge(Vis& vis, E e, const G& g) {
  69         vis.finish_edge(e, g);
  70       }
  71     };
  72
  73     template <> struct do_call_finish_edge<false> {
  74       template <typename E, typename G, typename Vis>
  75       static void call_finish_edge(Vis&, E, const G&) {}
  76     };
  77
  78     template <typename E, typename G, typename Vis>
  79     void call_finish_edge(Vis& vis, E e, const G& g) { // Only call if method exists
  80 #if ((defined(__GNUC__) && (__GNUC__ > 4) || ((__GNUC__ == 4) && (__GNUC_MINOR__ >= 9))) || \
  81       defined(__clang__) || \
  82      (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 1200)))
  83       do_call_finish_edge<
  84         has_member_function_finish_edge<Vis, void,
  85           boost::mpl::vector<E, const G&> >::value>::call_finish_edge(vis, e, g);
  86 #else
  87       do_call_finish_edge<has_member_function_finish_edge<Vis, void>::value>::call_finish_edge(vis, e, g);
  88 #endif
  89     }
  90
  91
  92 // Define BOOST_RECURSIVE_DFS to use older, recursive version.
  93 // It is retained for a while in order to perform performance
  94 // comparison.
  95 #ifndef BOOST_RECURSIVE_DFS
  96
  97     // If the vertex u and the iterators ei and ei_end are thought of as the
  98     // context of the algorithm, each push and pop from the stack could
  99     // be thought of as a context shift.
 100     // Each pass through "while (ei != ei_end)" may refer to the out-edges of
 101     // an entirely different vertex, because the context of the algorithm
 102     // shifts every time a white adjacent vertex is discovered.
 103     // The corresponding context shift back from the adjacent vertex occurs
 104     // after all of its out-edges have been examined.
 105     //
 106     // See https://lists.boost.org/Archives/boost/2003/06/49265.php for FAQ.
 107
 108     template <class IncidenceGraph, class DFSVisitor, class ColorMap,
 109             class TerminatorFunc>
 110     void depth_first_visit_impl
 111       (const IncidenceGraph& g,
 112        typename graph_traits<IncidenceGraph>::vertex_descriptor u,
 113        DFSVisitor& vis,
 114        ColorMap color, TerminatorFunc func = TerminatorFunc())
 115     {
 116       BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> ));
 117       BOOST_CONCEPT_ASSERT(( DFSVisitorConcept<DFSVisitor, IncidenceGraph> ));
 118       typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
 119       typedef typename graph_traits<IncidenceGraph>::edge_descriptor Edge;
 120       BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<ColorMap, Vertex> ));
 121       typedef typename property_traits<ColorMap>::value_type ColorValue;
 122       BOOST_CONCEPT_ASSERT(( ColorValueConcept<ColorValue> ));
 123       typedef color_traits<ColorValue> Color;
 124       typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter;
 125       typedef std::pair<Vertex, std::pair<boost::optional<Edge>, std::pair<Iter, Iter> > > VertexInfo;
 126
 127       boost::optional<Edge> src_e;
 128       Iter ei, ei_end;
 129       std::vector<VertexInfo> stack;
 130
 131       // Possible optimization for vector
 132       //stack.reserve(num_vertices(g));
 133
 134       put(color, u, Color::gray());
 135       vis.discover_vertex(u, g);
 136       boost::tie(ei, ei_end) = out_edges(u, g);
 137       if (func(u, g)) {
 138           // If this vertex terminates the search, we push empty range
 139           stack.push_back(std::make_pair(u, std::make_pair(boost::optional<Edge>(), std::make_pair(ei_end, ei_end))));
 140       } else {
 141           stack.push_back(std::make_pair(u, std::make_pair(boost::optional<Edge>(), std::make_pair(ei, ei_end))));
 142       }
 143       while (!stack.empty()) {
 144         VertexInfo& back = stack.back();
 145         u = back.first;
 146         src_e = back.second.first;
 147         boost::tie(ei, ei_end) = back.second.second;
 148         stack.pop_back();
 149         // finish_edge has to be called here, not after the
 150         // loop. Think of the pop as the return from a recursive call.
 151         if (src_e) {
 152           call_finish_edge(vis, src_e.get(), g);
 153         }
 154         while (ei != ei_end) {
 155           Vertex v = target(*ei, g);
 156           vis.examine_edge(*ei, g);
 157           ColorValue v_color = get(color, v);
 158           if (v_color == Color::white()) {
 159             vis.tree_edge(*ei, g);
 160             src_e = *ei;
 161             stack.push_back(std::make_pair(u, std::make_pair(src_e, std::make_pair(++ei, ei_end))));
 162             u = v;
 163             put(color, u, Color::gray());
 164             vis.discover_vertex(u, g);
 165             boost::tie(ei, ei_end) = out_edges(u, g);
 166             if (func(u, g)) {
 167                 ei = ei_end;
 168             }
 169           } else {
 170             if (v_color == Color::gray()) {
 171               vis.back_edge(*ei, g);
 172             } else {
 173               vis.forward_or_cross_edge(*ei, g);
 174             }
 175             call_finish_edge(vis, *ei, g);
 176             ++ei;
 177           }
 178         }
 179         put(color, u, Color::black());
 180         vis.finish_vertex(u, g);
 181       }
 182     }
 183
 184 #else // BOOST_RECURSIVE_DFS is defined
 185
 186     template <class IncidenceGraph, class DFSVisitor, class ColorMap,
 187               class TerminatorFunc>
 188     void depth_first_visit_impl
 189       (const IncidenceGraph& g,
 190        typename graph_traits<IncidenceGraph>::vertex_descriptor u,
 191        DFSVisitor& vis,  // pass-by-reference here, important!
 192        ColorMap color, TerminatorFunc func)
 193     {
 194       BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> ));
 195       BOOST_CONCEPT_ASSERT(( DFSVisitorConcept<DFSVisitor, IncidenceGraph> ));
 196       typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
 197       BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<ColorMap, Vertex> ));
 198       typedef typename property_traits<ColorMap>::value_type ColorValue;
 199       BOOST_CONCEPT_ASSERT(( ColorValueConcept<ColorValue> ));
 200       typedef color_traits<ColorValue> Color;
 201       typename graph_traits<IncidenceGraph>::out_edge_iterator ei, ei_end;
 202
 203       put(color, u, Color::gray());          vis.discover_vertex(u, g);
 204
 205       if (!func(u, g))
 206         for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
 207           Vertex v = target(*ei, g);           vis.examine_edge(*ei, g);
 208           ColorValue v_color = get(color, v);
 209           if (v_color == Color::white()) {     vis.tree_edge(*ei, g);
 210           depth_first_visit_impl(g, v, vis, color, func);
 211           } else if (v_color == Color::gray()) vis.back_edge(*ei, g);
 212           else                                 vis.forward_or_cross_edge(*ei, g);
 213           call_finish_edge(vis, *ei, g);
 214         }
 215       put(color, u, Color::black());         vis.finish_vertex(u, g);
 216     }
 217
 218 #endif
 219
 220   } // namespace detail
 221
 222   template <class VertexListGraph, class DFSVisitor, class ColorMap>
 223   void
 224   depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color,
 225                      typename graph_traits<VertexListGraph>::vertex_descriptor start_vertex)
 226   {
 227     typedef typename graph_traits<VertexListGraph>::vertex_descriptor Vertex;
 228     BOOST_CONCEPT_ASSERT(( DFSVisitorConcept<DFSVisitor, VertexListGraph> ));
 229     typedef typename property_traits<ColorMap>::value_type ColorValue;
 230     typedef color_traits<ColorValue> Color;
 231
 232     typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
 233     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
 234       Vertex u = implicit_cast<Vertex>(*ui);
 235       put(color, u, Color::white()); vis.initialize_vertex(u, g);
 236     }
 237
 238     if (start_vertex != detail::get_default_starting_vertex(g)){ vis.start_vertex(start_vertex, g);
 239       detail::depth_first_visit_impl(g, start_vertex, vis, color,
 240                                      detail::nontruth2());
 241     }
 242
 243     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
 244       Vertex u = implicit_cast<Vertex>(*ui);
 245       ColorValue u_color = get(color, u);
 246       if (u_color == Color::white()) {       vis.start_vertex(u, g);
 247         detail::depth_first_visit_impl(g, u, vis, color, detail::nontruth2());
 248       }
 249     }
 250   }
 251
 252   template <class VertexListGraph, class DFSVisitor, class ColorMap>
 253   void
 254   depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color)
 255   {
 256     typedef typename boost::graph_traits<VertexListGraph>::vertex_iterator vi;
 257     std::pair<vi, vi> verts = vertices(g);
 258     if (verts.first == verts.second)
 259       return;
 260
 261     depth_first_search(g, vis, color, detail::get_default_starting_vertex(g));
 262   }
 263
 264   template <class Visitors = null_visitor>
 265   class dfs_visitor {
 266   public:
 267     dfs_visitor() { }
 268     dfs_visitor(Visitors vis) : m_vis(vis) { }
 269
 270     template <class Vertex, class Graph>
 271     void initialize_vertex(Vertex u, const Graph& g) {
 272       invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
 273     }
 274     template <class Vertex, class Graph>
 275     void start_vertex(Vertex u, const Graph& g) {
 276       invoke_visitors(m_vis, u, g, ::boost::on_start_vertex());
 277     }
 278     template <class Vertex, class Graph>
 279     void discover_vertex(Vertex u, const Graph& g) {
 280       invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex());
 281     }
 282     template <class Edge, class Graph>
 283     void examine_edge(Edge u, const Graph& g) {
 284       invoke_visitors(m_vis, u, g, ::boost::on_examine_edge());
 285     }
 286     template <class Edge, class Graph>
 287     void tree_edge(Edge u, const Graph& g) {
 288       invoke_visitors(m_vis, u, g, ::boost::on_tree_edge());
 289     }
 290     template <class Edge, class Graph>
 291     void back_edge(Edge u, const Graph& g) {
 292       invoke_visitors(m_vis, u, g, ::boost::on_back_edge());
 293     }
 294     template <class Edge, class Graph>
 295     void forward_or_cross_edge(Edge u, const Graph& g) {
 296       invoke_visitors(m_vis, u, g, ::boost::on_forward_or_cross_edge());
 297     }
 298     template <class Edge, class Graph>
 299     void finish_edge(Edge u, const Graph& g) {
 300       invoke_visitors(m_vis, u, g, ::boost::on_finish_edge());
 301     }
 302     template <class Vertex, class Graph>
 303     void finish_vertex(Vertex u, const Graph& g) {
 304       invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
 305     }
 306
 307     BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,dfs)
 308     BOOST_GRAPH_EVENT_STUB(on_start_vertex,dfs)
 309     BOOST_GRAPH_EVENT_STUB(on_discover_vertex,dfs)
 310     BOOST_GRAPH_EVENT_STUB(on_examine_edge,dfs)
 311     BOOST_GRAPH_EVENT_STUB(on_tree_edge,dfs)
 312     BOOST_GRAPH_EVENT_STUB(on_back_edge,dfs)
 313     BOOST_GRAPH_EVENT_STUB(on_forward_or_cross_edge,dfs)
 314     BOOST_GRAPH_EVENT_STUB(on_finish_edge,dfs)
 315     BOOST_GRAPH_EVENT_STUB(on_finish_vertex,dfs)
 316
 317   protected:
 318     Visitors m_vis;
 319   };
 320   template <class Visitors>
 321   dfs_visitor<Visitors>
 322   make_dfs_visitor(Visitors vis) {
 323     return dfs_visitor<Visitors>(vis);
 324   }
 325   typedef dfs_visitor<> default_dfs_visitor;
 326
 327   // Boost.Parameter named parameter variant
 328   namespace graph {
 329     namespace detail {
 330       template <typename Graph>
 331       struct depth_first_search_impl {
 332         typedef void result_type;
 333         template <typename ArgPack>
 334         void operator()(const Graph& g, const ArgPack& arg_pack) const {
 335           using namespace boost::graph::keywords;
 336           boost::depth_first_search(g,
 337                                     arg_pack[_visitor | make_dfs_visitor(null_visitor())],
 338                                     boost::detail::make_color_map_from_arg_pack(g, arg_pack),
 339                                     arg_pack[_root_vertex || boost::detail::get_default_starting_vertex_t<Graph>(g)]);
 340         }
 341       };
 342     }
 343     BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(depth_first_search, 1, 4)
 344   }
 345
 346   BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(depth_first_search, 1)
 347
 348   template <class IncidenceGraph, class DFSVisitor, class ColorMap>
 349   void depth_first_visit
 350     (const IncidenceGraph& g,
 351      typename graph_traits<IncidenceGraph>::vertex_descriptor u,
 352      DFSVisitor vis, ColorMap color)
 353   {
 354     vis.start_vertex(u, g);
 355     detail::depth_first_visit_impl(g, u, vis, color, detail::nontruth2());
 356   }
 357
 358   template <class IncidenceGraph, class DFSVisitor, class ColorMap,
 359             class TerminatorFunc>
 360   void depth_first_visit
 361     (const IncidenceGraph& g,
 362      typename graph_traits<IncidenceGraph>::vertex_descriptor u,
 363      DFSVisitor vis, ColorMap color, TerminatorFunc func = TerminatorFunc())
 364   {
 365     vis.start_vertex(u, g);
 366     detail::depth_first_visit_impl(g, u, vis, color, func);
 367   }
 368 } // namespace boost
 369
 370 #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/depth_first_search.hpp>)
 371
 372 #endif