\manpage {node\_partition} {} {Node Partitions}
 
\definition
An instance of the data type $node\_partition$ is a partition of the nodes
of a graph $G$.
 
\creation P 
 
\create {(graph\ G)}
   { creates a \name\ \var\ containing for every node $v$ in $G$ a
            block $\{v\}$. }
 
 
\operations 1.2 4.5
 
\opl int same\_block {(node\ v, \ node\ w)}
           {  returns true if $v$ and $w$ belong to the
              same block of \var. }
 
 
\opl void union\_blocks {(node\ v, \ node\ w)}
           {  unites the blocks of \var\ containing nodes
	      $v$ and $w$. }
 
 
\op  node find {(node\ v)}
           {  returns a canonical representative node of
	      the block that contains node $v$. }
 
 
\implementation
A node partition for a graph $G$ is implemented by a combination of a 
partition $P$ and a node array of $partition\_item$ associating with 
each node in $G$ a partition item in $P$. Initialization takes linear time,
union\_blocks takes time $O(1)$ (worst-case), and same\_block and find take 
time $O(\alpha(n))$ (amortized).  The space requirement is $O(n)$, where $n$ 
is the number of nodes of $G$.
 
