Changeset 2505:1bb471764ab8 in lemon-0.x for lemon/unionfind.h

Timestamp:

10/30/07 21:21:10 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3351

Message:

Redesign interface of MaxMatching? and UnionFindEnum?
New class ExtendFindEnum?

Faster MaxMatching?

File:

• lemon/unionfind.h (modified) (19 diffs)

lemon/unionfind.h

@@ -179 +179 @@
   private:
     
+    ItemIntMap& index;
+
     // If the parent stores negative value for an item then that item
-    // is root item and it has -items[it].parent component size.  Else
+    // is root item and it has ~(items[it].parent) component id.  Else
     // the items[it].parent contains the index of the parent.
     //
-    // The \c nextItem and \c prevItem provides the double-linked
-    // cyclic list of one component's items. The \c prevClass and
-    // \c nextClass gives the double linked list of the representant
-    // items. 
+    // The \c next and \c prev provides the double-linked
+    // cyclic list of one component's items.
     struct ItemT {
       int parent;
       Item item;
 
-      int nextItem, prevItem;
-      int nextClass, prevClass;
+      int next, prev;
     };
 
     std::vector<ItemT> items;
-    ItemIntMap& index;
-
-    int firstClass;
+    int firstFreeItem;
+
+    struct ClassT {
+      int size;
+      int firstItem;
+      int next, prev;
+    };
+    
+    std::vector<ClassT> classes;
+    int firstClass, firstFreeClass;
+
+    int newClass() {
+      if (firstFreeClass == -1) {
+        int cdx = classes.size();
+        classes.push_back(ClassT());
+        return cdx;
+      } else {
+        int cdx = firstFreeClass;
+        firstFreeClass = classes[firstFreeClass].next;
+        return cdx;
+      }
+    }
+
+    int newItem() {
+      if (firstFreeItem == -1) {
+        int idx = items.size();
+        items.push_back(ItemT());
+        return idx;
+      } else {
+        int idx = firstFreeItem;
+        firstFreeItem = items[firstFreeItem].next;
+        return idx;
+      }
+    }
 
 
@@ -218 +248 @@
     }
 
