\manpage {partition} {} {Partitions} 
 
\definition
An instance  $P$ of the data type $partition$ consists of a finite set of
items ($partition\_item$) and a partition of this set
into blocks.
 
\creation P 
 
\create { }
   { creates an instance $P$ of type $partition$ and initializes it to
            the empty partition. }
 
 
\operations 3 4
 
\opl partition\_item make\_block {()}
           {  returns a new $partition\_item$ $it$ and adds
	     the block $\{it\}$ to partition $P$. }
 
 
\opl partition\_item find {(partition\_item\ p)}
           {  returns a canonical item of the block that
	     contains item $p$, i.e., if $P$.same\_block($p,q$)
	     then $P$.find($p$) = $P$.find($q$).\\
	     \precond $p$ is an item in $P$.  }
 
 
\opl int same\_block {(partition\_item\ p, \ partition\_item\ q)}
           {  returns true if $p$ and $q$ belong to the same
	      block of partition $P$.\\
	      \precond $p$ and $q$ are items in $P$. }
 
 
\opl void union\_blocks {(partition\_item\ p, \ partition\_item\ q)}
           {  unites the blocks of partition $P$ containing
	     items $p$ and $q$.\\
	     \precond $p$ and $q$ are items in $P$. }
 
 
\implementation
Partitions are implemented by the union find algorithm with weighted union
and path compression (cf.~\cite{T83}).  Any sequence of $n$ make\_block and 
$m \ge n$ other operations takes time $O(m\alpha(m,n))$.
 
\example
    Spanning Tree Algorithms (cf. section \ref{Graph Algorithms}).
 
