source: lemon-0.x/src/hugo/unionfind.h @ 906:17f31d280385

/* -*- C++ -*-
 * src/hugo/unionfind.h - Part of HUGOlib, a generic C++ optimization library
 *
 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Combinatorial Optimization Research Group, 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 HUGO_UNION_FIND_H
#define HUGO_UNION_FIND_H

//!\ingroup auxdat
//!\file
//!\brief Union-Find data structures.
//!
//!\bug unionfind_test.cc doesn't work with Intel compiler. It compiles but
//!fails to run (Segmentation fault).


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

#include <hugo/invalid.h>

namespace hugo {

  //! \addtogroup 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 The elements are automatically added only if the map 
   * given to the constructor was filled with -1's. Otherwise you
   * need to add all the elements by the \ref insert() method.
   * \bug It is not clear what the constructor parameter is used for.
   */

  template <typename T, typename TIntMap>
  class UnionFind {
    
  public:
    typedef T ElementType;
    typedef std::pair<int,int> PairType;

  private:
    std::vector<PairType> data;
    TIntMap& map;

  public:
    UnionFind(TIntMap& m) : map(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(T a)
    {
      int comp0 = map[a];
      if (comp0 < 0) {
        return insert(a);
      }
      int comp = comp0;
      int next;
      while ( (next = data[comp].first) != comp) {
        comp = next;
      }
      while ( (next = data[comp0].first) != comp) {
        data[comp0].first = comp;
        comp0 = next;
      }

      return comp;
    }

    /**
     * \brief Insert a new element into the structure.
     *
     * This method inserts a new element into the data structure. 
     *
     * It is not required to use this method:
     * if the map given to the constructor was filled 
     * with -1's then it is called automatically
     * on the first \ref find or \ref join.
     *
     * The method returns the index of the new component.
     */

    int insert(T a)
    {
      int n = data.size();
      data.push_back(std::make_pair(n, 1));
      map.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 elemenent \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(T a, T b)
    {
      int ca = find(a);
      int cb = find(b);

      if ( ca == cb ) 
        return false;

      if ( data[ca].second > data[cb].second ) {
        data[cb].first = ca;
        data[ca].second += data[cb].second;
      }
      else {
        data[ca].first = cb;
        data[cb].second += data[ca].second;
      }
      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(T a)
    {
      int ca = find(a);
      return data[ca].second;
    }

  };




  /*******************************************************/


#ifdef DEVELOPMENT_DOCS

  /**
   * \brief The auxiliary class for the \ref UnionFindEnum class.
   *
   * In the \ref UnionFindEnum class all components are represented as
   * a std::list. 
   * Items of these lists are UnionFindEnumItem structures.
   *
   * The class has four fields:
   *  - T me - the actual element 
   *  - IIter parent - the parent of the element in the union-find structure
   *  - int size - the size of the component of the element. 
   *            Only valid if the element
   *            is the leader of the component.
   *  - CIter my_class - pointer into the list of components 
   *            pointing to the component of the element.
   *            Only valid if the element is the leader of the component.
   */

#endif

  template <typename T>
  struct UnionFindEnumItem {

    typedef std::list<UnionFindEnumItem> ItemList;
    typedef std::list<ItemList> ClassList;
    typedef typename ItemList::iterator IIter;
    typedef typename ClassList::iterator CIter;

    T me;
    IIter parent;
    int size;
    CIter my_class;

    UnionFindEnumItem() {}
    UnionFindEnumItem(const T &_me, CIter _my_class): 
      me(_me), size(1), my_class(_my_class) {}
  };


  /**
   * \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 T, template <typename Item> class Map>
  class UnionFindEnum {

    typedef std::list<UnionFindEnumItem<T> > ItemList;
    typedef std::list<ItemList> ClassList;
    typedef typename ItemList::iterator IIter;
    typedef typename ItemList::const_iterator IcIter;
    typedef typename ClassList::iterator CIter;
    typedef typename ClassList::const_iterator CcIter;

  public:
    typedef T ElementType;
    typedef UnionFindEnumItem<T> ItemType;
    typedef Map< IIter > MapType;

  private:
    MapType& m;
    ClassList classes;

    IIter _find(IIter a) const {
      IIter comp = a;
      IIter next;
      while( (next = comp->parent) != comp ) {
        comp = next;
      }

      IIter comp1 = a;
      while( (next = comp1->parent) != comp ) {
        comp1->parent = comp->parent;
        comp1 = next;
      }
      return comp;
    }

  public:
    UnionFindEnum(MapType& _m) : m(_m) {}


    /**
     * \brief Insert the given element into a new component.
     *
     * This method creates a new component consisting only of the
     * given element.
     */

    void insert(const T &a)
    {


      classes.push_back(ItemList());
      CIter aclass = classes.end();
      --aclass;

      ItemList &alist = *aclass;
      alist.push_back(ItemType(a, aclass));
      IIter ai = alist.begin();

      ai->parent = ai;
      m.set(a, ai);

    }

    /**
     * \brief Insert the given element into the component of the others.
     *
     * This methods insert the element \e a into the component of the
     * element \e comp. 
     */

    void insert(const T &a, const T &comp) {
      
      IIter clit = _find(m[comp]);
      ItemList &c = *clit->my_class;
      c.push_back(ItemType(a,0));
      IIter ai = c.end();
      --ai;
      ai->parent = clit;
      m.set(a, ai);
      ++clit->size;
    }


    /**
     * \brief Find the leader of the component of the given element.
     *
     * The method returns the leader of the component of the given element.
     */

    T find(const T &a) const {
      return _find(m[a])->me;
    }


    /**
     * \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 elemenent \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(T a, T b) {

      IIter ca = _find(m[a]);
      IIter cb = _find(m[b]);

      if ( ca == cb ) {
        return false;
      }

      if ( ca->size > cb->size ) {

        cb->parent = ca->parent;
        ca->size += cb->size;
        
        ItemList &alist = *ca->my_class;
        alist.splice(alist.end(),*cb->my_class);

        classes.erase(cb->my_class);
        cb->my_class = 0;
      }
      else {

        ca->parent = cb->parent;
        cb->size += ca->size;
        
        ItemList &blist = *cb->my_class;
        blist.splice(blist.end(),*ca->my_class);

        classes.erase(ca->my_class);
        ca->my_class = 0;
      }

      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 T &a) const {
      return _find(m[a])->size;
    }


    /**
     * \brief Split up the component of the element. 
     *
     * Splitting the component of the element into sigleton
     * components (component of size one).
     */

    void split(const T &a) {

      IIter ca = _find(m[a]);
 
      if ( ca->size == 1 )
        return;
      
      CIter aclass = ca->my_class;

      for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
        classes.push_back(ItemList());
        CIter nl = --classes.end();
        nl->splice(nl->end(), *aclass, curr);

        curr->size=1;
        curr->parent=curr;
        curr->my_class = nl;
      }

      ca->size=1;
      return;
    }


    /**
     * \brief Set the given element to the leader element of its component.
     *
     * Set the given element to the leader element of its component.
     */

    void makeRep(const T &a) {

      IIter ia = m[a];
      IIter la = _find(ia);
      if (la == ia) return;

      ia->my_class = la->my_class;
      la->my_class = 0;

      ia->size = la->size;

      CIter l = ia->my_class;
      l->splice(l->begin(),*l,ia);

      ia->parent = ia;
      la->parent = ia;
    }

    /**
     * \brief Move the given element to an other 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 T &a, const T &comp) {

      IIter ai = m[a];
      IIter lai = _find(ai);
      IIter clit = _find(m[comp]);

      if (lai == clit)
        return false;

      ItemList &c = *clit->my_class;

      bool is_leader = (lai == ai);
      bool singleton = false;

      if (is_leader) {
        ++lai;
      }

      c.splice(c.end(), *lai->my_class, ai);

      if (is_leader) {
        if (ai->size == 1) {
          classes.erase(ai->my_class);
          singleton = true;
        }
        else {
          lai->size = ai->size; 
          lai->my_class = ai->my_class; 
        }
      }
      if (!singleton) {
        for (IIter i = lai; i != lai->my_class->end(); ++i)
          i->parent = lai;
        --lai->size;
      }

      ai->parent = clit;
      ai->my_class = 0;
      ++clit->size;

      return true;
    }


    /**
     * \brief Remove the given element from the structure.
     *
     * Remove 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.
     */
    void erase(const T &a) {

      IIter ma = m[a];
      if (ma == 0) return;

      IIter la = _find(ma);
      if (la == ma) {
        if (ma -> size == 1){
          classes.erase(ma->my_class);
          m.set(a,0);
          return;
        }
        ++la;
        la->size = ma->size; 
        la->my_class = ma->my_class;    
      }

      for (IIter i = la; i != la->my_class->end(); ++i) {
        i->parent = la;
      }

      la->size--;
      la->my_class->erase(ma);
      m.set(a,0);
    }

    /**
     * \brief Removes the component of the given element from the structure.
     *
     * Removes the component of the given element from the structure.
     */

    void eraseClass(const T &a) {
      IIter ma = m[a];
      if (ma == 0) return;
#     ifdef DEBUG
      CIter c = _find(ma)->my_class;
      for (IIter i=c->begin(); i!=c->end(); ++i)
        m.set(i->me, 0);
#     endif
      classes.erase(_find(ma)->my_class);
    }


    class ClassIt {
      friend class UnionFindEnum;

      CcIter i;
    public:
      ClassIt(Invalid): i(0) {}
      ClassIt() {}
      
      operator const T& () const { 
        ItemList const &ll = *i;
        return (ll.begin())->me; }
      bool operator == (ClassIt it) const {
        return (i == it.i);
      }
      bool operator != (ClassIt it) const {
        return (i != it.i);
      }
      bool operator < (ClassIt it) const {
        return (i < it.i);
      }

      bool valid() const { return i != 0; }
    private:
      void first(const ClassList &l) { i = l.begin(); validate(l); }
      void next(const ClassList &l) {
        ++i; 
        validate(l);
      }
      void validate(const ClassList &l) {
        if ( i == l.end() ) 
          i = 0;
      }
    };

    /**
     * \brief Sets the iterator to point to the first component.
     * 
     * Sets the iterator to point to the first component.
     *
     * With the \ref first, \ref valid and \ref next methods you can
     * iterate through the components. For example:
     * \code
     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
     *  for (U.first(iter); U.valid(iter); U.next(iter)) {
     *    // iter is convertible to Graph::Node
     *    cout << iter << endl;
     *  }
     * \endcode
     */

    ClassIt& first(ClassIt& it) const {
      it.first(classes);
      return it;
    }

    /**
     * \brief Returns whether the iterator is valid.
     *
     * Returns whether the iterator is valid.
     *
     * With the \ref first, \ref valid and \ref next methods you can
     * iterate through the components. See the example here: \ref first.
     */

    bool valid(ClassIt const &it) const {
      return it.valid(); 
    }

    /**
     * \brief Steps the iterator to the next component. 
     *
     * Steps the iterator to the next component.
     *
     * With the \ref first, \ref valid and \ref next methods you can
     * iterate through the components. See the example here: \ref first.
     */

    ClassIt& next(ClassIt& it) const {
      it.next(classes);
      return it;
    }


    class ItemIt {
      friend class UnionFindEnum;

      IcIter i;
      const ItemList *l;
    public:
      ItemIt(Invalid): i(0) {}
      ItemIt() {}
      
      operator const T& () const { return i->me; }
      bool operator == (ItemIt it) const {
        return (i == it.i);
      }
      bool operator != (ItemIt it) const {
        return (i != it.i);
      }
      bool operator < (ItemIt it) const {
        return (i < it.i);
      }

      bool valid() const { return i != 0; }
    private:
      void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
      void next() {
        ++i; 
        validate();
      }
      void validate() {
        if ( i == l->end() ) 
          i = 0;
      }
    };



    /**
     * \brief Sets the iterator to point to the first element of the component.
     * 
     * \anchor first2 
     * Sets the iterator to point to the first element of the component.
     *
     * With the \ref first2 "first", \ref valid2 "valid" 
     * and \ref next2 "next" methods you can
     * iterate through the elements of a component. For example
     * (iterating through the component of the node \e node):
     * \code
     * Graph::Node node = ...;
     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
     *   for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
     *     // iiter is convertible to Graph::Node
     *     cout << iiter << endl;
     *   }
     * \endcode
     */
    
    ItemIt& first(ItemIt& it, const T& a) const {
      it.first( * _find(m[a])->my_class );
      return it;
    }

    /**
     * \brief Returns whether the iterator is valid.
     *
     * \anchor valid2
     * Returns whether the iterator is valid.
     *
     * With the \ref first2 "first", \ref valid2 "valid" 
     * and \ref next2 "next" methods you can
     * iterate through the elements of a component.
     * See the example here: \ref first2 "first".
     */

    bool valid(ItemIt const &it) const {
      return it.valid(); 
    }

    /**
     * \brief Steps the iterator to the next component. 
     *
     * \anchor next2
     * Steps the iterator to the next component.
     *
     * With the \ref first2 "first", \ref valid2 "valid" 
     * and \ref next2 "next" methods you can
     * iterate through the elements of a component.
     * See the example here: \ref first2 "first".
     */

    ItemIt& next(ItemIt& it) const {
      it.next();
      return it;
    }
    
  };


  //! @}

} //namespace hugo

#endif //HUGO_UNION_FIND_H