-    void unlaceClass(int k) {
-      if (items[k].prevClass != -1) {
-        items[items[k].prevClass].nextClass = items[k].nextClass;
+    int classIndex(int idx) const {
+      return ~(items[repIndex(idx)].parent);
+    }
+
+    void singletonItem(int idx) {
+      items[idx].next = idx;
+      items[idx].prev = idx;
+    }
+
+    void laceItem(int idx, int rdx) {
+      items[idx].prev = rdx;
+      items[idx].next = items[rdx].next;
+      items[items[rdx].next].prev = idx;
+      items[rdx].next = idx;
+    }
+
+    void unlaceItem(int idx) {
+      items[items[idx].prev].next = items[idx].next;
+      items[items[idx].next].prev = items[idx].prev;
+      
+      items[idx].next = firstFreeItem;
+      firstFreeItem = idx;
+    }
+
+    void spliceItems(int ak, int bk) {
+      items[items[ak].prev].next = bk;
+      items[items[bk].prev].next = ak;
+      int tmp = items[ak].prev;
+      items[ak].prev = items[bk].prev;
+      items[bk].prev = tmp;
+        
+    }
+
+    void laceClass(int cls) {
+      if (firstClass != -1) {
+        classes[firstClass].prev = cls;
+      }
+      classes[cls].next = firstClass;
+      classes[cls].prev = -1;
+      firstClass = cls;
+    } 
+
+    void unlaceClass(int cls) {
+      if (classes[cls].prev != -1) {
+        classes[classes[cls].prev].next = classes[cls].next;
       } else {
-        firstClass = items[k].nextClass;
-      }
-      if (items[k].nextClass != -1) {
-        items[items[k].nextClass].prevClass = items[k].prevClass;
-      }
+        firstClass = classes[cls].next;
+      }
+      if (classes[cls].next != -1) {
+        classes[classes[cls].next].prev = classes[cls].prev;
+      }
+      
+      classes[cls].next = firstFreeClass;
+      firstFreeClass = cls;
     } 
 
-    void spliceItems(int ak, int bk) {
-      items[items[ak].prevItem].nextItem = bk;
-      items[items[bk].prevItem].nextItem = ak;
-      int tmp = items[ak].prevItem;
-      items[ak].prevItem = items[bk].prevItem;
-      items[bk].prevItem = tmp;
-        
-    }
-
   public:
 
     UnionFindEnum(ItemIntMap& _index) 
-      : items(), index(_index), firstClass(-1) {}
+      : index(_index), items(), firstFreeItem(-1), 
+        firstClass(-1), firstFreeClass(-1) {}
     
     /// \brief Inserts the given element into a new component.
@@ -248 +315 @@
     /// given element.
     ///
-    void insert(const Item& item) {
-      ItemT t;
-
-      int idx = items.size();
+    int insert(const Item& item) {
+      int idx = newItem();
+
       index.set(item, idx);
 
-      t.nextItem = idx;
-      t.prevItem = idx;
-      t.item = item;
-      t.parent = -1;
-      
-      t.nextClass = firstClass;
-      if (firstClass != -1) {
-        items[firstClass].prevClass = idx;
-      }
-      t.prevClass = -1;
-      firstClass = idx;
-
-      items.push_back(t);
+      singletonItem(idx);
+      items[idx].item = item;
+
+      int cdx = newClass();
+
+      items[idx].parent = ~cdx;
+
+      laceClass(cdx);
+      classes[cdx].size = 1;
+      classes[cdx].firstItem = idx;
+
+      firstClass = cdx;
+      
+      return cdx;
     }
 
@@ -273 +340 @@
     /// This methods inserts the element \e a into the component of the
     /// element \e comp. 
-    void insert(const Item& item, const Item& comp) {
-      int k = repIndex(index[comp]);
-      ItemT t;
-
-      int idx = items.size();
+    void insert(const Item& item, int cls) {
+      int rdx = classes[cls].firstItem;
+      int idx = newItem();
+
       index.set(item, idx);
 
-      t.prevItem = k;
-      t.nextItem = items[k].nextItem;
-      items[items[k].nextItem].prevItem = idx;
-      items[k].nextItem = idx;
-
-      t.item = item;
-      t.parent = k;
-
-      --items[k].parent;
-
-      items.push_back(t);
+      laceItem(idx, rdx);
+
+      items[idx].item = item;
+      items[idx].parent = rdx;
+
+      ++classes[~(items[rdx].parent)].size;
     }
 
@@ -299 +360 @@
       items.clear();
       firstClass = -1;
-    }
-
-    /// \brief Finds the leader of the component of the given element.
-    ///
-    /// The method returns the leader of the component of the given element.
-    const Item& find(const Item &item) const {
-      return items[repIndex(index[item])].item;
+      firstFreeItem = -1;
+    }
+
+    /// \brief Finds the component of the given element.
+    ///
+    /// The method returns the component id of the given element.
+    int find(const Item &item) const {
+      return ~(items[repIndex(index[item])].parent);
     }
 
@@ -313 +375 @@
     /// Joins the component of element \e a and component of
     /// element \e b. If \e a and \e b are in the same component then
-    /// returns false else returns true.
-    bool join(const Item& a, const Item& b) {
+    /// returns -1 else returns the remaining class.
+    int join(const Item& a, const Item& b) {
 
       int ak = repIndex(index[a]);
@@ -320 +382 @@
 
       if (ak == bk) {
-        return false;
-      }
-
-      if ( items[ak].parent < items[bk].parent ) {
-        unlaceClass(bk);
-        items[ak].parent += items[bk].parent;
+        return -1;
+      }
+
+      int acx = ~(items[ak].parent);
+      int bcx = ~(items[bk].parent);
+
+      int rcx;
+
+      if (classes[acx].size > classes[bcx].size) {
+        classes[acx].size += classes[bcx].size;
         items[bk].parent = ak;
+        unlaceClass(bcx);
+        rcx = acx;
       } else {
-        unlaceClass(ak);
-        items[bk].parent += items[ak].parent;
+        classes[bcx].size += classes[acx].size;
         items[ak].parent = bk;
+        unlaceClass(acx);
+        rcx = bcx;
       }
       spliceItems(ak, bk);
 
-      return true;
-    }
-
-    /// \brief Returns the size of the component of element \e a.
-    ///
-    /// Returns the size of the component of element \e a.
-    int size(const Item &item) const {
-      return - items[repIndex(index[item])].parent;
-    }
-
-    /// \brief Splits up the component of the element. 
-    ///
-    /// Splitting the component of the element into sigleton
-    /// components (component of size one).
-    void split(const Item &item) {
-      int k = repIndex(index[item]);
-      int idx = items[k].nextItem;
-      while (idx != k) {
-        int next = items[idx].nextItem;
+      return rcx;
+    }
+
+    /// \brief Returns the size of the class.
+    ///
+    /// Returns the size of the class.
+    int size(int cls) const {
+      return classes[cls].size;
+    }
+
+    /// \brief Splits up the component. 
+    ///
+    /// Splitting the component into singleton components (component
+    /// of size one).
+    void split(int cls) {
+      int fdx = classes[cls].firstItem;
+      int idx = items[fdx].next;
+      while (idx != fdx) {
+        int next = items[idx].next;
+
+        singletonItem(idx);
+
+        int cdx = newClass();        
+        items[idx].parent = ~cdx;
+
+        laceClass(cdx);
+        classes[cdx].size = 1;
+        classes[cdx].firstItem = idx;
         
-        items[idx].parent = -1;
-        items[idx].prevItem = idx;
-        items[idx].nextItem = idx;
-        
-        items[idx].nextClass = firstClass;
-        items[firstClass].prevClass = idx;
-        firstClass = idx;
-
         idx = next;
       }
 
-      items[idx].parent = -1;
-      items[idx].prevItem = idx;
-      items[idx].nextItem = idx;
-      
-      items[firstClass].prevClass = -1;
-    }
-
-    /// \brief Sets the given element to the leader element of its component.
-    ///
-    /// Sets the given element to the leader element of its component.
-    void makeRep(const Item &item) {
-      int nk = index[item];
-      int k = repIndex(nk);
-      if (nk == k) return;
-      
-      if (items[k].prevClass != -1) {
-        items[items[k].prevClass].nextClass = nk;
-      } else {
-        firstClass = nk;
-      }
-      if (items[k].nextClass != -1) {
-        items[items[k].nextClass].prevClass = nk;
-      }
-      
-      int idx = items[k].nextItem;
-      while (idx != k) {
-        items[idx].parent = nk;
-        idx = items[idx].nextItem;
-      }
-      
-      items[nk].parent = items[k].parent;
-      items[k].parent = nk;
+      items[idx].prev = idx;
+      items[idx].next = idx;
+
+      classes[~(items[idx].parent)].size = 1;
+      
     }
 
@@ -406 +449 @@
     /// \warning It is an error to remove an element which is not in
     /// the structure.
-    void erase(const Item &item) {
+    /// \warning This running time of this operation is proportional to the
+    /// number of the items in this class.
+    void erase(const Item& item) {
       int idx = index[item];
-      if (rep(idx)) {
-        int k = idx;
-        if (items[k].parent == -1) {
-          unlaceClass(idx);
-          return;
-        } else {
-          int nk = items[k].nextItem;
-          if (items[k].prevClass != -1) {
-            items[items[k].prevClass].nextClass = nk;
-          } else {
-            firstClass = nk;
-          }
-          if (items[k].nextClass != -1) {
-            items[items[k].nextClass].prevClass = nk;
-          }
-      
-          int l = items[k].nextItem;
-          while (l != k) {
-            items[l].parent = nk;
-            l = items[l].nextItem;
-          }
+      int fdx = items[idx].next;
+
+      int cdx = classIndex(idx);
+      if (idx == fdx) {
+        unlaceClass(cdx);
+        items[idx].next = firstFreeItem;
+        firstFreeItem = idx;
+        return;
+      } else {
+        classes[cdx].firstItem = fdx;
+        --classes[cdx].size;
+        items[fdx].parent = ~cdx;
+
+        unlaceItem(idx);
+        idx = items[fdx].next;
+        while (idx != fdx) {
+          items[idx].parent = fdx;
+          idx = items[idx].next;
+        }
           
-          items[nk].parent = items[k].parent + 1;
-        }
-      } else {
-        
-        int k = repIndex(idx);
-        idx = items[k].nextItem;
-        while (idx != k) {
-          items[idx].parent = k;
-          idx = items[idx].nextItem;
-        }
-
-        ++items[k].parent;
-      }
-
-      idx = index[item];      
-      items[items[idx].prevItem].nextItem = items[idx].nextItem;
-      items[items[idx].nextItem].prevItem = items[idx].prevItem;
+      }
 
     }    
-
-    /// \brief Moves the given element to another component.
-    ///
-    /// This method moves the element \e a from its component
-    /// to the component of \e comp.
-    /// If \e a and \e comp are in the same component then
-    /// it returns false otherwise it returns true.
-    bool move(const Item &item, const Item &comp) {
-      if (repIndex(index[item]) == repIndex(index[comp])) return false;
-      erase(item);
-      insert(item, comp);
-      return true;
-    }
-
 
     /// \brief Removes the component of the given element from the structure.
@@ -470 +483 @@
     /// \warning It is an error to give an element which is not in the
     /// structure.
-    void eraseClass(const Item &item) {
-      unlaceClass(repIndex(index[item]));
+    void eraseClass(int cls) {
+      int fdx = classes[cls].firstItem;
+      unlaceClass(cls);
+      items[items[fdx].prev].next = firstFreeItem;
+      firstFreeItem = fdx;
     }
 
@@ -477 +493 @@
     ///
     /// ClassIt is a lemon style iterator for the components. It iterates
-    /// on the representant items of the classes.
+    /// on the ids of the classes.
     class ClassIt {
     public:
@@ -484 +500 @@
       /// Constructor of the iterator
       ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
-        idx = unionFind->firstClass;
+        cdx = unionFind->firstClass;
       }
 
@@ -490 +506 @@
       ///
       /// Constructor to get invalid iterator
-      ClassIt(Invalid) : unionFind(0), idx(-1) {}
+      ClassIt(Invalid) : unionFind(0), cdx(-1) {}
       
       /// \brief Increment operator
@@ -496 +512 @@
       /// It steps to the next representant item.
       ClassIt& operator++() {
-        idx = unionFind->items[idx].nextClass;
+        cdx = unionFind->classes[cdx].next;
         return *this;
       }
@@ -503 +519 @@
       ///
       /// It converts the iterator to the current representant item.
-      operator const Item&() const {
-        return unionFind->items[idx].item;
+      operator int() const {
+        return cdx;
       }
 
@@ -511 +527 @@
       /// Equality operator
       bool operator==(const ClassIt& i) { 
-        return i.idx == idx;
+        return i.cdx == cdx;
       }
 
@@ -518 +534 @@
       /// Inequality operator
       bool operator!=(const ClassIt& i) { 
-        return i.idx != idx;
+        return i.cdx != cdx;
       }
       
     private:
       const UnionFindEnum* unionFind;
-      int idx;
+      int cdx;
     };
 
@@ -546 +562 @@
       /// Constructor of the iterator. The iterator iterates
       /// on the class of the \c item.
-      ItemIt(const UnionFindEnum& ufe, const Item& item) : unionFind(&ufe) {
-        idx = unionFind->repIndex(unionFind->index[item]);
+      ItemIt(const UnionFindEnum& ufe, int cls) : unionFind(&ufe) {
+        fdx = idx = unionFind->classes[cls].firstItem;
       }
 
@@ -559 +575 @@
       /// It steps to the next item in the class.
       ItemIt& operator++() {
-        idx = unionFind->items[idx].nextItem;
-        if (unionFind->rep(idx)) idx = -1;
+        idx = unionFind->items[idx].next;
+        if (idx == fdx) idx = -1;
         return *this;
       }
@@ -587 +603 @@
     private:
       const UnionFindEnum* unionFind;
-      int idx;
+      int idx, fdx;
     };
 
   };
 
+  /// \ingroup auxdat
+  ///
+  /// \brief A \e Extend-Find data structure implementation which
+  /// is able to enumerate the components.
+  ///
+  /// The class implements an \e Extend-Find data structure which is
+  /// able to enumerate the components and the items in a
+  /// component. The data structure is a simplification of the
+  /// Union-Find structure, and it does not allow to merge two components.
+  ///
+  /// \pre You need to add all the elements by the \ref insert()
+  /// method.
+  template <typename _ItemIntMap>
+  class ExtendFindEnum {
+  public:
+    
+    typedef _ItemIntMap ItemIntMap;
+    typedef typename ItemIntMap::Key Item;
+
+  private:
+    
+    ItemIntMap& index;
+
+    struct ItemT {
+      int cls;
+      Item item;
+      int next, prev;
+    };
+
+    std::vector<ItemT> items;
+    int firstFreeItem;
+
+    struct ClassT {
+      int firstItem;
+      int next, prev;
+    };
+
+    std::vector<ClassT> classes;
+
+    int firstClass, firstFreeClass;
+
+    int newClass() {
+      if (firstFreeClass != -1) {
+        int cdx = firstFreeClass;
+        firstFreeClass = classes[cdx].next;
+        return cdx;
+      } else {
+        classes.push_back(ClassT());
+        return classes.size() - 1;
+      }
+    }
+
+    int newItem() {
+      if (firstFreeItem != -1) {
+        int idx = firstFreeItem;
+        firstFreeItem = items[idx].next;
+        return idx;
+      } else {
+        items.push_back(ItemT());
+        return items.size() - 1;
+      }
+    }
+
+  public:
+
+    /// \brief Constructor
+    ExtendFindEnum(ItemIntMap& _index) 
+      : index(_index), items(), firstFreeItem(-1), 
+        classes(), firstClass(-1), firstFreeClass(-1) {}
+    
+    /// \brief Inserts the given element into a new component.
+    ///
+    /// This method creates a new component consisting only of the
+    /// given element.
+    int insert(const Item& item) {
+      int cdx = newClass();
+      classes[cdx].prev = -1;
+      classes[cdx].next = firstClass;
+      firstClass = cdx;
+      
+      int idx = newItem();
+      items[idx].item = item;
+      items[idx].cls = cdx;
+      items[idx].prev = idx;
+      items[idx].next = idx;
+
+      classes[cdx].firstItem = idx;
+
+      index.set(item, idx);
+      
+      return cdx;
+    }
+
+    /// \brief Inserts the given element into the given component.
+    ///
+    /// This methods inserts the element \e item a into the \e cls class.
+    void insert(const Item& item, int cls) {
+      int idx = newItem();
+      int rdx = classes[cls].firstItem;
+      items[idx].item = item;
+      items[idx].cls = cls;
+
+      items[idx].prev = rdx;
+      items[idx].next = items[rdx].next;
+      items[items[rdx].next].prev = idx;
+      items[rdx].next = idx;
+
+      index.set(item, idx);
+    }
+
+    /// \brief Clears the union-find data structure
+    ///
+    /// Erase each item from the data structure.
+    void clear() {
+      items.clear();
+      classes.clear;
+      firstClass = firstFreeClass = firstFreeItem = -1;
+    }
+
+    /// \brief Gives back the class of the \e item.
+    ///
+    /// Gives back the class of the \e item.
+    int find(const Item &item) const {
+      return items[index[item]].cls;
+    }
+    
+    /// \brief Removes the given element from the structure.
+    ///
+    /// Removes the element from its component and if the component becomes
+    /// empty then removes that component from the component list.
+    ///
+    /// \warning It is an error to remove an element which is not in
+    /// the structure.
+    void erase(const Item &item) {
+      int idx = index[item];
+      int cdx = items[idx].cls;
+      
+      if (idx == items[idx].next) {
+        if (classes[cdx].prev != -1) {
+          classes[classes[cdx].prev].next = classes[cdx].next; 
+        } else {
+          firstClass = classes[cdx].next;
+        }
+        if (classes[cdx].next != -1) {
+          classes[classes[cdx].next].prev = classes[cdx].prev; 
+        }
+        classes[cdx].next = firstFreeClass;
+        firstFreeClass = cdx;
+      } else {
+        classes[cdx].firstItem = items[idx].next;
+        items[items[idx].next].prev = items[idx].prev;
+        items[items[idx].prev].next = items[idx].next;
+      }
+      items[idx].next = firstFreeItem;
+      firstFreeItem = idx;
+        
+    }    
+
+    
+    /// \brief Removes the component of the given element from the structure.
+    ///
+    /// Removes the component of the given element from the structure.
+    ///
+    /// \warning It is an error to give an element which is not in the
+    /// structure.
+    void eraseClass(int cdx) {
+      int idx = classes[cdx].firstItem;
+      items[items[idx].prev].next = firstFreeItem;
+      firstFreeItem = idx;
+
+      if (classes[cdx].prev != -1) {
+        classes[classes[cdx].prev].next = classes[cdx].next; 
+      } else {
+        firstClass = classes[cdx].next;
+      }
+      if (classes[cdx].next != -1) {
+        classes[classes[cdx].next].prev = classes[cdx].prev; 
+      }
+      classes[cdx].next = firstFreeClass;
+      firstFreeClass = cdx;
+    }
+
+    /// \brief Lemon style iterator for the classes.
+    ///
+    /// ClassIt is a lemon style iterator for the components. It iterates
+    /// on the ids of classes.
+    class ClassIt {
+    public:
+      /// \brief Constructor of the iterator
+      ///
+      /// Constructor of the iterator
+      ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {
+        cdx = extendFind->firstClass;
+      }
+
+      /// \brief Constructor to get invalid iterator
+      ///
+      /// Constructor to get invalid iterator
+      ClassIt(Invalid) : extendFind(0), cdx(-1) {}
+      
+      /// \brief Increment operator
+      ///
+      /// It steps to the next representant item.
+      ClassIt& operator++() {
+        cdx = extendFind->classes[cdx].next;
+        return *this;
+      }
+      
+      /// \brief Conversion operator
+      ///
+      /// It converts the iterator to the current class id.
+      operator int() const {
+        return cdx;
+      }
+
+      /// \brief Equality operator
+      ///
+      /// Equality operator
+      bool operator==(const ClassIt& i) { 
+        return i.cdx == cdx;
+      }
+
+      /// \brief Inequality operator
+      ///
+      /// Inequality operator
+      bool operator!=(const ClassIt& i) { 
+        return i.cdx != cdx;
+      }
+      
+    private:
+      const ExtendFindEnum* extendFind;
+      int cdx;
+    };
+
+    /// \brief Lemon style iterator for the items of a component.
+    ///
+    /// ClassIt is a lemon style iterator for the components. It iterates
+    /// on the items of a class. By example if you want to iterate on
+    /// each items of each classes then you may write the next code.
+    ///\code
+    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
+    ///   std::cout << "Class: ";
+    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
+    ///     std::cout << toString(iit) << ' ' << std::endl;
+    ///   }
+    ///   std::cout << std::endl;
+    /// }
+    ///\endcode
+    class ItemIt {
+    public:
+      /// \brief Constructor of the iterator
+      ///
+      /// Constructor of the iterator. The iterator iterates
+      /// on the class of the \c item.
+      ItemIt(const ExtendFindEnum& ufe, int cls) : extendFind(&ufe) {
+        fdx = idx = extendFind->classes[cls].firstItem;
+      }
+
+      /// \brief Constructor to get invalid iterator
+      ///
+      /// Constructor to get invalid iterator
+      ItemIt(Invalid) : extendFind(0), idx(-1) {}
+      
+      /// \brief Increment operator
+      ///
+      /// It steps to the next item in the class.
+      ItemIt& operator++() {
+        idx = extendFind->items[idx].next;
+        if (fdx == idx) idx = -1;
+        return *this;
+      }
+      
+      /// \brief Conversion operator
+      ///
+      /// It converts the iterator to the current item.
+      operator const Item&() const {
+        return extendFind->items[idx].item;
+      }
+
+      /// \brief Equality operator
+      ///
+      /// Equality operator
+      bool operator==(const ItemIt& i) { 
+        return i.idx == idx;
+      }
+
+      /// \brief Inequality operator
+      ///
+      /// Inequality operator
+      bool operator!=(const ItemIt& i) { 
+        return i.idx != idx;
+      }
+      
+    private:
+      const ExtendFindEnum* extendFind;
+      int idx, fdx;
+    };
+
+  };
 
   //! @}