Back to home page

EIC code displayed by LXR

 
 

    


File indexing completed on 2025-01-30 09:43:00

0001 //
0002 //=======================================================================
0003 // Copyright 1997-2001 University of Notre Dame.
0004 // Copyright 2009 Trustees of Indiana University.
0005 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Michael Hansen
0006 //
0007 // Distributed under the Boost Software License, Version 1.0. (See
0008 // accompanying file LICENSE_1_0.txt or copy at
0009 // http://www.boost.org/LICENSE_1_0.txt)
0010 //=======================================================================
0011 //
0012 
0013 #ifndef BOOST_INCREMENTAL_COMPONENTS_HPP
0014 #define BOOST_INCREMENTAL_COMPONENTS_HPP
0015 
0016 #include <boost/tuple/tuple.hpp>
0017 #include <boost/graph/detail/incremental_components.hpp>
0018 #include <boost/iterator/counting_iterator.hpp>
0019 #include <boost/smart_ptr/make_shared.hpp>
0020 #include <boost/pending/disjoint_sets.hpp>
0021 #include <iterator>
0022 
0023 namespace boost
0024 {
0025 
0026 // A connected component algorithm for the case when dynamically
0027 // adding (but not removing) edges is common.  The
0028 // incremental_components() function is a preparing operation. Call
0029 // same_component to check whether two vertices are in the same
0030 // component, or use disjoint_set::find_set to determine the
0031 // representative for a vertex.
0032 
0033 // This version of connected components does not require a full
0034 // Graph. Instead, it just needs an edge list, where the vertices of
0035 // each edge need to be of integer type. The edges are assumed to
0036 // be undirected. The other difference is that the result is stored in
0037 // a container, instead of just a decorator.  The container should be
0038 // empty before the algorithm is called. It will grow during the
0039 // course of the algorithm. The container must be a model of
0040 // BackInsertionSequence and RandomAccessContainer
0041 // (std::vector is a good choice). After running the algorithm the
0042 // index container will map each vertex to the representative
0043 // vertex of the component to which it belongs.
0044 //
0045 // Adapted from an implementation by Alex Stepanov. The disjoint
0046 // sets data structure is from Tarjan's "Data Structures and Network
0047 // Algorithms", and the application to connected components is
0048 // similar to the algorithm described in Ch. 22 of "Intro to
0049 // Algorithms" by Cormen, et. all.
0050 //
0051 
0052 // An implementation of disjoint sets can be found in
0053 // boost/pending/disjoint_sets.hpp
0054 
0055 template < class EdgeListGraph, class DisjointSets >
0056 void incremental_components(EdgeListGraph& g, DisjointSets& ds)
0057 {
0058     typename graph_traits< EdgeListGraph >::edge_iterator e, end;
0059     for (boost::tie(e, end) = edges(g); e != end; ++e)
0060         ds.union_set(source(*e, g), target(*e, g));
0061 }
0062 
0063 template < class ParentIterator >
0064 void compress_components(ParentIterator first, ParentIterator last)
0065 {
0066     for (ParentIterator current = first; current != last; ++current)
0067         detail::find_representative_with_full_compression(
0068             first, current - first);
0069 }
0070 
0071 template < class ParentIterator >
0072 typename std::iterator_traits< ParentIterator >::difference_type
0073 component_count(ParentIterator first, ParentIterator last)
0074 {
0075     std::ptrdiff_t count = 0;
0076     for (ParentIterator current = first; current != last; ++current)
0077         if (*current == current - first)
0078             ++count;
0079     return count;
0080 }
0081 
0082 // This algorithm can be applied to the result container of the
0083 // connected_components algorithm to normalize
0084 // the components.
0085 template < class ParentIterator >
0086 void normalize_components(ParentIterator first, ParentIterator last)
0087 {
0088     for (ParentIterator current = first; current != last; ++current)
0089         detail::normalize_node(first, current - first);
0090 }
0091 
0092 template < class VertexListGraph, class DisjointSets >
0093 void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds)
0094 {
0095     typename graph_traits< VertexListGraph >::vertex_iterator v, vend;
0096     for (boost::tie(v, vend) = vertices(G); v != vend; ++v)
0097         ds.make_set(*v);
0098 }
0099 
0100 template < class Vertex, class DisjointSet >
0101 inline bool same_component(Vertex u, Vertex v, DisjointSet& ds)
0102 {
0103     return ds.find_set(u) == ds.find_set(v);
0104 }
0105 
0106 // Class that builds a quick-access indexed linked list that allows
0107 // for fast iterating through a parent component's children.
0108 template < typename IndexType > class component_index
0109 {
0110 
0111 private:
0112     typedef std::vector< IndexType > IndexContainer;
0113 
0114 public:
0115     typedef counting_iterator< IndexType > iterator;
0116     typedef iterator const_iterator;
0117     typedef IndexType value_type;
0118     typedef IndexType size_type;
0119 
0120     typedef detail::component_index_iterator<
0121         typename IndexContainer::iterator >
0122         component_iterator;
0123 
0124 public:
0125     template < typename ParentIterator, typename ElementIndexMap >
0126     component_index(ParentIterator parent_start, ParentIterator parent_end,
0127         const ElementIndexMap& index_map)
0128     : m_num_elements(std::distance(parent_start, parent_end))
0129     , m_components(make_shared< IndexContainer >())
0130     , m_index_list(make_shared< IndexContainer >(m_num_elements))
0131     {
0132 
0133         build_index_lists(parent_start, index_map);
0134 
0135     } // component_index
0136 
0137     template < typename ParentIterator >
0138     component_index(ParentIterator parent_start, ParentIterator parent_end)
0139     : m_num_elements(std::distance(parent_start, parent_end))
0140     , m_components(make_shared< IndexContainer >())
0141     , m_index_list(make_shared< IndexContainer >(m_num_elements))
0142     {
0143 
0144         build_index_lists(parent_start, boost::identity_property_map());
0145 
0146     } // component_index
0147 
0148     // Returns the number of components
0149     inline std::size_t size() const { return (m_components->size()); }
0150 
0151     // Beginning iterator for component indices
0152     iterator begin() const { return (iterator(0)); }
0153 
0154     // End iterator for component indices
0155     iterator end() const { return (iterator(this->size())); }
0156 
0157     // Returns a pair of begin and end iterators for the child
0158     // elements of component [component_index].
0159     std::pair< component_iterator, component_iterator > operator[](
0160         IndexType component_index) const
0161     {
0162 
0163         IndexType first_index = (*m_components)[component_index];
0164 
0165         return (std::make_pair(
0166             component_iterator(m_index_list->begin(), first_index),
0167             component_iterator(m_num_elements)));
0168     }
0169 
0170 private:
0171     template < typename ParentIterator, typename ElementIndexMap >
0172     void build_index_lists(
0173         ParentIterator parent_start, const ElementIndexMap& index_map)
0174     {
0175 
0176         typedef
0177             typename std::iterator_traits< ParentIterator >::value_type Element;
0178         typename IndexContainer::iterator index_list = m_index_list->begin();
0179 
0180         // First pass - find root elements, construct index list
0181         for (IndexType element_index = 0; element_index < m_num_elements;
0182              ++element_index)
0183         {
0184 
0185             Element parent_element = parent_start[element_index];
0186             IndexType parent_index = get(index_map, parent_element);
0187 
0188             if (element_index != parent_index)
0189             {
0190                 index_list[element_index] = parent_index;
0191             }
0192             else
0193             {
0194                 m_components->push_back(element_index);
0195 
0196                 // m_num_elements is the linked list terminator
0197                 index_list[element_index] = m_num_elements;
0198             }
0199         }
0200 
0201         // Second pass - build linked list
0202         for (IndexType element_index = 0; element_index < m_num_elements;
0203              ++element_index)
0204         {
0205 
0206             Element parent_element = parent_start[element_index];
0207             IndexType parent_index = get(index_map, parent_element);
0208 
0209             if (element_index != parent_index)
0210             {
0211 
0212                 // Follow list until a component parent is found
0213                 while (index_list[parent_index] != m_num_elements)
0214                 {
0215                     parent_index = index_list[parent_index];
0216                 }
0217 
0218                 // Push element to the front of the linked list
0219                 index_list[element_index] = index_list[parent_index];
0220                 index_list[parent_index] = element_index;
0221             }
0222         }
0223 
0224     } // build_index_lists
0225 
0226 protected:
0227     IndexType m_num_elements;
0228     shared_ptr< IndexContainer > m_components, m_index_list;
0229 
0230 }; // class component_index
0231 
0232 } // namespace boost
0233 
0234 #endif // BOOST_INCREMENTAL_COMPONENTS_HPP