home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / node_mat.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  2.4 KB  |  70 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.8 Two dimensional node arrays  (node\_matrix)}
  4.  
  5.  
  6. An instance $M$ of the data type $node\_matrix$  is 
  7. a partial mapping from the set of node pairs $V\times V$
  8. of a graph to a set of variables of a data type $E$, called the element type 
  9. of $M$. The domain $I$ of $M$ is called the index set of $M$. $M$ is said to 
  10. be valid for all node pairs in $I$. A node matrix can also be viewed as a 
  11. node array with element type $node\_array(E)$ ($node\_array(node\_array(E))$). 
  12.  
  13.  
  14. \bigskip
  15. {\bf 1. Declaration of a node matrix type}
  16.  
  17. \decl node\_matrix E 
  18.  
  19. introduces a new data type with name \name\ consisting of all 
  20. node matrices with element type $E$.
  21.  
  22.  
  23. \bigskip
  24. {\bf 2. Creation of a node\_matrix}
  25.  
  26.  
  27. a) \create M {}
  28.  
  29. b) \create M (G)
  30.  
  31. c) \create M (G,x)
  32.  
  33. creates an instance $M$ of type \name. Variant a) initializes the index set 
  34. of $M$ to the empty set, Variants b) and c) initialize the index set of $A$ 
  35. to be the set of all node pairs of graph $G$, i.e., $M$ is made valid for all 
  36. pairs in $V \times V$ where $V$ is the set of nodes currently contained in $G$. 
  37. Variant c) in addition initializes  $M(v,w)$ with $x$ for all nodes $v,w \in V$.
  38.  
  39.  
  40. \bigskip
  41. {\bf 3. \operations }
  42. \medskip
  43. \+\op void  init {graph\ G}         
  44.                              {sets the index set of $M$ to $V\times V$, where }
  45. \+\nop                       {$V$ is the set of all nodes of $G$ }
  46. \smallskip
  47. \+\op void  init {graph\ G,\ E\ x}    
  48.                             {sets the index set of $M$ to $V\times V$, where }
  49. \+\nop                      {$V$ is the set of all nodes of $G$ and initializes}
  50. \+\nop                      {$M(v,w)$ to $x$ for all $v,w \in V$.}
  51. \smallskip
  52. \+\opf E\&  {node\ v,\ node\ w}
  53.                             {returns the variable $M(v,w)$.}
  54. \+\nop                      {\precond $M$ must be valid for $v$ and $w$.}
  55. \smallskip
  56. \+&$node\_array(E)\&$ $M[v]$ &&returns the node\_array  $M(v).$\cr
  57.  
  58. \bigskip
  59. {\bf 4. Implementation}
  60.  
  61. Node matrices for a graph $G$ are implemented by vectors of node arrays and an 
  62. internal numbering of the nodes of $G$. The access operation 
  63. takes constant time, the init operation takes time $O(n^2)$, where $n$ is the 
  64. number of nodes currently contained in $G$. The space requirement is $O(n^2)$.
  65. Note that a node matrix is only valid for the nodes contained in $G$ at the 
  66. moment of the matrix declaration or initialization ($init$). Access operations 
  67. for later added nodes are not allowed.
  68.  
  69.  
  70.