http://www.ousob.com --- Legacy Redefined OuSob - File: /wwwroot/clipx/usr/include/boost/graph/biconnected_components.hpp

// 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> 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) : comp(comp), c(c), dtm(dtm), dfs_time(dfs_time), lowpt(lowpt), pred(pred), out(out), S(S) { } template <typename Vertex, typename Graph> void start_vertex(const Vertex& u, Graph&) { put(pred, u, u); } template <typename Vertex, typename Graph> void discover_vertex(const Vertex& u, Graph&) { put(dtm, u, ++dfs_time); put(lowpt, u, get(dtm, u)); } template <typename Edge, typename Graph> void tree_edge(const Edge& e, Graph& g) { S.push(e); put(pred, target(e, g), source(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)))); } } template <typename Vertex, typename Graph> void finish_vertex(const Vertex& u, Graph& g) { BOOST_USING_STD_MIN(); Vertex parent = get(pred, u); bool is_art_point = false; if ( get(dtm, parent) > get(dtm, u) ) { parent = get(pred, parent); is_art_point = true; } if ( parent == u ) { // at top if ( get(dtm, u) + 1 == get(dtm, get(pred, u)) ) 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; } ComponentMap comp; std::size_t& c; DiscoverTimeMap dtm; std::size_t& dfs_time; LowPointMap lowpt; PredecessorMap pred; OutputIterator out; Stack& S; }; } // namespace detail template<typename Graph, typename ComponentMap, typename OutputIterator, typename DiscoverTimeMap, typename LowPointMap, typename PredecessorMap, typename VertexIndexMap> std::pair<std::size_t, OutputIterator> biconnected_components(const Graph & g, ComponentMap comp, OutputIterator out, DiscoverTimeMap discover_time, LowPointMap lowpt, PredecessorMap pred, VertexIndexMap index_map) { 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; detail::biconnected_components_visitor<ComponentMap, DiscoverTimeMap, LowPointMap, PredecessorMap, OutputIterator, std::stack<edge_t> > vis(comp, num_components, discover_time, dfs_time, lowpt, pred, out, S); depth_first_search(g, visitor(vis).vertex_index_map(index_map)); return std::pair<std::size_t, OutputIterator>(num_components, vis.out); } template<typename Graph, typename ComponentMap, typename OutputIterator, typename DiscoverTimeMap, typename LowPointMap, typename VertexIndexMap> std::pair<std::size_t, OutputIterator> biconnected_components(const Graph & g, ComponentMap comp, OutputIterator out, DiscoverTimeMap discover_time, LowPointMap lowpt, VertexIndexMap index_map) { 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 (g, comp, out, discover_time, lowpt, make_iterator_property_map(pred.begin(), index_map, vert), index_map); } template<typename Graph, typename ComponentMap, typename OutputIterator, typename VertexIndexMap> std::pair<std::size_t, OutputIterator> biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, VertexIndexMap index_map) { typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type; std::vector<vertices_size_type> discover_time(num_vertices(g)); std::vector<vertices_size_type> lowpt(num_vertices(g)); vertices_size_type vst(0); return biconnected_components (g, comp, out, make_iterator_property_map(discover_time.begin(), index_map, vst), make_iterator_property_map(lowpt.begin(), index_map, vst), index_map); } 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, get(vertex_index, g)); } 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> 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 VertexIndexMap> OutputIterator articulation_points(const Graph& g, OutputIterator out, VertexIndexMap index_map) { return biconnected_components(g, dummy_property_map(), out, index_map).second; } template<typename Graph, typename OutputIterator> OutputIterator articulation_points(const Graph& g, OutputIterator out) { return biconnected_components(g, dummy_property_map(), out, get(vertex_index, g)).second; } } // namespace boost #endif /* BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP */