epoc32/include/stdapis/boost/graph/biconnected_components.hpp
branchSymbian2
changeset 2 2fe1408b6811
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/graph/biconnected_components.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,415 @@
     1.4 +// Copyright (c) Jeremy Siek 2001
     1.5 +// Copyright (c) Douglas Gregor 2004
     1.6 +//
     1.7 +// Distributed under the Boost Software License, Version 1.0. (See
     1.8 +// accompanying file LICENSE_1_0.txt or copy at
     1.9 +// http://www.boost.org/LICENSE_1_0.txt)
    1.10 +
    1.11 +// NOTE: this final is generated by libs/graph/doc/biconnected_components.w
    1.12 +
    1.13 +#ifndef BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP
    1.14 +#define BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP
    1.15 +
    1.16 +#include <stack>
    1.17 +#include <vector>
    1.18 +#include <algorithm> // for std::min and std::max
    1.19 +#include <boost/config.hpp>
    1.20 +#include <boost/limits.hpp>
    1.21 +#include <boost/graph/graph_traits.hpp>
    1.22 +#include <boost/graph/graph_concepts.hpp>
    1.23 +#include <boost/property_map.hpp>
    1.24 +#include <boost/graph/depth_first_search.hpp>
    1.25 +#include <boost/graph/graph_utility.hpp>
    1.26 +
    1.27 +namespace boost
    1.28 +{
    1.29 +  namespace detail
    1.30 +  {
    1.31 +    template<typename ComponentMap, typename DiscoverTimeMap,
    1.32 +             typename LowPointMap, typename PredecessorMap,
    1.33 +             typename OutputIterator, typename Stack, 
    1.34 +             typename DFSVisitor>
    1.35 +    struct biconnected_components_visitor : public dfs_visitor<>
    1.36 +    {
    1.37 +      biconnected_components_visitor
    1.38 +        (ComponentMap comp, std::size_t& c, DiscoverTimeMap dtm,
    1.39 +         std::size_t& dfs_time, LowPointMap lowpt, PredecessorMap pred,
    1.40 +         OutputIterator out, Stack& S, DFSVisitor vis)
    1.41 +          : comp(comp), c(c), dtm(dtm), dfs_time(dfs_time), lowpt(lowpt),
    1.42 +            pred(pred), out(out), S(S), vis(vis) { }
    1.43 +
    1.44 +      template <typename Vertex, typename Graph>
    1.45 +      void initialize_vertex(const Vertex& u, Graph& g)
    1.46 +      {
    1.47 +        vis.initialize_vertex(u, g);
    1.48 +      }
    1.49 +
    1.50 +      template <typename Vertex, typename Graph>
    1.51 +      void start_vertex(const Vertex& u, Graph& g)
    1.52 +      {
    1.53 +        put(pred, u, u);
    1.54 +        vis.start_vertex(u, g);
    1.55 +      }
    1.56 +
    1.57 +      template <typename Vertex, typename Graph>
    1.58 +      void discover_vertex(const Vertex& u, Graph& g)
    1.59 +      {
    1.60 +        put(dtm, u, ++dfs_time);
    1.61 +        put(lowpt, u, get(dtm, u));
    1.62 +        vis.discover_vertex(u, g);
    1.63 +      }
    1.64 +
    1.65 +      template <typename Edge, typename Graph>
    1.66 +      void examine_edge(const Edge& e, Graph& g)
    1.67 +      {
    1.68 +        vis.examine_edge(e, g);
    1.69 +      }
    1.70 +
    1.71 +      template <typename Edge, typename Graph>
    1.72 +      void tree_edge(const Edge& e, Graph& g)
    1.73 +      {
    1.74 +        S.push(e);
    1.75 +        put(pred, target(e, g), source(e, g));
    1.76 +        vis.tree_edge(e, g);
    1.77 +      }
    1.78 +
    1.79 +      template <typename Edge, typename Graph>
    1.80 +      void back_edge(const Edge& e, Graph& g)
    1.81 +      {
    1.82 +        BOOST_USING_STD_MIN();
    1.83 +
    1.84 +        if ( target(e, g) != get(pred, source(e, g)) ) {
    1.85 +          S.push(e);
    1.86 +          put(lowpt, source(e, g),
    1.87 +              min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, source(e, g)),
    1.88 +                                                   get(dtm, target(e, g))));
    1.89 +        vis.back_edge(e, g);
    1.90 +      }
    1.91 +      }
    1.92 +
    1.93 +      template <typename Edge, typename Graph>
    1.94 +      void forward_or_cross_edge(const Edge& e, Graph& g)
    1.95 +      {
    1.96 +        vis.forward_or_cross_edge(e, g);
    1.97 +      }
    1.98 +
    1.99 +      template <typename Vertex, typename Graph>
   1.100 +      void finish_vertex(const Vertex& u, Graph& g)
   1.101 +      {
   1.102 +        BOOST_USING_STD_MIN();
   1.103 +        Vertex parent = get(pred, u);
   1.104 +        const std::size_t dtm_of_dubious_parent = get(dtm, parent);
   1.105 +        bool is_art_point = false;
   1.106 +        if ( dtm_of_dubious_parent > get(dtm, u) ) {
   1.107 +          parent = get(pred, parent);
   1.108 +          is_art_point = true;
   1.109 +          put(pred, get(pred, u), u);
   1.110 +          put(pred, u, parent);
   1.111 +        }
   1.112 +
   1.113 +        if ( parent == u ) { // at top
   1.114 +          if ( get(dtm, u) + 1 == dtm_of_dubious_parent )
   1.115 +            is_art_point = false;
   1.116 +        } else {
   1.117 +          put(lowpt, parent,
   1.118 +              min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, parent),
   1.119 +                                                   get(lowpt, u)));
   1.120 +
   1.121 +          if (get(lowpt, u) >= get(dtm, parent)) {
   1.122 +            if ( get(dtm, parent) > get(dtm, get(pred, parent)) ) {
   1.123 +              put(pred, u, get(pred, parent));
   1.124 +              put(pred, parent, u);
   1.125 +            }
   1.126 +
   1.127 +            while ( get(dtm, source(S.top(), g)) >= get(dtm, u) ) {
   1.128 +              put(comp, S.top(), c);
   1.129 +              S.pop();
   1.130 +            }
   1.131 +            put(comp, S.top(), c);
   1.132 +              S.pop();
   1.133 +            ++c;
   1.134 +            if ( S.empty() ) {
   1.135 +              put(pred, u, parent);
   1.136 +              put(pred, parent, u);
   1.137 +            }
   1.138 +          }
   1.139 +        }
   1.140 +        if ( is_art_point )
   1.141 +          *out++ = u;
   1.142 +        vis.finish_vertex(u, g);
   1.143 +      }
   1.144 +
   1.145 +      ComponentMap comp;
   1.146 +      std::size_t& c;
   1.147 +      DiscoverTimeMap dtm;
   1.148 +      std::size_t& dfs_time;
   1.149 +      LowPointMap lowpt;
   1.150 +      PredecessorMap pred;
   1.151 +      OutputIterator out;
   1.152 +      Stack& S;
   1.153 +      DFSVisitor vis;
   1.154 +    };
   1.155 +
   1.156 +  template<typename Graph, typename ComponentMap, typename OutputIterator,
   1.157 +        typename VertexIndexMap, typename DiscoverTimeMap, typename LowPointMap,
   1.158 +        typename PredecessorMap, typename DFSVisitor>
   1.159 +  std::pair<std::size_t, OutputIterator>
   1.160 +    biconnected_components_impl(const Graph & g, ComponentMap comp,
   1.161 +        OutputIterator out, VertexIndexMap index_map, DiscoverTimeMap dtm,
   1.162 +        LowPointMap lowpt, PredecessorMap pred, DFSVisitor dfs_vis)
   1.163 +  {
   1.164 +    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
   1.165 +    typedef typename graph_traits<Graph>::edge_descriptor edge_t;
   1.166 +    function_requires<VertexListGraphConcept<Graph> >();
   1.167 +    function_requires<IncidenceGraphConcept<Graph> >();
   1.168 +    function_requires<WritablePropertyMapConcept<ComponentMap, edge_t> >();
   1.169 +    function_requires<ReadWritePropertyMapConcept<DiscoverTimeMap,
   1.170 +                                                  vertex_t> >();
   1.171 +    function_requires<ReadWritePropertyMapConcept<LowPointMap, vertex_t > >();
   1.172 +    function_requires<ReadWritePropertyMapConcept<PredecessorMap,
   1.173 +                                                  vertex_t> >();
   1.174 +
   1.175 +    std::size_t num_components = 0;
   1.176 +    std::size_t dfs_time = 0;
   1.177 +      std::stack<edge_t> S;
   1.178 +
   1.179 +      biconnected_components_visitor<ComponentMap, DiscoverTimeMap,
   1.180 +          LowPointMap, PredecessorMap, OutputIterator, std::stack<edge_t>, 
   1.181 +          DFSVisitor>
   1.182 +      vis(comp, num_components, dtm, dfs_time, lowpt, pred, out, 
   1.183 +          S, dfs_vis);
   1.184 +
   1.185 +    depth_first_search(g, visitor(vis).vertex_index_map(index_map));
   1.186 +
   1.187 +    return std::pair<std::size_t, OutputIterator>(num_components, vis.out);
   1.188 +  }
   1.189 +
   1.190 +    template <typename PredecessorMap>
   1.191 +    struct bicomp_dispatch3
   1.192 +    {
   1.193 +  template<typename Graph, typename ComponentMap, typename OutputIterator,
   1.194 +                typename VertexIndexMap, typename DiscoverTimeMap, 
   1.195 +                typename LowPointMap, class P, class T, class R>
   1.196 +      static std::pair<std::size_t, OutputIterator> apply (const Graph & g, 
   1.197 +          ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 
   1.198 +          DiscoverTimeMap dtm, LowPointMap lowpt, 
   1.199 +          const bgl_named_params<P, T, R>& params, PredecessorMap pred)
   1.200 +      {
   1.201 +        return biconnected_components_impl
   1.202 +                (g, comp, out, index_map, dtm, lowpt, pred,
   1.203 +                 choose_param(get_param(params, graph_visitor),
   1.204 +                    make_dfs_visitor(null_visitor())));
   1.205 +      }
   1.206 +    };
   1.207 +    
   1.208 +    template <>
   1.209 +    struct bicomp_dispatch3<error_property_not_found>
   1.210 +    {
   1.211 +      template<typename Graph, typename ComponentMap, typename OutputIterator,
   1.212 +                typename VertexIndexMap, typename DiscoverTimeMap, 
   1.213 +                typename LowPointMap, class P, class T, class R>
   1.214 +      static std::pair<std::size_t, OutputIterator> apply (const Graph & g, 
   1.215 +          ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 
   1.216 +          DiscoverTimeMap dtm, LowPointMap lowpt, 
   1.217 +          const bgl_named_params<P, T, R>& params, 
   1.218 +          error_property_not_found)
   1.219 +  {
   1.220 +    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
   1.221 +    std::vector<vertex_t> pred(num_vertices(g));
   1.222 +    vertex_t vert = graph_traits<Graph>::null_vertex();
   1.223 +
   1.224 +        return biconnected_components_impl
   1.225 +                (g, comp, out, index_map, dtm, lowpt, 
   1.226 +              make_iterator_property_map(pred.begin(), index_map, vert),
   1.227 +                 choose_param(get_param(params, graph_visitor),
   1.228 +                    make_dfs_visitor(null_visitor())));
   1.229 +  }
   1.230 +    };
   1.231 +
   1.232 +    template <typename LowPointMap>
   1.233 +    struct bicomp_dispatch2
   1.234 +    {
   1.235 +  template<typename Graph, typename ComponentMap, typename OutputIterator,
   1.236 +                typename VertexIndexMap, typename DiscoverTimeMap, 
   1.237 +                typename P, typename T, typename R>
   1.238 +      static std::pair<std::size_t, OutputIterator> apply (const Graph& g, 
   1.239 +          ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 
   1.240 +          DiscoverTimeMap dtm, const bgl_named_params<P, T, R>& params, 
   1.241 +          LowPointMap lowpt)
   1.242 +      {
   1.243 +        typedef typename property_value< bgl_named_params<P,T,R>,
   1.244 +            vertex_predecessor_t>::type dispatch_type;
   1.245 +
   1.246 +        return bicomp_dispatch3<dispatch_type>::apply
   1.247 +            (g, comp, out, index_map, dtm, lowpt, params, 
   1.248 +             get_param(params, vertex_predecessor));
   1.249 +      }
   1.250 +    };
   1.251 +
   1.252 +
   1.253 +    template <>
   1.254 +    struct bicomp_dispatch2<error_property_not_found>
   1.255 +    {
   1.256 +      template<typename Graph, typename ComponentMap, typename OutputIterator,
   1.257 +                typename VertexIndexMap, typename DiscoverTimeMap, 
   1.258 +                typename P, typename T, typename R>
   1.259 +      static std::pair<std::size_t, OutputIterator> apply (const Graph& g, 
   1.260 +          ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 
   1.261 +          DiscoverTimeMap dtm, const bgl_named_params<P, T, R>& params, 
   1.262 +          error_property_not_found)
   1.263 +  {
   1.264 +    typedef typename graph_traits<Graph>::vertices_size_type
   1.265 +      vertices_size_type;
   1.266 +    std::vector<vertices_size_type> lowpt(num_vertices(g));
   1.267 +        vertices_size_type vst(0);
   1.268 +
   1.269 +        typedef typename property_value< bgl_named_params<P,T,R>,
   1.270 +            vertex_predecessor_t>::type dispatch_type;
   1.271 +  
   1.272 +        return bicomp_dispatch3<dispatch_type>::apply
   1.273 +            (g, comp, out, index_map, dtm,
   1.274 +             make_iterator_property_map(lowpt.begin(), index_map, vst),
   1.275 +             params, get_param(params, vertex_predecessor));
   1.276 +      }
   1.277 +    };
   1.278 +
   1.279 +    template <typename DiscoverTimeMap>
   1.280 +    struct bicomp_dispatch1
   1.281 +    {
   1.282 +      template<typename Graph, typename ComponentMap, typename OutputIterator,
   1.283 +                typename VertexIndexMap, class P, class T, class R>
   1.284 +      static std::pair<std::size_t, OutputIterator> apply(const Graph& g, 
   1.285 +          ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 
   1.286 +          const bgl_named_params<P, T, R>& params, DiscoverTimeMap dtm)
   1.287 +      {
   1.288 +        typedef typename property_value< bgl_named_params<P,T,R>,
   1.289 +            vertex_lowpoint_t>::type dispatch_type;
   1.290 +
   1.291 +        return bicomp_dispatch2<dispatch_type>::apply
   1.292 +            (g, comp, out, index_map, dtm, params, 
   1.293 +             get_param(params, vertex_lowpoint));
   1.294 +      }
   1.295 +    };
   1.296 +
   1.297 +    template <>
   1.298 +    struct bicomp_dispatch1<error_property_not_found>
   1.299 +    {
   1.300 +      template<typename Graph, typename ComponentMap, typename OutputIterator,
   1.301 +                typename VertexIndexMap, class P, class T, class R>
   1.302 +      static std::pair<std::size_t, OutputIterator> apply(const Graph& g, 
   1.303 +          ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 
   1.304 +          const bgl_named_params<P, T, R>& params, error_property_not_found)
   1.305 +      {
   1.306 +        typedef typename graph_traits<Graph>::vertices_size_type
   1.307 +            vertices_size_type;
   1.308 +        std::vector<vertices_size_type> discover_time(num_vertices(g));
   1.309 +    vertices_size_type vst(0);
   1.310 +
   1.311 +        typedef typename property_value< bgl_named_params<P,T,R>,
   1.312 +            vertex_lowpoint_t>::type dispatch_type;
   1.313 +
   1.314 +        return bicomp_dispatch2<dispatch_type>::apply
   1.315 +            (g, comp, out, index_map, 
   1.316 +              make_iterator_property_map(discover_time.begin(), index_map, vst),
   1.317 +             params, get_param(params, vertex_lowpoint));
   1.318 +      }
   1.319 +    };
   1.320 +
   1.321 +  }
   1.322 +
   1.323 +  template<typename Graph, typename ComponentMap, typename OutputIterator,
   1.324 +      typename DiscoverTimeMap, typename LowPointMap>
   1.325 +  std::pair<std::size_t, OutputIterator>
   1.326 +  biconnected_components(const Graph& g, ComponentMap comp, 
   1.327 +      OutputIterator out, DiscoverTimeMap dtm, LowPointMap lowpt)
   1.328 +  {
   1.329 +    typedef detail::error_property_not_found dispatch_type;
   1.330 +
   1.331 +    return detail::bicomp_dispatch3<dispatch_type>::apply
   1.332 +            (g, comp, out, 
   1.333 +             get(vertex_index, g), 
   1.334 +             dtm, lowpt, 
   1.335 +             bgl_named_params<int, buffer_param_t>(0), 
   1.336 +             detail::error_property_not_found());
   1.337 +  }
   1.338 +
   1.339 +  template <typename Graph, typename ComponentMap, typename OutputIterator,
   1.340 +      typename P, typename T, typename R>
   1.341 +  std::pair<std::size_t, OutputIterator>
   1.342 +  biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, 
   1.343 +      const bgl_named_params<P, T, R>& params)
   1.344 +  {
   1.345 +    typedef typename property_value< bgl_named_params<P,T,R>,
   1.346 +        vertex_discover_time_t>::type dispatch_type;
   1.347 +
   1.348 +    return detail::bicomp_dispatch1<dispatch_type>::apply(g, comp, out, 
   1.349 +        choose_const_pmap(get_param(params, vertex_index), g, vertex_index), 
   1.350 +        params, get_param(params, vertex_discover_time));
   1.351 +  }
   1.352 +
   1.353 +  template < typename Graph, typename ComponentMap, typename OutputIterator>
   1.354 +  std::pair<std::size_t, OutputIterator>
   1.355 +  biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out)
   1.356 +  {
   1.357 +    return biconnected_components(g, comp, out,  
   1.358 +        bgl_named_params<int, buffer_param_t>(0));
   1.359 +  }
   1.360 +
   1.361 +  namespace graph_detail {
   1.362 +    struct dummy_output_iterator
   1.363 +    {
   1.364 +      typedef std::output_iterator_tag iterator_category;
   1.365 +      typedef void value_type;
   1.366 +      typedef void pointer;
   1.367 +      typedef void difference_type;
   1.368 +
   1.369 +      struct reference {
   1.370 +        template<typename T>
   1.371 +        reference& operator=(const T&) { return *this; }
   1.372 +      };
   1.373 +
   1.374 +      reference operator*() const { return reference(); }
   1.375 +      dummy_output_iterator& operator++() { return *this; }
   1.376 +      dummy_output_iterator operator++(int) { return *this; }
   1.377 +    };
   1.378 +  } // end namespace graph_detail
   1.379 +
   1.380 +  template <typename Graph, typename ComponentMap,
   1.381 +      typename P, typename T, typename R>
   1.382 +  std::size_t
   1.383 +  biconnected_components(const Graph& g, ComponentMap comp, 
   1.384 +      const bgl_named_params<P, T, R>& params)
   1.385 +  {
   1.386 +    return biconnected_components(g, comp,
   1.387 +        graph_detail::dummy_output_iterator(), params).first;
   1.388 +  }
   1.389 +
   1.390 +  template <typename Graph, typename ComponentMap>
   1.391 +  std::size_t
   1.392 +  biconnected_components(const Graph& g, ComponentMap comp)
   1.393 +  {
   1.394 +    return biconnected_components(g, comp,
   1.395 +                                  graph_detail::dummy_output_iterator()).first;
   1.396 +  }
   1.397 +
   1.398 +  template<typename Graph, typename OutputIterator, 
   1.399 +      typename P, typename T, typename R>
   1.400 +  OutputIterator
   1.401 +  articulation_points(const Graph& g, OutputIterator out, 
   1.402 +      const bgl_named_params<P, T, R>& params)
   1.403 +  {
   1.404 +    return biconnected_components(g, dummy_property_map(), out, 
   1.405 +        params).second;
   1.406 +  }
   1.407 +
   1.408 +  template<typename Graph, typename OutputIterator>
   1.409 +  OutputIterator
   1.410 +  articulation_points(const Graph& g, OutputIterator out)
   1.411 +  {
   1.412 +    return biconnected_components(g, dummy_property_map(), out, 
   1.413 +        bgl_named_params<int, buffer_param_t>(0)).second;
   1.414 +  }
   1.415 +
   1.416 +}                               // namespace boost
   1.417 +
   1.418 +#endif  /* BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP */