EIC code displayed by LXR master/​include/​boost/​pending/​disjoint_sets.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-01-18 09:43:31

 //
 //=======================================================================
 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
 // 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_DISJOINT_SETS_HPP
 #define BOOST_DISJOINT_SETS_HPP
 
 #include <vector>
 #include <boost/graph/properties.hpp>
 #include <boost/pending/detail/disjoint_sets.hpp>
 
 namespace boost
 {
 
 struct find_with_path_halving
 {
     template < class ParentPA, class Vertex >
     Vertex operator()(ParentPA p, Vertex v)
     {
         return detail::find_representative_with_path_halving(p, v);
     }
 };
 
 struct find_with_full_path_compression
 {
     template < class ParentPA, class Vertex >
     Vertex operator()(ParentPA p, Vertex v)
     {
         return detail::find_representative_with_full_compression(p, v);
     }
 };
 
 // This is a generalized functor to provide disjoint sets operations
 // with "union by rank" and "path compression".  A disjoint-set data
 // structure maintains a collection S={S1, S2, ..., Sk} of disjoint
 // sets. Each set is identified by a representative, which is some
 // member of of the set. Sets are represented by rooted trees. Two
 // heuristics: "union by rank" and "path compression" are used to
 // speed up the operations.
 
 // Disjoint Set requires two vertex properties for internal use.  A
 // RankPA and a ParentPA. The RankPA must map Vertex to some Integral type
 // (preferably the size_type associated with Vertex). The ParentPA
 // must map Vertex to Vertex.
 template < class RankPA, class ParentPA,
     class FindCompress = find_with_full_path_compression >
 class disjoint_sets
 {
     typedef disjoint_sets self;
 
     inline disjoint_sets() {}
 
 public:
     inline disjoint_sets(RankPA r, ParentPA p) : rank(r), parent(p) {}
 
     inline disjoint_sets(const self& c) : rank(c.rank), parent(c.parent) {}
 
     // Make Set -- Create a singleton set containing vertex x
     template < class Element > inline void make_set(Element x)
     {
         put(parent, x, x);
         typedef typename property_traits< RankPA >::value_type R;
         put(rank, x, R());
     }
 
     // Link - union the two sets represented by vertex x and y
     template < class Element > inline void link(Element x, Element y)
     {
         detail::link_sets(parent, rank, x, y, rep);
     }
 
     // Union-Set - union the two sets containing vertex x and y
     template < class Element > inline void union_set(Element x, Element y)
     {
         link(find_set(x), find_set(y));
     }
 
     // Find-Set - returns the Element representative of the set
     // containing Element x and applies path compression.
     template < class Element > inline Element find_set(Element x)
     {
         return rep(parent, x);
     }
 
     template < class ElementIterator >
     inline std::size_t count_sets(ElementIterator first, ElementIterator last)
     {
         std::size_t count = 0;
         for (; first != last; ++first)
             if (get(parent, *first) == *first)
                 ++count;
         return count;
     }
 
     template < class ElementIterator >
     inline void normalize_sets(ElementIterator first, ElementIterator last)
     {
         for (; first != last; ++first)
             detail::normalize_node(parent, *first);
     }
 
     template < class ElementIterator >
     inline void compress_sets(ElementIterator first, ElementIterator last)
     {
         for (; first != last; ++first)
             detail::find_representative_with_full_compression(parent, *first);
     }
 
 protected:
     RankPA rank;
     ParentPA parent;
     FindCompress rep;
 };
 
 template < class ID = identity_property_map,
     class InverseID = identity_property_map,
     class FindCompress = find_with_full_path_compression >
 class disjoint_sets_with_storage
 {
     typedef typename property_traits< ID >::value_type Index;
     typedef std::vector< Index > ParentContainer;
     typedef std::vector< unsigned char > RankContainer;
 
 public:
     typedef typename ParentContainer::size_type size_type;
 
     disjoint_sets_with_storage(
         size_type n = 0, ID id_ = ID(), InverseID inv = InverseID())
     : id(id_), id_to_vertex(inv), rank(n, 0), parent(n)
     {
         for (Index i = 0; i < n; ++i)
             parent[i] = i;
     }
     // note this is not normally needed
     template < class Element > inline void make_set(Element x)
     {
         parent[x] = x;
         rank[x] = 0;
     }
     template < class Element > inline void link(Element x, Element y)
     {
         extend_sets(x, y);
         detail::link_sets(&parent[0], &rank[0], get(id, x), get(id, y), rep);
     }
     template < class Element > inline void union_set(Element x, Element y)
     {
         Element rx = find_set(x);
         Element ry = find_set(y);
         link(rx, ry);
     }
     template < class Element > inline Element find_set(Element x)
     {
         return id_to_vertex[rep(&parent[0], get(id, x))];
     }
 
     template < class ElementIterator >
     inline std::size_t count_sets(ElementIterator first, ElementIterator last)
     {
         std::size_t count = 0;
         for (; first != last; ++first)
             if (parent[*first] == *first)
                 ++count;
         return count;
     }
 
     template < class ElementIterator >
     inline void normalize_sets(ElementIterator first, ElementIterator last)
     {
         for (; first != last; ++first)
             detail::normalize_node(&parent[0], *first);
     }
 
     template < class ElementIterator >
     inline void compress_sets(ElementIterator first, ElementIterator last)
     {
         for (; first != last; ++first)
             detail::find_representative_with_full_compression(
                 &parent[0], *first);
     }
 
     const ParentContainer& parents() { return parent; }
 
 protected:
     template < class Element > inline void extend_sets(Element x, Element y)
     {
         Index needed
             = get(id, x) > get(id, y) ? get(id, x) + 1 : get(id, y) + 1;
         if (needed > parent.size())
         {
             rank.insert(rank.end(), needed - rank.size(), 0);
             for (Index k = parent.size(); k < needed; ++k)
                 parent.push_back(k);
         }
     }
 
     ID id;
     InverseID id_to_vertex;
     RankContainer rank;
     ParentContainer parent;
     FindCompress rep;
 };
 
 } // namespace boost
 
 #endif // BOOST_DISJOINT_SETS_HPP

This page was automatically generated by the 2.3.7 LXR engine. The LXR team