COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/unionfind.h

    r236 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    11781178            if (nodes[nodes[jd].next].size < cmax) {
    11791179              pushLeft(nodes[jd].next, nodes[jd].left);
    1180               if (less(nodes[jd].left, nodes[jd].next)) {
    1181                 nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
    1182                 nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
     1180              if (less(jd, nodes[jd].next) ||
     1181                  nodes[jd].item == nodes[pd].item) {
     1182                nodes[nodes[jd].next].prio = nodes[jd].prio;
     1183                nodes[nodes[jd].next].item = nodes[jd].item;
    11831184              }
    11841185              popLeft(pd);
     
    11891190              popLeft(nodes[jd].next);
    11901191              pushRight(jd, ld);
    1191               if (less(ld, nodes[jd].left)) {
     1192              if (less(ld, nodes[jd].left) ||
     1193                  nodes[ld].item == nodes[pd].item) {
    11921194                nodes[jd].item = nodes[ld].item;
    1193                 nodes[jd].prio = nodes[jd].prio;
     1195                nodes[jd].prio = nodes[ld].prio;
    11941196              }
    11951197              if (nodes[nodes[jd].next].item == nodes[ld].item) {
     
    12201222            if (nodes[nodes[jd].prev].size < cmax) {
    12211223              pushRight(nodes[jd].prev, nodes[jd].right);
    1222               if (less(nodes[jd].right, nodes[jd].prev)) {
    1223                 nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
    1224                 nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
     1224              if (less(jd, nodes[jd].prev) ||
     1225                  nodes[jd].item == nodes[pd].item) {
     1226                nodes[nodes[jd].prev].prio = nodes[jd].prio;
     1227                nodes[nodes[jd].prev].item = nodes[jd].item;
    12251228              }
    12261229              popRight(pd);
     
    12311234              popRight(nodes[jd].prev);
    12321235              pushLeft(jd, ld);
    1233               if (less(ld, nodes[jd].right)) {
     1236              if (less(ld, nodes[jd].right) ||
     1237                  nodes[ld].item == nodes[pd].item) {
    12341238                nodes[jd].item = nodes[ld].item;
    1235                 nodes[jd].prio = nodes[jd].prio;
     1239                nodes[jd].prio = nodes[ld].prio;
    12361240              }
    12371241              if (nodes[nodes[jd].prev].item == nodes[ld].item) {
     
    12511255      return comp(nodes[id].prio, nodes[jd].prio);
    12521256    }
    1253 
    1254     bool equal(int id, int jd) const {
    1255       return !less(id, jd) && !less(jd, id);
    1256     }
    1257 
    12581257
    12591258  public:
     
    14011400              push(new_id, right_id);
    14021401              pushRight(new_id, ~(classes[r].parent));
    1403               setPrio(new_id);
     1402
     1403              if (less(~classes[r].parent, right_id)) {
     1404                nodes[new_id].item = nodes[~classes[r].parent].item;
     1405                nodes[new_id].prio = nodes[~classes[r].parent].prio;
     1406              } else {
     1407                nodes[new_id].item = nodes[right_id].item;
     1408                nodes[new_id].prio = nodes[right_id].prio;
     1409              }
    14041410
    14051411              id = nodes[id].parent;
     
    14411447              push(new_id, left_id);
    14421448              pushLeft(new_id, ~(classes[l].parent));
    1443               setPrio(new_id);
     1449
     1450              if (less(~classes[l].parent, left_id)) {
     1451                nodes[new_id].item = nodes[~classes[l].parent].item;
     1452                nodes[new_id].prio = nodes[~classes[l].parent].prio;
     1453              } else {
     1454                nodes[new_id].item = nodes[left_id].item;
     1455                nodes[new_id].prio = nodes[left_id].prio;
     1456              }
    14441457
    14451458              id = nodes[id].parent;
Note: See TracChangeset for help on using the changeset viewer.