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.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 */