home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / node_set.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  1.7 KB  |  59 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.9 Sets of nodes and edges (node\_set, edge\_set)}
  4.  
  5.  
  6. An instance $S$ of the data type $node\_set$ ($edge\_set$) is a subset of 
  7. the nodes (edges) of a graph $G$. $S$ is said to be valid for the nodes 
  8. (edges) of $G$.
  9.  
  10.  
  11. \bigskip
  12. {\bf 1. Creation of a node or edge set}
  13.  
  14. $node\_set$ $S(G)$;\nl
  15. $edge\_set$ $S(G)$;
  16.  
  17. creates an instance $S$ of type $node\_set$  ($edge\_set$) valid for all nodes
  18. (edges) currently contained in graph $G$ and initializes it to the empty set. 
  19.  
  20.  
  21. \bigskip
  22. \def\var{$S$}
  23. {\bf 2. Operations on a node/edge set S}
  24. \medskip
  25. \+\op void insert {x}                 
  26.                                 {adds node (edge) $x$ to $S$}
  27. \smallskip
  28. \+\op void del {x}                    
  29.                                 {removes node (edge) $x$ from $S$}
  30. \smallskip
  31. \+\op bool member {x}                 
  32.                                 {returns true if $x$ in $S$, false otherwise}
  33. \smallskip
  34. \+\op node/edge choose {}                 
  35.                                 {return a node (edge) of $S$}
  36. \smallskip
  37. \+\op int  size  {}                  
  38.                                 {returns the size of $S$}
  39. \smallskip
  40. \+\op bool  empty {}                  
  41.                                 {returns true iff $S$ is the empty set}
  42. \smallskip
  43. \+\op void clear {}                   
  44.                                 {makes $S$ the empty set}
  45.  
  46. \bigskip
  47. {\bf 3. Implementation}
  48.  
  49. A node (edge) set $S$ for a graph $G$ is implemented by a combination of a 
  50. list  $L$ of nodes (edges) and a node (edge) array of list\_items 
  51. associating with each node (edge) its position in $L$. All operations 
  52. take constant time, except of clear which takes time $O(|S|)$. The space 
  53. requirement is $O(n)$, where $n$ is the number of nodes (edges) of $G$.
  54.  
  55.  
  56. \vfill\eject
  57.  
  58.  
  59.