1.1 --- a/lemon/kruskal.h Wed Sep 06 10:28:13 2006 +0000
1.2 +++ b/lemon/kruskal.h Wed Sep 06 11:17:12 2006 +0000
1.3 @@ -24,6 +24,8 @@
1.4 #include <lemon/unionfind.h>
1.5 #include <lemon/bits/utility.h>
1.6 #include <lemon/bits/traits.h>
1.7 +#include <lemon/time_measure.h>
1.8 +#include <iostream>
1.9
1.10 ///\ingroup spantree
1.11 ///\file
1.12 @@ -117,8 +119,12 @@
1.13 typedef typename GR::template NodeMap<int> NodeIntMap;
1.14 typedef typename GR::Node Node;
1.15
1.16 - NodeIntMap comp(g, -1);
1.17 - UnionFind<Node,NodeIntMap> uf(comp);
1.18 + Timer timer;
1.19 + NodeIntMap comp(g);
1.20 + UnionFind<Node,NodeIntMap> uf(comp);
1.21 + for (typename GR::NodeIt it(g); it != INVALID; ++it) {
1.22 + uf.insert(it);
1.23 + }
1.24
1.25 EdgeCost tot_cost = 0;
1.26 for (typename IN::const_iterator p = in.begin();
1.27 @@ -132,6 +138,7 @@
1.28 out.set((*p).first, false);
1.29 }
1.30 }
1.31 + std::cout << timer << std::endl;
1.32 return tot_cost;
1.33 }
1.34
2.1 --- a/lemon/max_matching.h Wed Sep 06 10:28:13 2006 +0000
2.2 +++ b/lemon/max_matching.h Wed Sep 06 11:17:12 2006 +0000
2.3 @@ -65,7 +65,8 @@
2.4 typedef typename Graph::NodeIt NodeIt;
2.5 typedef typename Graph::IncEdgeIt IncEdgeIt;
2.6
2.7 - typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
2.8 + typedef typename Graph::template NodeMap<int> UFECrossRef;
2.9 + typedef UnionFindEnum<Node, UFECrossRef> UFE;
2.10
2.11 public:
2.12
2.13 @@ -121,10 +122,12 @@
2.14 //undefined for the base nodes of the blossoms (i.e. for the
2.15 //representative elements of UFE blossom) and for the nodes in C
2.16
2.17 - typename UFE::MapType blossom_base(g);
2.18 + UFECrossRef blossom_base(g);
2.19 UFE blossom(blossom_base);
2.20 - typename UFE::MapType tree_base(g);
2.21 +
2.22 + UFECrossRef tree_base(g);
2.23 UFE tree(tree_base);
2.24 +
2.25 //If these UFE's would be members of the class then also
2.26 //blossom_base and tree_base should be a member.
2.27
2.28 @@ -549,15 +552,13 @@
2.29 _mate.set(u,tmp);
2.30 }
2.31 Node y=blossom.find(x);
2.32 - typename UFE::ItemIt it;
2.33 - for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {
2.34 - if ( position[it] == D ) {
2.35 - typename UFE::ItemIt b_it;
2.36 - for (blossom.first(b_it,it); blossom.valid(b_it); blossom.next(b_it)) {
2.37 - position.set( b_it ,C);
2.38 + for (typename UFE::ItemIt tit(tree, y); tit != INVALID; ++tit) {
2.39 + if ( position[tit] == D ) {
2.40 + for (typename UFE::ItemIt bit(blossom, tit); bit != INVALID; ++bit) {
2.41 + position.set( bit ,C);
2.42 }
2.43 - blossom.eraseClass(it);
2.44 - } else position.set( it ,C);
2.45 + blossom.eraseClass(tit);
2.46 + } else position.set( tit ,C);
2.47 }
2.48 tree.eraseClass(y);
2.49
3.1 --- a/lemon/unionfind.h Wed Sep 06 10:28:13 2006 +0000
3.2 +++ b/lemon/unionfind.h Wed Sep 06 11:17:12 2006 +0000
3.3 @@ -36,701 +36,543 @@
3.4 //! \addtogroup auxdat
3.5 //! @{
3.6
3.7 - /**
3.8 - * \brief A \e Union-Find data structure implementation
3.9 - *
3.10 - * The class implements the \e Union-Find data structure.
3.11 - * The union operation uses rank heuristic, while
3.12 - * the find operation uses path compression.
3.13 - * This is a very simple but efficient implementation, providing
3.14 - * only four methods: join (union), find, insert and size.
3.15 - * For more features see the \ref UnionFindEnum class.
3.16 - *
3.17 - * It is primarily used in Kruskal algorithm for finding minimal
3.18 - * cost spanning tree in a graph.
3.19 - * \sa kruskal()
3.20 - *
3.21 - * \pre The elements are automatically added only if the map
3.22 - * given to the constructor was filled with -1's. Otherwise you
3.23 - * need to add all the elements by the \ref insert() method.
3.24 - * \bug It is not clear what the constructor parameter is used for.
3.25 - */
3.26 -
3.27 - template <typename T, typename TIntMap>
3.28 + /// \brief A \e Union-Find data structure implementation
3.29 + ///
3.30 + /// The class implements the \e Union-Find data structure.
3.31 + /// The union operation uses rank heuristic, while
3.32 + /// the find operation uses path compression.
3.33 + /// This is a very simple but efficient implementation, providing
3.34 + /// only four methods: join (union), find, insert and size.
3.35 + /// For more features see the \ref UnionFindEnum class.
3.36 + ///
3.37 + /// It is primarily used in Kruskal algorithm for finding minimal
3.38 + /// cost spanning tree in a graph.
3.39 + /// \sa kruskal()
3.40 + ///
3.41 + /// \pre You need to add all the elements by the \ref insert()
3.42 + /// method.
3.43 + template <typename Item, typename ItemIntMap>
3.44 class UnionFind {
3.45
3.46 public:
3.47 - typedef T ElementType;
3.48 - typedef std::pair<int,int> PairType;
3.49 + typedef Item ElementType;
3.50
3.51 private:
3.52 - std::vector<PairType> data;
3.53 - TIntMap& map;
3.54 + // If the items vector stores negative value for an item then
3.55 + // that item is root item and it has -items[it] component size.
3.56 + // Else the items[it] contains the index of the parent.
3.57 + std::vector<int> items;
3.58 + ItemIntMap& index;
3.59 +
3.60 + bool rep(int idx) const {
3.61 + return items[idx] < 0;
3.62 + }
3.63 +
3.64 + int repIndex(int idx) const {
3.65 + int k = idx;
3.66 + while (!rep(k)) {
3.67 + k = items[k] ;
3.68 + }
3.69 + while (idx != k) {
3.70 + int next = items[idx];
3.71 + const_cast<int&>(items[idx]) = k;
3.72 + idx = next;
3.73 + }
3.74 + return k;
3.75 + }
3.76
3.77 public:
3.78 - UnionFind(TIntMap& m) : map(m) {}
3.79
3.80 - /**
3.81 - * \brief Returns the index of the element's component.
3.82 - *
3.83 - * The method returns the index of the element's component.
3.84 - * This is an integer between zero and the number of inserted elements.
3.85 - */
3.86 + /// \brief Constructor
3.87 + ///
3.88 + /// Constructor of the UnionFind class. You should give an item to
3.89 + /// integer map which will be used from the data structure. If you
3.90 + /// modify directly this map that may cause segmentation fault,
3.91 + /// invalid data structure, or infinite loop when you use again
3.92 + /// the union-find.
3.93 + UnionFind(ItemIntMap& m) : index(m) {}
3.94
3.95 - int find(T a)
3.96 - {
3.97 - int comp0 = map[a];
3.98 - if (comp0 < 0) {
3.99 - return insert(a);
3.100 - }
3.101 - int comp = comp0;
3.102 - int next;
3.103 - while ( (next = data[comp].first) != comp) {
3.104 - comp = next;
3.105 - }
3.106 - while ( (next = data[comp0].first) != comp) {
3.107 - data[comp0].first = comp;
3.108 - comp0 = next;
3.109 - }
3.110 -
3.111 - return comp;
3.112 + /// \brief Returns the index of the element's component.
3.113 + ///
3.114 + /// The method returns the index of the element's component.
3.115 + /// This is an integer between zero and the number of inserted elements.
3.116 + ///
3.117 + int find(const Item& a) {
3.118 + return repIndex(index[a]);
3.119 }
3.120
3.121 - /**
3.122 - * \brief Inserts a new element into the structure.
3.123 - *
3.124 - * This method inserts a new element into the data structure.
3.125 - *
3.126 - * It is not required to use this method:
3.127 - * if the map given to the constructor was filled
3.128 - * with -1's then it is called automatically
3.129 - * on the first \ref find or \ref join.
3.130 - *
3.131 - * The method returns the index of the new component.
3.132 - */
3.133 -
3.134 - int insert(T a)
3.135 - {
3.136 - int n = data.size();
3.137 - data.push_back(std::make_pair(n, 1));
3.138 - map.set(a,n);
3.139 + /// \brief Inserts a new element into the structure.
3.140 + ///
3.141 + /// This method inserts a new element into the data structure.
3.142 + ///
3.143 + /// The method returns the index of the new component.
3.144 + int insert(const Item& a) {
3.145 + int n = items.size();
3.146 + items.push_back(-1);
3.147 + index.set(a,n);
3.148 return n;
3.149 }
3.150
3.151 - /**
3.152 - * \brief Joining the components of element \e a and element \e b.
3.153 - *
3.154 - * This is the \e union operation of the Union-Find structure.
3.155 - * Joins the component of element \e a and component of
3.156 - * element \e b. If \e a and \e b are in the same component then
3.157 - * it returns false otherwise it returns true.
3.158 - */
3.159 + /// \brief Joining the components of element \e a and element \e b.
3.160 + ///
3.161 + /// This is the \e union operation of the Union-Find structure.
3.162 + /// Joins the component of element \e a and component of
3.163 + /// element \e b. If \e a and \e b are in the same component then
3.164 + /// it returns false otherwise it returns true.
3.165 + bool join(const Item& a, const Item& b) {
3.166 + int ka = repIndex(index[a]);
3.167 + int kb = repIndex(index[b]);
3.168
3.169 - bool join(T a, T b)
3.170 - {
3.171 - int ca = find(a);
3.172 - int cb = find(b);
3.173 -
3.174 - if ( ca == cb )
3.175 + if ( ka == kb )
3.176 return false;
3.177
3.178 - if ( data[ca].second > data[cb].second ) {
3.179 - data[cb].first = ca;
3.180 - data[ca].second += data[cb].second;
3.181 - }
3.182 - else {
3.183 - data[ca].first = cb;
3.184 - data[cb].second += data[ca].second;
3.185 + if (items[ka] < items[kb]) {
3.186 + items[ka] += items[kb];
3.187 + items[kb] = ka;
3.188 + } else {
3.189 + items[kb] += items[ka];
3.190 + items[ka] = kb;
3.191 }
3.192 return true;
3.193 }
3.194
3.195 - /**
3.196 - * \brief Returns the size of the component of element \e a.
3.197 - *
3.198 - * Returns the size of the component of element \e a.
3.199 - */
3.200 -
3.201 - int size(T a)
3.202 - {
3.203 - int ca = find(a);
3.204 - return data[ca].second;
3.205 + /// \brief Returns the size of the component of element \e a.
3.206 + ///
3.207 + /// Returns the size of the component of element \e a.
3.208 + int size(const Item& a) {
3.209 + int k = repIndex(index[a]);
3.210 + return - items[k];
3.211 }
3.212
3.213 };
3.214
3.215
3.216 + /// \brief A \e Union-Find data structure implementation which
3.217 + /// is able to enumerate the components.
3.218 + ///
3.219 + /// The class implements a \e Union-Find data structure
3.220 + /// which is able to enumerate the components and the items in
3.221 + /// a component. If you don't need this feature then perhaps it's
3.222 + /// better to use the \ref UnionFind class which is more efficient.
3.223 + ///
3.224 + /// The union operation uses rank heuristic, while
3.225 + /// the find operation uses path compression.
3.226 + ///
3.227 + /// \pre You need to add all the elements by the \ref insert()
3.228 + /// method.
3.229 + ///
3.230 + template <typename _Item, typename _ItemIntMap>
3.231 + class UnionFindEnum {
3.232 + public:
3.233 +
3.234 + typedef _Item Item;
3.235 + typedef _ItemIntMap ItemIntMap;
3.236 +
3.237 + private:
3.238 +
3.239 + // If the parent stores negative value for an item then that item
3.240 + // is root item and it has -items[it].parent component size. Else
3.241 + // the items[it].parent contains the index of the parent.
3.242 + //
3.243 + // The \c nextItem and \c prevItem provides the double-linked
3.244 + // cyclic list of one component's items. The \c prevClass and
3.245 + // \c nextClass gives the double linked list of the representant
3.246 + // items.
3.247 + struct ItemT {
3.248 + int parent;
3.249 + Item item;
3.250
3.251 + int nextItem, prevItem;
3.252 + int nextClass, prevClass;
3.253 + };
3.254
3.255 - /*******************************************************/
3.256 + std::vector<ItemT> items;
3.257 + ItemIntMap& index;
3.258
3.259 + int firstClass;
3.260
3.261 -#ifdef DEVELOPMENT_DOCS
3.262
3.263 - /**
3.264 - * \brief The auxiliary class for the \ref UnionFindEnum class.
3.265 - *
3.266 - * In the \ref UnionFindEnum class all components are represented as
3.267 - * a std::list.
3.268 - * Items of these lists are UnionFindEnumItem structures.
3.269 - *
3.270 - * The class has four fields:
3.271 - * - T me - the actual element
3.272 - * - IIter parent - the parent of the element in the union-find structure
3.273 - * - int size - the size of the component of the element.
3.274 - * Only valid if the element
3.275 - * is the leader of the component.
3.276 - * - CIter my_class - pointer into the list of components
3.277 - * pointing to the component of the element.
3.278 - * Only valid if the element is the leader of the component.
3.279 - */
3.280 -
3.281 -#endif
3.282 -
3.283 - template <typename T>
3.284 - struct UnionFindEnumItem {
3.285 -
3.286 - typedef std::list<UnionFindEnumItem> ItemList;
3.287 - typedef std::list<ItemList> ClassList;
3.288 - typedef typename ItemList::iterator IIter;
3.289 - typedef typename ClassList::iterator CIter;
3.290 -
3.291 - T me;
3.292 - IIter parent;
3.293 - int size;
3.294 - CIter my_class;
3.295 -
3.296 - UnionFindEnumItem() {}
3.297 - UnionFindEnumItem(const T &_me, CIter _my_class):
3.298 - me(_me), size(1), my_class(_my_class) {}
3.299 - };
3.300 -
3.301 -
3.302 - /**
3.303 - * \brief A \e Union-Find data structure implementation which
3.304 - * is able to enumerate the components.
3.305 - *
3.306 - * The class implements a \e Union-Find data structure
3.307 - * which is able to enumerate the components and the items in
3.308 - * a component. If you don't need this feature then perhaps it's
3.309 - * better to use the \ref UnionFind class which is more efficient.
3.310 - *
3.311 - * The union operation uses rank heuristic, while
3.312 - * the find operation uses path compression.
3.313 - *
3.314 - * \pre You
3.315 - * need to add all the elements by the \ref insert() method.
3.316 - */
3.317 -
3.318 -
3.319 - template <typename T, template <typename Item> class Map>
3.320 - class UnionFindEnum {
3.321 -
3.322 - typedef std::list<UnionFindEnumItem<T> > ItemList;
3.323 - typedef std::list<ItemList> ClassList;
3.324 - typedef typename ItemList::iterator IIter;
3.325 - typedef typename ItemList::const_iterator IcIter;
3.326 - typedef typename ClassList::iterator CIter;
3.327 - typedef typename ClassList::const_iterator CcIter;
3.328 -
3.329 - public:
3.330 - typedef T ElementType;
3.331 - typedef UnionFindEnumItem<T> ItemType;
3.332 - typedef Map< IIter > MapType;
3.333 -
3.334 - private:
3.335 - MapType& m;
3.336 - ClassList classes;
3.337 -
3.338 - IIter _find(IIter a) const {
3.339 - IIter comp = a;
3.340 - IIter next;
3.341 - while( (next = comp->parent) != comp ) {
3.342 - comp = next;
3.343 - }
3.344 -
3.345 - IIter comp1 = a;
3.346 - while( (next = comp1->parent) != comp ) {
3.347 - comp1->parent = comp->parent;
3.348 - comp1 = next;
3.349 - }
3.350 - return comp;
3.351 + bool rep(int idx) const {
3.352 + return items[idx].parent < 0;
3.353 }
3.354
3.355 - const ItemList& classOf(const T &a) const {
3.356 - return *_find(m[a])->my_class;
3.357 + int repIndex(int idx) const {
3.358 + int k = idx;
3.359 + while (!rep(k)) {
3.360 + k = items[k].parent;
3.361 + }
3.362 + while (idx != k) {
3.363 + int next = items[idx].parent;
3.364 + const_cast<int&>(items[idx].parent) = k;
3.365 + idx = next;
3.366 + }
3.367 + return k;
3.368 + }
3.369 +
3.370 + void unlaceClass(int k) {
3.371 + if (items[k].prevClass != -1) {
3.372 + items[items[k].prevClass].nextClass = items[k].nextClass;
3.373 + } else {
3.374 + firstClass = items[k].nextClass;
3.375 + }
3.376 + if (items[k].nextClass != -1) {
3.377 + items[items[k].nextClass].prevClass = items[k].prevClass;
3.378 + }
3.379 + }
3.380 +
3.381 + void spliceItems(int ak, int bk) {
3.382 + items[items[ak].prevItem].nextItem = bk;
3.383 + items[items[bk].prevItem].nextItem = ak;
3.384 + int tmp = items[ak].prevItem;
3.385 + items[ak].prevItem = items[bk].prevItem;
3.386 + items[bk].prevItem = tmp;
3.387 +
3.388 }
3.389
3.390 public:
3.391 - UnionFindEnum(MapType& _m) : m(_m) {}
3.392
3.393 + UnionFindEnum(ItemIntMap& _index)
3.394 + : items(), index(_index), firstClass(-1) {}
3.395 +
3.396 + /// \brief Inserts the given element into a new component.
3.397 + ///
3.398 + /// This method creates a new component consisting only of the
3.399 + /// given element.
3.400 + ///
3.401 + void insert(const Item& item) {
3.402 + ItemT t;
3.403
3.404 - /**
3.405 - * \brief Inserts the given element into a new component.
3.406 - *
3.407 - * This method creates a new component consisting only of the
3.408 - * given element.
3.409 - */
3.410 + int idx = items.size();
3.411 + index.set(item, idx);
3.412
3.413 - void insert(const T &a)
3.414 - {
3.415 + t.nextItem = idx;
3.416 + t.prevItem = idx;
3.417 + t.item = item;
3.418 + t.parent = -1;
3.419 +
3.420 + t.nextClass = firstClass;
3.421 + if (firstClass != -1) {
3.422 + items[firstClass].prevClass = idx;
3.423 + }
3.424 + t.prevClass = -1;
3.425 + firstClass = idx;
3.426
3.427 -
3.428 - classes.push_back(ItemList());
3.429 - CIter aclass = classes.end();
3.430 - --aclass;
3.431 -
3.432 - ItemList &alist = *aclass;
3.433 - alist.push_back(ItemType(a, aclass));
3.434 - IIter ai = alist.begin();
3.435 -
3.436 - ai->parent = ai;
3.437 - m.set(a, ai);
3.438 -
3.439 + items.push_back(t);
3.440 }
3.441
3.442 - /**
3.443 - * \brief Inserts the given element into the component of the others.
3.444 - *
3.445 - * This methods inserts the element \e a into the component of the
3.446 - * element \e comp.
3.447 - */
3.448 + /// \brief Inserts the given element into the component of the others.
3.449 + ///
3.450 + /// This methods inserts the element \e a into the component of the
3.451 + /// element \e comp.
3.452 + void insert(const Item& item, const Item& comp) {
3.453 + int k = repIndex(index[comp]);
3.454 + ItemT t;
3.455
3.456 - void insert(const T &a, const T &comp) {
3.457 -
3.458 - IIter clit = _find(m[comp]);
3.459 - ItemList &c = *clit->my_class;
3.460 - c.push_back(ItemType(a,CIter()));
3.461 - IIter ai = c.end();
3.462 - --ai;
3.463 - ai->parent = clit;
3.464 - m.set(a, ai);
3.465 - ++clit->size;
3.466 + int idx = items.size();
3.467 + index.set(item, idx);
3.468 +
3.469 + t.prevItem = k;
3.470 + t.nextItem = items[k].nextItem;
3.471 + items[items[k].nextItem].prevItem = idx;
3.472 + items[k].nextItem = idx;
3.473 +
3.474 + t.item = item;
3.475 + t.parent = k;
3.476 +
3.477 + --items[k].parent;
3.478 +
3.479 + items.push_back(t);
3.480 }
3.481
3.482 -
3.483 - /**
3.484 - * \brief Finds the leader of the component of the given element.
3.485 - *
3.486 - * The method returns the leader of the component of the given element.
3.487 - */
3.488 -
3.489 - T find(const T &a) const {
3.490 - return _find(m[a])->me;
3.491 + /// \brief Finds the leader of the component of the given element.
3.492 + ///
3.493 + /// The method returns the leader of the component of the given element.
3.494 + const Item& find(const Item &item) const {
3.495 + return items[repIndex(index[item])].item;
3.496 }
3.497
3.498 + /// \brief Joining the component of element \e a and element \e b.
3.499 + ///
3.500 + /// This is the \e union operation of the Union-Find structure.
3.501 + /// Joins the component of element \e a and component of
3.502 + /// element \e b. If \e a and \e b are in the same component then
3.503 + /// returns false else returns true.
3.504 + bool join(const Item& a, const Item& b) {
3.505
3.506 - /**
3.507 - * \brief Joining the component of element \e a and element \e b.
3.508 - *
3.509 - * This is the \e union operation of the Union-Find structure.
3.510 - * Joins the component of element \e a and component of
3.511 - * element \e b. If \e a and \e b are in the same component then
3.512 - * returns false else returns true.
3.513 - */
3.514 + int ak = repIndex(index[a]);
3.515 + int bk = repIndex(index[b]);
3.516
3.517 - bool join(T a, T b) {
3.518 -
3.519 - IIter ca = _find(m[a]);
3.520 - IIter cb = _find(m[b]);
3.521 -
3.522 - if ( ca == cb ) {
3.523 + if (ak == bk) {
3.524 return false;
3.525 }
3.526
3.527 - if ( ca->size > cb->size ) {
3.528 -
3.529 - cb->parent = ca->parent;
3.530 - ca->size += cb->size;
3.531 -
3.532 - ItemList &alist = *ca->my_class;
3.533 - alist.splice(alist.end(),*cb->my_class);
3.534 -
3.535 - classes.erase(cb->my_class);
3.536 + if ( items[ak].parent < items[bk].parent ) {
3.537 + unlaceClass(bk);
3.538 + items[ak].parent += items[bk].parent;
3.539 + items[bk].parent = ak;
3.540 + } else {
3.541 + unlaceClass(bk);
3.542 + items[bk].parent += items[ak].parent;
3.543 + items[ak].parent = bk;
3.544 }
3.545 - else {
3.546 -
3.547 - ca->parent = cb->parent;
3.548 - cb->size += ca->size;
3.549 -
3.550 - ItemList &blist = *cb->my_class;
3.551 - blist.splice(blist.end(),*ca->my_class);
3.552 -
3.553 - classes.erase(ca->my_class);
3.554 - }
3.555 + spliceItems(ak, bk);
3.556
3.557 return true;
3.558 }
3.559
3.560 -
3.561 - /**
3.562 - * \brief Returns the size of the component of element \e a.
3.563 - *
3.564 - * Returns the size of the component of element \e a.
3.565 - */
3.566 -
3.567 - int size(const T &a) const {
3.568 - return _find(m[a])->size;
3.569 + /// \brief Returns the size of the component of element \e a.
3.570 + ///
3.571 + /// Returns the size of the component of element \e a.
3.572 + int size(const Item &item) const {
3.573 + return - items[repIndex(index[item])].parent;
3.574 }
3.575
3.576 + /// \brief Splits up the component of the element.
3.577 + ///
3.578 + /// Splitting the component of the element into sigleton
3.579 + /// components (component of size one).
3.580 + void split(const Item &item) {
3.581 + int k = repIndex(index[item]);
3.582 + int idx = items[k].nextItem;
3.583 + while (idx != k) {
3.584 + int next = items[idx].nextItem;
3.585 +
3.586 + items[idx].parent = -1;
3.587 + items[idx].prevItem = idx;
3.588 + items[idx].nextItem = idx;
3.589 +
3.590 + items[idx].nextClass = firstClass;
3.591 + items[firstClass].prevClass = idx;
3.592 + firstClass = idx;
3.593
3.594 - /**
3.595 - * \brief Splits up the component of the element.
3.596 - *
3.597 - * Splitting the component of the element into sigleton
3.598 - * components (component of size one).
3.599 - */
3.600 -
3.601 - void split(const T &a) {
3.602 -
3.603 - IIter ca = _find(m[a]);
3.604 -
3.605 - if ( ca->size == 1 )
3.606 - return;
3.607 -
3.608 - CIter aclass = ca->my_class;
3.609 -
3.610 - for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
3.611 - classes.push_back(ItemList());
3.612 - CIter nl = --classes.end();
3.613 - nl->splice(nl->end(), *aclass, curr);
3.614 -
3.615 - curr->size=1;
3.616 - curr->parent=curr;
3.617 - curr->my_class = nl;
3.618 + idx = next;
3.619 }
3.620
3.621 - ca->size=1;
3.622 - return;
3.623 + items[idx].parent = -1;
3.624 + items[idx].prevItem = idx;
3.625 + items[idx].nextItem = idx;
3.626 +
3.627 + items[firstClass].prevClass = -1;
3.628 }
3.629
3.630 -
3.631 - /**
3.632 - * \brief Sets the given element to the leader element of its component.
3.633 - *
3.634 - * Sets the given element to the leader element of its component.
3.635 - */
3.636 -
3.637 - void makeRep(const T &a) {
3.638 -
3.639 - IIter ia = m[a];
3.640 - IIter la = _find(ia);
3.641 - if (la == ia) return;
3.642 -
3.643 - ia->my_class = la->my_class;
3.644 -
3.645 - ia->size = la->size;
3.646 -
3.647 - CIter l = ia->my_class;
3.648 - l->splice(l->begin(),*l,ia);
3.649 -
3.650 - ia->parent = ia;
3.651 - la->parent = ia;
3.652 + /// \brief Sets the given element to the leader element of its component.
3.653 + ///
3.654 + /// Sets the given element to the leader element of its component.
3.655 + void makeRep(const Item &item) {
3.656 + int nk = index[item];
3.657 + int k = repIndex(nk);
3.658 + if (nk == k) return;
3.659 +
3.660 + if (items[k].prevClass != -1) {
3.661 + items[items[k].prevClass].nextClass = nk;
3.662 + } else {
3.663 + firstClass = nk;
3.664 + }
3.665 + if (items[k].nextClass != -1) {
3.666 + items[items[k].nextClass].prevClass = nk;
3.667 + }
3.668 +
3.669 + int idx = items[k].nextItem;
3.670 + while (idx != k) {
3.671 + items[idx].parent = nk;
3.672 + idx = items[idx].nextItem;
3.673 + }
3.674 +
3.675 + items[nk].parent = items[k].parent;
3.676 + items[k].parent = nk;
3.677 }
3.678
3.679 - /**
3.680 - * \brief Moves the given element to another component.
3.681 - *
3.682 - * This method moves the element \e a from its component
3.683 - * to the component of \e comp.
3.684 - * If \e a and \e comp are in the same component then
3.685 - * it returns false otherwise it returns true.
3.686 - */
3.687 + /// \brief Removes the given element from the structure.
3.688 + ///
3.689 + /// Removes the element from its component and if the component becomes
3.690 + /// empty then removes that component from the component list.
3.691 + ///
3.692 + /// \warning It is an error to remove an element which is not in
3.693 + /// the structure.
3.694 + void erase(const Item &item) {
3.695 + int idx = index[item];
3.696 + if (rep(idx)) {
3.697 + int k = idx;
3.698 + if (items[k].parent == -1) {
3.699 + unlaceClass(idx);
3.700 + return;
3.701 + } else {
3.702 + int nk = items[k].nextItem;
3.703 + if (items[k].prevClass != -1) {
3.704 + items[items[k].prevClass].nextClass = nk;
3.705 + } else {
3.706 + firstClass = nk;
3.707 + }
3.708 + if (items[k].nextClass != -1) {
3.709 + items[items[k].nextClass].prevClass = nk;
3.710 + }
3.711 +
3.712 + int idx = items[k].nextItem;
3.713 + while (idx != k) {
3.714 + items[idx].parent = nk;
3.715 + idx = items[idx].nextItem;
3.716 + }
3.717 +
3.718 + items[nk].parent = items[k].parent + 1;
3.719 + }
3.720 + } else {
3.721 +
3.722 + int k = repIndex(idx);
3.723 + idx = items[k].nextItem;
3.724 + while (idx != k) {
3.725 + items[idx].parent = k;
3.726 + idx = items[idx].nextItem;
3.727 + }
3.728
3.729 - bool move(const T &a, const T &comp) {
3.730 -
3.731 - IIter ai = m[a];
3.732 - IIter lai = _find(ai);
3.733 - IIter clit = _find(m[comp]);
3.734 -
3.735 - if (lai == clit)
3.736 - return false;
3.737 -
3.738 - ItemList &cl = *clit->my_class,
3.739 - &al = *lai->my_class;
3.740 -
3.741 - bool is_leader = (lai == ai);
3.742 - bool singleton = false;
3.743 -
3.744 - if (is_leader) {
3.745 - ++lai;
3.746 + ++items[k].parent;
3.747 }
3.748
3.749 - cl.splice(cl.end(), al, ai);
3.750 + idx = index[item];
3.751 + items[items[idx].prevItem].nextItem = items[idx].nextItem;
3.752 + items[items[idx].nextItem].prevItem = items[idx].prevItem;
3.753
3.754 - if (is_leader) {
3.755 - if (ai->size == 1) {
3.756 - classes.erase(ai->my_class);
3.757 - singleton = true;
3.758 - }
3.759 - else {
3.760 - lai->size = ai->size;
3.761 - lai->my_class = ai->my_class;
3.762 - }
3.763 - }
3.764 - if (!singleton) {
3.765 - for (IIter i = lai; i != al.end(); ++i)
3.766 - i->parent = lai;
3.767 - --lai->size;
3.768 - }
3.769 + }
3.770
3.771 - ai->parent = clit;
3.772 - ++clit->size;
3.773 -
3.774 + /// \brief Moves the given element to another component.
3.775 + ///
3.776 + /// This method moves the element \e a from its component
3.777 + /// to the component of \e comp.
3.778 + /// If \e a and \e comp are in the same component then
3.779 + /// it returns false otherwise it returns true.
3.780 + bool move(const Item &item, const Item &comp) {
3.781 + if (repIndex(index[item]) == repIndex(index[comp])) return false;
3.782 + erase(item);
3.783 + insert(item, comp);
3.784 return true;
3.785 }
3.786
3.787
3.788 - /**
3.789 - * \brief Removes the given element from the structure.
3.790 - *
3.791 - * Removes the element from its component and if the component becomes
3.792 - * empty then removes that component from the component list.
3.793 - *
3.794 - * It is an error to remove an element which is not in the structure.
3.795 - */
3.796 - void erase(const T &a) {
3.797 + /// \brief Removes the component of the given element from the structure.
3.798 + ///
3.799 + /// Removes the component of the given element from the structure.
3.800 + ///
3.801 + /// \warning It is an error to give an element which is not in the
3.802 + /// structure.
3.803 + void eraseClass(const Item &item) {
3.804 + unlaceClass(repIndex(index[item]));
3.805 + }
3.806
3.807 - IIter ma = m[a];
3.808 -
3.809 - IIter la = _find(ma);
3.810 - if (la == ma) {
3.811 - if (ma -> size == 1){
3.812 - classes.erase(ma->my_class);
3.813 - return;
3.814 - }
3.815 - ++la;
3.816 - la->size = ma->size;
3.817 - la->my_class = ma->my_class;
3.818 + /// \brief Lemon style iterator for the representant items.
3.819 + ///
3.820 + /// ClassIt is a lemon style iterator for the components. It iterates
3.821 + /// on the representant items of the classes.
3.822 + class ClassIt {
3.823 + public:
3.824 + /// \brief Constructor of the iterator
3.825 + ///
3.826 + /// Constructor of the iterator
3.827 + ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
3.828 + idx = unionFind->firstClass;
3.829 }
3.830
3.831 - for (IIter i = la; i != la->my_class->end(); ++i) {
3.832 - i->parent = la;
3.833 + /// \brief Constructor to get invalid iterator
3.834 + ///
3.835 + /// Constructor to get invalid iterator
3.836 + ClassIt(Invalid) : unionFind(0), idx(-1) {}
3.837 +
3.838 + /// \brief Increment operator
3.839 + ///
3.840 + /// It steps to the next representant item.
3.841 + ClassIt& operator++() {
3.842 + idx = unionFind->items[idx].nextClass;
3.843 + return *this;
3.844 + }
3.845 +
3.846 + /// \brief Conversion operator
3.847 + ///
3.848 + /// It converts the iterator to the current representant item.
3.849 + operator const Item&() const {
3.850 + return unionFind->items[idx].item;
3.851 }
3.852
3.853 - la->size--;
3.854 - la->my_class->erase(ma);
3.855 - }
3.856 + /// \brief Equality operator
3.857 + ///
3.858 + /// Equality operator
3.859 + bool operator==(const ClassIt& i) {
3.860 + return i.idx == idx;
3.861 + }
3.862
3.863 - /**
3.864 - * \brief Removes the component of the given element from the structure.
3.865 - *
3.866 - * Removes the component of the given element from the structure.
3.867 - *
3.868 - * It is an error to give an element which is not in the structure.
3.869 - */
3.870 -
3.871 - void eraseClass(const T &a) {
3.872 - IIter ma = m[a];
3.873 - classes.erase(_find(ma)->my_class);
3.874 - }
3.875 -
3.876 -
3.877 - class ClassIt {
3.878 - friend class UnionFindEnum;
3.879 -
3.880 - CcIter i;
3.881 - const ClassList *l;
3.882 -
3.883 - public:
3.884 - ClassIt(Invalid): l(0) {}
3.885 - ClassIt() {}
3.886 - ClassIt(UnionFindEnum const &ufe) {
3.887 - l = &ufe.classes;
3.888 - i = l->begin();
3.889 + /// \brief Inequality operator
3.890 + ///
3.891 + /// Inequality operator
3.892 + bool operator!=(const ClassIt& i) {
3.893 + return i.idx != idx;
3.894 }
3.895
3.896 - operator const T& () const {
3.897 - ItemList const &ll = *i;
3.898 - return (ll.begin())->me;
3.899 - }
3.900 - bool operator == (ClassIt const &it) const {
3.901 - return (l==it.l && i==it.i) || (!valid() && !it.valid());
3.902 - }
3.903 - bool operator != (ClassIt const &it) const {
3.904 - return !(*this == it);
3.905 - }
3.906 - bool operator < (ClassIt const &it) const {
3.907 - return (i < it.i);
3.908 + private:
3.909 + const UnionFindEnum* unionFind;
3.910 + int idx;
3.911 + };
3.912 +
3.913 + /// \brief Lemon style iterator for the items of a component.
3.914 + ///
3.915 + /// ClassIt is a lemon style iterator for the components. It iterates
3.916 + /// on the items of a class. By example if you want to iterate on
3.917 + /// each items of each classes then you may write the next code.
3.918 + ///\code
3.919 + /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
3.920 + /// std::cout << "Class: ";
3.921 + /// for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
3.922 + /// std::cout << toString(iit) << ' ' << std::endl;
3.923 + /// }
3.924 + /// std::cout << std::endl;
3.925 + /// }
3.926 + ///\endcode
3.927 + class ItemIt {
3.928 + public:
3.929 + /// \brief Constructor of the iterator
3.930 + ///
3.931 + /// Constructor of the iterator. The iterator iterates
3.932 + /// on the class of the \c item.
3.933 + ItemIt(const UnionFindEnum& ufe, const Item& item) : unionFind(&ufe) {
3.934 + idx = unionFind->repIndex(unionFind->index[item]);
3.935 }
3.936
3.937 - bool operator==(Invalid) const {
3.938 - return !valid();
3.939 + /// \brief Constructor to get invalid iterator
3.940 + ///
3.941 + /// Constructor to get invalid iterator
3.942 + ItemIt(Invalid) : unionFind(0), idx(-1) {}
3.943 +
3.944 + /// \brief Increment operator
3.945 + ///
3.946 + /// It steps to the next item in the class.
3.947 + ItemIt& operator++() {
3.948 + idx = unionFind->items[idx].nextItem;
3.949 + if (unionFind->rep(idx)) idx = -1;
3.950 + return *this;
3.951 }
3.952 - bool operator!=(Invalid) const {
3.953 - return valid();
3.954 +
3.955 + /// \brief Conversion operator
3.956 + ///
3.957 + /// It converts the iterator to the current item.
3.958 + operator const Item&() const {
3.959 + return unionFind->items[idx].item;
3.960 }
3.961
3.962 - ClassIt& operator++() {
3.963 - ++i;
3.964 - return *this;
3.965 + /// \brief Equality operator
3.966 + ///
3.967 + /// Equality operator
3.968 + bool operator==(const ItemIt& i) {
3.969 + return i.idx == idx;
3.970 }
3.971
3.972 - // obsoleted:
3.973 - bool valid() const { return l!=0 && i!=l->end(); }
3.974 + /// \brief Inequality operator
3.975 + ///
3.976 + /// Inequality operator
3.977 + bool operator!=(const ItemIt& i) {
3.978 + return i.idx != idx;
3.979 + }
3.980 +
3.981 + private:
3.982 + const UnionFindEnum* unionFind;
3.983 + int idx;
3.984 };
3.985
3.986 - /**
3.987 - * \brief Sets the iterator to point to the first component.
3.988 - *
3.989 - * Sets the iterator to point to the first component.
3.990 - *
3.991 - * With the \ref first, \ref valid and \ref next methods you can
3.992 - * iterate through the components. For example:
3.993 - * \code
3.994 - * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
3.995 - * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
3.996 - * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
3.997 - * for (U.first(iter); U.valid(iter); U.next(iter)) {
3.998 - * // iter is convertible to Graph::Node
3.999 - * cout << iter << endl;
3.1000 - * }
3.1001 - * \endcode
3.1002 - *
3.1003 - * \bug obsoleted, use the new LEMON iterator interface instead
3.1004 - */
3.1005 -
3.1006 - ClassIt& first(ClassIt& it) const {
3.1007 - it = ClassIt(*this);
3.1008 - return it;
3.1009 - }
3.1010 -
3.1011 - /**
3.1012 - * \brief Returns whether the iterator is valid.
3.1013 - *
3.1014 - * Returns whether the iterator is valid.
3.1015 - *
3.1016 - * With the \ref first, \ref valid and \ref next methods you can
3.1017 - * iterate through the components. See the example here: \ref first.
3.1018 - *
3.1019 - * \bug obsoleted, use the new LEMON iterator interface instead
3.1020 - */
3.1021 -
3.1022 - bool valid(ClassIt const &it) const {
3.1023 - return it.valid();
3.1024 - }
3.1025 -
3.1026 - /**
3.1027 - * \brief Steps the iterator to the next component.
3.1028 - *
3.1029 - * Steps the iterator to the next component.
3.1030 - *
3.1031 - * With the \ref first, \ref valid and \ref next methods you can
3.1032 - * iterate through the components. See the example here: \ref first.
3.1033 - */
3.1034 -
3.1035 - ClassIt& next(ClassIt& it) const {
3.1036 - return ++it;
3.1037 - }
3.1038 -
3.1039 -
3.1040 - class ItemIt {
3.1041 - friend class UnionFindEnum;
3.1042 -
3.1043 - IcIter i;
3.1044 - const ItemList *l;
3.1045 - public:
3.1046 - ItemIt(Invalid): l(0) {}
3.1047 - ItemIt() {}
3.1048 - ItemIt(UnionFindEnum const &ufe, const T& a) {
3.1049 - l = &ufe.classOf(a);
3.1050 - i = l->begin();
3.1051 - }
3.1052 -
3.1053 - operator const T& () const { return i->me; }
3.1054 - bool operator == (ItemIt const &it) const {
3.1055 - return (l==it.l && i==it.i) || (!valid() && !it.valid());
3.1056 - }
3.1057 - bool operator != (ItemIt const &it) const {
3.1058 - return !(*this == it);
3.1059 - }
3.1060 - bool operator < (ItemIt const &it) const {
3.1061 - return (i < it.i);
3.1062 - }
3.1063 -
3.1064 - bool operator==(Invalid) const {
3.1065 - return !valid();
3.1066 - }
3.1067 - bool operator!=(Invalid) const {
3.1068 - return valid();
3.1069 - }
3.1070 -
3.1071 - ItemIt& operator++() {
3.1072 - ++i;
3.1073 - return *this;
3.1074 - }
3.1075 -
3.1076 - // obsoleted:
3.1077 - bool valid() const { return l!=0 && i!=l->end(); }
3.1078 - };
3.1079 -
3.1080 -
3.1081 -
3.1082 - /**
3.1083 - * \brief Sets the iterator to point to the first element of the component.
3.1084 - *
3.1085 - * \anchor first2
3.1086 - * Sets the iterator to point to the first element of the component.
3.1087 - *
3.1088 - * With the \ref first2 "first", \ref valid2 "valid"
3.1089 - * and \ref next2 "next" methods you can
3.1090 - * iterate through the elements of a component. For example
3.1091 - * (iterating through the component of the node \e node):
3.1092 - * \code
3.1093 - * Graph::Node node = ...;
3.1094 - * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
3.1095 - * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
3.1096 - * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
3.1097 - * for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
3.1098 - * // iiter is convertible to Graph::Node
3.1099 - * cout << iiter << endl;
3.1100 - * }
3.1101 - * \endcode
3.1102 - *
3.1103 - * \bug obsoleted, use the new LEMON iterator interface instead
3.1104 - */
3.1105 -
3.1106 - ItemIt& first(ItemIt& it, const T& a) const {
3.1107 - it = ItemIt(*this, a);
3.1108 - return it;
3.1109 - }
3.1110 -
3.1111 - /**
3.1112 - * \brief Returns whether the iterator is valid.
3.1113 - *
3.1114 - * \anchor valid2
3.1115 - * Returns whether the iterator is valid.
3.1116 - *
3.1117 - * With the \ref first2 "first", \ref valid2 "valid"
3.1118 - * and \ref next2 "next" methods you can
3.1119 - * iterate through the elements of a component.
3.1120 - * See the example here: \ref first2 "first".
3.1121 - *
3.1122 - * \bug obsoleted, use the new LEMON iterator interface instead
3.1123 - */
3.1124 -
3.1125 - bool valid(ItemIt const &it) const {
3.1126 - return it.valid();
3.1127 - }
3.1128 -
3.1129 - /**
3.1130 - * \brief Steps the iterator to the next component.
3.1131 - *
3.1132 - * \anchor next2
3.1133 - * Steps the iterator to the next component.
3.1134 - *
3.1135 - * With the \ref first2 "first", \ref valid2 "valid"
3.1136 - * and \ref next2 "next" methods you can
3.1137 - * iterate through the elements of a component.
3.1138 - * See the example here: \ref first2 "first".
3.1139 - *
3.1140 - * \bug obsoleted, use the new LEMON iterator interface instead
3.1141 - */
3.1142 -
3.1143 - ItemIt& next(ItemIt& it) const {
3.1144 - return ++it;
3.1145 - }
3.1146 -
3.1147 };
3.1148
3.1149
4.1 --- a/test/unionfind_test.cc Wed Sep 06 10:28:13 2006 +0000
4.2 +++ b/test/unionfind_test.cc Wed Sep 06 11:17:12 2006 +0000
4.3 @@ -25,19 +25,14 @@
4.4 using namespace lemon;
4.5 using namespace std;
4.6
4.7 -template <typename T>
4.8 -class BaseMap : public StdMap<int,T> {};
4.9 -
4.10 -typedef UnionFindEnum<int, BaseMap> UFE;
4.11 +typedef UnionFindEnum<int, StdMap<int, int> > UFE;
4.12
4.13 void print(UFE const &ufe) {
4.14 - UFE::ClassIt cit;
4.15 cout << "Print the classes of the structure:" << endl;
4.16 int i = 1;
4.17 - for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {
4.18 + for (UFE::ClassIt cit(ufe); cit != INVALID; ++cit) {
4.19 cout << " " << i << " (" << cit << "):" << flush;
4.20 - UFE::ItemIt iit;
4.21 - for (ufe.first(iit, cit); ufe.valid(iit); ufe.next(iit)) {
4.22 + for (UFE::ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
4.23 cout << " " << iit << flush;
4.24 }
4.25 cout << endl;
4.26 @@ -48,7 +43,7 @@
4.27
4.28
4.29 int main() {
4.30 - UFE::MapType base;
4.31 + StdMap<int, int> base;
4.32 UFE U(base);
4.33
4.34 U.insert(1);
4.35 @@ -75,6 +70,7 @@
4.36
4.37 U.insert(9);
4.38 U.insert(10,9);
4.39 +
4.40 check(U.join(8,10),"Test failed.");
4.41
4.42 check(U.move(9,4),"Test failed.");