alpar@906: /* -*- C++ -*-
alpar@906:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@1956:  * Copyright (C) 2003-2006
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906:  *
alpar@906:  * Permission to use, modify and distribute this software is granted
alpar@906:  * provided that this copyright notice appears in all copies. For
alpar@906:  * precise terms see the accompanying LICENSE file.
alpar@906:  *
alpar@906:  * This software is provided "AS IS" with no warranty of any kind,
alpar@906:  * express or implied, and with no claim as to its suitability for any
alpar@906:  * purpose.
alpar@906:  *
alpar@906:  */
alpar@906: 
alpar@921: #ifndef LEMON_UNION_FIND_H
alpar@921: #define LEMON_UNION_FIND_H
beckerjc@483: 
klao@491: //!\ingroup auxdat
beckerjc@483: //!\file
beckerjc@483: //!\brief Union-Find data structures.
alpar@774: //!
beckerjc@483: 
beckerjc@483: #include <vector>
beckerjc@483: #include <list>
beckerjc@483: #include <utility>
beckerjc@483: #include <algorithm>
beckerjc@483: 
deba@1993: #include <lemon/bits/invalid.h>
beckerjc@483: 
alpar@921: namespace lemon {
beckerjc@483: 
deba@2308:   /// \ingroup auxdat
deba@2308:   ///
deba@2205:   /// \brief A \e Union-Find data structure implementation
deba@2205:   ///
deba@2205:   /// The class implements the \e Union-Find data structure. 
deba@2205:   /// The union operation uses rank heuristic, while
deba@2205:   /// the find operation uses path compression.
deba@2205:   /// This is a very simple but efficient implementation, providing 
deba@2205:   /// only four methods: join (union), find, insert and size.
deba@2205:   /// For more features see the \ref UnionFindEnum class.
deba@2205:   ///
deba@2205:   /// It is primarily used in Kruskal algorithm for finding minimal
deba@2205:   /// cost spanning tree in a graph.
deba@2205:   /// \sa kruskal()
deba@2205:   ///
deba@2205:   /// \pre You need to add all the elements by the \ref insert()
deba@2205:   /// method.  
deba@2308:   template <typename _ItemIntMap>
beckerjc@483:   class UnionFind {
beckerjc@483:   public:
deba@2308: 
deba@2308:     typedef _ItemIntMap ItemIntMap;
deba@2308:     typedef typename ItemIntMap::Key Item;
beckerjc@483: 
beckerjc@483:   private:
deba@2205:     // If the items vector stores negative value for an item then
deba@2205:     // that item is root item and it has -items[it] component size.
deba@2205:     // Else the items[it] contains the index of the parent.
deba@2205:     std::vector<int> items;
deba@2205:     ItemIntMap& index;
deba@2205: 
deba@2205:     bool rep(int idx) const {
deba@2205:       return items[idx] < 0;
deba@2205:     }
deba@2205: 
deba@2205:     int repIndex(int idx) const {
deba@2205:       int k = idx;
deba@2205:       while (!rep(k)) {
deba@2205:         k = items[k] ;
deba@2205:       }
deba@2205:       while (idx != k) {
deba@2205:         int next = items[idx];
deba@2205:         const_cast<int&>(items[idx]) = k;
deba@2205:         idx = next;
deba@2205:       }
deba@2205:       return k;
deba@2205:     }
beckerjc@483: 
beckerjc@483:   public:
beckerjc@483: 
deba@2205:     /// \brief Constructor
deba@2205:     ///
deba@2205:     /// Constructor of the UnionFind class. You should give an item to
deba@2205:     /// integer map which will be used from the data structure. If you
deba@2205:     /// modify directly this map that may cause segmentation fault,
deba@2205:     /// invalid data structure, or infinite loop when you use again
deba@2205:     /// the union-find.
deba@2205:     UnionFind(ItemIntMap& m) : index(m) {}
beckerjc@483: 
deba@2205:     /// \brief Returns the index of the element's component.
deba@2205:     ///
deba@2205:     /// The method returns the index of the element's component.
deba@2205:     /// This is an integer between zero and the number of inserted elements.
deba@2205:     ///
deba@2205:     int find(const Item& a) {
deba@2205:       return repIndex(index[a]);
beckerjc@483:     }
beckerjc@483: 
deba@2205:     /// \brief Inserts a new element into the structure.
deba@2205:     ///
deba@2205:     /// This method inserts a new element into the data structure. 
deba@2205:     ///
deba@2205:     /// The method returns the index of the new component.
deba@2205:     int insert(const Item& a) {
deba@2205:       int n = items.size();
deba@2205:       items.push_back(-1);
deba@2205:       index.set(a,n);
beckerjc@483:       return n;
beckerjc@483:     }
beckerjc@483: 
deba@2205:     /// \brief Joining the components of element \e a and element \e b.
deba@2205:     ///
deba@2205:     /// This is the \e union operation of the Union-Find structure. 
deba@2205:     /// Joins the component of element \e a and component of
deba@2205:     /// element \e b. If \e a and \e b are in the same component then
deba@2205:     /// it returns false otherwise it returns true.
deba@2205:     bool join(const Item& a, const Item& b) {
deba@2205:       int ka = repIndex(index[a]);
deba@2205:       int kb = repIndex(index[b]);
beckerjc@483: 
deba@2205:       if ( ka == kb ) 
beckerjc@483: 	return false;
beckerjc@483: 
deba@2205:       if (items[ka] < items[kb]) {
deba@2205: 	items[ka] += items[kb];
deba@2205: 	items[kb] = ka;
deba@2205:       } else {
deba@2205: 	items[kb] += items[ka];
deba@2205: 	items[ka] = kb;
beckerjc@483:       }
beckerjc@483:       return true;
beckerjc@483:     }
beckerjc@483: 
deba@2205:     /// \brief Returns the size of the component of element \e a.
deba@2205:     ///
deba@2205:     /// Returns the size of the component of element \e a.
deba@2205:     int size(const Item& a) {
deba@2205:       int k = repIndex(index[a]);
deba@2205:       return - items[k];
beckerjc@483:     }
beckerjc@483: 
beckerjc@483:   };
beckerjc@483: 
deba@2308:   /// \ingroup auxdat
deba@2308:   ///
deba@2205:   /// \brief A \e Union-Find data structure implementation which
deba@2205:   /// is able to enumerate the components.
deba@2205:   ///
deba@2205:   /// The class implements a \e Union-Find data structure
deba@2205:   /// which is able to enumerate the components and the items in
deba@2205:   /// a component. If you don't need this feature then perhaps it's
deba@2205:   /// better to use the \ref UnionFind class which is more efficient.
deba@2205:   ///
deba@2205:   /// The union operation uses rank heuristic, while
deba@2205:   /// the find operation uses path compression.
deba@2205:   ///
deba@2205:   /// \pre You need to add all the elements by the \ref insert()
deba@2205:   /// method.
deba@2205:   ///
deba@2308:   template <typename _ItemIntMap>
deba@2205:   class UnionFindEnum {
deba@2205:   public:
deba@2205:     
deba@2205:     typedef _ItemIntMap ItemIntMap;
deba@2308:     typedef typename ItemIntMap::Key Item;
deba@2308: 
deba@2205:   private:
deba@2205:     
deba@2205:     // If the parent stores negative value for an item then that item
deba@2205:     // is root item and it has -items[it].parent component size.  Else
deba@2205:     // the items[it].parent contains the index of the parent.
deba@2205:     //
deba@2205:     // The \c nextItem and \c prevItem provides the double-linked
deba@2205:     // cyclic list of one component's items. The \c prevClass and
deba@2205:     // \c nextClass gives the double linked list of the representant
deba@2205:     // items. 
deba@2205:     struct ItemT {
deba@2205:       int parent;
deba@2205:       Item item;
beckerjc@483: 
deba@2205:       int nextItem, prevItem;
deba@2205:       int nextClass, prevClass;
deba@2205:     };
beckerjc@483: 
deba@2205:     std::vector<ItemT> items;
deba@2205:     ItemIntMap& index;
beckerjc@483: 
deba@2205:     int firstClass;
beckerjc@483: 
beckerjc@483: 
deba@2205:     bool rep(int idx) const {
deba@2205:       return items[idx].parent < 0;
beckerjc@483:     }
beckerjc@483: 
deba@2205:     int repIndex(int idx) const {
deba@2205:       int k = idx;
deba@2205:       while (!rep(k)) {
deba@2205:         k = items[k].parent;
deba@2205:       }
deba@2205:       while (idx != k) {
deba@2205:         int next = items[idx].parent;
deba@2205:         const_cast<int&>(items[idx].parent) = k;
deba@2205:         idx = next;
deba@2205:       }
deba@2205:       return k;
deba@2205:     }
deba@2205: 
deba@2205:     void unlaceClass(int k) {
deba@2205:       if (items[k].prevClass != -1) {
deba@2205:         items[items[k].prevClass].nextClass = items[k].nextClass;
deba@2205:       } else {
deba@2205:         firstClass = items[k].nextClass;
deba@2205:       }
deba@2205:       if (items[k].nextClass != -1) {
deba@2205:         items[items[k].nextClass].prevClass = items[k].prevClass;
deba@2205:       }
deba@2205:     } 
deba@2205: 
deba@2205:     void spliceItems(int ak, int bk) {
deba@2205:       items[items[ak].prevItem].nextItem = bk;
deba@2205:       items[items[bk].prevItem].nextItem = ak;
deba@2205:       int tmp = items[ak].prevItem;
deba@2205:       items[ak].prevItem = items[bk].prevItem;
deba@2205:       items[bk].prevItem = tmp;
deba@2205:         
klao@2003:     }
klao@2003: 
beckerjc@483:   public:
beckerjc@483: 
deba@2205:     UnionFindEnum(ItemIntMap& _index) 
deba@2205:       : items(), index(_index), firstClass(-1) {}
deba@2205:     
deba@2205:     /// \brief Inserts the given element into a new component.
deba@2205:     ///
deba@2205:     /// This method creates a new component consisting only of the
deba@2205:     /// given element.
deba@2205:     ///
deba@2205:     void insert(const Item& item) {
deba@2205:       ItemT t;
beckerjc@483: 
deba@2205:       int idx = items.size();
deba@2205:       index.set(item, idx);
beckerjc@483: 
deba@2205:       t.nextItem = idx;
deba@2205:       t.prevItem = idx;
deba@2205:       t.item = item;
deba@2205:       t.parent = -1;
deba@2205:       
deba@2205:       t.nextClass = firstClass;
deba@2205:       if (firstClass != -1) {
deba@2205:         items[firstClass].prevClass = idx;
deba@2205:       }
deba@2205:       t.prevClass = -1;
deba@2205:       firstClass = idx;
beckerjc@483: 
deba@2205:       items.push_back(t);
beckerjc@483:     }
beckerjc@483: 
deba@2205:     /// \brief Inserts the given element into the component of the others.
deba@2205:     ///
deba@2205:     /// This methods inserts the element \e a into the component of the
deba@2205:     /// element \e comp. 
deba@2205:     void insert(const Item& item, const Item& comp) {
deba@2205:       int k = repIndex(index[comp]);
deba@2205:       ItemT t;
beckerjc@483: 
deba@2205:       int idx = items.size();
deba@2205:       index.set(item, idx);
deba@2205: 
deba@2205:       t.prevItem = k;
deba@2205:       t.nextItem = items[k].nextItem;
deba@2205:       items[items[k].nextItem].prevItem = idx;
deba@2205:       items[k].nextItem = idx;
deba@2205: 
deba@2205:       t.item = item;
deba@2205:       t.parent = k;
deba@2205: 
deba@2205:       --items[k].parent;
deba@2205: 
deba@2205:       items.push_back(t);
beckerjc@483:     }
beckerjc@483: 
deba@2205:     /// \brief Finds the leader of the component of the given element.
deba@2205:     ///
deba@2205:     /// The method returns the leader of the component of the given element.
deba@2205:     const Item& find(const Item &item) const {
deba@2205:       return items[repIndex(index[item])].item;
beckerjc@483:     }
beckerjc@483: 
deba@2205:     /// \brief Joining the component of element \e a and element \e b.
deba@2205:     ///
deba@2205:     /// This is the \e union operation of the Union-Find structure. 
deba@2205:     /// Joins the component of element \e a and component of
deba@2205:     /// element \e b. If \e a and \e b are in the same component then
deba@2205:     /// returns false else returns true.
deba@2205:     bool join(const Item& a, const Item& b) {
beckerjc@483: 
deba@2205:       int ak = repIndex(index[a]);
deba@2205:       int bk = repIndex(index[b]);
beckerjc@483: 
deba@2205:       if (ak == bk) {
beckerjc@483: 	return false;
beckerjc@483:       }
beckerjc@483: 
deba@2205:       if ( items[ak].parent < items[bk].parent ) {
deba@2205:         unlaceClass(bk);
deba@2205:         items[ak].parent += items[bk].parent;
deba@2205: 	items[bk].parent = ak;
deba@2205:       } else {
deba@2332:         unlaceClass(ak);
deba@2205:         items[bk].parent += items[ak].parent;
deba@2205: 	items[ak].parent = bk;
beckerjc@483:       }
deba@2205:       spliceItems(ak, bk);
beckerjc@483: 
beckerjc@483:       return true;
beckerjc@483:     }
beckerjc@483: 
deba@2205:     /// \brief Returns the size of the component of element \e a.
deba@2205:     ///
deba@2205:     /// Returns the size of the component of element \e a.
deba@2205:     int size(const Item &item) const {
deba@2205:       return - items[repIndex(index[item])].parent;
beckerjc@483:     }
beckerjc@483: 
deba@2205:     /// \brief Splits up the component of the element. 
deba@2205:     ///
deba@2205:     /// Splitting the component of the element into sigleton
deba@2205:     /// components (component of size one).
deba@2205:     void split(const Item &item) {
deba@2205:       int k = repIndex(index[item]);
deba@2205:       int idx = items[k].nextItem;
deba@2205:       while (idx != k) {
deba@2205:         int next = items[idx].nextItem;
deba@2205:         
deba@2205:         items[idx].parent = -1;
deba@2205:         items[idx].prevItem = idx;
deba@2205:         items[idx].nextItem = idx;
deba@2205:         
deba@2205:         items[idx].nextClass = firstClass;
deba@2205:         items[firstClass].prevClass = idx;
deba@2205:         firstClass = idx;
beckerjc@483: 
deba@2205:         idx = next;
beckerjc@483:       }
beckerjc@483: 
deba@2205:       items[idx].parent = -1;
deba@2205:       items[idx].prevItem = idx;
deba@2205:       items[idx].nextItem = idx;
deba@2205:       
deba@2205:       items[firstClass].prevClass = -1;
beckerjc@483:     }
beckerjc@483: 
deba@2205:     /// \brief Sets the given element to the leader element of its component.
deba@2205:     ///
deba@2205:     /// Sets the given element to the leader element of its component.
deba@2205:     void makeRep(const Item &item) {
deba@2205:       int nk = index[item];
deba@2205:       int k = repIndex(nk);
deba@2205:       if (nk == k) return;
deba@2205:       
deba@2205:       if (items[k].prevClass != -1) {
deba@2205:         items[items[k].prevClass].nextClass = nk;
deba@2205:       } else {
deba@2205:         firstClass = nk;
deba@2205:       }
deba@2205:       if (items[k].nextClass != -1) {
deba@2205:         items[items[k].nextClass].prevClass = nk;
deba@2205:       }
deba@2205:       
deba@2205:       int idx = items[k].nextItem;
deba@2205:       while (idx != k) {
deba@2205:         items[idx].parent = nk;
deba@2205:         idx = items[idx].nextItem;
deba@2205:       }
deba@2205:       
deba@2205:       items[nk].parent = items[k].parent;
deba@2205:       items[k].parent = nk;
beckerjc@483:     }
beckerjc@483: 
deba@2205:     /// \brief Removes the given element from the structure.
deba@2205:     ///
deba@2205:     /// Removes the element from its component and if the component becomes
deba@2205:     /// empty then removes that component from the component list.
deba@2205:     ///
deba@2205:     /// \warning It is an error to remove an element which is not in
deba@2205:     /// the structure.
deba@2205:     void erase(const Item &item) {
deba@2205:       int idx = index[item];
deba@2205:       if (rep(idx)) {
deba@2205:         int k = idx;
deba@2205:         if (items[k].parent == -1) {
deba@2205:           unlaceClass(idx);
deba@2205:           return;
deba@2205:         } else {
deba@2205:           int nk = items[k].nextItem;
deba@2205:           if (items[k].prevClass != -1) {
deba@2205:             items[items[k].prevClass].nextClass = nk;
deba@2205:           } else {
deba@2205:             firstClass = nk;
deba@2205:           }
deba@2205:           if (items[k].nextClass != -1) {
deba@2205:             items[items[k].nextClass].prevClass = nk;
deba@2205:           }
deba@2205:       
deba@2205:           int idx = items[k].nextItem;
deba@2205:           while (idx != k) {
deba@2205:             items[idx].parent = nk;
deba@2205:             idx = items[idx].nextItem;
deba@2205:           }
deba@2205:           
deba@2205:           items[nk].parent = items[k].parent + 1;
deba@2205:         }
deba@2205:       } else {
deba@2205:         
deba@2205:         int k = repIndex(idx);
deba@2205:         idx = items[k].nextItem;
deba@2205:         while (idx != k) {
deba@2205:           items[idx].parent = k;
deba@2205:           idx = items[idx].nextItem;
deba@2205:         }
beckerjc@483: 
deba@2205:         ++items[k].parent;
beckerjc@483:       }
beckerjc@483: 
deba@2205:       idx = index[item];      
deba@2205:       items[items[idx].prevItem].nextItem = items[idx].nextItem;
deba@2205:       items[items[idx].nextItem].prevItem = items[idx].prevItem;
beckerjc@483: 
deba@2205:     }    
beckerjc@483: 
deba@2205:     /// \brief Moves the given element to another component.
deba@2205:     ///
deba@2205:     /// This method moves the element \e a from its component
deba@2205:     /// to the component of \e comp.
deba@2205:     /// If \e a and \e comp are in the same component then
deba@2205:     /// it returns false otherwise it returns true.
deba@2205:     bool move(const Item &item, const Item &comp) {
deba@2205:       if (repIndex(index[item]) == repIndex(index[comp])) return false;
deba@2205:       erase(item);
deba@2205:       insert(item, comp);
beckerjc@483:       return true;
beckerjc@483:     }
beckerjc@483: 
beckerjc@483: 
deba@2205:     /// \brief Removes the component of the given element from the structure.
deba@2205:     ///
deba@2205:     /// Removes the component of the given element from the structure.
deba@2205:     ///
deba@2205:     /// \warning It is an error to give an element which is not in the
deba@2205:     /// structure.
deba@2205:     void eraseClass(const Item &item) {
deba@2205:       unlaceClass(repIndex(index[item]));
deba@2205:     }
beckerjc@483: 
deba@2205:     /// \brief Lemon style iterator for the representant items.
deba@2205:     ///
deba@2205:     /// ClassIt is a lemon style iterator for the components. It iterates
deba@2205:     /// on the representant items of the classes.
deba@2205:     class ClassIt {
deba@2205:     public:
deba@2205:       /// \brief Constructor of the iterator
deba@2205:       ///
deba@2205:       /// Constructor of the iterator
deba@2205:       ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
deba@2205:         idx = unionFind->firstClass;
beckerjc@483:       }
beckerjc@483: 
deba@2205:       /// \brief Constructor to get invalid iterator
deba@2205:       ///
deba@2205:       /// Constructor to get invalid iterator
deba@2205:       ClassIt(Invalid) : unionFind(0), idx(-1) {}
deba@2205:       
deba@2205:       /// \brief Increment operator
deba@2205:       ///
deba@2205:       /// It steps to the next representant item.
deba@2205:       ClassIt& operator++() {
deba@2205:         idx = unionFind->items[idx].nextClass;
deba@2205:         return *this;
deba@2205:       }
deba@2205:       
deba@2205:       /// \brief Conversion operator
deba@2205:       ///
deba@2205:       /// It converts the iterator to the current representant item.
deba@2205:       operator const Item&() const {
deba@2205:         return unionFind->items[idx].item;
beckerjc@483:       }
beckerjc@483: 
deba@2205:       /// \brief Equality operator
deba@2205:       ///
deba@2205:       /// Equality operator
deba@2205:       bool operator==(const ClassIt& i) { 
deba@2205:         return i.idx == idx;
deba@2205:       }
beckerjc@483: 
deba@2205:       /// \brief Inequality operator
deba@2205:       ///
deba@2205:       /// Inequality operator
deba@2205:       bool operator!=(const ClassIt& i) { 
deba@2205:         return i.idx != idx;
klao@2003:       }
beckerjc@483:       
deba@2205:     private:
deba@2205:       const UnionFindEnum* unionFind;
deba@2205:       int idx;
deba@2205:     };
deba@2205: 
deba@2205:     /// \brief Lemon style iterator for the items of a component.
deba@2205:     ///
deba@2205:     /// ClassIt is a lemon style iterator for the components. It iterates
deba@2205:     /// on the items of a class. By example if you want to iterate on
deba@2205:     /// each items of each classes then you may write the next code.
deba@2205:     ///\code
deba@2205:     /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
deba@2205:     ///   std::cout << "Class: ";
deba@2205:     ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
deba@2205:     ///     std::cout << toString(iit) << ' ' << std::endl;
deba@2205:     ///   }
deba@2205:     ///   std::cout << std::endl;
deba@2205:     /// }
deba@2205:     ///\endcode
deba@2205:     class ItemIt {
deba@2205:     public:
deba@2205:       /// \brief Constructor of the iterator
deba@2205:       ///
deba@2205:       /// Constructor of the iterator. The iterator iterates
deba@2205:       /// on the class of the \c item.
deba@2205:       ItemIt(const UnionFindEnum& ufe, const Item& item) : unionFind(&ufe) {
deba@2205:         idx = unionFind->repIndex(unionFind->index[item]);
beckerjc@483:       }
beckerjc@483: 
deba@2205:       /// \brief Constructor to get invalid iterator
deba@2205:       ///
deba@2205:       /// Constructor to get invalid iterator
deba@2205:       ItemIt(Invalid) : unionFind(0), idx(-1) {}
deba@2205:       
deba@2205:       /// \brief Increment operator
deba@2205:       ///
deba@2205:       /// It steps to the next item in the class.
deba@2205:       ItemIt& operator++() {
deba@2205:         idx = unionFind->items[idx].nextItem;
deba@2205:         if (unionFind->rep(idx)) idx = -1;
deba@2205:         return *this;
klao@2003:       }
deba@2205:       
deba@2205:       /// \brief Conversion operator
deba@2205:       ///
deba@2205:       /// It converts the iterator to the current item.
deba@2205:       operator const Item&() const {
deba@2205:         return unionFind->items[idx].item;
klao@2003:       }
klao@2003: 
deba@2205:       /// \brief Equality operator
deba@2205:       ///
deba@2205:       /// Equality operator
deba@2205:       bool operator==(const ItemIt& i) { 
deba@2205:         return i.idx == idx;
klao@2003:       }
klao@2003: 
deba@2205:       /// \brief Inequality operator
deba@2205:       ///
deba@2205:       /// Inequality operator
deba@2205:       bool operator!=(const ItemIt& i) { 
deba@2205:         return i.idx != idx;
deba@2205:       }
deba@2205:       
deba@2205:     private:
deba@2205:       const UnionFindEnum* unionFind;
deba@2205:       int idx;
beckerjc@483:     };
beckerjc@483: 
beckerjc@483:   };
beckerjc@483: 
beckerjc@483: 
beckerjc@483:   //! @}
beckerjc@483: 
alpar@921: } //namespace lemon
beckerjc@483: 
alpar@921: #endif //LEMON_UNION_FIND_H