]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright (c) Jeremy Siek 2001 |
2 | // Copyright (c) Douglas Gregor 2004 | |
3 | // | |
4 | // Distributed under the Boost Software License, Version 1.0. (See | |
5 | // accompanying file LICENSE_1_0.txt or copy at | |
6 | // http://www.boost.org/LICENSE_1_0.txt) | |
7 | ||
8 | // NOTE: this final is generated by libs/graph/doc/biconnected_components.w | |
9 | ||
10 | #ifndef BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP | |
11 | #define BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP | |
12 | ||
13 | #include <stack> | |
14 | #include <vector> | |
15 | #include <algorithm> // for std::min and std::max | |
16 | #include <boost/config.hpp> | |
17 | #include <boost/limits.hpp> | |
18 | #include <boost/graph/graph_traits.hpp> | |
19 | #include <boost/graph/graph_concepts.hpp> | |
20 | #include <boost/property_map/property_map.hpp> | |
21 | #include <boost/graph/depth_first_search.hpp> | |
22 | #include <boost/graph/graph_utility.hpp> | |
23 | #include <boost/concept/assert.hpp> | |
24 | #include <boost/assert.hpp> | |
25 | ||
26 | namespace boost | |
27 | { | |
28 | namespace detail | |
29 | { | |
30 | template<typename ComponentMap, typename DiscoverTimeMap, | |
31 | typename LowPointMap, typename PredecessorMap, | |
32 | typename OutputIterator, typename Stack, | |
33 | typename ArticulationVector, typename IndexMap, | |
34 | typename DFSVisitor> | |
35 | struct biconnected_components_visitor : public dfs_visitor<> | |
36 | { | |
37 | biconnected_components_visitor | |
38 | (ComponentMap comp, std::size_t& c, | |
39 | std::size_t& children_of_root, DiscoverTimeMap dtm, | |
40 | std::size_t& dfs_time, LowPointMap lowpt, PredecessorMap pred, | |
41 | OutputIterator out, Stack& S, | |
42 | ArticulationVector& is_articulation_point, IndexMap index_map, | |
43 | DFSVisitor vis) | |
44 | : comp(comp), c(c), children_of_root(children_of_root), | |
45 | dtm(dtm), dfs_time(dfs_time), lowpt(lowpt), | |
46 | pred(pred), out(out), S(S), | |
47 | is_articulation_point(is_articulation_point), | |
48 | index_map(index_map), vis(vis) { } | |
49 | ||
50 | template <typename Vertex, typename Graph> | |
51 | void initialize_vertex(const Vertex& u, Graph& g) | |
52 | { | |
53 | put(pred, u, u); | |
54 | vis.initialize_vertex(u, g); | |
55 | } | |
56 | ||
57 | template <typename Vertex, typename Graph> | |
58 | void start_vertex(const Vertex& u, Graph& g) | |
59 | { | |
60 | children_of_root = 0; | |
61 | vis.start_vertex(u, g); | |
62 | } | |
63 | ||
64 | template <typename Vertex, typename Graph> | |
65 | void discover_vertex(const Vertex& u, Graph& g) | |
66 | { | |
67 | put(dtm, u, ++dfs_time); | |
68 | put(lowpt, u, get(dtm, u)); | |
69 | vis.discover_vertex(u, g); | |
70 | } | |
71 | ||
72 | template <typename Edge, typename Graph> | |
73 | void examine_edge(const Edge& e, Graph& g) | |
74 | { | |
75 | vis.examine_edge(e, g); | |
76 | } | |
77 | ||
78 | template <typename Edge, typename Graph> | |
79 | void tree_edge(const Edge& e, Graph& g) | |
80 | { | |
81 | typename boost::graph_traits<Graph>::vertex_descriptor src = source(e, g); | |
82 | typename boost::graph_traits<Graph>::vertex_descriptor tgt = target(e, g); | |
83 | ||
84 | S.push(e); | |
85 | put(pred, tgt, src); | |
86 | if ( get(pred, src) == src ) { | |
87 | ++children_of_root; | |
88 | } | |
89 | vis.tree_edge(e, g); | |
90 | } | |
91 | ||
92 | template <typename Edge, typename Graph> | |
93 | void back_edge(const Edge& e, Graph& g) | |
94 | { | |
95 | BOOST_USING_STD_MIN(); | |
96 | ||
97 | typename boost::graph_traits<Graph>::vertex_descriptor src = source(e, g); | |
98 | typename boost::graph_traits<Graph>::vertex_descriptor tgt = target(e, g); | |
99 | if ( tgt != get(pred, src) ) { | |
100 | S.push(e); | |
101 | put(lowpt, src, | |
102 | min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, src), | |
103 | get(dtm, tgt))); | |
104 | } | |
105 | vis.back_edge(e, g); | |
106 | } | |
107 | ||
108 | template <typename Edge, typename Graph> | |
109 | void forward_or_cross_edge(const Edge& e, Graph& g) | |
110 | { | |
111 | vis.forward_or_cross_edge(e, g); | |
112 | } | |
113 | ||
114 | template <typename Vertex, typename Graph> | |
115 | void finish_vertex(const Vertex& u, Graph& g) | |
116 | { | |
117 | BOOST_USING_STD_MIN(); | |
118 | Vertex parent = get(pred, u); | |
119 | if (parent == u) { // Root of tree is special | |
120 | is_articulation_point[get(index_map, u)] = (children_of_root > 1); | |
121 | } else { | |
122 | put(lowpt, parent, | |
123 | min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, parent), | |
124 | get(lowpt, u))); | |
125 | if ( get(lowpt, u) >= get(dtm, parent) ) { | |
126 | is_articulation_point[get(index_map, parent)] = true; | |
127 | while ( get(dtm, source(S.top(), g)) >= get(dtm, u) ) { | |
128 | put(comp, S.top(), c); | |
129 | S.pop(); | |
130 | } | |
131 | BOOST_ASSERT (source(S.top(), g) == parent); | |
132 | BOOST_ASSERT (target(S.top(), g) == u); | |
133 | put(comp, S.top(), c); | |
134 | S.pop(); | |
135 | ++c; | |
136 | } | |
137 | } | |
138 | if ( is_articulation_point[get(index_map, u)] ) { | |
139 | *out++ = u; | |
140 | } | |
141 | vis.finish_vertex(u, g); | |
142 | } | |
143 | ||
144 | ComponentMap comp; | |
145 | std::size_t& c; | |
146 | std::size_t& children_of_root; | |
147 | DiscoverTimeMap dtm; | |
148 | std::size_t& dfs_time; | |
149 | LowPointMap lowpt; | |
150 | PredecessorMap pred; | |
151 | OutputIterator out; | |
152 | Stack& S; | |
153 | ArticulationVector& is_articulation_point; | |
154 | IndexMap index_map; | |
155 | DFSVisitor vis; | |
156 | }; | |
157 | ||
158 | template<typename Graph, typename ComponentMap, typename OutputIterator, | |
159 | typename VertexIndexMap, typename DiscoverTimeMap, typename LowPointMap, | |
160 | typename PredecessorMap, typename DFSVisitor> | |
161 | std::pair<std::size_t, OutputIterator> | |
162 | biconnected_components_impl(const Graph & g, ComponentMap comp, | |
163 | OutputIterator out, VertexIndexMap index_map, DiscoverTimeMap dtm, | |
164 | LowPointMap lowpt, PredecessorMap pred, DFSVisitor dfs_vis) | |
165 | { | |
166 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; | |
167 | typedef typename graph_traits<Graph>::edge_descriptor edge_t; | |
168 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> )); | |
169 | BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> )); | |
170 | BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<ComponentMap, edge_t> )); | |
171 | BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<DiscoverTimeMap, | |
172 | vertex_t> )); | |
173 | BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<LowPointMap, vertex_t > )); | |
174 | BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<PredecessorMap, | |
175 | vertex_t> )); | |
176 | ||
177 | std::size_t num_components = 0; | |
178 | std::size_t children_of_root; | |
179 | std::size_t dfs_time = 0; | |
180 | std::stack<edge_t> S; | |
181 | std::vector<char> is_articulation_point(num_vertices(g)); | |
182 | ||
183 | biconnected_components_visitor<ComponentMap, DiscoverTimeMap, | |
184 | LowPointMap, PredecessorMap, OutputIterator, std::stack<edge_t>, | |
185 | std::vector<char>, VertexIndexMap, DFSVisitor> | |
186 | vis(comp, num_components, children_of_root, dtm, dfs_time, | |
187 | lowpt, pred, out, S, is_articulation_point, index_map, dfs_vis); | |
188 | ||
189 | depth_first_search(g, visitor(vis).vertex_index_map(index_map)); | |
190 | ||
191 | return std::pair<std::size_t, OutputIterator>(num_components, vis.out); | |
192 | } | |
193 | ||
194 | template <typename PredecessorMap> | |
195 | struct bicomp_dispatch3 | |
196 | { | |
197 | template<typename Graph, typename ComponentMap, typename OutputIterator, | |
198 | typename VertexIndexMap, typename DiscoverTimeMap, | |
199 | typename LowPointMap, class P, class T, class R> | |
200 | static std::pair<std::size_t, OutputIterator> apply (const Graph & g, | |
201 | ComponentMap comp, OutputIterator out, VertexIndexMap index_map, | |
202 | DiscoverTimeMap dtm, LowPointMap lowpt, | |
203 | const bgl_named_params<P, T, R>& params, PredecessorMap pred) | |
204 | { | |
205 | return biconnected_components_impl | |
206 | (g, comp, out, index_map, dtm, lowpt, pred, | |
207 | choose_param(get_param(params, graph_visitor), | |
208 | make_dfs_visitor(null_visitor()))); | |
209 | } | |
210 | }; | |
211 | ||
212 | template <> | |
213 | struct bicomp_dispatch3<param_not_found> | |
214 | { | |
215 | template<typename Graph, typename ComponentMap, typename OutputIterator, | |
216 | typename VertexIndexMap, typename DiscoverTimeMap, | |
217 | typename LowPointMap, class P, class T, class R> | |
218 | static std::pair<std::size_t, OutputIterator> apply (const Graph & g, | |
219 | ComponentMap comp, OutputIterator out, VertexIndexMap index_map, | |
220 | DiscoverTimeMap dtm, LowPointMap lowpt, | |
221 | const bgl_named_params<P, T, R>& params, | |
222 | param_not_found) | |
223 | { | |
224 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; | |
225 | std::vector<vertex_t> pred(num_vertices(g)); | |
226 | vertex_t vert = graph_traits<Graph>::null_vertex(); | |
227 | ||
228 | return biconnected_components_impl | |
229 | (g, comp, out, index_map, dtm, lowpt, | |
230 | make_iterator_property_map(pred.begin(), index_map, vert), | |
231 | choose_param(get_param(params, graph_visitor), | |
232 | make_dfs_visitor(null_visitor()))); | |
233 | } | |
234 | }; | |
235 | ||
236 | template <typename LowPointMap> | |
237 | struct bicomp_dispatch2 | |
238 | { | |
239 | template<typename Graph, typename ComponentMap, typename OutputIterator, | |
240 | typename VertexIndexMap, typename DiscoverTimeMap, | |
241 | typename P, typename T, typename R> | |
242 | static std::pair<std::size_t, OutputIterator> apply (const Graph& g, | |
243 | ComponentMap comp, OutputIterator out, VertexIndexMap index_map, | |
244 | DiscoverTimeMap dtm, const bgl_named_params<P, T, R>& params, | |
245 | LowPointMap lowpt) | |
246 | { | |
247 | typedef typename get_param_type< vertex_predecessor_t, bgl_named_params<P,T,R> >::type dispatch_type; | |
248 | ||
249 | return bicomp_dispatch3<dispatch_type>::apply | |
250 | (g, comp, out, index_map, dtm, lowpt, params, | |
251 | get_param(params, vertex_predecessor)); | |
252 | } | |
253 | }; | |
254 | ||
255 | ||
256 | template <> | |
257 | struct bicomp_dispatch2<param_not_found> | |
258 | { | |
259 | template<typename Graph, typename ComponentMap, typename OutputIterator, | |
260 | typename VertexIndexMap, typename DiscoverTimeMap, | |
261 | typename P, typename T, typename R> | |
262 | static std::pair<std::size_t, OutputIterator> apply (const Graph& g, | |
263 | ComponentMap comp, OutputIterator out, VertexIndexMap index_map, | |
264 | DiscoverTimeMap dtm, const bgl_named_params<P, T, R>& params, | |
265 | param_not_found) | |
266 | { | |
267 | typedef typename graph_traits<Graph>::vertices_size_type | |
268 | vertices_size_type; | |
269 | std::vector<vertices_size_type> lowpt(num_vertices(g)); | |
270 | vertices_size_type vst(0); | |
271 | ||
272 | typedef typename get_param_type< vertex_predecessor_t, bgl_named_params<P,T,R> >::type dispatch_type; | |
273 | ||
274 | return bicomp_dispatch3<dispatch_type>::apply | |
275 | (g, comp, out, index_map, dtm, | |
276 | make_iterator_property_map(lowpt.begin(), index_map, vst), | |
277 | params, get_param(params, vertex_predecessor)); | |
278 | } | |
279 | }; | |
280 | ||
281 | template <typename DiscoverTimeMap> | |
282 | struct bicomp_dispatch1 | |
283 | { | |
284 | template<typename Graph, typename ComponentMap, typename OutputIterator, | |
285 | typename VertexIndexMap, class P, class T, class R> | |
286 | static std::pair<std::size_t, OutputIterator> apply(const Graph& g, | |
287 | ComponentMap comp, OutputIterator out, VertexIndexMap index_map, | |
288 | const bgl_named_params<P, T, R>& params, DiscoverTimeMap dtm) | |
289 | { | |
290 | typedef typename get_param_type< vertex_lowpoint_t, bgl_named_params<P,T,R> >::type dispatch_type; | |
291 | ||
292 | return bicomp_dispatch2<dispatch_type>::apply | |
293 | (g, comp, out, index_map, dtm, params, | |
294 | get_param(params, vertex_lowpoint)); | |
295 | } | |
296 | }; | |
297 | ||
298 | template <> | |
299 | struct bicomp_dispatch1<param_not_found> | |
300 | { | |
301 | template<typename Graph, typename ComponentMap, typename OutputIterator, | |
302 | typename VertexIndexMap, class P, class T, class R> | |
303 | static std::pair<std::size_t, OutputIterator> apply(const Graph& g, | |
304 | ComponentMap comp, OutputIterator out, VertexIndexMap index_map, | |
305 | const bgl_named_params<P, T, R>& params, param_not_found) | |
306 | { | |
307 | typedef typename graph_traits<Graph>::vertices_size_type | |
308 | vertices_size_type; | |
309 | std::vector<vertices_size_type> discover_time(num_vertices(g)); | |
310 | vertices_size_type vst(0); | |
311 | ||
312 | typedef typename get_param_type< vertex_lowpoint_t, bgl_named_params<P,T,R> >::type dispatch_type; | |
313 | ||
314 | return bicomp_dispatch2<dispatch_type>::apply | |
315 | (g, comp, out, index_map, | |
316 | make_iterator_property_map(discover_time.begin(), index_map, vst), | |
317 | params, get_param(params, vertex_lowpoint)); | |
318 | } | |
319 | }; | |
320 | ||
321 | } | |
322 | ||
323 | template<typename Graph, typename ComponentMap, typename OutputIterator, | |
324 | typename DiscoverTimeMap, typename LowPointMap> | |
325 | std::pair<std::size_t, OutputIterator> | |
326 | biconnected_components(const Graph& g, ComponentMap comp, | |
327 | OutputIterator out, DiscoverTimeMap dtm, LowPointMap lowpt) | |
328 | { | |
329 | typedef param_not_found dispatch_type; | |
330 | ||
331 | return detail::bicomp_dispatch3<dispatch_type>::apply | |
332 | (g, comp, out, | |
333 | get(vertex_index, g), | |
334 | dtm, lowpt, | |
335 | bgl_named_params<int, buffer_param_t>(0), | |
336 | param_not_found()); | |
337 | } | |
338 | ||
339 | template <typename Graph, typename ComponentMap, typename OutputIterator, | |
340 | typename P, typename T, typename R> | |
341 | std::pair<std::size_t, OutputIterator> | |
342 | biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, | |
343 | const bgl_named_params<P, T, R>& params) | |
344 | { | |
345 | typedef typename get_param_type< vertex_discover_time_t, bgl_named_params<P,T,R> >::type dispatch_type; | |
346 | ||
347 | return detail::bicomp_dispatch1<dispatch_type>::apply(g, comp, out, | |
348 | choose_const_pmap(get_param(params, vertex_index), g, vertex_index), | |
349 | params, get_param(params, vertex_discover_time)); | |
350 | } | |
351 | ||
352 | template < typename Graph, typename ComponentMap, typename OutputIterator> | |
353 | std::pair<std::size_t, OutputIterator> | |
354 | biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out) | |
355 | { | |
356 | return biconnected_components(g, comp, out, | |
357 | bgl_named_params<int, buffer_param_t>(0)); | |
358 | } | |
359 | ||
360 | namespace graph_detail { | |
361 | struct dummy_output_iterator | |
362 | { | |
363 | typedef std::output_iterator_tag iterator_category; | |
364 | typedef void value_type; | |
365 | typedef void pointer; | |
366 | typedef void difference_type; | |
367 | ||
368 | struct reference { | |
369 | template<typename T> | |
370 | reference& operator=(const T&) { return *this; } | |
371 | }; | |
372 | ||
373 | reference operator*() const { return reference(); } | |
374 | dummy_output_iterator& operator++() { return *this; } | |
375 | dummy_output_iterator operator++(int) { return *this; } | |
376 | }; | |
377 | } // end namespace graph_detail | |
378 | ||
379 | template <typename Graph, typename ComponentMap, | |
380 | typename P, typename T, typename R> | |
381 | std::size_t | |
382 | biconnected_components(const Graph& g, ComponentMap comp, | |
383 | const bgl_named_params<P, T, R>& params) | |
384 | { | |
385 | return biconnected_components(g, comp, | |
386 | graph_detail::dummy_output_iterator(), params).first; | |
387 | } | |
388 | ||
389 | template <typename Graph, typename ComponentMap> | |
390 | std::size_t | |
391 | biconnected_components(const Graph& g, ComponentMap comp) | |
392 | { | |
393 | return biconnected_components(g, comp, | |
394 | graph_detail::dummy_output_iterator()).first; | |
395 | } | |
396 | ||
397 | template<typename Graph, typename OutputIterator, | |
398 | typename P, typename T, typename R> | |
399 | OutputIterator | |
400 | articulation_points(const Graph& g, OutputIterator out, | |
401 | const bgl_named_params<P, T, R>& params) | |
402 | { | |
403 | return biconnected_components(g, dummy_property_map(), out, | |
404 | params).second; | |
405 | } | |
406 | ||
407 | template<typename Graph, typename OutputIterator> | |
408 | OutputIterator | |
409 | articulation_points(const Graph& g, OutputIterator out) | |
410 | { | |
411 | return biconnected_components(g, dummy_property_map(), out, | |
412 | bgl_named_params<int, buffer_param_t>(0)).second; | |
413 | } | |
414 | ||
415 | } // namespace boost | |
416 | ||
417 | #endif /* BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP */ |