\manpage {edge\_set} {} {Sets of Edges} 
 
\definition
An instance $S$ of the data type $edge\_set$ is a subset of
the edges of a graph $G$. $S$ is said to be valid for the
edges of $G$.
 
\creation S 
 
\create {(graph\ G)}
   { creates an instance $S$ of type $edge\_set$ valid for all edges
            currently in graph $G$ and initializes it to the empty set. } 
 
 
\operations 1.3 4 
 
\op  void insert {(edge\ x)}
           {  adds edge $x$ to $S$.  }
 
 
\op  void del {(edge\ x)}
           {  removes edge $x$ from $S$.  }
 
 
\op  bool member {(edge\ x)}
           {  returns true if $x$ in $S$, false otherwise.  }
 
 
\op  edge choose {()}
           {  return a edge of $S$.  }
 
 
\op  int  size {()}
           {  returns the size of $S$.  }
 
 
\op  bool empty {()}
           {  returns true iff $S$ is the empty set.  }
 
 
\op  void clear {()}
           {  makes $S$ the empty set.  }
 
 
\implementation
A edge set $S$ for a graph $G$ is implemented by a combination of a 
list  $L$ of edges and a edge array of list\_items 
associating with each edge its position in $L$. All operations 
take constant time, except for clear which takes time $O(|S|)$. The space 
requirement is $O(n)$, where $n$ is the number of edges of $G$.
 
