COIN-OR::LEMON - Graph Library

Changeset 462:0ab31578af67 in lemon-0.x for src


Ignore:
Timestamp:
04/28/04 22:55:18 (20 years ago)
Author:
beckerjc
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@613
Message:

Doc for the union-find structures.

Location:
src/work/johanna
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/johanna/unionfind.h

    r394 r462  
    22#ifndef HUGO_UNION_FIND_H
    33#define HUGO_UNION_FIND_H
     4
     5//!ingroup auxdat
     6//!\file
     7//!\brief Union-Find data structures.
     8
    49
    510#include <vector>
     
    1116
    1217namespace hugo {
     18
     19  //! \addtogroup auxdat
     20  //! @{
     21
     22  /**
     23   * \brief A \e Union-Find data structure implementation
     24   *
     25   * The class implements the \e Union-Find data structure.
     26   * The union operation uses rank heuristic, while
     27   * the find operation uses path compresson.
     28   * This is a very simple but efficient implementation, providing
     29   * only four methods: join (union), find, insert and size.
     30   * For more features see the \ref UnionFindEnum class.
     31   *
     32   * \pre The elements are automatically added only if the map
     33   * given to the constructor was filled with -1's. Otherwise you
     34   * need to add all the elements by the \ref insert() method.
     35   */
    1336
    1437  template <typename T, typename TIntMap>
     
    2649    UnionFind(TIntMap& m) : map(m) {}
    2750
     51    /**
     52     * \brief Returns the index of the element's component.
     53     *
     54     * The method returns the index of the element's component.
     55     * This is an integer between zero and the number of inserted elements.
     56     */
    2857
    2958    int find(T a)
     
    4574      return comp;
    4675    }
     76
     77    /**
     78     * \brief Insert a new element into the structure.
     79     *
     80     * This method inserts a new element into the data structure.
     81     *
     82     * It is not required to use this method:
     83     * if the map given to the constructor was filled
     84     * with -1's then it is called automatically
     85     * on the first \ref find or \ref join.
     86     *
     87     * The method returns the index of the new component.
     88     */
    4789
    4890    int insert(T a)
     
    5496    }
    5597
     98    /**
     99     * \brief Joining the components of element \e a and element \e b.
     100     *
     101     * This is the \e union operation of the Union-Find structure.
     102     * Joins the component of elemenent \e a and component of
     103     * element \e b. If \e a and \e b are in the same component then
     104     * it returns false otherwise it returns true.
     105     */
     106
    56107    bool join(T a, T b)
    57108    {
     
    73124    }
    74125
     126    /**
     127     * \brief Returns the size of the component of element \e a.
     128     *
     129     * Returns the size of the component of element \e a.
     130     */
     131
    75132    int size(T a)
    76133    {
     
    87144
    88145
     146#ifdef DEVELOPMENT_DOCS
     147
     148  /**
     149   * \brief The auxiliary class for the \ref UnionFindEnum class.
     150   *
     151   * In the \ref UnionFindEnum class all components are represented as
     152   * a std::list.
     153   * Items of these lists are UnionFindEnumItem structures.
     154   *
     155   * The class has four fields:
     156   *  - T me - the actual element
     157   *  - IIter parent - the parent of the element in the union-find structure
     158   *  - int size - the size of the component of the element.
     159   *            Only valid if the element
     160   *            is the leader of the component.
     161   *  - CIter my_class - pointer into the list of components
     162   *            pointing to the component of the element.
     163   *            Only valid if the element is the leader of the component.
     164   */
     165
     166#endif
    89167
    90168  template <typename T>
     
    105183      me(_me), size(1), my_class(_my_class) {}
    106184  };
     185
     186
     187  /**
     188   * \brief A \e Union-Find data structure implementation which
     189   * is able to enumerate the components.
     190   *
     191   * The class implements an \e Union-Find data structure
     192   * which is able to enumerate the components and the items in
     193   * a component. If you don't need this feature then perhaps it's
     194   * better to use the \ref UnionFind class which is more efficient.
     195   *
     196   * The union operation uses rank heuristic, while
     197   * the find operation uses path compresson.
     198   *
     199   * \pre You
     200   * need to add all the elements by the \ref insert() method.
     201   */
     202
    107203
    108204  template <typename T, template <typename Item> class Map>
     
    125221    ClassList classes;
    126222
    127     //    IIter where(const T &a) { return m[a]; }
    128     //    IIter parent(IIter a) { return a->parent; }
    129     //    P sibling(P a) { return &m[a->sibling]; }
    130 
    131223    IIter _find(IIter a) const {
    132224      IIter comp = a;
     
    147239    UnionFindEnum(MapType& _m) : m(_m) {}
    148240
     241
     242    /**
     243     * \brief Insert the given element into a new component.
     244     *
     245     * This method creates a new component consisting only of the
     246     * given element.
     247     */
     248
    149249    void insert(const T &a)
    150250    {
     
    164264    }
    165265
     266    /**
     267     * \brief Find the leader of the component of the given element.
     268     *
     269     * The method returns the leader of the component of the given element.
     270     */
     271
    166272    T find(const T &a) const {
    167273      return _find(m[a])->me;
    168274    }
     275
     276
     277    /**
     278     * \brief Joining the component of element \e a and element \e b.
     279     *
     280     * This is the \e union operation of the Union-Find structure.
     281     * Joins the component of elemenent \e a and component of
     282     * element \e b. If \e a and \e b are in the same component then
     283     * returns false else returns true.
     284     */
    169285
    170286    bool join(T a, T b) {
     
    203319    }
    204320
     321
     322    /**
     323     * \brief Returns the size of the component of element \e a.
     324     *
     325     * Returns the size of the component of element \e a.
     326     */
     327
    205328    int size(const T &a) const {
    206329      return _find(m[a])->size;
    207330    }
    208331
    209    
     332
     333    /**
     334     * \brief Split up the component of the element.
     335     *
     336     * Splitting the component of the element into sigleton
     337     * components (component of size one).
     338     */
     339
    210340    void split(const T &a) {
    211341
     
    231361    }
    232362
     363
     364    /**
     365     * \brief Set the given element to the leader element of its component.
     366     *
     367     * Set the given element to the leader element of its component.
     368     */
     369
     370    void makeRep(const T &a) {
     371
     372      IIter ia = m[a];
     373      IIter la = _find(ia);
     374      if (la == ia) return;
     375
     376      ia->my_class = la->my_class;
     377      la->my_class = 0;
     378
     379      ia->size = la->size;
     380
     381      CIter l = ia->my_class;
     382      l->splice(l->begin(),*l,ia);
     383
     384      ia->parent = ia;
     385      la->parent = ia;
     386    }
     387
     388
     389    /**
     390     * \brief Remove the given element from the structure.
     391     *
     392     * Remove the given element from the structure.
     393     *
     394     * Removes the element from its component and if the component becomes
     395     * empty then removes that component from the component list.
     396     */
    233397    void erase(const T &a) {
    234398
     
    244408        }
    245409        ++la;
    246         la->size = ma->size - 1;
     410        la->size = ma->size;
    247411        la->my_class = ma->my_class;   
    248412      }
     
    252416      }
    253417
     418      la->size--;
    254419      la->my_class->erase(ma);
    255420      m.set(a,0);
    256421    }
     422
     423    /**
     424     * \brief Removes the component of the given element from the structure.
     425     *
     426     * Removes the component of the given element from the structure.
     427     */
    257428
    258429    void eraseClass(const T &a) {
     
    302473    };
    303474
     475    /**
     476     * \brief Sets the iterator to point to the first component.
     477     *
     478     * Sets the iterator to point to the first component.
     479     *
     480     * With the \ref first, \ref valid and \ref next methods you can
     481     * iterate through the components. For example:
     482     * \code
     483     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
     484     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
     485     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
     486     *  for (U.first(iter); U.valid(iter); U.next(iter)) {
     487     *    // iter is convertible to Graph::Node
     488     *    cout << iter << endl;
     489     *  }
     490     * \endcode
     491     */
    304492
    305493    ClassIt& first(ClassIt& it) const {
     
    308496    }
    309497
     498    /**
     499     * \brief Returns whether the iterator is valid.
     500     *
     501     * Returns whether the iterator is valid.
     502     *
     503     * With the \ref first, \ref valid and \ref next methods you can
     504     * iterate through the components. See the example here: \ref first.
     505     */
     506
    310507    bool valid(ClassIt const &it) const {
    311508      return it.valid();
    312509    }
     510
     511    /**
     512     * \brief Steps the iterator to the next component.
     513     *
     514     * Steps the iterator to the next component.
     515     *
     516     * With the \ref first, \ref valid and \ref next methods you can
     517     * iterate through the components. See the example here: \ref first.
     518     */
    313519
    314520    ClassIt& next(ClassIt& it) const {
     
    352558
    353559
     560
     561    /**
     562     * \brief Sets the iterator to point to the first element of the component.
     563     *
     564     * \anchor first2
     565     * Sets the iterator to point to the first element of the component.
     566     *
     567     * With the \ref first2 "first", \ref valid2 "valid"
     568     * and \ref next2 "next" methods you can
     569     * iterate through the elements of a component. For example
     570     * (iterating through the component of the node \e node):
     571     * \code
     572     * Graph::Node node = ...;
     573     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
     574     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
     575     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
     576     *   for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
     577     *     // iiter is convertible to Graph::Node
     578     *     cout << iiter << endl;
     579     *   }
     580     * \endcode
     581     */
     582   
    354583    ItemIt& first(ItemIt& it, const T& a) const {
    355584      it.first( * _find(m[a])->my_class );
     
    357586    }
    358587
     588    /**
     589     * \brief Returns whether the iterator is valid.
     590     *
     591     * \anchor valid2
     592     * Returns whether the iterator is valid.
     593     *
     594     * With the \ref first2 "first", \ref valid2 "valid"
     595     * and \ref next2 "next" methods you can
     596     * iterate through the elements of a component.
     597     * See the example here: \ref first2 "first".
     598     */
     599
    359600    bool valid(ItemIt const &it) const {
    360601      return it.valid();
    361602    }
     603
     604    /**
     605     * \brief Steps the iterator to the next component.
     606     *
     607     * \anchor next2
     608     * Steps the iterator to the next component.
     609     *
     610     * With the \ref first2 "first", \ref valid2 "valid"
     611     * and \ref next2 "next" methods you can
     612     * iterate through the elements of a component.
     613     * See the example here: \ref first2 "first".
     614     */
    362615
    363616    ItemIt& next(ItemIt& it) const {
     
    366619    }
    367620   
    368 
    369 
    370621  };
    371622
     623
     624  //! @}
     625
    372626} //namespace hugo
    373627
  • src/work/johanna/unionfind_test.cc

    r394 r462  
    7676  cout << "size of the class of 6: " << U.size(6) << endl;
    7777  check(U.size(6) == 1);
     78  cout << "size of the class of 2: " << U.size(2) << endl;
     79  check(U.size(2) == 3);
    7880
    7981  cout <<"erase 1: " << endl;
    8082  U.erase(1);
    8183  print(U);
     84
     85  cout << "size of the class of 4: " << U.size(4) << endl;
     86  check(U.size(4) == 2);
     87  cout << "size of the class of 2: " << U.size(2) << endl;
     88  check(U.size(2) == 2);
     89
    8290
    8391  cout <<"erase 1: " << endl;
     
    93101  print(U);
    94102
     103
     104  cout << "size of the class of 4: " << U.size(4) << endl;
     105  check(U.size(4) == 2);
     106  cout << "size of the class of 3: " << U.size(3) << endl;
     107  check(U.size(3) == 1);
     108  cout << "size of the class of 2: " << U.size(2) << endl;
     109  check(U.size(2) == 2);
     110
     111
    95112  cout << "Joining 3 - 4 and 2 - 4 ..." << endl;
    96113  check(U.join(3,4));
    97114  check(!U.join(2,4));
    98115  print(U);
     116
     117
     118  cout << "size of the class of 4: " << U.size(4) << endl;
     119  check(U.size(4) == 3);
     120  cout << "size of the class of 3: " << U.size(3) << endl;
     121  check(U.size(3) == 3);
     122  cout << "size of the class of 2: " << U.size(2) << endl;
     123  check(U.size(2) == 3);
     124
     125  cout << "makeRep(4)" << endl;
     126  U.makeRep(4);
     127  print(U);
     128  cout << "makeRep(3)" << endl;
     129  U.makeRep(3);
     130  print(U);
     131  cout << "makeRep(2)" << endl;
     132  U.makeRep(2);
     133  print(U);
     134
     135  cout << "size of the class of 4: " << U.size(4) << endl;
     136  check(U.size(4) == 3);
     137  cout << "size of the class of 3: " << U.size(3) << endl;
     138  check(U.size(3) == 3);
     139  cout << "size of the class of 2: " << U.size(2) << endl;
     140  check(U.size(2) == 3);
     141
    99142
    100143  cout << "eraseClass 4 ..." << endl;
Note: See TracChangeset for help on using the changeset viewer.