source: lemon-0.x/lemon/unionfind.h @ 2427:d40c31b08d6f

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2007
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#ifndef LEMON_UNION_FIND_H
#define LEMON_UNION_FIND_H

//!\ingroup auxdat
//!\file
//!\brief Union-Find data structures.
//!

#include <vector>
#include <list>
#include <utility>
#include <algorithm>

#include <lemon/bits/invalid.h>

namespace lemon {

  /// \ingroup auxdat
  ///
  /// \brief A \e Union-Find data structure implementation
  ///
  /// The class implements the \e Union-Find data structure. 
  /// The union operation uses rank heuristic, while
  /// the find operation uses path compression.
  /// This is a very simple but efficient implementation, providing 
  /// only four methods: join (union), find, insert and size.
  /// For more features see the \ref UnionFindEnum class.
  ///
  /// It is primarily used in Kruskal algorithm for finding minimal
  /// cost spanning tree in a graph.
  /// \sa kruskal()
  ///
  /// \pre You need to add all the elements by the \ref insert()
  /// method.  
  template <typename _ItemIntMap>
  class UnionFind {
  public:

    typedef _ItemIntMap ItemIntMap;
    typedef typename ItemIntMap::Key Item;

  private:
    // If the items vector stores negative value for an item then
    // that item is root item and it has -items[it] component size.
    // Else the items[it] contains the index of the parent.
    std::vector<int> items;
    ItemIntMap& index;

    bool rep(int idx) const {
      return items[idx] < 0;
    }

    int repIndex(int idx) const {
      int k = idx;
      while (!rep(k)) {
        k = items[k] ;
      }
      while (idx != k) {
        int next = items[idx];
        const_cast<int&>(items[idx]) = k;
        idx = next;
      }
      return k;
    }

  public:

    /// \brief Constructor
    ///
    /// Constructor of the UnionFind class. You should give an item to
    /// integer map which will be used from the data structure. If you
    /// modify directly this map that may cause segmentation fault,
    /// invalid data structure, or infinite loop when you use again
    /// the union-find.
    UnionFind(ItemIntMap& m) : index(m) {}

    /// \brief Returns the index of the element's component.
    ///
    /// The method returns the index of the element's component.
    /// This is an integer between zero and the number of inserted elements.
    ///
    int find(const Item& a) {
      return repIndex(index[a]);
    }

    /// \brief Clears the union-find data structure
    ///
    /// Erase each item from the data structure.
    void clear() {
      items.clear();
    }

    /// \brief Inserts a new element into the structure.
    ///
    /// This method inserts a new element into the data structure. 
    ///
    /// The method returns the index of the new component.
    int insert(const Item& a) {
      int n = items.size();
      items.push_back(-1);
      index.set(a,n);
      return n;
    }

    /// \brief Joining the components of element \e a and element \e b.
    ///
    /// This is the \e union operation of the Union-Find structure. 
    /// 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
    /// it returns false otherwise it returns true.
    bool join(const Item& a, const Item& b) {
      int ka = repIndex(index[a]);
      int kb = repIndex(index[b]);

      if ( ka == kb ) 
        return false;

      if (items[ka] < items[kb]) {
        items[ka] += items[kb];
        items[kb] = ka;
      } else {
        items[kb] += items[ka];
        items[ka] = kb;
      }
      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& a) {
      int k = repIndex(index[a]);
      return - items[k];
    }

  };

  /// \ingroup auxdat
  ///
  /// \brief A \e Union-Find data structure implementation which
  /// is able to enumerate the components.
  ///
  /// The class implements a \e Union-Find data structure
  /// which is able to enumerate the components and the items in
  /// a component. If you don't need this feature then perhaps it's
  /// better to use the \ref UnionFind class which is more efficient.
  ///
  /// The union operation uses rank heuristic, while
  /// the find operation uses path compression.
  ///
  /// \pre You need to add all the elements by the \ref insert()
  /// method.
  ///
  template <typename _ItemIntMap>
  class UnionFindEnum {
  public:
    
    typedef _ItemIntMap ItemIntMap;
    typedef typename ItemIntMap::Key Item;

  private:
    
    // If the parent stores negative value for an item then that item
    // is root item and it has -items[it].parent component size.  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. 
    struct ItemT {
      int parent;
      Item item;

