]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |