Bug fix in heap unionfind (ticket #197)
authorBalazs Dezso <deba@inf.elte.hu>
Sun, 21 Dec 2008 20:45:25 +0100
changeset 46081d40f1c850c
parent 457 561be42c4b99
child 461 1229dc2f1d36
child 462 1cc2818c03c0
child 497 8b56605db6a8
Bug fix in heap unionfind (ticket #197)

The previous bugfix set the minimum value in internal nodes
wrongly. It corrects the problem.
lemon/unionfind.h
     1.1 --- a/lemon/unionfind.h	Sun Dec 21 00:13:02 2008 +0100
     1.2 +++ b/lemon/unionfind.h	Sun Dec 21 20:45:25 2008 +0100
     1.3 @@ -1177,7 +1177,8 @@
     1.4              int pd = nodes[jd].parent;
     1.5              if (nodes[nodes[jd].next].size < cmax) {
     1.6                pushLeft(nodes[jd].next, nodes[jd].left);
     1.7 -              if (nodes[jd].item == nodes[pd].item) {
     1.8 +              if (less(jd, nodes[jd].next) ||
     1.9 +                  nodes[jd].item == nodes[pd].item) {
    1.10                  nodes[nodes[jd].next].prio = nodes[jd].prio;
    1.11                  nodes[nodes[jd].next].item = nodes[jd].item;
    1.12                }
    1.13 @@ -1220,7 +1221,8 @@
    1.14              int pd = nodes[jd].parent;
    1.15              if (nodes[nodes[jd].prev].size < cmax) {
    1.16                pushRight(nodes[jd].prev, nodes[jd].right);
    1.17 -              if (nodes[jd].item == nodes[pd].item) {
    1.18 +              if (less(jd, nodes[jd].prev) ||
    1.19 +                  nodes[jd].item == nodes[pd].item) {
    1.20                  nodes[nodes[jd].prev].prio = nodes[jd].prio;
    1.21                  nodes[nodes[jd].prev].item = nodes[jd].item;
    1.22                }
    1.23 @@ -1253,11 +1255,6 @@
    1.24        return comp(nodes[id].prio, nodes[jd].prio);
    1.25      }
    1.26  
    1.27 -    bool equal(int id, int jd) const {
    1.28 -      return !less(id, jd) && !less(jd, id);
    1.29 -    }
    1.30 -
    1.31 -
    1.32    public:
    1.33  
    1.34      /// \brief Returns true when the given class is alive.