home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / graph1.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  4.7 KB  |  122 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.4 Parameterized Graphs (GRAPH)}
  4.  
  5. A parameterized graph $G$ is a graph whose nodes and edges contain additional
  6. (user defined) informations. Every node contains an element of a data type 
  7. $vtype$, called the node type of $G$ and every edge contains an element of a 
  8. data type $etype$ called the edge type of $G$. We use $<v,w,y>$ to denote an edge $(v,w)$ with information $y$ and $<x>$ to denote a node with information $x$.
  9.  
  10. All operations defined on instances of the data type $graph$ are also defined on
  11. instances of any parameterized graph type $GRAPH(vtype,etype)$. For 
  12. parameterized graphs there are additional operations to access or update the 
  13. informations associated with its nodes and edges.  
  14. Instances of a parameterized graph type can be used wherever an instance 
  15. of the data type $graph$ can be used, e.g., in assignments and as 
  16. arguments to functions with formal parameters of type $graph$ or $graph\&$. 
  17. If a function $f(graph\&\ G)$ is called with an argument $Q$ of type 
  18. $GRAPH(vtype,etype)$ then inside $f$ only the basic graph structure of $Q$ (the
  19. adjacency lists) can be accessed. The node and edge informations are hidden.
  20. This allows the design of generic graph algorithms, i.e., algorithms accepting
  21. instances of any parametrized graph type as argument.
  22.  
  23.  
  24. \bigskip
  25. {\bf 1. Declaration of a parameterized graph type}
  26.  
  27.  
  28. \decltwo GRAPH vtype etype
  29.  
  30. introduces a new data type with name \name\ consisting of all 
  31. parameterized graphs with node type $vtype$ and edge type $etype$. 
  32.  
  33.  
  34.  
  35. \bigskip
  36. {\bf 2. Creation of a parameterized graph}
  37.  
  38.  
  39. \create G {}
  40.  
  41. creates an instance \var\ of type \name\ and initializes it to the
  42. empty graph.
  43.  
  44.  
  45. \bigskip
  46. {\bf 3. \operations}
  47.  
  48. In addition to the operations of the data type $graph$ (see section 2):
  49. \medskip
  50. \+\op vtype  inf {node\ v}         
  51.                           {returns the information of node $v$ } 
  52. \medskip
  53. \+\op etype  inf {edge\ e}         
  54.                           {returns the information of edge $e$ }
  55. \medskip
  56. \+\op void   assign {node\ v,\ vtype\ x}
  57.                           {makes $x$ the information of node $v$ }
  58. \medskip
  59. \+\op void   assign {edge\ e,\ etype\ y}
  60.                           {makes $y$ the information of edge $e$ }
  61. \medskip
  62. \+\op node   new\_node {vtype\ x}   
  63.                           {adds a new node $<x>$ to $G$ and returns it}
  64. \medskip
  65. \+\op edge   new\_edge {node\ v,\ w,\ etype\ x} {}
  66. \+\nop                    {adds a new edge $e = <v,w,x>$ to $G$ by}
  67. \+\nop                    {appending it to the adjacency list of $v$}
  68. \+\nop                    { and returns $e$.}
  69. \medskip
  70. \+\op edge   new\_edge {edge\ e,\ node\  w,\ etype\ x,\ dir=after} {}
  71. \+\nop                    {adds a new edge $e\' = <source(e),w,x>$ to $G$}
  72. \+\nop                    {by inserting it after ($dir$=after) or before ($dir$}
  73. \+\nop                    {=before) edge $e$ into the adjacency list of }
  74. \+\nop                    {$source(e)$ and returns $e\'$.}
  75. \medskip
  76. \+\op void   sort\_nodes {}
  77.                           {the nodes of $G$ are sorted according to their}
  78. \+\nop                    {informations. \precond $vtype$ is linearly}
  79. \+\nop                    {ordered.}
  80. \smallskip
  81. \+\op void   sort\_edges {}
  82.                           {the edges of $G$ are sorted according to their}
  83. \+\nop                    {informations. \precond $etype$ is linearly}
  84. \+\nop                    {ordered.}
  85. \smallskip
  86. \+\op void   write {string\ fname}        
  87.                           {writes $G$ to the file with name $fname$. The}
  88. \+\nop                    {output functions $Print(vtype,ostream)$ and}
  89. \+\nop                    {$Print(etype,ostream)$ (cf. section 1.6) must}
  90. \+\nop                    {be defined. }
  91. \smallskip
  92. \+\op int   read {string\ fname}         
  93.                           {reads $G$ from the file with name $fname$. The}
  94. \+\nop                    {input functions $Read(vtype,istream)$ and }
  95. \+\nop                    {$Read(etype,istream)$ (cf. section 1.6) must}
  96. \+\nop                    {be defined. Returns error code}
  97. \+\nop                    {1 \quad if file $fname$ does not exist}
  98. \+\nop                    {2 \quad if graph is not of type $GRAPH(vtype,etype)$}
  99. \+\nop                    {3 \quad if file $fname$ does not contain a graph}
  100. \+\nop                    {0 \quad otherwise.}
  101.  
  102.  
  103.  
  104. \bigskip
  105. {\bf 4. Operators}
  106. \bigskip
  107. \+\opa vtype\&  {node\ v}  
  108.                            {returns a reference to $G$.inf($v$).}
  109. \medskip
  110. \+\opa etype\&  {edge\ e}  
  111.                            {returns a reference to $G$.inf($e$).}
  112.  
  113. \bigskip
  114. {\bf 5. Implementation}
  115.  
  116. Parameterized graphs are derived from directed graphs. All additional 
  117. operations for manipulating the node and edge informations take constant
  118. time.
  119.  
  120. \vfill\eject
  121.  
  122.