home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / partitio.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  1.9 KB  |  61 lines
  1. {\magonebf 3.10 Partitions (partition)}
  2.  
  3. An instance of the data type $partition$ consists of a finite set of 
  4. items (predefined type $partition\_item$) and a partition of this set 
  5. into blocks.
  6.  
  7.  
  8. \def\name{$partition$}
  9. \def\type{partition}
  10.  
  11. \bigskip
  12. {\bf 1. Creation of a partition}
  13.  
  14.  
  15. \create P {}
  16.  
  17. Creates an instance $P$ of type $partition$ and initializes it to the empty 
  18. partition. 
  19.  
  20.  
  21.  
  22. \bigskip
  23. {\bf 2. \operations}
  24.  
  25. \+\cleartabs & \hskip 3.2truecm & \hskip 4.8truecm &\cr
  26. \+\op partition\_item make\_block {}
  27.                              {returns a new $partition\_item$ $it$ and adds}
  28. \+\nop                       {the block $\{it\}$ to partition $P$.}
  29. \smallskip
  30. \+\op partition\_item find {partition\_item\ p} {}
  31. \+\nop                      {returns a canonical item of the block that}
  32. \+\nop                      {contains item $p$, i.e., if $P$.same\_block($p,q$)}
  33. \+\nop                      {then $P$.find($p$) = $P$.find($q$).}
  34. \+\nop                      {\precond{$p$ is an item in $P$.}}
  35. \smallskip
  36. \+\op bool            same\_block {partition\_item\  p,\ partition\_item\ q} {}
  37. \+\nop                       {returns true if $p$ and $q$ belong to the same}
  38. \+\nop                       {block of partition $P$.}
  39. \+\nop                       {\precond{$p$ and $q$ are items in $P$.}}
  40. \smallskip
  41. \+\op void            union\_blocks {partition\_item\ p,\ partition\_item\ q} {}
  42. \+\nop                       {unites the blocks of partition $P$ containing}
  43. \+\nop                       {items $p$ and $q$.}
  44. \+\nop                       {\precond{$p$ and $q$ are items in $P$.}}
  45.  
  46.  
  47. \bigskip
  48. {\bf 3. Implementation}
  49.  
  50. Partitions are implemented by the union find algorithm with weighted union
  51. and path compression (cf. [T83]).  Any sequence of $n$ make\_block and 
  52. $m \ge n$ other operations takes time $O(m\alpha(m,n))$, where $\alpha$ is 
  53. a functional inverse of Ackerman's function.
  54.  
  55.  
  56.  
  57. \bigskip
  58. {\bf 4. Example }
  59.  
  60. Spanning Tree Algorithms (cf. graph)
  61.