diff -r 000000000000 -r e4d67989cc36 ossrv_pub/boost_apis/boost/graph/biconnected_components.hpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ossrv_pub/boost_apis/boost/graph/biconnected_components.hpp	Tue Feb 02 02:01:42 2010 +0200
@@ -0,0 +1,415 @@
+// 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 */