Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:37:39 

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
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 #ifndef BOOST_GRAPH_UNDIRECTED_DFS_HPP
0012 #define BOOST_GRAPH_UNDIRECTED_DFS_HPP
0013 
0014 #include <boost/graph/depth_first_search.hpp>
0015 #include <vector>
0016 #include <boost/concept/assert.hpp>
0017 
0018 namespace boost
0019 {
0020 
0021 namespace detail
0022 {
0023 
0024 // Define BOOST_RECURSIVE_DFS to use older, recursive version.
0025 // It is retained for a while in order to perform performance
0026 // comparison.
0027 #ifndef BOOST_RECURSIVE_DFS
0028 
0029     template < typename IncidenceGraph, typename DFSVisitor,
0030         typename VertexColorMap, typename EdgeColorMap >
0031     void undir_dfv_impl(const IncidenceGraph& g,
0032         typename graph_traits< IncidenceGraph >::vertex_descriptor u,
0033         DFSVisitor& vis, VertexColorMap vertex_color, EdgeColorMap edge_color)
0034     {
0035         BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< IncidenceGraph >));
0036         BOOST_CONCEPT_ASSERT((DFSVisitorConcept< DFSVisitor, IncidenceGraph >));
0037         typedef
0038             typename graph_traits< IncidenceGraph >::vertex_descriptor Vertex;
0039         typedef typename graph_traits< IncidenceGraph >::edge_descriptor Edge;
0040         BOOST_CONCEPT_ASSERT(
0041             (ReadWritePropertyMapConcept< VertexColorMap, Vertex >));
0042         BOOST_CONCEPT_ASSERT(
0043             (ReadWritePropertyMapConcept< EdgeColorMap, Edge >));
0044         typedef
0045             typename property_traits< VertexColorMap >::value_type ColorValue;
0046         typedef
0047             typename property_traits< EdgeColorMap >::value_type EColorValue;
0048         BOOST_CONCEPT_ASSERT((ColorValueConcept< ColorValue >));
0049         BOOST_CONCEPT_ASSERT((ColorValueConcept< EColorValue >));
0050         typedef color_traits< ColorValue > Color;
0051         typedef color_traits< EColorValue > EColor;
0052         typedef typename graph_traits< IncidenceGraph >::out_edge_iterator Iter;
0053         typedef std::pair< Vertex,
0054             std::pair< boost::optional< Edge >, std::pair< Iter, Iter > > >
0055             VertexInfo;
0056 
0057         std::vector< VertexInfo > stack;
0058 
0059         put(vertex_color, u, Color::gray());
0060         vis.discover_vertex(u, g);
0061         stack.push_back(std::make_pair(
0062             u, std::make_pair(boost::optional< Edge >(), out_edges(u, g))));
0063         while (!stack.empty())
0064         {
0065             VertexInfo& back = stack.back();
0066             u = back.first;
0067             boost::optional< Edge > src_e = back.second.first;
0068             Iter ei = back.second.second.first,
0069                  ei_end = back.second.second.second;
0070             stack.pop_back();
0071             while (ei != ei_end)
0072             {
0073                 Vertex v = target(*ei, g);
0074                 vis.examine_edge(*ei, g);
0075                 ColorValue v_color = get(vertex_color, v);
0076                 EColorValue uv_color = get(edge_color, *ei);
0077                 put(edge_color, *ei, EColor::black());
0078                 if (v_color == Color::white())
0079                 {
0080                     vis.tree_edge(*ei, g);
0081                     src_e = *ei;
0082                     stack.push_back(std::make_pair(u,
0083                         std::make_pair(src_e, std::make_pair(++ei, ei_end))));
0084                     u = v;
0085                     put(vertex_color, u, Color::gray());
0086                     vis.discover_vertex(u, g);
0087                     boost::tie(ei, ei_end) = out_edges(u, g);
0088                 }
0089                 else if (v_color == Color::gray())
0090                 {
0091                     if (uv_color == EColor::white())
0092                         vis.back_edge(*ei, g);
0093                     call_finish_edge(vis, *ei, g);
0094                     ++ei;
0095                 }
0096                 else
0097                 { // if (v_color == Color::black())
0098                     call_finish_edge(vis, *ei, g);
0099                     ++ei;
0100                 }
0101             }
0102             put(vertex_color, u, Color::black());
0103             vis.finish_vertex(u, g);
0104             if (src_e)
0105                 call_finish_edge(vis, src_e.get(), g);
0106         }
0107     }
0108 
0109 #else // BOOST_RECURSIVE_DFS
0110 
0111     template < typename IncidenceGraph, typename DFSVisitor,
0112         typename VertexColorMap, typename EdgeColorMap >
0113     void undir_dfv_impl(const IncidenceGraph& g,
0114         typename graph_traits< IncidenceGraph >::vertex_descriptor u,
0115         DFSVisitor& vis, // pass-by-reference here, important!
0116         VertexColorMap vertex_color, EdgeColorMap edge_color)
0117     {
0118         BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< IncidenceGraph >));
0119         BOOST_CONCEPT_ASSERT((DFSVisitorConcept< DFSVisitor, IncidenceGraph >));
0120         typedef
0121             typename graph_traits< IncidenceGraph >::vertex_descriptor Vertex;
0122         typedef typename graph_traits< IncidenceGraph >::edge_descriptor Edge;
0123         BOOST_CONCEPT_ASSERT(
0124             (ReadWritePropertyMapConcept< VertexColorMap, Vertex >));
0125         BOOST_CONCEPT_ASSERT(
0126             (ReadWritePropertyMapConcept< EdgeColorMap, Edge >));
0127         typedef
0128             typename property_traits< VertexColorMap >::value_type ColorValue;
0129         typedef
0130             typename property_traits< EdgeColorMap >::value_type EColorValue;
0131         BOOST_CONCEPT_ASSERT((ColorValueConcept< ColorValue >));
0132         BOOST_CONCEPT_ASSERT((ColorValueConcept< EColorValue >));
0133         typedef color_traits< ColorValue > Color;
0134         typedef color_traits< EColorValue > EColor;
0135         typename graph_traits< IncidenceGraph >::out_edge_iterator ei, ei_end;
0136 
0137         put(vertex_color, u, Color::gray());
0138         vis.discover_vertex(u, g);
0139         for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei)
0140         {
0141             Vertex v = target(*ei, g);
0142             vis.examine_edge(*ei, g);
0143             ColorValue v_color = get(vertex_color, v);
0144             EColorValue uv_color = get(edge_color, *ei);
0145             put(edge_color, *ei, EColor::black());
0146             if (v_color == Color::white())
0147             {
0148                 vis.tree_edge(*ei, g);
0149                 undir_dfv_impl(g, v, vis, vertex_color, edge_color);
0150             }
0151             else if (v_color == Color::gray() && uv_color == EColor::white())
0152                 vis.back_edge(*ei, g);
0153             call_finish_edge(vis, *ei, g);
0154         }
0155         put(vertex_color, u, Color::black());
0156         vis.finish_vertex(u, g);
0157     }
0158 
0159 #endif // ! BOOST_RECURSIVE_DFS
0160 
0161 } // namespace detail
0162 
0163 template < typename Graph, typename DFSVisitor, typename VertexColorMap,
0164     typename EdgeColorMap, typename Vertex >
0165 void undirected_dfs(const Graph& g, DFSVisitor vis, VertexColorMap vertex_color,
0166     EdgeColorMap edge_color, Vertex start_vertex)
0167 {
0168     BOOST_CONCEPT_ASSERT((DFSVisitorConcept< DFSVisitor, Graph >));
0169     BOOST_CONCEPT_ASSERT((EdgeListGraphConcept< Graph >));
0170 
0171     typedef typename property_traits< VertexColorMap >::value_type ColorValue;
0172     typedef color_traits< ColorValue > Color;
0173 
0174     typename graph_traits< Graph >::vertex_iterator ui, ui_end;
0175     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
0176     {
0177         put(vertex_color, *ui, Color::white());
0178         vis.initialize_vertex(*ui, g);
0179     }
0180     typename graph_traits< Graph >::edge_iterator ei, ei_end;
0181     for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
0182         put(edge_color, *ei, Color::white());
0183 
0184     if (start_vertex != *vertices(g).first)
0185     {
0186         vis.start_vertex(start_vertex, g);
0187         detail::undir_dfv_impl(g, start_vertex, vis, vertex_color, edge_color);
0188     }
0189 
0190     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
0191     {
0192         ColorValue u_color = get(vertex_color, *ui);
0193         if (u_color == Color::white())
0194         {
0195             vis.start_vertex(*ui, g);
0196             detail::undir_dfv_impl(g, *ui, vis, vertex_color, edge_color);
0197         }
0198     }
0199 }
0200 
0201 template < typename Graph, typename DFSVisitor, typename VertexColorMap,
0202     typename EdgeColorMap >
0203 void undirected_dfs(const Graph& g, DFSVisitor vis, VertexColorMap vertex_color,
0204     EdgeColorMap edge_color)
0205 {
0206     undirected_dfs(g, vis, vertex_color, edge_color, *vertices(g).first);
0207 }
0208 
0209 namespace detail
0210 {
0211     template < typename VertexColorMap > struct udfs_dispatch
0212     {
0213 
0214         template < typename Graph, typename Vertex, typename DFSVisitor,
0215             typename EdgeColorMap, typename P, typename T, typename R >
0216         static void apply(const Graph& g, DFSVisitor vis, Vertex start_vertex,
0217             const bgl_named_params< P, T, R >&, EdgeColorMap edge_color,
0218             VertexColorMap vertex_color)
0219         {
0220             undirected_dfs(g, vis, vertex_color, edge_color, start_vertex);
0221         }
0222     };
0223 
0224     template <> struct udfs_dispatch< param_not_found >
0225     {
0226         template < typename Graph, typename Vertex, typename DFSVisitor,
0227             typename EdgeColorMap, typename P, typename T, typename R >
0228         static void apply(const Graph& g, DFSVisitor vis, Vertex start_vertex,
0229             const bgl_named_params< P, T, R >& params, EdgeColorMap edge_color,
0230             param_not_found)
0231         {
0232             std::vector< default_color_type > color_vec(num_vertices(g));
0233             default_color_type c = white_color; // avoid warning about un-init
0234             undirected_dfs(g, vis,
0235                 make_iterator_property_map(color_vec.begin(),
0236                     choose_const_pmap(
0237                         get_param(params, vertex_index), g, vertex_index),
0238                     c),
0239                 edge_color, start_vertex);
0240         }
0241     };
0242 
0243 } // namespace detail
0244 
0245 // Named Parameter Variant
0246 template < typename Graph, typename P, typename T, typename R >
0247 void undirected_dfs(const Graph& g, const bgl_named_params< P, T, R >& params)
0248 {
0249     typedef typename get_param_type< vertex_color_t,
0250         bgl_named_params< P, T, R > >::type C;
0251     detail::udfs_dispatch< C >::apply(g,
0252         choose_param(
0253             get_param(params, graph_visitor), make_dfs_visitor(null_visitor())),
0254         choose_param(get_param(params, root_vertex_t()), *vertices(g).first),
0255         params, get_param(params, edge_color), get_param(params, vertex_color));
0256 }
0257 
0258 template < typename IncidenceGraph, typename DFSVisitor,
0259     typename VertexColorMap, typename EdgeColorMap >
0260 void undirected_depth_first_visit(const IncidenceGraph& g,
0261     typename graph_traits< IncidenceGraph >::vertex_descriptor u,
0262     DFSVisitor vis, VertexColorMap vertex_color, EdgeColorMap edge_color)
0263 {
0264     detail::undir_dfv_impl(g, u, vis, vertex_color, edge_color);
0265 }
0266 
0267 } // namespace boost
0268 
0269 #endif
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!