// Copyright (c) Jeremy Siek 2001

// Copyright (c) Douglas Gregor 2004

//

// 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 <vector>

#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>

#include <boost/graph/depth_first_search.hpp>

#include <boost/graph/graph_utility.hpp>

namespace boost

{

  namespace detail

  {

    template<typename ComponentMap, typename DiscoverTimeMap,

             typename LowPointMap, typename PredecessorMap,

             typename OutputIterator, typename Stack, 

             typename DFSVisitor>

    struct biconnected_components_visitor : public dfs_visitor<>

    {

      biconnected_components_visitor

        (ComponentMap comp, std::size_t& c, DiscoverTimeMap dtm,

         std::size_t& dfs_time, LowPointMap lowpt, PredecessorMap pred,

         OutputIterator out, Stack& S, DFSVisitor vis)

          : comp(comp), c(c), dtm(dtm), dfs_time(dfs_time), lowpt(lowpt),

            pred(pred), out(out), S(S), vis(vis) { }

      template <typename Vertex, typename Graph>

      void initialize_vertex(const Vertex& u, Graph& g)

      {

        vis.initialize_vertex(u, g);

      }

      template <typename Vertex, typename Graph>

      void start_vertex(const Vertex& u, Graph& g)

      {

        put(pred, u, u);

        vis.start_vertex(u, g);

      }

      template <typename Vertex, typename Graph>

      void discover_vertex(const Vertex& u, Graph& g)

      {

        put(dtm, u, ++dfs_time);

        put(lowpt, u, get(dtm, u));

        vis.discover_vertex(u, g);

      }

      template <typename Edge, typename Graph>

      void examine_edge(const Edge& e, Graph& g)

      {

        vis.examine_edge(e, g);

      }

      template <typename Edge, typename Graph>

      void tree_edge(const Edge& e, Graph& g)

      {

        S.push(e);

        put(pred, target(e, g), source(e, g));

        vis.tree_edge(e, g);

      }

      template <typename Edge, typename Graph>

      void back_edge(const Edge& e, Graph& g)

      {

        BOOST_USING_STD_MIN();

        if ( target(e, g) != get(pred, source(e, g)) ) {

          S.push(e);

          put(lowpt, source(e, g),

              min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, source(e, g)),

                                                   get(dtm, target(e, g))));

        vis.back_edge(e, g);

      }

      }

      template <typename Edge, typename Graph>

      void forward_or_cross_edge(const Edge& e, Graph& g)

      {

        vis.forward_or_cross_edge(e, g);

      }

      template <typename Vertex, typename Graph>

      void finish_vertex(const Vertex& u, Graph& g)

      {

        BOOST_USING_STD_MIN();

        Vertex parent = get(pred, u);

        const std::size_t dtm_of_dubious_parent = get(dtm, parent);

        bool is_art_point = false;

        if ( dtm_of_dubious_parent > get(dtm, u) ) {

          parent = get(pred, parent);

          is_art_point = true;

          put(pred, get(pred, u), u);

          put(pred, u, parent);

        }

        if ( parent == u ) { // at top

          if ( get(dtm, u) + 1 == dtm_of_dubious_parent )

            is_art_point = false;

        } else {

          put(lowpt, parent,

              min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, parent),

                                                   get(lowpt, u)));

