http://www.ousob.com --- Legacy Redefined OuSob - File: /wwwroot/clipx/usr/include/boost/graph/depth_first_search.hpp

//======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Copyright 2003 Bruce Barr // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) //======================================================================= // Nonrecursive implementation of depth_first_visit_impl submitted by // Bruce Barr, schmoost <at> yahoo.com, May/June 2003. #ifndef BOOST_GRAPH_RECURSIVE_DFS_HPP #define BOOST_GRAPH_RECURSIVE_DFS_HPP #include <boost/config.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/graph_concepts.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/visitors.hpp> #include <boost/graph/named_function_params.hpp> #include <boost/ref.hpp> #include <boost/implicit_cast.hpp> #include <vector> #include <utility> namespace boost { template <class Visitor, class Graph> class DFSVisitorConcept { public: void constraints() { function_requires< CopyConstructibleConcept<Visitor> >(); vis.initialize_vertex(u, g); vis.start_vertex(u, g); vis.discover_vertex(u, g); vis.examine_edge(e, g); vis.tree_edge(e, g); vis.back_edge(e, g); vis.forward_or_cross_edge(e, g); vis.finish_vertex(u, g); } private: Visitor vis; Graph g; typename graph_traits<Graph>::vertex_descriptor u; typename graph_traits<Graph>::edge_descriptor e; }; namespace detail { struct nontruth2 { template<class T, class T2> bool operator()(const T&, const T2&) const { return false; } }; // Define BOOST_RECURSIVE_DFS to use older, recursive version. // It is retained for a while in order to perform performance // comparison. #ifndef BOOST_RECURSIVE_DFS // If the vertex u and the iterators ei and ei_end are thought of as the // context of the algorithm, each push and pop from the stack could // be thought of as a context shift. // Each pass through "while (ei != ei_end)" may refer to the out-edges of // an entirely different vertex, because the context of the algorithm // shifts every time a white adjacent vertex is discovered. // The corresponding context shift back from the adjacent vertex occurs // after all of its out-edges have been examined. // // See http://lists.boost.org/MailArchives/boost/msg48752.php for FAQ. template <class IncidenceGraph, class DFSVisitor, class ColorMap, class TerminatorFunc> void depth_first_visit_impl (const IncidenceGraph& g, typename graph_traits<IncidenceGraph>::vertex_descriptor u, DFSVisitor& vis, ColorMap color, TerminatorFunc func = TerminatorFunc()) { function_requires<IncidenceGraphConcept<IncidenceGraph> >(); function_requires<DFSVisitorConcept<DFSVisitor, IncidenceGraph> >(); typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex; function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >(); typedef typename property_traits<ColorMap>::value_type ColorValue; function_requires< ColorValueConcept<ColorValue> >(); typedef color_traits<ColorValue> Color; typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter; typedef std::pair<Vertex, std::pair<Iter, Iter> > VertexInfo; Iter ei, ei_end; std::vector<VertexInfo> stack; // Possible optimization for vector //stack.reserve(num_vertices(g)); typedef typename unwrap_reference<TerminatorFunc>::type TF; put(color, u, Color::gray()); vis.discover_vertex(u, g); tie(ei, ei_end) = out_edges(u, g); // Variable is needed to workaround a borland bug. TF& fn = static_cast<TF&>(func); if (fn(u, g)) { // If this vertex terminates the search, we push empty range stack.push_back(std::make_pair(u, std::make_pair(ei_end, ei_end))); } else { stack.push_back(std::make_pair(u, std::make_pair(ei, ei_end))); } while (!stack.empty()) { VertexInfo& back = stack.back(); u = back.first; tie(ei, ei_end) = back.second; stack.pop_back(); while (ei != ei_end) { Vertex v = target(*ei, g); vis.examine_edge(*ei, g); ColorValue v_color = get(color, v); if (v_color == Color::white()) { vis.tree_edge(*ei, g); stack.push_back(std::make_pair(u, std::make_pair(++ei, ei_end))); u = v; put(color, u, Color::gray()); vis.discover_vertex(u, g); tie(ei, ei_end) = out_edges(u, g); if (fn(u, g)) { ei = ei_end; } } else if (v_color == Color::gray()) { vis.back_edge(*ei, g); ++ei; } else { vis.forward_or_cross_edge(*ei, g); ++ei; } } put(color, u, Color::black()); vis.finish_vertex(u, g); } } #else // BOOST_RECURSIVE_DFS is defined template <class IncidenceGraph, class DFSVisitor, class ColorMap, class TerminatorFunc> void depth_first_visit_impl (const IncidenceGraph& g, typename graph_traits<IncidenceGraph>::vertex_descriptor u, DFSVisitor& vis, // pass-by-reference here, important! ColorMap color, TerminatorFunc func) { function_requires<IncidenceGraphConcept<IncidenceGraph> >(); function_requires<DFSVisitorConcept<DFSVisitor, IncidenceGraph> >(); typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex; function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >(); typedef typename property_traits<ColorMap>::value_type ColorValue; function_requires< ColorValueConcept<ColorValue> >(); typedef color_traits<ColorValue> Color; typename graph_traits<IncidenceGraph>::out_edge_iterator ei, ei_end; put(color, u, Color::gray()); vis.discover_vertex(u, g); typedef typename unwrap_reference<TerminatorFunc>::type TF; // Variable is needed to workaround a borland bug. TF& fn = static_cast<TF&>(func); if (!fn(u, g)) for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) { Vertex v = target(*ei, g); vis.examine_edge(*ei, g); ColorValue v_color = get(color, v); if (v_color == Color::white()) { vis.tree_edge(*ei, g); depth_first_visit_impl(g, v, vis, color, func); } else if (v_color == Color::gray()) vis.back_edge(*ei, g); else vis.forward_or_cross_edge(*ei, g); } put(color, u, Color::black()); vis.finish_vertex(u, g); } #endif } // namespace detail template <class VertexListGraph, class DFSVisitor, class ColorMap> void depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color, typename graph_traits<VertexListGraph>::vertex_descriptor start_vertex) { typedef typename graph_traits<VertexListGraph>::vertex_descriptor Vertex; function_requires<DFSVisitorConcept<DFSVisitor, VertexListGraph> >(); typedef typename property_traits<ColorMap>::value_type ColorValue; typedef color_traits<ColorValue> Color; typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end; for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { put(color, *ui, Color::white()); vis.initialize_vertex(*ui, g); } if (start_vertex != implicit_cast<Vertex>(*vertices(g).first)){ vis.start_vertex(start_vertex, g); detail::depth_first_visit_impl(g, start_vertex, vis, color, detail::nontruth2()); } for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { ColorValue u_color = get(color, *ui); if (u_color == Color::white()) { vis.start_vertex(*ui, g); detail::depth_first_visit_impl(g, *ui, vis, color, detail::nontruth2()); } } } template <class VertexListGraph, class DFSVisitor, class ColorMap> void depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color) { depth_first_search(g, vis, color, *vertices(g).first); } namespace detail { template <class ColorMap> struct dfs_dispatch { template <class VertexListGraph, class Vertex, class DFSVisitor, class P, class T, class R> static void apply(const VertexListGraph& g, DFSVisitor vis, Vertex start_vertex, const bgl_named_params<P, T, R>&, ColorMap color) { depth_first_search(g, vis, color, start_vertex); } }; template <> struct dfs_dispatch<detail::error_property_not_found> { template <class VertexListGraph, class Vertex, class DFSVisitor, class P, class T, class R> static void apply(const VertexListGraph& g, DFSVisitor vis, Vertex start_vertex, const bgl_named_params<P, T, R>& params, detail::error_property_not_found) { std::vector<default_color_type> color_vec(num_vertices(g)); default_color_type c = white_color; // avoid warning about un-init depth_first_search (g, vis, make_iterator_property_map (color_vec.begin(), choose_const_pmap(get_param(params, vertex_index), g, vertex_index), c), start_vertex); } }; } // namespace detail template <class Visitors = null_visitor> class dfs_visitor { public: dfs_visitor() { } dfs_visitor(Visitors vis) : m_vis(vis) { } template <class Vertex, class Graph> void initialize_vertex(Vertex u, const Graph& g) { invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex()); } template <class Vertex, class Graph> void start_vertex(Vertex u, const Graph& g) { invoke_visitors(m_vis, u, g, ::boost::on_start_vertex()); } template <class Vertex, class Graph> void discover_vertex(Vertex u, const Graph& g) { invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex()); } template <class Edge, class Graph> void examine_edge(Edge u, const Graph& g) { invoke_visitors(m_vis, u, g, ::boost::on_examine_edge()); } template <class Edge, class Graph> void tree_edge(Edge u, const Graph& g) { invoke_visitors(m_vis, u, g, ::boost::on_tree_edge()); } template <class Edge, class Graph> void back_edge(Edge u, const Graph& g) { invoke_visitors(m_vis, u, g, ::boost::on_back_edge()); } template <class Edge, class Graph> void forward_or_cross_edge(Edge u, const Graph& g) { invoke_visitors(m_vis, u, g, ::boost::on_forward_or_cross_edge()); } template <class Vertex, class Graph> void finish_vertex(Vertex u, const Graph& g) { invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex()); } BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,dfs) BOOST_GRAPH_EVENT_STUB(on_start_vertex,dfs) BOOST_GRAPH_EVENT_STUB(on_discover_vertex,dfs) BOOST_GRAPH_EVENT_STUB(on_examine_edge,dfs) BOOST_GRAPH_EVENT_STUB(on_tree_edge,dfs) BOOST_GRAPH_EVENT_STUB(on_back_edge,dfs) BOOST_GRAPH_EVENT_STUB(on_forward_or_cross_edge,dfs) BOOST_GRAPH_EVENT_STUB(on_finish_vertex,dfs) protected: Visitors m_vis; }; template <class Visitors> dfs_visitor<Visitors> make_dfs_visitor(Visitors vis) { return dfs_visitor<Visitors>(vis); } typedef dfs_visitor<> default_dfs_visitor; // Named Parameter Variant template <class VertexListGraph, class P, class T, class R> void depth_first_search(const VertexListGraph& g, const bgl_named_params<P, T, R>& params) { typedef typename property_value< bgl_named_params<P, T, R>, vertex_color_t>::type C; detail::dfs_dispatch<C>::apply (g, choose_param(get_param(params, graph_visitor), make_dfs_visitor(null_visitor())), choose_param(get_param(params, root_vertex_t()), *vertices(g).first), params, get_param(params, vertex_color) ); } template <class IncidenceGraph, class DFSVisitor, class ColorMap> void depth_first_visit (const IncidenceGraph& g, typename graph_traits<IncidenceGraph>::vertex_descriptor u, DFSVisitor vis, ColorMap color) { vis.start_vertex(u, g); detail::depth_first_visit_impl(g, u, vis, color, detail::nontruth2()); } template <class IncidenceGraph, class DFSVisitor, class ColorMap, class TerminatorFunc> void depth_first_visit (const IncidenceGraph& g, typename graph_traits<IncidenceGraph>::vertex_descriptor u, DFSVisitor vis, ColorMap color, TerminatorFunc func = TerminatorFunc()) { vis.start_vertex(u, g); detail::depth_first_visit_impl(g, u, vis, color, func); } } // namespace boost #endif