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 { biconnected_components_visitorboost::detail::biconnected_components_visitor37 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> initialize_vertexboost::detail::biconnected_components_visitor51 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> start_vertexboost::detail::biconnected_components_visitor58 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> discover_vertexboost::detail::biconnected_components_visitor65 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> examine_edgeboost::detail::biconnected_components_visitor73 void examine_edge(const Edge& e, Graph& g) 74 { 75 vis.examine_edge(e, g); 76 } 77 78 template <typename Edge, typename Graph> tree_edgeboost::detail::biconnected_components_visitor79 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> back_edgeboost::detail::biconnected_components_visitor93 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> forward_or_cross_edgeboost::detail::biconnected_components_visitor109 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> finish_vertexboost::detail::biconnected_components_visitor115 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> biconnected_components_impl(const Graph & g,ComponentMap comp,OutputIterator out,VertexIndexMap index_map,DiscoverTimeMap dtm,LowPointMap lowpt,PredecessorMap pred,DFSVisitor dfs_vis)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> applyboost::detail::bicomp_dispatch3200 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> applyboost::detail::bicomp_dispatch3218 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> applyboost::detail::bicomp_dispatch2242 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> applyboost::detail::bicomp_dispatch2262 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> applyboost::detail::bicomp_dispatch1286 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> applyboost::detail::bicomp_dispatch1303 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> biconnected_components(const Graph & g,ComponentMap comp,OutputIterator out,DiscoverTimeMap dtm,LowPointMap lowpt)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> biconnected_components(const Graph & g,ComponentMap comp,OutputIterator out,const bgl_named_params<P,T,R> & params)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> biconnected_components(const Graph & g,ComponentMap comp,OutputIterator out)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> operator =boost::graph_detail::dummy_output_iterator::reference370 reference& operator=(const T&) { return *this; } 371 }; 372 operator *boost::graph_detail::dummy_output_iterator373 reference operator*() const { return reference(); } operator ++boost::graph_detail::dummy_output_iterator374 dummy_output_iterator& operator++() { return *this; } operator ++boost::graph_detail::dummy_output_iterator375 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 biconnected_components(const Graph & g,ComponentMap comp,const bgl_named_params<P,T,R> & params)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 biconnected_components(const Graph & g,ComponentMap comp)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 articulation_points(const Graph & g,OutputIterator out)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 */ 418