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 | |
12 | #ifndef BOOST_GRAPH_STRONG_COMPONENTS_HPP |
13 | #define BOOST_GRAPH_STRONG_COMPONENTS_HPP |
14 | |
15 | #include <stack> |
16 | #include <boost/config.hpp> |
17 | #include <boost/graph/depth_first_search.hpp> |
18 | #include <boost/type_traits/conversion_traits.hpp> |
19 | #include <boost/static_assert.hpp> |
20 | #include <boost/graph/overloading.hpp> |
21 | #include <boost/concept/assert.hpp> |
22 | |
23 | namespace boost { |
24 | |
25 | //========================================================================== |
26 | // This is Tarjan's algorithm for strongly connected components |
27 | // from his paper "Depth first search and linear graph algorithms". |
28 | // It calculates the components in a single application of DFS. |
29 | // We implement the algorithm as a dfs-visitor. |
30 | |
31 | namespace detail { |
32 | |
33 | template <typename ComponentMap, typename RootMap, typename DiscoverTime, |
34 | typename Stack> |
35 | class tarjan_scc_visitor : public dfs_visitor<> |
36 | { |
37 | typedef typename property_traits<ComponentMap>::value_type comp_type; |
38 | typedef typename property_traits<DiscoverTime>::value_type time_type; |
39 | public: |
40 | tarjan_scc_visitor(ComponentMap comp_map, RootMap r, DiscoverTime d, |
41 | comp_type& c_, Stack& s_) |
42 | : c(c_), comp(comp_map), root(r), discover_time(d), |
43 | dfs_time(time_type()), s(s_) { } |
44 | |
45 | template <typename Graph> |
46 | void discover_vertex(typename graph_traits<Graph>::vertex_descriptor v, |
47 | const Graph&) { |
48 | put(root, v, v); |
49 | put(comp, v, (std::numeric_limits<comp_type>::max)()); |
50 | put(discover_time, v, dfs_time++); |
51 | s.push(v); |
52 | } |
53 | template <typename Graph> |
54 | void finish_vertex(typename graph_traits<Graph>::vertex_descriptor v, |
55 | const Graph& g) { |
56 | typename graph_traits<Graph>::vertex_descriptor w; |
57 | typename graph_traits<Graph>::out_edge_iterator ei, ei_end; |
58 | for (boost::tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) { |
59 | w = target(*ei, g); |
60 | if (get(comp, w) == (std::numeric_limits<comp_type>::max)()) |
61 | put(root, v, this->min_discover_time(get(root,v), get(root,w))); |
62 | } |
63 | if (get(root, v) == v) { |
64 | do { |
65 | w = s.top(); s.pop(); |
66 | put(comp, w, c); |
67 | put(root, w, v); |
68 | } while (w != v); |
69 | ++c; |
70 | } |
71 | } |
72 | private: |
73 | template <typename Vertex> |
74 | Vertex min_discover_time(Vertex u, Vertex v) { |
75 | return get(discover_time, u) < get(discover_time,v) ? u : v; |
76 | } |
77 | |
78 | comp_type& c; |
79 | ComponentMap comp; |
80 | RootMap root; |
81 | DiscoverTime discover_time; |
82 | time_type dfs_time; |
83 | Stack& s; |
84 | }; |
85 | |
86 | template <class Graph, class ComponentMap, class RootMap, |
87 | class DiscoverTime, class P, class T, class R> |
88 | typename property_traits<ComponentMap>::value_type |
89 | strong_components_impl |
90 | (const Graph& g, // Input |
91 | ComponentMap comp, // Output |
92 | // Internal record keeping |
93 | RootMap root, |
94 | DiscoverTime discover_time, |
95 | const bgl_named_params<P, T, R>& params) |
96 | { |
97 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
98 | BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<ComponentMap, Vertex> )); |
99 | BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<RootMap, Vertex> )); |
100 | typedef typename property_traits<RootMap>::value_type RootV; |
101 | BOOST_CONCEPT_ASSERT(( ConvertibleConcept<RootV, Vertex> )); |
102 | BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<DiscoverTime, Vertex> )); |
103 | |
104 | typename property_traits<ComponentMap>::value_type total = 0; |
105 | |
106 | std::stack<Vertex> s; |
107 | detail::tarjan_scc_visitor<ComponentMap, RootMap, DiscoverTime, |
108 | std::stack<Vertex> > |
109 | vis(comp, root, discover_time, total, s); |
110 | depth_first_search(g, params.visitor(vis)); |
111 | return total; |
112 | } |
113 | |
114 | //------------------------------------------------------------------------- |
115 | // The dispatch functions handle the defaults for the rank and discover |
116 | // time property maps. |
117 | // dispatch with class specialization to avoid VC++ bug |
118 | |
119 | template <class DiscoverTimeMap> |
120 | struct strong_comp_dispatch2 { |
121 | template <class Graph, class ComponentMap, class RootMap, class P, class T, class R> |
122 | inline static typename property_traits<ComponentMap>::value_type |
123 | apply(const Graph& g, |
124 | ComponentMap comp, |
125 | RootMap r_map, |
126 | const bgl_named_params<P, T, R>& params, |
127 | DiscoverTimeMap time_map) |
128 | { |
129 | return strong_components_impl(g, comp, r_map, time_map, params); |
130 | } |
131 | }; |
132 | |
133 | |
134 | template <> |
135 | struct strong_comp_dispatch2<param_not_found> { |
136 | template <class Graph, class ComponentMap, class RootMap, |
137 | class P, class T, class R> |
138 | inline static typename property_traits<ComponentMap>::value_type |
139 | apply(const Graph& g, |
140 | ComponentMap comp, |
141 | RootMap r_map, |
142 | const bgl_named_params<P, T, R>& params, |
143 | param_not_found) |
144 | { |
145 | typedef typename graph_traits<Graph>::vertices_size_type size_type; |
146 | size_type n = num_vertices(g) > 0 ? num_vertices(g) : 1; |
147 | std::vector<size_type> time_vec(n); |
148 | return strong_components_impl |
149 | (g, comp, r_map, |
150 | make_iterator_property_map(time_vec.begin(), choose_const_pmap |
151 | (get_param(params, vertex_index), |
152 | g, vertex_index), time_vec[0]), |
153 | params); |
154 | } |
155 | }; |
156 | |
157 | template <class Graph, class ComponentMap, class RootMap, |
158 | class P, class T, class R, class DiscoverTimeMap> |
159 | inline typename property_traits<ComponentMap>::value_type |
160 | scc_helper2(const Graph& g, |
161 | ComponentMap comp, |
162 | RootMap r_map, |
163 | const bgl_named_params<P, T, R>& params, |
164 | DiscoverTimeMap time_map) |
165 | { |
166 | return strong_comp_dispatch2<DiscoverTimeMap>::apply(g, comp, r_map, params, time_map); |
167 | } |
168 | |
169 | template <class RootMap> |
170 | struct strong_comp_dispatch1 { |
171 | |
172 | template <class Graph, class ComponentMap, class P, class T, class R> |
173 | inline static typename property_traits<ComponentMap>::value_type |
174 | apply(const Graph& g, |
175 | ComponentMap comp, |
176 | const bgl_named_params<P, T, R>& params, |
177 | RootMap r_map) |
178 | { |
179 | return scc_helper2(g, comp, r_map, params, get_param(params, vertex_discover_time)); |
180 | } |
181 | }; |
182 | template <> |
183 | struct strong_comp_dispatch1<param_not_found> { |
184 | |
185 | template <class Graph, class ComponentMap, |
186 | class P, class T, class R> |
187 | inline static typename property_traits<ComponentMap>::value_type |
188 | apply(const Graph& g, |
189 | ComponentMap comp, |
190 | const bgl_named_params<P, T, R>& params, |
191 | param_not_found) |
192 | { |
193 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
194 | typename std::vector<Vertex>::size_type |
195 | n = num_vertices(g) > 0 ? num_vertices(g) : 1; |
196 | std::vector<Vertex> root_vec(n); |
197 | return scc_helper2 |
198 | (g, comp, |
199 | make_iterator_property_map(root_vec.begin(), choose_const_pmap |
200 | (get_param(params, vertex_index), |
201 | g, vertex_index), root_vec[0]), |
202 | params, |
203 | get_param(params, vertex_discover_time)); |
204 | } |
205 | }; |
206 | |
207 | template <class Graph, class ComponentMap, class RootMap, |
208 | class P, class T, class R> |
209 | inline typename property_traits<ComponentMap>::value_type |
210 | scc_helper1(const Graph& g, |
211 | ComponentMap comp, |
212 | const bgl_named_params<P, T, R>& params, |
213 | RootMap r_map) |
214 | { |
215 | return detail::strong_comp_dispatch1<RootMap>::apply(g, comp, params, |
216 | r_map); |
217 | } |
218 | |
219 | } // namespace detail |
220 | |
221 | template <class Graph, class ComponentMap, |
222 | class P, class T, class R> |
223 | inline typename property_traits<ComponentMap>::value_type |
224 | strong_components(const Graph& g, ComponentMap comp, |
225 | const bgl_named_params<P, T, R>& params |
226 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag)) |
227 | { |
228 | typedef typename graph_traits<Graph>::directed_category DirCat; |
229 | BOOST_STATIC_ASSERT((is_convertible<DirCat*, directed_tag*>::value == true)); |
230 | return detail::scc_helper1(g, comp, params, |
231 | get_param(params, vertex_root_t())); |
232 | } |
233 | |
234 | template <class Graph, class ComponentMap> |
235 | inline typename property_traits<ComponentMap>::value_type |
236 | strong_components(const Graph& g, ComponentMap comp |
237 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag)) |
238 | { |
239 | typedef typename graph_traits<Graph>::directed_category DirCat; |
240 | BOOST_STATIC_ASSERT((is_convertible<DirCat*, directed_tag*>::value == true)); |
241 | bgl_named_params<int, int> params(0); |
242 | return strong_components(g, comp, params); |
243 | } |
244 | |
245 | template <typename Graph, typename ComponentMap, typename ComponentLists> |
246 | void build_component_lists |
247 | (const Graph& g, |
248 | typename graph_traits<Graph>::vertices_size_type num_scc, |
249 | ComponentMap component_number, |
250 | ComponentLists& components) |
251 | { |
252 | components.resize(num_scc); |
253 | typename graph_traits<Graph>::vertex_iterator vi, vi_end; |
254 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
255 | components[component_number[*vi]].push_back(*vi); |
256 | } |
257 | |
258 | |
259 | } // namespace boost |
260 | |
261 | #include <queue> |
262 | #include <vector> |
263 | #include <boost/graph/transpose_graph.hpp> |
264 | #include <boost/pending/indirect_cmp.hpp> |
265 | #include <boost/graph/connected_components.hpp> // for components_recorder |
266 | |
267 | namespace boost { |
268 | |
269 | //========================================================================== |
270 | // This is the version of strongly connected components from |
271 | // "Intro. to Algorithms" by Cormen, Leiserson, Rivest, which was |
272 | // adapted from "Data Structure and Algorithms" by Aho, Hopcroft, |
273 | // and Ullman, who credit the algorithm to S.R. Kosaraju and M. Sharir. |
274 | // The algorithm is based on computing DFS forests the graph |
275 | // and its transpose. |
276 | |
277 | // This algorithm is slower than Tarjan's by a constant factor, uses |
278 | // more memory, and puts more requirements on the graph type. |
279 | |
280 | template <class Graph, class DFSVisitor, class ComponentsMap, |
281 | class DiscoverTime, class FinishTime, |
282 | class ColorMap> |
283 | typename property_traits<ComponentsMap>::value_type |
284 | kosaraju_strong_components(Graph& G, ComponentsMap c, |
285 | FinishTime finish_time, ColorMap color) |
286 | { |
287 | BOOST_CONCEPT_ASSERT(( MutableGraphConcept<Graph> )); |
288 | // ... |
289 | |
290 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
291 | typedef typename property_traits<ColorMap>::value_type ColorValue; |
292 | typedef color_traits<ColorValue> Color; |
293 | typename property_traits<FinishTime>::value_type time = 0; |
294 | depth_first_search |
295 | (G, make_dfs_visitor(stamp_times(finish_time, time, on_finish_vertex())), |
296 | color); |
297 | |
298 | Graph G_T(num_vertices(G)); |
299 | transpose_graph(G, G_T); |
300 | |
301 | typedef typename property_traits<ComponentsMap>::value_type count_type; |
302 | |
303 | count_type c_count(0); |
304 | detail::components_recorder<ComponentsMap> |
305 | vis(c, c_count); |
306 | |
307 | // initialize G_T |
308 | typename graph_traits<Graph>::vertex_iterator ui, ui_end; |
309 | for (boost::tie(ui, ui_end) = vertices(G_T); ui != ui_end; ++ui) |
310 | put(color, *ui, Color::white()); |
311 | |
312 | typedef typename property_traits<FinishTime>::value_type D; |
313 | typedef indirect_cmp< FinishTime, std::less<D> > Compare; |
314 | |
315 | Compare fl(finish_time); |
316 | std::priority_queue<Vertex, std::vector<Vertex>, Compare > Q(fl); |
317 | |
318 | typename graph_traits<Graph>::vertex_iterator i, j, iend, jend; |
319 | boost::tie(i, iend) = vertices(G_T); |
320 | boost::tie(j, jend) = vertices(G); |
321 | for ( ; i != iend; ++i, ++j) { |
322 | put(finish_time, *i, get(finish_time, *j)); |
323 | Q.push(*i); |
324 | } |
325 | |
326 | while ( !Q.empty() ) { |
327 | Vertex u = Q.top(); |
328 | Q.pop(); |
329 | if (get(color, u) == Color::white()) { |
330 | depth_first_visit(G_T, u, vis, color); |
331 | ++c_count; |
332 | } |
333 | } |
334 | return c_count; |
335 | } |
336 | |
337 | } // namespace boost |
338 | |
339 | #ifdef BOOST_GRAPH_USE_MPI |
340 | # include <boost/graph/distributed/strong_components.hpp> |
341 | #endif |
342 | |
343 | #endif // BOOST_GRAPH_STRONG_COMPONENTS_HPP |
344 | |