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