\bigskip
\bigskip
{\magonebf 5.7 Node and edge arrays (node\_array, edge\_array)}

An instance $A$ of the data type $node\_array$ ($edge\_array$) is a partial 
mapping from the node set $V$ (edge set $E$) of a (u)graph $G$ to a set of 
variables of a data 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 (edges) in $I$. 



\bigskip
{\bf 1. Declaration of node and edge array types}

\decl node/edge\_array E 

introduces a new data type with name $node\_array(E)$ ($edge\_array(E)$)
consisting of all node (edge) arrays with element type $E$.


\def\name {$node/edge\_array$}
\def\type {$node/edge\_array$}

\bigskip
{\bf 2. Creation of a node array (edge array)}

a) \create A {}

b) \create A (graph\ G)

c) \create A (graph\ G,\ E\ x)

d) \create A (graph\ G,\ int\ n,\ E\ x)    


creates an instance $A$ of type $node\_array(E)$ or $edge\_array(E)$. Variant a)
initializes the index set of $A$ to the empty set, Variants b) and c) 
initialize the index set of $A$ to be the entire node (edge) set of graph $G$,
i.e., $A$ is made valid for all nodes (edges) currently contained in $G$. 
Variant c) in addition initializes $A(i)$ with $x$ for all nodes (edges) 
$i$ of $G$. Variant d) makes $A$ a $node/edge\_array(E)$ valid for up to $n$ 
nodes/edges of $G$, \precond $n \ge |V|$ ($|E|$), this is useful if you want
to use the array for later inserted nodes/edges.



\bigskip
\def\var{$A$}
{\bf 3. Operations}
\medskip

\+\op void  init {graph\ G}         
                             {sets the index set $I$ of $A$ to the node (edge)}
\+\nop                       {set of $G$, i.e., makes $A$ valid for all nodes}
\+\nop                       {(edges) of $G$.}
\smallskip
\+\op void  init {graph\ G,\ E\ x}    
                             {makes $A$ valid for all nodes (edges) of $G$ }
\+\nop                       {and sets $A(i) = x$ for all nodes (edges) of $G$}
\smallskip
\+\op void  init {graph\ G,\ int\ n,\ E\ x}  {}
\+\nop                       {makes $A$ valid for at most $n$ nodes (edges)}
\+\nop                       {of $G$ and sets $A(i) = x$ for all nodes (edges)}
\+\nop                       {of $G$. \precond $n \ge |V|$ ($n \ge |E|$). }
\smallskip
\+\opa E\&  {node/edge\ i}                    
                             {access the variable $A(i)$.}
\+\nop                       {\precond $A$ must be valid for $i$.}

\bigskip
{\bf 4. Implementation}

Node (edge) 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 (edges) currently in $G$. The space requirement is $O(n)$.

{\bf Remark}: A node (edge) array is only valid for a bounded number of
the nodes (edges) contained in $G$. This number is either the total number
of nodes of $G$ at the moment of the array creation (variants a) \dots c)) or 
it is explicitely set by the user (variant d)).  Access operations for 
additional later added nodes (edges) are not allowed. Fully dynamic node and
edge arrays can be realized by using hashing arrays, e.g., 
$h\_array(node,\dots)$ (cf. section~4.5).

\vfill\eject

