boost/graph/biconnected_components.hpp

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