home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / node_arr.tex < prev    next >
Encoding:
Text File  |  1991-12-05  |  3.2 KB  |  89 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.7 Node and edge arrays (node\_array, edge\_array)}
  4.  
  5. An instance $A$ of the data type $node\_array$ ($edge\_array$) is a partial 
  6. mapping from the node set $V$ (edge set $E$) of a (u)graph $G$ to a set of 
  7. variables of a data type $E$, called the element type of the array. The 
  8. domain $I$ of $A$ is called the index set of $A$ and $A(x)$ is called the 
  9. element at position $x$. $A$ is said to be valid for all nodes (edges) in $I$. 
  10.  
  11.  
  12.  
  13. \bigskip
  14. {\bf 1. Declaration of node and edge array types}
  15.  
  16. \decl node/edge\_array E 
  17.  
  18. introduces a new data type with name $node\_array(E)$ ($edge\_array(E)$)
  19. consisting of all node (edge) arrays with element type $E$.
  20.  
  21.  
  22. \def\name {$node/edge\_array$}
  23. \def\type {$node/edge\_array$}
  24.  
  25. \bigskip
  26. {\bf 2. Creation of a node array (edge array)}
  27.  
  28. a) \create A {}
  29.  
  30. b) \create A (graph\ G)
  31.  
  32. c) \create A (graph\ G,\ E\ x)
  33.  
  34. d) \create A (graph\ G,\ int\ n,\ E\ x)    
  35.  
  36.  
  37. creates an instance $A$ of type $node\_array(E)$ or $edge\_array(E)$. Variant a)
  38. initializes the index set of $A$ to the empty set, Variants b) and c) 
  39. initialize the index set of $A$ to be the entire node (edge) set of graph $G$,
  40. i.e., $A$ is made valid for all nodes (edges) currently contained in $G$. 
  41. Variant c) in addition initializes $A(i)$ with $x$ for all nodes (edges) 
  42. $i$ of $G$. Variant d) makes $A$ a $node/edge\_array(E)$ valid for up to $n$ 
  43. nodes/edges of $G$, \precond $n \ge |V|$ ($|E|$), this is useful if you want
  44. to use the array for later inserted nodes/edges.
  45.  
  46.  
  47.  
  48. \bigskip
  49. \def\var{$A$}
  50. {\bf 3. Operations}
  51. \medskip
  52.  
  53. \+\op void  init {graph\ G}         
  54.                              {sets the index set $I$ of $A$ to the node (edge)}
  55. \+\nop                       {set of $G$, i.e., makes $A$ valid for all nodes}
  56. \+\nop                       {(edges) of $G$.}
  57. \smallskip
  58. \+\op void  init {graph\ G,\ E\ x}    
  59.                              {makes $A$ valid for all nodes (edges) of $G$ }
  60. \+\nop                       {and sets $A(i) = x$ for all nodes (edges) of $G$}
  61. \smallskip
  62. \+\op void  init {graph\ G,\ int\ n,\ E\ x}  {}
  63. \+\nop                       {makes $A$ valid for at most $n$ nodes (edges)}
  64. \+\nop                       {of $G$ and sets $A(i) = x$ for all nodes (edges)}
  65. \+\nop                       {of $G$. \precond $n \ge |V|$ ($n \ge |E|$). }
  66. \smallskip
  67. \+\opa E\&  {node/edge\ i}                    
  68.                              {access the variable $A(i)$.}
  69. \+\nop                       {\precond $A$ must be valid for $i$.}
  70.  
  71. \bigskip
  72. {\bf 4. Implementation}
  73.  
  74. Node (edge) arrays for a graph $G$ are implemented by \CC vectors and an 
  75. internal numbering of the nodes and edges of $G$. The access operation 
  76. takes constant time, $init$ takes time $O(n)$, where $n$ is the number of 
  77. nodes (edges) currently in $G$. The space requirement is $O(n)$.
  78.  
  79. {\bf Remark}: A node (edge) array is only valid for a bounded number of
  80. the nodes (edges) contained in $G$. This number is either the total number
  81. of nodes of $G$ at the moment of the array creation (variants a) \dots c)) or 
  82. it is explicitely set by the user (variant d)).  Access operations for 
  83. additional later added nodes (edges) are not allowed. Fully dynamic node and
  84. edge arrays can be realized by using hashing arrays, e.g., 
  85. $h\_array(node,\dots)$ (cf. section~4.5).
  86.  
  87. \vfill\eject
  88.  
  89.