COIN-OR::LEMON - Graph Library

Changeset 481:54d8feda437b in lemon-0.x for src/work/johanna


Ignore:
Timestamp:
04/29/04 18:45:40 (21 years ago)
Author:
beckerjc
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@638
Message:

Three new methods in UnionFindEnum?.
UnionFindEnum? completed.

Location:
src/work/johanna
Files:
2 edited

Legend:

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

    r462 r481  
    265265
    266266    /**
     267     * \brief Insert the given element into the component of the others.
     268     *
     269     * This methods insert the element \e a into the component of the
     270     * element \e comp.
     271     */
     272
     273    void insert(const T &a, const T &comp) {
     274     
     275      IIter clit = _find(m[comp]);
     276      ItemList &c = *clit->my_class;
     277      c.push_back(ItemType(a,0));
     278      IIter ai = c.end();
     279      --ai;
     280      ai->parent = clit;
     281      m.set(a, ai);
     282      ++clit->size;
     283    }
     284
     285
     286    /**
    267287     * \brief Find the leader of the component of the given element.
    268288     *
     
    384404      ia->parent = ia;
    385405      la->parent = ia;
     406    }
     407
     408    /**
     409     * \brief Move the given element to an other component.
     410     *
     411     * This method moves the element \e a from its component
     412     * to the component of \e comp.
     413     * If \e a and \e comp are in the same component then
     414     * it returns false otherwise it returns true.
     415     */
     416
     417    bool move(const T &a, const T &comp) {
     418
     419      IIter ai = m[a];
     420      IIter lai = _find(ai);
     421      IIter clit = _find(m[comp]);
     422
     423      if (lai == clit)
     424        return false;
     425
     426      ItemList &c = *clit->my_class;
     427
     428      bool is_leader = (lai == ai);
     429      bool singleton = false;
     430
     431      if (is_leader) {
     432        ++lai;
     433      }
     434
     435      c.splice(c.end(), *lai->my_class, ai);
     436
     437      if (is_leader) {
     438        if (ai->size == 1) {
     439          classes.erase(ai->my_class);
     440          singleton = true;
     441        }
     442        else {
     443          lai->size = ai->size;
     444          lai->my_class = ai->my_class;
     445        }
     446      }
     447      if (!singleton) {
     448        for (IIter i = lai; i != lai->my_class->end(); ++i)
     449          i->parent = lai;
     450        --lai->size;
     451      }
     452
     453      ai->parent = clit;
     454      ai->my_class = 0;
     455      ++clit->size;
     456
     457      return true;
    386458    }
    387459
  • src/work/johanna/unionfind_test.cc

    r462 r481  
    7070  print(U);
    7171
     72  cout << "Inserting 8 to the component of 5 ..." << endl;
     73  U.insert(8,5);
     74  print(U);
     75
    7276  cout << "size of the class of 4: " << U.size(4) << endl;
    7377  check(U.size(4) == 3);
    7478  cout << "size of the class of 5: " << U.size(5) << endl;
    75   check(U.size(5) == 2);
     79  check(U.size(5) == 3);
    7680  cout << "size of the class of 6: " << U.size(6) << endl;
    7781  check(U.size(6) == 1);
     
    7983  check(U.size(2) == 3);
    8084
     85  cout << "Inserting 9 ..." << endl;
     86  U.insert(9);
     87  print(U);
     88  cout << "Inserting 10 to the component of 9 ..." << endl;
     89  U.insert(10,9);
     90  print(U);
     91
     92  cout << "Joining 8 and 10..." << endl;
     93  check(U.join(8,10));
     94  print(U);
     95
     96  cout << "Move 9 to the class of 4 ..." << endl;
     97  check(U.move(9,4));
     98  print(U);
     99
     100  cout << "Move 9 to the class of 2 ..." << endl;
     101  check(!U.move(9,2));
     102  print(U);
     103
     104  cout << "size of the class of 4: " << U.size(4) << endl;
     105  check(U.size(4) == 4);
     106  cout << "size of the class of 9: " << U.size(9) << endl;
     107  check(U.size(9) == 4);
     108 
     109  cout << "Move 5 to the class of 6 ..." << endl;
     110  check(U.move(5,6));
     111  print(U);
     112
     113  cout << "size of the class of 5: " << U.size(5) << endl;
     114  check(U.size(5) == 2);
     115  cout << "size of the class of 8: " << U.size(8) << endl;
     116  check(U.size(8) == 3);
     117
     118  cout << "Move 7 to the class of 10 ..." << endl;
     119  check(U.move(7,10));
     120  print(U);
     121
     122  cout << "size of the class of 7: " << U.size(7) << endl;
     123  check(U.size(7) == 4);
     124
     125  cout <<"erase 9: " << endl;
     126  U.erase(9);
     127  print(U);
     128
    81129  cout <<"erase 1: " << endl;
    82130  U.erase(1);
     
    97145  print(U);
    98146
    99   cout << "split the class of 5: " << endl;
    100   U.split(5);
     147  cout << "split the class of 8: " << endl;
     148  U.split(8);
    101149  print(U);
    102150
Note: See TracChangeset for help on using the changeset viewer.