Chris@16: //
Chris@16: //=======================================================================
Chris@16: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
Chris@16: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: //
Chris@16: #ifndef BOOST_GRAPH_UNDIRECTED_DFS_HPP
Chris@16: #define BOOST_GRAPH_UNDIRECTED_DFS_HPP
Chris@16: 
Chris@16: #include <boost/graph/depth_first_search.hpp>
Chris@16: #include <vector>
Chris@16: #include <boost/concept/assert.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16: // Define BOOST_RECURSIVE_DFS to use older, recursive version.
Chris@16: // It is retained for a while in order to perform performance
Chris@16: // comparison.
Chris@16: #ifndef BOOST_RECURSIVE_DFS
Chris@16: 
Chris@16:     template <typename IncidenceGraph, typename DFSVisitor, 
Chris@16:               typename VertexColorMap, typename EdgeColorMap>
Chris@16:     void undir_dfv_impl
Chris@16:       (const IncidenceGraph& g,
Chris@16:        typename graph_traits<IncidenceGraph>::vertex_descriptor u, 
Chris@16:        DFSVisitor& vis,
Chris@16:        VertexColorMap vertex_color,
Chris@16:        EdgeColorMap edge_color)
Chris@16:     {
Chris@16:       BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> ));
Chris@16:       BOOST_CONCEPT_ASSERT(( DFSVisitorConcept<DFSVisitor, IncidenceGraph> ));
Chris@16:       typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
Chris@16:       typedef typename graph_traits<IncidenceGraph>::edge_descriptor Edge;
Chris@16:       BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<VertexColorMap,Vertex> ));
Chris@16:       BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<EdgeColorMap,Edge> ));
Chris@16:       typedef typename property_traits<VertexColorMap>::value_type ColorValue;
Chris@16:       typedef typename property_traits<EdgeColorMap>::value_type EColorValue;
Chris@16:       BOOST_CONCEPT_ASSERT(( ColorValueConcept<ColorValue> ));
Chris@16:       BOOST_CONCEPT_ASSERT(( ColorValueConcept<EColorValue> ));
Chris@16:       typedef color_traits<ColorValue> Color;
Chris@16:       typedef color_traits<EColorValue> EColor;
Chris@16:       typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter;
Chris@16:       typedef std::pair<Vertex, std::pair<boost::optional<Edge>, std::pair<Iter, Iter> > > VertexInfo;
Chris@16: 
Chris@16:       std::vector<VertexInfo> stack;
Chris@16: 
Chris@16:       put(vertex_color, u, Color::gray());
Chris@16:       vis.discover_vertex(u, g);
Chris@16:       stack.push_back(std::make_pair(u, std::make_pair(boost::optional<Edge>(), out_edges(u, g))));
Chris@16:       while (!stack.empty()) {
Chris@16:         VertexInfo& back = stack.back();
Chris@16:         u = back.first;
Chris@16:         boost::optional<Edge> src_e = back.second.first;
Chris@16:         Iter ei = back.second.second.first, ei_end = back.second.second.second;
Chris@16:         stack.pop_back();
Chris@16:         while (ei != ei_end) {
Chris@16:           Vertex v = target(*ei, g);
Chris@16:           vis.examine_edge(*ei, g);
Chris@16:           ColorValue v_color = get(vertex_color, v);
Chris@16:           EColorValue uv_color = get(edge_color, *ei);
Chris@16:           put(edge_color, *ei, EColor::black());
Chris@16:           if (v_color == Color::white()) {
Chris@16:             vis.tree_edge(*ei, g);
Chris@16:             src_e = *ei;
Chris@16:             stack.push_back(std::make_pair(u, std::make_pair(src_e, std::make_pair(++ei, ei_end))));
Chris@16:             u = v;
Chris@16:             put(vertex_color, u, Color::gray());
Chris@16:             vis.discover_vertex(u, g);
Chris@16:             boost::tie(ei, ei_end) = out_edges(u, g);
Chris@16:           } else if (v_color == Color::gray()) {
Chris@16:             if (uv_color == EColor::white()) vis.back_edge(*ei, g);
Chris@16:             call_finish_edge(vis, *ei, g);
Chris@16:             ++ei;
Chris@16:           } else { // if (v_color == Color::black())
Chris@16:             call_finish_edge(vis, *ei, g);
Chris@16:             ++ei;
Chris@16:           }
Chris@16:         }
Chris@16:         put(vertex_color, u, Color::black());
Chris@16:         vis.finish_vertex(u, g);
Chris@16:         if (src_e) call_finish_edge(vis, src_e.get(), g);
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16: #else // BOOST_RECURSIVE_DFS
Chris@16: 
Chris@16:     template <typename IncidenceGraph, typename DFSVisitor, 
Chris@16:               typename VertexColorMap, typename EdgeColorMap>
Chris@16:     void undir_dfv_impl
Chris@16:       (const IncidenceGraph& g,
Chris@16:        typename graph_traits<IncidenceGraph>::vertex_descriptor u, 
Chris@16:        DFSVisitor& vis,  // pass-by-reference here, important!
Chris@16:        VertexColorMap vertex_color,
Chris@16:        EdgeColorMap edge_color)
Chris@16:     {
Chris@16:       BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> ));
Chris@16:       BOOST_CONCEPT_ASSERT(( DFSVisitorConcept<DFSVisitor, IncidenceGraph> ));
Chris@16:       typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
Chris@16:       typedef typename graph_traits<IncidenceGraph>::edge_descriptor Edge;
Chris@16:       BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<VertexColorMap,Vertex> ));
Chris@16:       BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<EdgeColorMap,Edge> ));
Chris@16:       typedef typename property_traits<VertexColorMap>::value_type ColorValue;
Chris@16:       typedef typename property_traits<EdgeColorMap>::value_type EColorValue;
Chris@16:       BOOST_CONCEPT_ASSERT(( ColorValueConcept<ColorValue> ));
Chris@16:       BOOST_CONCEPT_ASSERT(( ColorValueConcept<EColorValue> ));
Chris@16:       typedef color_traits<ColorValue> Color;
Chris@16:       typedef color_traits<EColorValue> EColor;
Chris@16:       typename graph_traits<IncidenceGraph>::out_edge_iterator ei, ei_end;
Chris@16: 
Chris@16:       put(vertex_color, u, Color::gray());   vis.discover_vertex(u, g);
Chris@16:       for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
Chris@16:         Vertex v = target(*ei, g);           vis.examine_edge(*ei, g);
Chris@16:         ColorValue v_color = get(vertex_color, v);
Chris@16:         EColorValue uv_color = get(edge_color, *ei);
Chris@16:         put(edge_color, *ei, EColor::black());
Chris@16:         if (v_color == Color::white()) {     vis.tree_edge(*ei, g);
Chris@16:           undir_dfv_impl(g, v, vis, vertex_color, edge_color);
Chris@16:         } else if (v_color == Color::gray() && uv_color == EColor::white())
Chris@16:                                              vis.back_edge(*ei, g);
Chris@16:                                              call_finish_edge(vis, *ei, g);
Chris@16:       }
Chris@16:       put(vertex_color, u, Color::black());  vis.finish_vertex(u, g);
Chris@16:     }
Chris@16: 
Chris@16: #endif // ! BOOST_RECURSIVE_DFS
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:   template <typename Graph, typename DFSVisitor, 
Chris@16:             typename VertexColorMap, typename EdgeColorMap, 
Chris@16:             typename Vertex>
Chris@16:   void
Chris@16:   undirected_dfs(const Graph& g, DFSVisitor vis, 
Chris@16:                  VertexColorMap vertex_color, EdgeColorMap edge_color,
Chris@16:                  Vertex start_vertex)
Chris@16:   {
Chris@16:     BOOST_CONCEPT_ASSERT(( DFSVisitorConcept<DFSVisitor, Graph> ));
Chris@16:     BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph> ));
Chris@16: 
Chris@16:     typedef typename property_traits<VertexColorMap>::value_type ColorValue;
Chris@16:     typedef color_traits<ColorValue> Color;
Chris@16: 
Chris@16:     typename graph_traits<Graph>::vertex_iterator ui, ui_end;
Chris@16:     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
Chris@16:       put(vertex_color, *ui, Color::white());   vis.initialize_vertex(*ui, g);
Chris@16:     }
Chris@16:     typename graph_traits<Graph>::edge_iterator ei, ei_end;
Chris@16:     for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
Chris@16:       put(edge_color, *ei, Color::white());
Chris@16: 
Chris@16:     if (start_vertex != *vertices(g).first){ vis.start_vertex(start_vertex, g);
Chris@16:       detail::undir_dfv_impl(g, start_vertex, vis, vertex_color, edge_color);
Chris@16:     }
Chris@16: 
Chris@16:     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
Chris@16:       ColorValue u_color = get(vertex_color, *ui);
Chris@16:       if (u_color == Color::white()) {       vis.start_vertex(*ui, g);
Chris@16:         detail::undir_dfv_impl(g, *ui, vis, vertex_color, edge_color);
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Graph, typename DFSVisitor, typename VertexColorMap,
Chris@16:     typename EdgeColorMap>
Chris@16:   void
Chris@16:   undirected_dfs(const Graph& g, DFSVisitor vis, 
Chris@16:                  VertexColorMap vertex_color, EdgeColorMap edge_color)
Chris@16:   {
Chris@16:     undirected_dfs(g, vis, vertex_color, edge_color, *vertices(g).first);
Chris@16:   }
Chris@16: 
Chris@16:   namespace detail {
Chris@16:     template <typename VertexColorMap>
Chris@16:     struct udfs_dispatch {
Chris@16: 
Chris@16:       template <typename Graph, typename Vertex, 
Chris@16:                 typename DFSVisitor, typename EdgeColorMap,
Chris@16:                 typename P, typename T, typename R>
Chris@16:       static void
Chris@16:       apply(const Graph& g, DFSVisitor vis, Vertex start_vertex,
Chris@16:             const bgl_named_params<P, T, R>&,
Chris@16:             EdgeColorMap edge_color,
Chris@16:             VertexColorMap vertex_color)
Chris@16:       {
Chris@16:         undirected_dfs(g, vis, vertex_color, edge_color, start_vertex);
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     template <>
Chris@16:     struct udfs_dispatch<param_not_found> {
Chris@16:       template <typename Graph, typename Vertex, typename DFSVisitor,
Chris@16:                 typename EdgeColorMap,
Chris@16:                 typename P, typename T, typename R>
Chris@16:       static void
Chris@16:       apply(const Graph& g, DFSVisitor vis, Vertex start_vertex,
Chris@16:             const bgl_named_params<P, T, R>& params,
Chris@16:             EdgeColorMap edge_color,
Chris@16:             param_not_found)
Chris@16:       {
Chris@16:         std::vector<default_color_type> color_vec(num_vertices(g));
Chris@16:         default_color_type c = white_color; // avoid warning about un-init
Chris@16:         undirected_dfs
Chris@16:           (g, vis, make_iterator_property_map
Chris@16:            (color_vec.begin(),
Chris@16:             choose_const_pmap(get_param(params, vertex_index),
Chris@16:                               g, vertex_index), c),
Chris@16:            edge_color,
Chris@16:            start_vertex);
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:   } // namespace detail
Chris@16:   
Chris@16: 
Chris@16:   // Named Parameter Variant
Chris@16:   template <typename Graph, typename P, typename T, typename R>
Chris@16:   void
Chris@16:   undirected_dfs(const Graph& g, 
Chris@16:                  const bgl_named_params<P, T, R>& params)
Chris@16:   {
Chris@16:     typedef typename get_param_type< vertex_color_t, bgl_named_params<P, T, R> >::type C;
Chris@16:     detail::udfs_dispatch<C>::apply
Chris@16:       (g,
Chris@16:        choose_param(get_param(params, graph_visitor),
Chris@16:                     make_dfs_visitor(null_visitor())),
Chris@16:        choose_param(get_param(params, root_vertex_t()),
Chris@16:                     *vertices(g).first),
Chris@16:        params,
Chris@16:        get_param(params, edge_color),
Chris@16:        get_param(params, vertex_color)
Chris@16:        );
Chris@16:   }
Chris@16:   
Chris@16: 
Chris@16:   template <typename IncidenceGraph, typename DFSVisitor, 
Chris@16:     typename VertexColorMap, typename EdgeColorMap>
Chris@16:   void undirected_depth_first_visit
Chris@16:     (const IncidenceGraph& g,
Chris@16:      typename graph_traits<IncidenceGraph>::vertex_descriptor u, 
Chris@16:      DFSVisitor vis, VertexColorMap vertex_color, EdgeColorMap edge_color)
Chris@16:   {
Chris@16:     detail::undir_dfv_impl(g, u, vis, vertex_color, edge_color);
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: 
Chris@16: #endif