Changeset - r460:81d40f1c850c
« 457:561be4
497:8b5660 »
462:1cc281 »
461:1229dc »
gravatar
deba@inf.elte.hu
deba@inf.elte.hu
Bug fix in heap unionfind (ticket #197) The previous bugfix set the minimum value in internal nodes wrongly. It corrects the problem.
0 1 0
default
1 file changed with 4 insertions and 7 deletions:
lemon/unionfind.h
4
7
↑ Collapse diff ↑
lemon/unionfind.h
Show white space 16 line context
... ... 
@@ -1172,17 +1172,18 @@
1172 1172 
            classes[id].depth -= 1;
1173 1173 
            nodes[kd].parent = ~id;
1174 1174 
            deleteNode(jd);
1175 1175 
            jd = kd;
1176 1176 
          } else {
1177 1177 
            int pd = nodes[jd].parent;
1178 1178 
            if (nodes[nodes[jd].next].size < cmax) {
1179 1179 
              pushLeft(nodes[jd].next, nodes[jd].left);
1180 
              if (nodes[jd].item == nodes[pd].item) {
1180 
              if (less(jd, nodes[jd].next) ||
1181 
                  nodes[jd].item == nodes[pd].item) {
1181 1182 
                nodes[nodes[jd].next].prio = nodes[jd].prio;
1182 1183 
                nodes[nodes[jd].next].item = nodes[jd].item;
1183 1184 
              }
1184 1185 
              popLeft(pd);
1185 1186 
              deleteNode(jd);
1186 1187 
              jd = pd;
1187 1188 
            } else {
1188 1189 
              int ld = nodes[nodes[jd].next].left;
... ... 
@@ -1215,17 +1216,18 @@
1215 1216 
            classes[id].depth -= 1;
1216 1217 
            nodes[kd].parent = ~id;
1217 1218 
            deleteNode(jd);
1218 1219 
            jd = kd;
1219 1220 
          } else {
1220 1221 
            int pd = nodes[jd].parent;
1221 1222 
            if (nodes[nodes[jd].prev].size < cmax) {
1222 1223 
              pushRight(nodes[jd].prev, nodes[jd].right);
1223 
              if (nodes[jd].item == nodes[pd].item) {
1224 
              if (less(jd, nodes[jd].prev) ||
1225 
                  nodes[jd].item == nodes[pd].item) {
1224 1226 
                nodes[nodes[jd].prev].prio = nodes[jd].prio;
1225 1227 
                nodes[nodes[jd].prev].item = nodes[jd].item;
1226 1228 
              }
1227 1229 
              popRight(pd);
1228 1230 
              deleteNode(jd);
1229 1231 
              jd = pd;
1230 1232 
            } else {
1231 1233 
              int ld = nodes[nodes[jd].prev].right;
... ... 
@@ -1248,21 +1250,16 @@
1248 1250 
      }
1249 1251 
    }
1250 1252 

			




	1251
	1253
	
		

			




	1252
	1254
	
		
    bool less(int id, int jd) const {


			




	1253
	1255
	
		
      return comp(nodes[id].prio, nodes[jd].prio);


			




	1254
	1256
	
		
    }


			




	1255
	1257
	
		

			




	1256
	
	
		
    bool equal(int id, int jd) const {


			




	1257
	
	
		
      return !less(id, jd) && !less(jd, id);


			




	1258
	
	
		
    }


			




	1259
	
	
		

			




	1260
	
	
		

			




	1261
	1258
	
		
  public:


			




	1262
	1259
	
		

			




	1263
	1260
	
		
    /// \brief Returns true when the given class is alive.


			




	1264
	1261
	
		
    ///


			




	1265
	1262
	
		
    /// Returns true when the given class is alive, ie. the class is


			




	1266
	1263
	
		
    /// not nested into other class.


			




	1267
	1264
	
		
    bool alive(int cls) const {


			




	1268
	1265
	
		
      return classes[cls].parent < 0;


			




        

    






    
    



    


    

     
    
0 comments (0 inline)