biconnected_components.hpp

support vector clustering for vc++

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