\manpage {node\_array} {E} {Node Arrays}
 
\definition
An instance $A$ of the parameterized data type $node\_array\<E\>$
is a partial mapping from the node set of a graph $G$ to the set of 
variables of type $E$, called the element type of the array. The domain 
$I$ of $A$ is called the index set of $A$ and $A(x)$ is called the element 
at position $x$. $A$ is said to be valid for all nodes in $I$.
 
\creation A 
 
\create { }
   { creates an instance $A$ of type $node\_array\<E\>$ with empty
            index set. }
 
 
\create {(graph\ G)}
   { creates an instance $A$ of type $node\_array\<E\>$ and initializes
            the index set of $A$ to the current node set of graph $G$.  }
 
 
\create {(graph\ G,\ E\ x)}
   { creates an instance $A$ of type $node\_array\<E\>$, sets the
            index set of $A$ to the current node set of graph $G$ and 
            initializes $A(v)$ with $x$ for all nodes $v$ of $G$.  }
 
 
\create {(graph\ G,\ int\ n,\ E\ x)}
   { creates an instance $A$ of type $node\_array\<E\>$ valid for
            up to $n$ nodes of graph $G$ and initializes $A(v)$ with $x$ 
            for all nodes $v$ of $G$. \precond $n \ge |V|$. $A$ is also
            valid for the next $n - |V|$ nodes added to $G$. }
 
 
\operations 1.3 4.7 
 
\arrop E\&  {node\ v}
         {  returns the variable $A(v)$.\\
	      \precond $A$ must be valid for $v$. }
 
 
\op  void init {( graph\ G)}
           {  sets the index set $I$ of $A$ to the node
	      set of $G$, i.e., makes $A$ valid for all nodes 
              of $G$. }
 
 
\op  void init {( graph\ G, \ E\ x)}
           {  makes $A$ valid for all nodes of $G$
	      and sets $A(v) = x$ for all nodes $v$ of $G$. }
 
 
\op  void init {( graph\ G, \ int\ n, \ E\ x)}
           {  makes $A$ valid for at most $n$ nodes
	      of $G$ and sets $A(i) = x$ for all nodes  
	      of $G$. \precond {$n \ge |V|$}. $A$ is also
              valid for the next  $n - |V|$ nodes added to $G$.  }
 
 
\implementation
Node arrays for a graph $G$ are implemented by \CC vectors and an
internal numbering of the nodes and edges of $G$. The access operation
takes constant time, $init$ takes time $O(n)$, where $n$ is the number of
nodes in $G$. The space requirement is $O(n)$.
    
{\bf Remark}: A node array is only valid for a bounded number of
nodes of $G$. This number is either the number
of nodes of $G$ at the moment of creation of the array or it is explicitely 
set by the user. Dynamic node arrays can be realized by node 
maps (cf. section \ref{Node Maps}). 
 