      int nextItem, prevItem;
      int nextClass, prevClass;
    };

    std::vector<ItemT> items;
    ItemIntMap& index;

    int firstClass;


    bool rep(int idx) const {
      return items[idx].parent < 0;
    }

    int repIndex(int idx) const {
      int k = idx;
      while (!rep(k)) {
        k = items[k].parent;
      }
      while (idx != k) {
        int next = items[idx].parent;
        const_cast<int&>(items[idx].parent) = k;
        idx = next;
      }
      return k;
    }

    void unlaceClass(int k) {
      if (items[k].prevClass != -1) {
        items[items[k].prevClass].nextClass = items[k].nextClass;
      } else {
        firstClass = items[k].nextClass;
      }
      if (items[k].nextClass != -1) {
        items[items[k].nextClass].prevClass = items[k].prevClass;
      }
    } 

    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) {}
    
    /// \brief Inserts the given element into a new component.
    ///
    /// This method creates a new component consisting only of the
    /// given element.
    ///
    void insert(const Item& item) {
      ItemT t;

      int idx = items.size();
      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);
    }

    /// \brief Inserts the given element into the component of the others.
    ///
    /// 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();
      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);
    }

    /// \brief Clears the union-find data structure
    ///
    /// Erase each item from the data structure.
    void clear() {
      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;
    }

    /// \brief Joining the component of element \e a and element \e b.
    ///
    /// This is the \e union operation of the Union-Find structure. 
    /// 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) {

      int ak = repIndex(index[a]);
      int bk = repIndex(index[b]);

      if (ak == bk) {
        return false;
      }

      if ( items[ak].parent < items[bk].parent ) {
        unlaceClass(bk);
        items[ak].parent += items[bk].parent;
        items[bk].parent = ak;
      } else {
        unlaceClass(ak);
        items[bk].parent += items[ak].parent;
        items[ak].parent = bk;
      }
      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;
        
        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;
    }

    /// \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];
      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;
          }
          
          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.
    ///
    /// 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(const Item &item) {
      unlaceClass(repIndex(index[item]));
    }

    /// \brief Lemon style iterator for the representant items.
    ///
    /// ClassIt is a lemon style iterator for the components. It iterates
    /// on the representant items of the classes.
    class ClassIt {
    public:
      /// \brief Constructor of the iterator
      ///
      /// Constructor of the iterator
      ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
        idx = unionFind->firstClass;
      }

      /// \brief Constructor to get invalid iterator
      ///
      /// Constructor to get invalid iterator
      ClassIt(Invalid) : unionFind(0), idx(-1) {}
      
      /// \brief Increment operator
      ///
      /// It steps to the next representant item.
      ClassIt& operator++() {
        idx = unionFind->items[idx].nextClass;
        return *this;
      }
      
      /// \brief Conversion operator
      ///
      /// It converts the iterator to the current representant item.
      operator const Item&() const {
        return unionFind->items[idx].item;
      }

      /// \brief Equality operator
      ///
      /// Equality operator
      bool operator==(const ClassIt& i) { 
        return i.idx == idx;
      }

      /// \brief Inequality operator
      ///
      /// Inequality operator
      bool operator!=(const ClassIt& i) { 
        return i.idx != idx;
      }
      
    private:
      const UnionFindEnum* unionFind;
      int idx;
    };

    /// \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 UnionFindEnum& ufe, const Item& item) : unionFind(&ufe) {
        idx = unionFind->repIndex(unionFind->index[item]);
      }

      /// \brief Constructor to get invalid iterator
      ///
      /// Constructor to get invalid iterator
      ItemIt(Invalid) : unionFind(0), idx(-1) {}
      
      /// \brief Increment operator
      ///
      /// It steps to the next item in the class.
      ItemIt& operator++() {
        idx = unionFind->items[idx].nextItem;
        if (unionFind->rep(idx)) idx = -1;
        return *this;
      }
      
      /// \brief Conversion operator
      ///
      /// It converts the iterator to the current item.
      operator const Item&() const {
        return unionFind->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 UnionFindEnum* unionFind;
      int idx;
    };

  };


  //! @}

} //namespace lemon

#endif //LEMON_UNION_FIND_H