biconnected_components.hpp

来自「CGAL is a collaborative effort of severa」· HPP 代码 · 共 112 行

// Copyright (c) Jeremy Siek 2001
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

// NOTE: this final is generated by libs/graph/doc/biconnected_components.w

#ifndef BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP
#define BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP

#include <stack>
#include <algorithm> // for std::min and std::max
#include <boost/config.hpp>
#include <boost/limits.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/property_map.hpp>

namespace boost
{
  namespace detail
  {
    template < typename Graph, typename ComponentMap,
      typename DiscoverTimeMap, typename LowPointMap, typename Stack >
      void biconnect(typename graph_traits < Graph >::vertex_descriptor v,
                     typename graph_traits < Graph >::vertex_descriptor u,
                     bool at_top,
                     const Graph & g,
                     ComponentMap comp,
                     std::size_t & c,
                     DiscoverTimeMap d,
                     std::size_t & dfs_time, LowPointMap lowpt, Stack & S)
    {
      BOOST_USING_STD_MIN();
      typedef typename graph_traits < Graph >::vertex_descriptor vertex_t;
      typedef typename property_traits < DiscoverTimeMap >::value_type D;
      D infinity = (std::numeric_limits < D >::max)();
        put(d, v, ++dfs_time);
        put(lowpt, v, get(d, v));
      typename graph_traits < Graph >::out_edge_iterator ei, ei_end;
      for (tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei)
      {
        vertex_t w = target(*ei, g);
        if (get(d, w) == infinity)
        {
          S.push(*ei);
          biconnect(w, v, false, g, comp, c, d, dfs_time, lowpt, S);
          put(lowpt, v, min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, v), get(lowpt, w)));
          if (get(lowpt, w) >= get(d, v))
          {
            while (d[source(S.top(), g)] >= d[w]) {
              put(comp, S.top(), c);
              S.pop();
            }
            put(comp, S.top(), c);
              S.pop();
            ++c;

          }
        } else if (get(d, w) < get(d, v) && (!at_top && w != u))
        {
          S.push(*ei);
          put(lowpt, v, min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, v), get(d, w)));
        }
      }
    }

  }

  template < typename Graph, typename ComponentMap,
    typename DiscoverTimeMap, typename LowPointMap >
    void biconnected_components
    (typename graph_traits < Graph >::vertex_descriptor v,
     typename graph_traits < Graph >::vertex_descriptor u,
     const Graph & g,
     ComponentMap comp,
     std::size_t & num_components,
     DiscoverTimeMap discover_time, LowPointMap lowpt)
  {
    typedef typename graph_traits < Graph >::vertex_descriptor vertex_t;
    typedef typename graph_traits < Graph >::edge_descriptor edge_t;
    function_requires < VertexListGraphConcept < Graph > >();
    function_requires < IncidenceGraphConcept < Graph > >();
    function_requires < WritablePropertyMapConcept < ComponentMap,
      edge_t > >();
    function_requires < ReadWritePropertyMapConcept < DiscoverTimeMap,
      vertex_t > >();
    function_requires < ReadWritePropertyMapConcept < LowPointMap,
      vertex_t > >();

    typedef typename property_traits < DiscoverTimeMap >::value_type D;
    num_components = 0;
    std::size_t dfs_time = 0;
    std::stack < edge_t > S;
    typename graph_traits < Graph >::vertex_iterator wi, wi_end;
    std::size_t infinity = (std::numeric_limits < std::size_t >::max)();
    for (tie(wi, wi_end) = vertices(g); wi != wi_end; ++wi)
      put(discover_time, *wi, infinity);

    for (tie(wi, wi_end) = vertices(g); wi != wi_end; ++wi)
      if (get(discover_time, *wi) == (std::numeric_limits < D >::max)())
        detail::biconnect(*wi, *wi, true,
                          g, comp, num_components,
                          discover_time, dfs_time, lowpt, S);

  }

}                               // namespace boost

#endif  /* BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP */