Imported Upstream version 1.49.0upstream/1.49.0

1 files changed, 220 insertions, 0 deletions

diff --git a/boost/pending/disjoint_sets.hpp b/boost/pending/disjoint_sets.hpp
new file mode 100644
index 0000000000..e64bc2b713
--- /dev/null
+++ b/boost/pending/disjoint_sets.hpp
@@ -0,0 +1,220 @@
+//
+//=======================================================================
+// 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