          if (get(lowpt, u) >= get(dtm, parent)) {

            if ( get(dtm, parent) > get(dtm, get(pred, parent)) ) {

              put(pred, u, get(pred, parent));

              put(pred, parent, u);

            }

            while ( get(dtm, source(S.top(), g)) >= get(dtm, u) ) {

              put(comp, S.top(), c);

              S.pop();

            }

            put(comp, S.top(), c);

              S.pop();

            ++c;

            if ( S.empty() ) {

              put(pred, u, parent);

              put(pred, parent, u);

            }

          }

        }

        if ( is_art_point )

          *out++ = u;

        vis.finish_vertex(u, g);

      }

      ComponentMap comp;

      std::size_t& c;

      DiscoverTimeMap dtm;

      std::size_t& dfs_time;

      LowPointMap lowpt;

      PredecessorMap pred;

      OutputIterator out;

      Stack& S;

      DFSVisitor vis;

    };

  template<typename Graph, typename ComponentMap, typename OutputIterator,

        typename VertexIndexMap, typename DiscoverTimeMap, typename LowPointMap,

        typename PredecessorMap, typename DFSVisitor>

  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)

  {

    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 > >();

    function_requires<ReadWritePropertyMapConcept<PredecessorMap,

                                                  vertex_t> >();

    std::size_t num_components = 0;

    std::size_t dfs_time = 0;

      std::stack<edge_t> S;

      biconnected_components_visitor<ComponentMap, DiscoverTimeMap,

          LowPointMap, PredecessorMap, OutputIterator, std::stack<edge_t>, 

          DFSVisitor>

      vis(comp, num_components, dtm, dfs_time, lowpt, pred, out, 

          S, dfs_vis);

    depth_first_search(g, visitor(vis).vertex_index_map(index_map));

    return std::pair<std::size_t, OutputIterator>(num_components, vis.out);

  }

    template <typename PredecessorMap>

    struct bicomp_dispatch3

    {

  template<typename Graph, typename ComponentMap, typename OutputIterator,

                typename VertexIndexMap, typename DiscoverTimeMap, 

                typename LowPointMap, class P, class T, class R>

      static std::pair<std::size_t, OutputIterator> apply (const Graph & g, 

          ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 

          DiscoverTimeMap dtm, LowPointMap lowpt, 

          const bgl_named_params<P, T, R>& params, PredecessorMap pred)

      {

        return biconnected_components_impl

                (g, comp, out, index_map, dtm, lowpt, pred,

                 choose_param(get_param(params, graph_visitor),

                    make_dfs_visitor(null_visitor())));

      }

    };

    template <>

    struct bicomp_dispatch3<error_property_not_found>

    {

      template<typename Graph, typename ComponentMap, typename OutputIterator,

                typename VertexIndexMap, typename DiscoverTimeMap, 

                typename LowPointMap, class P, class T, class R>

      static std::pair<std::size_t, OutputIterator> apply (const Graph & g, 

          ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 

          DiscoverTimeMap dtm, LowPointMap lowpt, 

          const bgl_named_params<P, T, R>& params, 

          error_property_not_found)

  {

    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;

    std::vector<vertex_t> pred(num_vertices(g));

    vertex_t vert = graph_traits<Graph>::null_vertex();

        return biconnected_components_impl

                (g, comp, out, index_map, dtm, lowpt, 

              make_iterator_property_map(pred.begin(), index_map, vert),

                 choose_param(get_param(params, graph_visitor),

                    make_dfs_visitor(null_visitor())));

  }

    };

    template <typename LowPointMap>

    struct bicomp_dispatch2

    {

  template<typename Graph, typename ComponentMap, typename OutputIterator,

                typename VertexIndexMap, typename DiscoverTimeMap, 

                typename P, typename T, typename R>

      static std::pair<std::size_t, OutputIterator> apply (const Graph& g, 

          ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 

          DiscoverTimeMap dtm, const bgl_named_params<P, T, R>& params, 

          LowPointMap lowpt)

      {

        typedef typename property_value< bgl_named_params<P,T,R>,

            vertex_predecessor_t>::type dispatch_type;

        return bicomp_dispatch3<dispatch_type>::apply

            (g, comp, out, index_map, dtm, lowpt, params, 

             get_param(params, vertex_predecessor));

      }

    };

    template <>

    struct bicomp_dispatch2<error_property_not_found>

    {

      template<typename Graph, typename ComponentMap, typename OutputIterator,

                typename VertexIndexMap, typename DiscoverTimeMap, 

                typename P, typename T, typename R>

      static std::pair<std::size_t, OutputIterator> apply (const Graph& g, 

          ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 

          DiscoverTimeMap dtm, const bgl_named_params<P, T, R>& params, 

          error_property_not_found)

  {

    typedef typename graph_traits<Graph>::vertices_size_type

      vertices_size_type;

    std::vector<vertices_size_type> lowpt(num_vertices(g));

        vertices_size_type vst(0);

        typedef typename property_value< bgl_named_params<P,T,R>,

            vertex_predecessor_t>::type dispatch_type;

        return bicomp_dispatch3<dispatch_type>::apply

            (g, comp, out, index_map, dtm,

             make_iterator_property_map(lowpt.begin(), index_map, vst),

             params, get_param(params, vertex_predecessor));

      }

    };

    template <typename DiscoverTimeMap>

    struct bicomp_dispatch1

    {

      template<typename Graph, typename ComponentMap, typename OutputIterator,

                typename VertexIndexMap, class P, class T, class R>

      static std::pair<std::size_t, OutputIterator> apply(const Graph& g, 

          ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 

          const bgl_named_params<P, T, R>& params, DiscoverTimeMap dtm)

      {

        typedef typename property_value< bgl_named_params<P,T,R>,

            vertex_lowpoint_t>::type dispatch_type;

        return bicomp_dispatch2<dispatch_type>::apply

            (g, comp, out, index_map, dtm, params, 

             get_param(params, vertex_lowpoint));

      }

    };

    template <>

    struct bicomp_dispatch1<error_property_not_found>

    {

      template<typename Graph, typename ComponentMap, typename OutputIterator,

                typename VertexIndexMap, class P, class T, class R>

      static std::pair<std::size_t, OutputIterator> apply(const Graph& g, 

          ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 

          const bgl_named_params<P, T, R>& params, error_property_not_found)

      {

        typedef typename graph_traits<Graph>::vertices_size_type

            vertices_size_type;

        std::vector<vertices_size_type> discover_time(num_vertices(g));

    vertices_size_type vst(0);

        typedef typename property_value< bgl_named_params<P,T,R>,

            vertex_lowpoint_t>::type dispatch_type;

        return bicomp_dispatch2<dispatch_type>::apply

            (g, comp, out, index_map, 

              make_iterator_property_map(discover_time.begin(), index_map, vst),

             params, get_param(params, vertex_lowpoint));

      }

    };

  }

  template<typename Graph, typename ComponentMap, typename OutputIterator,

      typename DiscoverTimeMap, typename LowPointMap>

  std::pair<std::size_t, OutputIterator>

  biconnected_components(const Graph& g, ComponentMap comp, 

      OutputIterator out, DiscoverTimeMap dtm, LowPointMap lowpt)

  {

    typedef detail::error_property_not_found dispatch_type;

    return detail::bicomp_dispatch3<dispatch_type>::apply

            (g, comp, out, 

             get(vertex_index, g), 

             dtm, lowpt, 

             bgl_named_params<int, buffer_param_t>(0), 

             detail::error_property_not_found());

  }

  template <typename Graph, typename ComponentMap, typename OutputIterator,

      typename P, typename T, typename R>

  std::pair<std::size_t, OutputIterator>

  biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, 

      const bgl_named_params<P, T, R>& params)

  {

    typedef typename property_value< bgl_named_params<P,T,R>,

        vertex_discover_time_t>::type dispatch_type;

    return detail::bicomp_dispatch1<dispatch_type>::apply(g, comp, out, 

        choose_const_pmap(get_param(params, vertex_index), g, vertex_index), 

        params, get_param(params, vertex_discover_time));

  }

  template < typename Graph, typename ComponentMap, typename OutputIterator>

  std::pair<std::size_t, OutputIterator>

  biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out)

  {

    return biconnected_components(g, comp, out,  

        bgl_named_params<int, buffer_param_t>(0));

  }

  namespace graph_detail {

    struct dummy_output_iterator

    {

      typedef std::output_iterator_tag iterator_category;

      typedef void value_type;

      typedef void pointer;

      typedef void difference_type;

      struct reference {

        template<typename T>

        reference& operator=(const T&) { return *this; }

      };

      reference operator*() const { return reference(); }

      dummy_output_iterator& operator++() { return *this; }

      dummy_output_iterator operator++(int) { return *this; }

    };

  } // end namespace graph_detail

  template <typename Graph, typename ComponentMap,

      typename P, typename T, typename R>

  std::size_t

  biconnected_components(const Graph& g, ComponentMap comp, 

      const bgl_named_params<P, T, R>& params)

  {

    return biconnected_components(g, comp,

        graph_detail::dummy_output_iterator(), params).first;

  }

  template <typename Graph, typename ComponentMap>

  std::size_t

  biconnected_components(const Graph& g, ComponentMap comp)

  {

    return biconnected_components(g, comp,

                                  graph_detail::dummy_output_iterator()).first;

  }

  template<typename Graph, typename OutputIterator, 

      typename P, typename T, typename R>

  OutputIterator

  articulation_points(const Graph& g, OutputIterator out, 

      const bgl_named_params<P, T, R>& params)

  {

    return biconnected_components(g, dummy_property_map(), out, 

        params).second;

  }

  template<typename Graph, typename OutputIterator>

  OutputIterator

  articulation_points(const Graph& g, OutputIterator out)

  {

    return biconnected_components(g, dummy_property_map(), out, 

        bgl_named_params<int, buffer_param_t>(0)).second;

  }

}                               // namespace boost

#endif  /* BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP */