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