home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / ugraph.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  2.4 KB  |  68 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.5 Parameterized undirected graphs (UGRAPH)}
  4.  
  5. A parameterized undirected graph $G$ is an undirected graph whose nodes and 
  6. edges contain additional (user defined) informations. Every node contains an 
  7. element of a data type $vtype$, called the node type of $G$ and every edge 
  8. contains an element of a data type $etype$ called the edge type of $G$. 
  9. We use $<\{v,w\},y>$ to denote the undirected edge $\{v,w\}$ with information 
  10. $y$ and $<x>$ to denote a node with information $x$. 
  11.  
  12.  
  13.  
  14. \bigskip
  15. {\bf 1. Declaration of a parameterized undirected graph type}
  16.  
  17.  
  18.  
  19. \decltwo UGRAPH vtype etype 
  20.  
  21. introduces a new data type with name \name\ consisting of all
  22. undirected parameterized graphs with node type $vtype$ and edge type $etype$.
  23.  
  24.  
  25. \medskip
  26. {\bf 2. Creation of a parameterized undirected graph }
  27.  
  28. \create G {}
  29.  
  30. creates an instance G of type \name and and initializes it to the empty graph.
  31.  
  32.  
  33. \medskip
  34. {\bf 3. \operations}
  35.  
  36. In addition to the operations of the data type $ugraph$ (see section 5.3):
  37. \medskip
  38. \+\op vtype/etype  inf {node/edge\ a}         
  39.                           {returns the information of node/edge $a$ } 
  40. \smallskip
  41. \+\op void   assign {node/edge\ a,\ vtype/etype\ x} {}
  42. \+\nop                    {makes $x$ the information of node/edge $a$ }
  43. \smallskip
  44. \+\op node   new\_node {vtype\ x}   
  45.                           {adds a new node $<x>$ to $G$ and returns it}
  46. \smallskip
  47. \+\op edge new\_edge {node\ v,\ node\ w,\ etype\ x} {}
  48. \+\nop                    {inserts the undirected edge $<\{v,w\},x>$ into }
  49. \+\nop                    {$G$ by appending it to the adjacency lists of }
  50. \+\nop                    {both $v$ and $w$ and returns it }
  51. \smallskip
  52. \+\op edge new\_edge {node\ v,\ node\ w,\ edge\ e1,\ edge\ e2,\ etype\ x,\ rel\_pos\ dir1=} {}
  53. \+\nop                     {$after,\ rel\_pos\ dir2=after$)}
  54. \+\nop                     {inserts the undirected edge $<\{v,w\},x>$ after}
  55. \+\nop                     {(if $dir1=after$) or before (if $dir1=before$) }
  56. \+\nop                     {the edge $e1$ into the adjacency list of $v$ and }
  57. \+\nop                     {after (if $dir2=after$) or before (if $dir2=$}
  58. \+\nop                     {$before$) the edge $e2$ into the adjacency list}
  59. \+\nop                     {of $w$ and returns it.}
  60.  
  61. \bigskip
  62. {\bf 4. Implementation}
  63.  
  64. Parameterized undirected graphs are derived from undirected graphs. All 
  65. additional operations for manipulating the node and edge informations take 
  66. constant time.
  67.  
  68.