home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / basic / _partiti.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  1.5 KB  |  73 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _partition.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. //------------------------------------------------------------------------------
  18. // partition.c
  19. // implementation of data type partition
  20. // (union find with weighted union rule and path compression)
  21. //
  22. // S. Naeher     1989
  23. //------------------------------------------------------------------------------
  24.  
  25. #include <LEDA/partition.h>
  26.  
  27.  
  28. void partition::clear()
  29. { // delete all used items
  30.  
  31.   partition_item p = used_items; 
  32.   while (used_items)
  33.   { p = used_items;
  34.     used_items = used_items->next;
  35.     clear_inf(p->info);
  36.     delete p;
  37.    }
  38.  }
  39.   
  40.  
  41.  
  42. partition_item partition::find(partition_item it) 
  43. { // find with path compression
  44.  
  45.   partition_item x,root = it;
  46.  
  47.   while (root->father) root = root->father;
  48.  
  49.   while (it!=root)
  50.   { x = it->father;
  51.     it->father = root;
  52.     it = x;
  53.    }
  54.   return root;
  55.  }
  56.  
  57. void partition::union_blocks(partition_item a, partition_item b)
  58. { // weighted union
  59.  
  60.   a = find(a);
  61.   b = find(b);
  62.  
  63.   if (a==b) return;
  64.  
  65.   if (a->size > b->size)
  66.        { b->father = a;
  67.          a->size += b->size; }
  68.   else { a->father = b;
  69.          b->size += a->size; }
  70.  
  71.  }
  72.  
  73.