1 //
2 //=======================================================================
3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
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 #ifndef BOOST_GRAPH_UNDIRECTED_DFS_HPP
12 #define BOOST_GRAPH_UNDIRECTED_DFS_HPP
13 
14 #include <boost/graph/depth_first_search.hpp>
15 #include <vector>
16 #include <boost/concept/assert.hpp>
17 
18 namespace boost {
19 
20   namespace detail {
21 
22 // Define BOOST_RECURSIVE_DFS to use older, recursive version.
23 // It is retained for a while in order to perform performance
24 // comparison.
25 #ifndef BOOST_RECURSIVE_DFS
26 
27     template <typename IncidenceGraph, typename DFSVisitor,
28               typename VertexColorMap, typename EdgeColorMap>
undir_dfv_impl(const IncidenceGraph & g,typename graph_traits<IncidenceGraph>::vertex_descriptor u,DFSVisitor & vis,VertexColorMap vertex_color,EdgeColorMap edge_color)29     void undir_dfv_impl
30       (const IncidenceGraph& g,
31        typename graph_traits<IncidenceGraph>::vertex_descriptor u,
32        DFSVisitor& vis,
33        VertexColorMap vertex_color,
34        EdgeColorMap edge_color)
35     {
36       BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> ));
37       BOOST_CONCEPT_ASSERT(( DFSVisitorConcept<DFSVisitor, IncidenceGraph> ));
38       typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
39       typedef typename graph_traits<IncidenceGraph>::edge_descriptor Edge;
40       BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<VertexColorMap,Vertex> ));
41       BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<EdgeColorMap,Edge> ));
42       typedef typename property_traits<VertexColorMap>::value_type ColorValue;
43       typedef typename property_traits<EdgeColorMap>::value_type EColorValue;
44       BOOST_CONCEPT_ASSERT(( ColorValueConcept<ColorValue> ));
45       BOOST_CONCEPT_ASSERT(( ColorValueConcept<EColorValue> ));
46       typedef color_traits<ColorValue> Color;
47       typedef color_traits<EColorValue> EColor;
48       typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter;
49       typedef std::pair<Vertex, std::pair<boost::optional<Edge>, std::pair<Iter, Iter> > > VertexInfo;
50 
51       std::vector<VertexInfo> stack;
52 
53       put(vertex_color, u, Color::gray());
54       vis.discover_vertex(u, g);
55       stack.push_back(std::make_pair(u, std::make_pair(boost::optional<Edge>(), out_edges(u, g))));
56       while (!stack.empty()) {
57         VertexInfo& back = stack.back();
58         u = back.first;
59         boost::optional<Edge> src_e = back.second.first;
60         Iter ei = back.second.second.first, ei_end = back.second.second.second;
61         stack.pop_back();
62         while (ei != ei_end) {
63           Vertex v = target(*ei, g);
64           vis.examine_edge(*ei, g);
65           ColorValue v_color = get(vertex_color, v);
66           EColorValue uv_color = get(edge_color, *ei);
67           put(edge_color, *ei, EColor::black());
68           if (v_color == Color::white()) {
69             vis.tree_edge(*ei, g);
70             src_e = *ei;
71             stack.push_back(std::make_pair(u, std::make_pair(src_e, std::make_pair(++ei, ei_end))));
72             u = v;
73             put(vertex_color, u, Color::gray());
74             vis.discover_vertex(u, g);
75             boost::tie(ei, ei_end) = out_edges(u, g);
76           } else if (v_color == Color::gray()) {
77             if (uv_color == EColor::white()) vis.back_edge(*ei, g);
78             call_finish_edge(vis, *ei, g);
79             ++ei;
80           } else { // if (v_color == Color::black())
81             call_finish_edge(vis, *ei, g);
82             ++ei;
83           }
84         }
85         put(vertex_color, u, Color::black());
86         vis.finish_vertex(u, g);
87         if (src_e) call_finish_edge(vis, src_e.get(), g);
88       }
89     }
90 
91 #else // BOOST_RECURSIVE_DFS
92 
93     template <typename IncidenceGraph, typename DFSVisitor,
94               typename VertexColorMap, typename EdgeColorMap>
95     void undir_dfv_impl
96       (const IncidenceGraph& g,
97        typename graph_traits<IncidenceGraph>::vertex_descriptor u,
98        DFSVisitor& vis,  // pass-by-reference here, important!
99        VertexColorMap vertex_color,
100        EdgeColorMap edge_color)
101     {
102       BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> ));
103       BOOST_CONCEPT_ASSERT(( DFSVisitorConcept<DFSVisitor, IncidenceGraph> ));
104       typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
105       typedef typename graph_traits<IncidenceGraph>::edge_descriptor Edge;
106       BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<VertexColorMap,Vertex> ));
107       BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<EdgeColorMap,Edge> ));
108       typedef typename property_traits<VertexColorMap>::value_type ColorValue;
109       typedef typename property_traits<EdgeColorMap>::value_type EColorValue;
110       BOOST_CONCEPT_ASSERT(( ColorValueConcept<ColorValue> ));
111       BOOST_CONCEPT_ASSERT(( ColorValueConcept<EColorValue> ));
112       typedef color_traits<ColorValue> Color;
113       typedef color_traits<EColorValue> EColor;
114       typename graph_traits<IncidenceGraph>::out_edge_iterator ei, ei_end;
115 
116       put(vertex_color, u, Color::gray());   vis.discover_vertex(u, g);
117       for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
118         Vertex v = target(*ei, g);           vis.examine_edge(*ei, g);
119         ColorValue v_color = get(vertex_color, v);
120         EColorValue uv_color = get(edge_color, *ei);
121         put(edge_color, *ei, EColor::black());
122         if (v_color == Color::white()) {     vis.tree_edge(*ei, g);
123           undir_dfv_impl(g, v, vis, vertex_color, edge_color);
124         } else if (v_color == Color::gray() && uv_color == EColor::white())
125                                              vis.back_edge(*ei, g);
126                                              call_finish_edge(vis, *ei, g);
127       }
128       put(vertex_color, u, Color::black());  vis.finish_vertex(u, g);
129     }
130 
131 #endif // ! BOOST_RECURSIVE_DFS
132 
133   } // namespace detail
134 
135   template <typename Graph, typename DFSVisitor,
136             typename VertexColorMap, typename EdgeColorMap,
137             typename Vertex>
138   void
undirected_dfs(const Graph & g,DFSVisitor vis,VertexColorMap vertex_color,EdgeColorMap edge_color,Vertex start_vertex)139   undirected_dfs(const Graph& g, DFSVisitor vis,
140                  VertexColorMap vertex_color, EdgeColorMap edge_color,
141                  Vertex start_vertex)
142   {
143     BOOST_CONCEPT_ASSERT(( DFSVisitorConcept<DFSVisitor, Graph> ));
144     BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph> ));
145 
146     typedef typename property_traits<VertexColorMap>::value_type ColorValue;
147     typedef color_traits<ColorValue> Color;
148 
149     typename graph_traits<Graph>::vertex_iterator ui, ui_end;
150     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
151       put(vertex_color, *ui, Color::white());   vis.initialize_vertex(*ui, g);
152     }
153     typename graph_traits<Graph>::edge_iterator ei, ei_end;
154     for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
155       put(edge_color, *ei, Color::white());
156 
157     if (start_vertex != *vertices(g).first){ vis.start_vertex(start_vertex, g);
158       detail::undir_dfv_impl(g, start_vertex, vis, vertex_color, edge_color);
159     }
160 
161     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
162       ColorValue u_color = get(vertex_color, *ui);
163       if (u_color == Color::white()) {       vis.start_vertex(*ui, g);
164         detail::undir_dfv_impl(g, *ui, vis, vertex_color, edge_color);
165       }
166     }
167   }
168 
169   template <typename Graph, typename DFSVisitor, typename VertexColorMap,
170     typename EdgeColorMap>
171   void
undirected_dfs(const Graph & g,DFSVisitor vis,VertexColorMap vertex_color,EdgeColorMap edge_color)172   undirected_dfs(const Graph& g, DFSVisitor vis,
173                  VertexColorMap vertex_color, EdgeColorMap edge_color)
174   {
175     undirected_dfs(g, vis, vertex_color, edge_color, *vertices(g).first);
176   }
177 
178   namespace detail {
179     template <typename VertexColorMap>
180     struct udfs_dispatch {
181 
182       template <typename Graph, typename Vertex,
183                 typename DFSVisitor, typename EdgeColorMap,
184                 typename P, typename T, typename R>
185       static void
applyboost::detail::udfs_dispatch186       apply(const Graph& g, DFSVisitor vis, Vertex start_vertex,
187             const bgl_named_params<P, T, R>&,
188             EdgeColorMap edge_color,
189             VertexColorMap vertex_color)
190       {
191         undirected_dfs(g, vis, vertex_color, edge_color, start_vertex);
192       }
193     };
194 
195     template <>
196     struct udfs_dispatch<param_not_found> {
197       template <typename Graph, typename Vertex, typename DFSVisitor,
198                 typename EdgeColorMap,
199                 typename P, typename T, typename R>
200       static void
applyboost::detail::udfs_dispatch201       apply(const Graph& g, DFSVisitor vis, Vertex start_vertex,
202             const bgl_named_params<P, T, R>& params,
203             EdgeColorMap edge_color,
204             param_not_found)
205       {
206         std::vector<default_color_type> color_vec(num_vertices(g));
207         default_color_type c = white_color; // avoid warning about un-init
208         undirected_dfs
209           (g, vis, make_iterator_property_map
210            (color_vec.begin(),
211             choose_const_pmap(get_param(params, vertex_index),
212                               g, vertex_index), c),
213            edge_color,
214            start_vertex);
215       }
216     };
217 
218   } // namespace detail
219 
220 
221   // Named Parameter Variant
222   template <typename Graph, typename P, typename T, typename R>
223   void
undirected_dfs(const Graph & g,const bgl_named_params<P,T,R> & params)224   undirected_dfs(const Graph& g,
225                  const bgl_named_params<P, T, R>& params)
226   {
227     typedef typename get_param_type< vertex_color_t, bgl_named_params<P, T, R> >::type C;
228     detail::udfs_dispatch<C>::apply
229       (g,
230        choose_param(get_param(params, graph_visitor),
231                     make_dfs_visitor(null_visitor())),
232        choose_param(get_param(params, root_vertex_t()),
233                     *vertices(g).first),
234        params,
235        get_param(params, edge_color),
236        get_param(params, vertex_color)
237        );
238   }
239 
240 
241   template <typename IncidenceGraph, typename DFSVisitor,
242     typename VertexColorMap, typename EdgeColorMap>
undirected_depth_first_visit(const IncidenceGraph & g,typename graph_traits<IncidenceGraph>::vertex_descriptor u,DFSVisitor vis,VertexColorMap vertex_color,EdgeColorMap edge_color)243   void undirected_depth_first_visit
244     (const IncidenceGraph& g,
245      typename graph_traits<IncidenceGraph>::vertex_descriptor u,
246      DFSVisitor vis, VertexColorMap vertex_color, EdgeColorMap edge_color)
247   {
248     detail::undir_dfv_impl(g, u, vis, vertex_color, edge_color);
249   }
250 
251 
252 } // namespace boost
253 
254 
255 #endif
256