home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / node_par.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  1.4 KB  |  52 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.10 Node partitions (node\_partition)}
  4.  
  5. An instance of the data type $node\_partition$ is a partition of the nodes
  6. of some graph $G$.
  7.  
  8.  
  9. \def\name{$node\_partition$}
  10. \def\type{node\_partition}
  11.  
  12. \bigskip
  13. {\bf 1. Creation of a node partition}
  14.  
  15.  
  16. \create P (G)
  17.  
  18. creates an instance \var\ of type \name\ containing for every node $v$ in 
  19. $G$ a block $\{v\}$. 
  20.  
  21.  
  22.  
  23. \bigskip
  24. {\bf 2. \operations}
  25.  
  26. \+\cleartabs & \hskip 1.5truecm & \hskip 6.5truecm &\cr
  27. \+\op bool  same\_block   {node\ v,\ node\ w}  
  28.                              {returns true if $v$ and $w$ belong to the }
  29. \+\nop                       {same block of \var.}
  30. \smallskip
  31. \+\op void union\_blocks {node\ v,\ node\ w} 
  32.                              {unites the blocks of \var\ containing nodes}
  33. \+\nop                       {$v$ and $w$.}
  34. \smallskip
  35. \+\op node find {node\ v}    {returns a canonical representative node of}
  36. \+\nop                       {the block that contains node $v$.}
  37. \smallskip
  38.  
  39.  
  40. \bigskip
  41. {\bf 3. Implementation}
  42.  
  43. A node partition for a graph $G$ is implemented by a combination of a 
  44. partition $P$ and a node array of $partition\_item$ associating with 
  45. each node in $G$ a partition item in $P$. Initialization takes linear time,
  46. union\_blocks takes time $O(1)$ (worst-case), and same\_block and find take 
  47. time $O(\alpha(n))$ (amortized).  The space requirement is $O(n)$, where $n$ 
  48. is the number of nodes of $G$.
  49.  
  50. \vfill\eject
  51.  
  52.