1 //

     2 //=======================================================================

     3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

     4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek

     5 //

     6 // Distributed under the Boost Software License, Version 1.0. (See

     7 // accompanying file LICENSE_1_0.txt or copy at

     8 // http://www.boost.org/LICENSE_1_0.txt)

     9 //=======================================================================

    10 //

    11 #ifndef BOOST_DISJOINT_SETS_HPP

    12 #define BOOST_DISJOINT_SETS_HPP

    13 

    14 #include <vector>

    15 #include <boost/graph/properties.hpp>

    16 #include <boost/pending/detail/disjoint_sets.hpp>

    17 

    18 namespace boost {

    19 

    20   struct find_with_path_halving {

    21     template <class ParentPA, class Vertex>

    22     Vertex operator()(ParentPA p, Vertex v) { 

    23       return detail::find_representative_with_path_halving(p, v);

    24     }

    25   };

    26 

    27   struct find_with_full_path_compression {

    28     template <class ParentPA, class Vertex>

    29     Vertex operator()(ParentPA p, Vertex v){

    30       return detail::find_representative_with_full_compression(p, v);

    31     }

    32   };

    33 

    34   // This is a generalized functor to provide disjoint sets operations

    35   // with "union by rank" and "path compression".  A disjoint-set data

    36   // structure maintains a collection S={S1, S2, ..., Sk} of disjoint

    37   // sets. Each set is identified by a representative, which is some

    38   // member of of the set. Sets are represented by rooted trees. Two

    39   // heuristics: "union by rank" and "path compression" are used to

    40   // speed up the operations.

    41 

    42   // Disjoint Set requires two vertex properties for internal use.  A

    43   // RankPA and a ParentPA. The RankPA must map Vertex to some Integral type

    44   // (preferably the size_type associated with Vertex). The ParentPA

    45   // must map Vertex to Vertex.

    46   template <class RankPA, class ParentPA,

    47     class FindCompress = find_with_full_path_compression

    48     >

    49   class disjoint_sets {

    50     typedef disjoint_sets self;

    51     

    52     inline disjoint_sets() {}

    53   public:

    54     inline disjoint_sets(RankPA r, ParentPA p) 

    55       : rank(r), parent(p) {}

    56 

    57     inline disjoint_sets(const self& c) 

    58       : rank(c.rank), parent(c.parent) {}

    59     

    60     // Make Set -- Create a singleton set containing vertex x

    61     template <class Element>

    62     inline void make_set(Element x)

    63     {

    64       put(parent, x, x);

    65       typedef typename property_traits<RankPA>::value_type R;

    66       put(rank, x, R());

    67     }

    68     

    69     // Link - union the two sets represented by vertex x and y

    70     template <class Element>

    71     inline void link(Element x, Element y)

    72     {

    73       detail::link_sets(parent, rank, x, y, rep);

    74     }

    75     

    76     // Union-Set - union the two sets containing vertex x and y 

    77     template <class Element>

    78     inline void union_set(Element x, Element y)

    79     {

    80       link(find_set(x), find_set(y));

    81     }

    82     

    83     // Find-Set - returns the Element representative of the set

    84     // containing Element x and applies path compression.

    85     template <class Element>

    86     inline Element find_set(Element x)

    87     {

    88       return rep(parent, x);

    89     }

    90 

    91     template <class ElementIterator>

    92     inline std::size_t count_sets(ElementIterator first, ElementIterator last)

    93     {

    94       std::size_t count = 0;  

    95       for ( ; first != last; ++first)

    96       if (get(parent, *first) == *first)

    97         ++count;

    98       return count;

    99     }

   100 

   101     template <class ElementIterator>

   102     inline void normalize_sets(ElementIterator first, ElementIterator last)

   103     {

   104       for (; first != last; ++first) 

   105         detail::normalize_node(parent, *first);

   106     }    

   107     

   108     template <class ElementIterator>

   109     inline void compress_sets(ElementIterator first, ElementIterator last)

   110     {

   111       for (; first != last; ++first) 

   112         detail::find_representative_with_full_compression(parent, *first);

   113     }    

   114   protected:

   115     RankPA rank;

   116     ParentPA parent;

   117     FindCompress rep;

   118   };

   119 

   120 

   121   

   122 

   123   template <class ID = identity_property_map,

   124             class InverseID = identity_property_map,

   125             class FindCompress = find_with_full_path_compression

   126             >

   127   class disjoint_sets_with_storage

   128   {

   129     typedef typename property_traits<ID>::value_type Index;

   130     typedef std::vector<Index> ParentContainer;

   131     typedef std::vector<unsigned char> RankContainer;

   132   public:

   133     typedef typename ParentContainer::size_type size_type;

   134 

   135     disjoint_sets_with_storage(size_type n = 0,

   136                                ID id_ = ID(),

   137                                InverseID inv = InverseID())

   138       : id(id_), id_to_vertex(inv), rank(n, 0), parent(n)

   139     {

   140       for (Index i = 0; i < n; ++i)

   141         parent[i] = i;

   142     }

   143     // note this is not normally needed

   144     template <class Element>

   145     inline void 

   146     make_set(Element x) {

   147       parent[x] = x;

   148       rank[x]   = 0;

   149     }

   150     template <class Element>

   151     inline void 

   152     link(Element x, Element y)

   153     {

   154       extend_sets(x,y);

   155       detail::link_sets(&parent[0], &rank[0], 

   156                         get(id,x), get(id,y), rep);

   157     }

   158     template <class Element>

   159     inline void 

   160     union_set(Element x, Element y) {

   161       Element rx = find_set(x);

   162       Element ry = find_set(y);

   163       link(rx, ry);

   164     }

   165     template <class Element>

   166     inline Element find_set(Element x) {

   167       return id_to_vertex[rep(&parent[0], get(id,x))];

   168     }

   169 

   170     template <class ElementIterator>

   171     inline std::size_t count_sets(ElementIterator first, ElementIterator last)

   172     {

   173       std::size_t count = 0;  

   174       for ( ; first != last; ++first)

   175       if (parent[*first] == *first)

   176         ++count;

   177       return count;

   178     }

   179 

   180     template <class ElementIterator>

   181     inline void normalize_sets(ElementIterator first, ElementIterator last)

   182     {

   183       for (; first != last; ++first) 

   184         detail::normalize_node(&parent[0], *first);

   185     }    

   186     

   187     template <class ElementIterator>

   188     inline void compress_sets(ElementIterator first, ElementIterator last)

   189     {

   190       for (; first != last; ++first) 

   191         detail::find_representative_with_full_compression(&parent[0],

   192                                                           *first);

   193     }    

   194 

   195     const ParentContainer& parents() { return parent; }

   196 

   197   protected:

   198 

   199     template <class Element>

   200     inline void 

   201     extend_sets(Element x, Element y)

   202     {

   203       Index needed = get(id,x) > get(id,y) ? get(id,x) + 1 : get(id,y) + 1;

   204       if (needed > parent.size()) {

   205         rank.insert(rank.end(), needed - rank.size(), 0);

   206         for (Index k = parent.size(); k < needed; ++k)

   207         parent.push_back(k);

   208       } 

   209     }

   210 

   211     ID id;

   212     InverseID id_to_vertex;

   213     RankContainer rank;

   214     ParentContainer parent;

   215     FindCompress rep;

   216   };

   217 

   218 } // namespace boost

   219 

   220 #endif // BOOST_DISJOINT_SETS_HPP