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