boost/graph/depth_first_search.hpp

0001 //=======================================================================
0002 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0003 // Copyright 2003 Bruce Barr
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010
0011 // Nonrecursive implementation of depth_first_visit_impl submitted by
0012 // Bruce Barr, schmoost <at> yahoo.com, May/June 2003.
0013 #ifndef BOOST_GRAPH_RECURSIVE_DFS_HPP
0014 #define BOOST_GRAPH_RECURSIVE_DFS_HPP
0015
0016 #include <boost/config.hpp>
0017 #include <boost/graph/graph_traits.hpp>
0018 #include <boost/graph/graph_concepts.hpp>
0019 #include <boost/graph/properties.hpp>
0020 #include <boost/graph/visitors.hpp>
0021 #include <boost/graph/named_function_params.hpp>
0022 #include <boost/graph/detail/mpi_include.hpp>
0023 #include <boost/ref.hpp>
0024 #include <boost/implicit_cast.hpp>
0025 #include <boost/optional.hpp>
0026 #include <boost/parameter.hpp>
0027 #include <boost/concept/assert.hpp>
0028 #include <boost/tti/has_member_function.hpp>
0029
0030 #include <vector>
0031 #include <utility>
0032
0033 namespace boost
0034 {
0035
0036 template < class Visitor, class Graph > class DFSVisitorConcept
0037 {
0038 public:
0039     void constraints()
0040     {
0041         BOOST_CONCEPT_ASSERT((CopyConstructibleConcept< Visitor >));
0042         vis.initialize_vertex(u, g);
0043         vis.start_vertex(u, g);
0044         vis.discover_vertex(u, g);
0045         vis.examine_edge(e, g);
0046         vis.tree_edge(e, g);
0047         vis.back_edge(e, g);
0048         vis.forward_or_cross_edge(e, g);
0049         // vis.finish_edge(e, g); // Optional for user
0050         vis.finish_vertex(u, g);
0051     }
0052
0053 private:
0054     Visitor vis;
0055     Graph g;
0056     typename graph_traits< Graph >::vertex_descriptor u;
0057     typename graph_traits< Graph >::edge_descriptor e;
0058 };
0059
0060 namespace detail
0061 {
0062
0063     struct nontruth2
0064     {
0065         template < class T, class T2 >
0066         bool operator()(const T&, const T2&) const
0067         {
0068             return false;
0069         }
0070     };
0071
0072     BOOST_TTI_HAS_MEMBER_FUNCTION(finish_edge)
0073
0074     template < bool IsCallable > struct do_call_finish_edge
0075     {
0076         template < typename E, typename G, typename Vis >
0077         static void call_finish_edge(Vis& vis, E e, const G& g)
0078         {
0079             vis.finish_edge(e, g);
0080         }
0081     };
0082
0083     template <> struct do_call_finish_edge< false >
0084     {
0085         template < typename E, typename G, typename Vis >
0086         static void call_finish_edge(Vis&, E, const G&)
0087         {
0088         }
0089     };
0090
0091     template < typename E, typename G, typename Vis >
0092     void call_finish_edge(Vis& vis, E e, const G& g)
0093     { // Only call if method exists
0094 #if ((defined(__GNUC__) && (__GNUC__ > 4)               \
0095          || ((__GNUC__ == 4) && (__GNUC_MINOR__ >= 9))) \
0096     || defined(__clang__)                               \
0097     || (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 1200)))
0098         do_call_finish_edge< has_member_function_finish_edge< Vis, void,
0099             boost::mpl::vector< E, const G& > >::value >::call_finish_edge(vis,
0100             e, g);
0101 #else
0102         do_call_finish_edge< has_member_function_finish_edge< Vis,
0103             void >::value >::call_finish_edge(vis, e, g);
0104 #endif
0105     }
0106
0107 // Define BOOST_RECURSIVE_DFS to use older, recursive version.
0108 // It is retained for a while in order to perform performance
0109 // comparison.
0110 #ifndef BOOST_RECURSIVE_DFS
0111
0112     // If the vertex u and the iterators ei and ei_end are thought of as the
0113     // context of the algorithm, each push and pop from the stack could
0114     // be thought of as a context shift.
0115     // Each pass through "while (ei != ei_end)" may refer to the out-edges of
0116     // an entirely different vertex, because the context of the algorithm
0117     // shifts every time a white adjacent vertex is discovered.
0118     // The corresponding context shift back from the adjacent vertex occurs
0119     // after all of its out-edges have been examined.
0120     //
0121     // See https://lists.boost.org/Archives/boost/2003/06/49265.php for FAQ.
0122
0123     template < class IncidenceGraph, class DFSVisitor, class ColorMap,
0124         class TerminatorFunc >
0125     void depth_first_visit_impl(const IncidenceGraph& g,
0126         typename graph_traits< IncidenceGraph >::vertex_descriptor u,
0127         DFSVisitor& vis, ColorMap color, TerminatorFunc func = TerminatorFunc())
0128     {
0129         BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< IncidenceGraph >));
0130         BOOST_CONCEPT_ASSERT((DFSVisitorConcept< DFSVisitor, IncidenceGraph >));
0131         typedef
0132             typename graph_traits< IncidenceGraph >::vertex_descriptor Vertex;
0133         typedef typename graph_traits< IncidenceGraph >::edge_descriptor Edge;
0134         BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< ColorMap, Vertex >));
0135         typedef typename property_traits< ColorMap >::value_type ColorValue;
0136         BOOST_CONCEPT_ASSERT((ColorValueConcept< ColorValue >));
0137         typedef color_traits< ColorValue > Color;
0138         typedef typename graph_traits< IncidenceGraph >::out_edge_iterator Iter;
0139         typedef std::pair< Vertex,
0140             std::pair< boost::optional< Edge >, std::pair< Iter, Iter > > >
0141             VertexInfo;
0142
0143         boost::optional< Edge > src_e;
0144         Iter ei, ei_end;
0145         std::vector< VertexInfo > stack;
0146
0147         // Possible optimization for vector
0148         // stack.reserve(num_vertices(g));
0149
0150         put(color, u, Color::gray());
0151         vis.discover_vertex(u, g);
0152         boost::tie(ei, ei_end) = out_edges(u, g);
0153         if (func(u, g))
0154         {
0155             // If this vertex terminates the search, we push empty range
0156             stack.push_back(std::make_pair(u,
0157                 std::make_pair(boost::optional< Edge >(),
0158                     std::make_pair(ei_end, ei_end))));
0159         }
0160         else
0161         {
0162             stack.push_back(std::make_pair(u,
0163                 std::make_pair(
0164                     boost::optional< Edge >(), std::make_pair(ei, ei_end))));
0165         }
0166         while (!stack.empty())
0167         {
0168             VertexInfo& back = stack.back();
0169             u = back.first;
0170             src_e = back.second.first;
0171             boost::tie(ei, ei_end) = back.second.second;
0172             stack.pop_back();
0173             // finish_edge has to be called here, not after the
0174             // loop. Think of the pop as the return from a recursive call.
0175             if (src_e)
0176             {
0177                 call_finish_edge(vis, src_e.get(), g);
0178             }
0179             while (ei != ei_end)
0180             {
0181                 Vertex v = target(*ei, g);
0182                 vis.examine_edge(*ei, g);
0183                 ColorValue v_color = get(color, v);
0184                 if (v_color == Color::white())
0185                 {
0186                     vis.tree_edge(*ei, g);
0187                     src_e = *ei;
0188                     stack.push_back(std::make_pair(u,
0189                         std::make_pair(src_e, std::make_pair(++ei, ei_end))));
0190                     u = v;
0191                     put(color, u, Color::gray());
0192                     vis.discover_vertex(u, g);
0193                     boost::tie(ei, ei_end) = out_edges(u, g);
0194                     if (func(u, g))
0195                     {
0196                         ei = ei_end;
0197                     }
0198                 }
0199                 else
0200                 {
0201                     if (v_color == Color::gray())
0202                     {
0203                         vis.back_edge(*ei, g);
0204                     }
0205                     else
0206                     {
0207                         vis.forward_or_cross_edge(*ei, g);
0208                     }
0209                     call_finish_edge(vis, *ei, g);
0210                     ++ei;
0211                 }
0212             }
0213             put(color, u, Color::black());
0214             vis.finish_vertex(u, g);
0215         }
0216     }
0217
0218 #else // BOOST_RECURSIVE_DFS is defined
0219
0220     template < class IncidenceGraph, class DFSVisitor, class ColorMap,
0221         class TerminatorFunc >
0222     void depth_first_visit_impl(const IncidenceGraph& g,
0223         typename graph_traits< IncidenceGraph >::vertex_descriptor u,
0224         DFSVisitor& vis, // pass-by-reference here, important!
0225         ColorMap color, TerminatorFunc func)
0226     {
0227         BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< IncidenceGraph >));
0228         BOOST_CONCEPT_ASSERT((DFSVisitorConcept< DFSVisitor, IncidenceGraph >));
0229         typedef
0230             typename graph_traits< IncidenceGraph >::vertex_descriptor Vertex;
0231         BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< ColorMap, Vertex >));
0232         typedef typename property_traits< ColorMap >::value_type ColorValue;
0233         BOOST_CONCEPT_ASSERT((ColorValueConcept< ColorValue >));
0234         typedef color_traits< ColorValue > Color;
0235         typename graph_traits< IncidenceGraph >::out_edge_iterator ei, ei_end;
0236
0237         put(color, u, Color::gray());
0238         vis.discover_vertex(u, g);
0239
0240         if (!func(u, g))
0241             for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei)
0242             {
0243                 Vertex v = target(*ei, g);
0244                 vis.examine_edge(*ei, g);
0245                 ColorValue v_color = get(color, v);
0246                 if (v_color == Color::white())
0247                 {
0248                     vis.tree_edge(*ei, g);
0249                     depth_first_visit_impl(g, v, vis, color, func);
0250                 }
0251                 else if (v_color == Color::gray())
0252                     vis.back_edge(*ei, g);
0253                 else
0254                     vis.forward_or_cross_edge(*ei, g);
0255                 call_finish_edge(vis, *ei, g);
0256             }
0257         put(color, u, Color::black());
0258         vis.finish_vertex(u, g);
0259     }
0260
0261 #endif
0262
0263 } // namespace detail
0264
0265 template < class VertexListGraph, class DFSVisitor, class ColorMap >
0266 void depth_first_search(const VertexListGraph& g, DFSVisitor vis,
0267     ColorMap color,
0268     typename graph_traits< VertexListGraph >::vertex_descriptor start_vertex)
0269 {
0270     typedef typename graph_traits< VertexListGraph >::vertex_descriptor Vertex;
0271     BOOST_CONCEPT_ASSERT((DFSVisitorConcept< DFSVisitor, VertexListGraph >));
0272     typedef typename property_traits< ColorMap >::value_type ColorValue;
0273     typedef color_traits< ColorValue > Color;
0274
0275     typename graph_traits< VertexListGraph >::vertex_iterator ui, ui_end;
0276     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
0277     {
0278         Vertex u = implicit_cast< Vertex >(*ui);
0279         put(color, u, Color::white());
0280         vis.initialize_vertex(u, g);
0281     }
0282
0283     if (start_vertex != detail::get_default_starting_vertex(g))
0284     {
0285         vis.start_vertex(start_vertex, g);
0286         detail::depth_first_visit_impl(
0287             g, start_vertex, vis, color, detail::nontruth2());
0288     }
0289
0290     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
0291     {
0292         Vertex u = implicit_cast< Vertex >(*ui);
0293         ColorValue u_color = get(color, u);
0294         if (u_color == Color::white())
0295         {
0296             vis.start_vertex(u, g);
0297             detail::depth_first_visit_impl(
0298                 g, u, vis, color, detail::nontruth2());
0299         }
0300     }
0301 }
0302
0303 template < class VertexListGraph, class DFSVisitor, class ColorMap >
0304 void depth_first_search(
0305     const VertexListGraph& g, DFSVisitor vis, ColorMap color)
0306 {
0307     typedef typename boost::graph_traits< VertexListGraph >::vertex_iterator vi;
0308     std::pair< vi, vi > verts = vertices(g);
0309     if (verts.first == verts.second)
0310         return;
0311
0312     depth_first_search(g, vis, color, detail::get_default_starting_vertex(g));
0313 }
0314
0315 template < class Visitors = null_visitor > class dfs_visitor
0316 {
0317 public:
0318     dfs_visitor() {}
0319     dfs_visitor(Visitors vis) : m_vis(vis) {}
0320
0321     template < class Vertex, class Graph >
0322     void initialize_vertex(Vertex u, const Graph& g)
0323     {
0324         invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
0325     }
0326     template < class Vertex, class Graph >
0327     void start_vertex(Vertex u, const Graph& g)
0328     {
0329         invoke_visitors(m_vis, u, g, ::boost::on_start_vertex());
0330     }
0331     template < class Vertex, class Graph >
0332     void discover_vertex(Vertex u, const Graph& g)
0333     {
0334         invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex());
0335     }
0336     template < class Edge, class Graph >
0337     void examine_edge(Edge u, const Graph& g)
0338     {
0339         invoke_visitors(m_vis, u, g, ::boost::on_examine_edge());
0340     }
0341     template < class Edge, class Graph > void tree_edge(Edge u, const Graph& g)
0342     {
0343         invoke_visitors(m_vis, u, g, ::boost::on_tree_edge());
0344     }
0345     template < class Edge, class Graph > void back_edge(Edge u, const Graph& g)
0346     {
0347         invoke_visitors(m_vis, u, g, ::boost::on_back_edge());
0348     }
0349     template < class Edge, class Graph >
0350     void forward_or_cross_edge(Edge u, const Graph& g)
0351     {
0352         invoke_visitors(m_vis, u, g, ::boost::on_forward_or_cross_edge());
0353     }
0354     template < class Edge, class Graph >
0355     void finish_edge(Edge u, const Graph& g)
0356     {
0357         invoke_visitors(m_vis, u, g, ::boost::on_finish_edge());
0358     }
0359     template < class Vertex, class Graph >
0360     void finish_vertex(Vertex u, const Graph& g)
0361     {
0362         invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
0363     }
0364
0365     BOOST_GRAPH_EVENT_STUB(on_initialize_vertex, dfs)
0366     BOOST_GRAPH_EVENT_STUB(on_start_vertex, dfs)
0367     BOOST_GRAPH_EVENT_STUB(on_discover_vertex, dfs)
0368     BOOST_GRAPH_EVENT_STUB(on_examine_edge, dfs)
0369     BOOST_GRAPH_EVENT_STUB(on_tree_edge, dfs)
0370     BOOST_GRAPH_EVENT_STUB(on_back_edge, dfs)
0371     BOOST_GRAPH_EVENT_STUB(on_forward_or_cross_edge, dfs)
0372     BOOST_GRAPH_EVENT_STUB(on_finish_edge, dfs)
0373     BOOST_GRAPH_EVENT_STUB(on_finish_vertex, dfs)
0374
0375 protected:
0376     Visitors m_vis;
0377 };
0378 template < class Visitors >
0379 dfs_visitor< Visitors > make_dfs_visitor(Visitors vis)
0380 {
0381     return dfs_visitor< Visitors >(vis);
0382 }
0383 typedef dfs_visitor<> default_dfs_visitor;
0384
0385 // Boost.Parameter named parameter variant
0386 namespace graph
0387 {
0388     namespace detail
0389     {
0390         template < typename Graph > struct depth_first_search_impl
0391         {
0392             typedef void result_type;
0393             template < typename ArgPack >
0394             void operator()(const Graph& g, const ArgPack& arg_pack) const
0395             {
0396                 using namespace boost::graph::keywords;
0397                 boost::depth_first_search(g,
0398                     arg_pack[_visitor | make_dfs_visitor(null_visitor())],
0399                     boost::detail::make_color_map_from_arg_pack(g, arg_pack),
0400                     arg_pack[_root_vertex
0401                         || boost::detail::get_default_starting_vertex_t<
0402                             Graph >(g)]);
0403             }
0404         };
0405     }
0406     BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(depth_first_search, 1, 4)
0407 }
0408
0409 BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(depth_first_search, 1)
0410
0411 template < class IncidenceGraph, class DFSVisitor, class ColorMap >
0412 void depth_first_visit(const IncidenceGraph& g,
0413     typename graph_traits< IncidenceGraph >::vertex_descriptor u,
0414     DFSVisitor vis, ColorMap color)
0415 {
0416     vis.start_vertex(u, g);
0417     detail::depth_first_visit_impl(g, u, vis, color, detail::nontruth2());
0418 }
0419
0420 template < class IncidenceGraph, class DFSVisitor, class ColorMap,
0421     class TerminatorFunc >
0422 void depth_first_visit(const IncidenceGraph& g,
0423     typename graph_traits< IncidenceGraph >::vertex_descriptor u,
0424     DFSVisitor vis, ColorMap color, TerminatorFunc func = TerminatorFunc())
0425 {
0426     vis.start_vertex(u, g);
0427     detail::depth_first_visit_impl(g, u, vis, color, func);
0428 }
0429 } // namespace boost
0430
0431 #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/depth_first_search.hpp>)
0432
0433 #endif