// Copyright (c) Jeremy Siek 2001
//
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without fee,
// provided that the above copyright notice appears in all copies and
// that both that copyright notice and this permission notice appear
// in supporting documentation.  Silicon Graphics makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied warranty.

// 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 <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)
    {
      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, std::min(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, std::min(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 graph_traits < Graph >::vertex_descriptor vertex_t;
    typedef 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 */
