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