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

//======================================================================= // Copyright 2002 Indiana University. // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek // // 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) //======================================================================= #ifndef BOOST_GRAPH_DETAIL_INCREMENTAL_COMPONENTS_HPP #define BOOST_GRAPH_DETAIL_INCREMENTAL_COMPONENTS_HPP #include <boost/operators.hpp> #include <boost/pending/disjoint_sets.hpp> namespace boost { namespace detail { //========================================================================= // Implementation detail of incremental_components //------------------------------------------------------------------------- // Helper functions for the component_index class // Record the representative vertices in the header array. // Representative vertices now point to the component number. template <class Parent, class OutputIterator, class Integer> inline void build_components_header(Parent p, OutputIterator header, Integer num_nodes) { Parent component = p; Integer component_num = 0; for (Integer v = 0; v != num_nodes; ++v) if (p[v] == v) { *header++ = v; component[v] = component_num++; } } // Pushes x onto the front of the list. The list is represented in // an array. template <class Next, class T, class V> inline void array_push_front(Next next, T& head, V x) { T tmp = head; head = x; next[x] = tmp; } // Create a linked list of the vertices in each component // by reusing the representative array. template <class Parent1, class Parent2, class Integer> void link_components(Parent1 component, Parent2 header, Integer num_nodes, Integer num_components) { // Make the non-representative vertices point to their component Parent1 representative = component; for (Integer v = 0; v != num_nodes; ++v) if (component[v] >= num_components || header[component[v]] != v) component[v] = component[representative[v]]; // initialize the "head" of the lists to "NULL" std::fill_n(header, num_components, num_nodes); // Add each vertex to the linked list for its component Parent1 next = component; for (Integer k = 0; k != num_nodes; ++k) array_push_front(next, header[component[k]], k); } template <class IndexContainer, class HeaderContainer> void construct_component_index(IndexContainer& index, HeaderContainer& header) { typedef typename IndexContainer::value_type Integer; build_components_header(index.begin(), std::back_inserter(header), Integer(index.end() - index.begin())); link_components(index.begin(), header.begin(), Integer(index.end() - index.begin()), Integer(header.end() - header.begin())); } template <class IndexIterator, class Integer, class Distance> class component_iterator : boost::forward_iterator_helper< component_iterator<IndexIterator,Integer,Distance>, Integer, Distance,Integer*, Integer&> { public: typedef component_iterator self; IndexIterator next; Integer node; typedef std::forward_iterator_tag iterator_category; typedef Integer value_type; typedef Integer& reference; typedef Integer* pointer; typedef Distance difference_type; component_iterator() {} component_iterator(IndexIterator x, Integer i) : next(x), node(i) {} Integer operator*() const { return node; } self& operator++() { node = next[node]; return *this; } }; template <class IndexIterator, class Integer, class Distance> inline bool operator==(const component_iterator<IndexIterator, Integer, Distance>& x, const component_iterator<IndexIterator, Integer, Distance>& y) { return x.node == y.node; } } // namespace detail } // namespace detail #endif // BOOST_GRAPH_DETAIL_INCREMENTAL_COMPONENTS_HPP