home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / graph2.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  10.5 KB  |  259 lines
  1. \bigskip
  2. {\magonebf 5.1 Directed graphs (graph)}
  3.  
  4. An instance $G$ of the data type $graph$ consists of a set of nodes $V$ and a 
  5. set of edges E ($node$ and $edge$ are predefined data types). Every edge $e\in 
  6. E$ is a pair of nodes $(v,w) \in V\times V$, $v$ is called the source of $e$ and
  7. $w$ is called the target of $e$. With every node $v$ the list of its adjacent 
  8. edges $adj\_list(v) = \{\ e \in E\ | source(e) = v\ \}$, called the adjacency 
  9. list of $v$, is associated.
  10.  
  11. \bigskip
  12. \def\name{$graph$}
  13. \def\type{graph}
  14. {\bf 1. Creation of a graph}
  15.  
  16. \create G {}
  17.  
  18. creates an instance $G$ of type $graph$ and initializes it to the
  19. empty graph.
  20.  
  21.  
  22. \bigskip
  23. {\bf 2. \operations}
  24.  
  25. {\bf a) Access operations}
  26. \+\cleartabs & \hskip 2truecm & \hskip 5.5truecm &\cr
  27. \+\op int        indeg {node\ v}                     
  28.                                       {returns the indegree of node $v$}
  29. \smallskip
  30. \+\op int        outdeg {node\ v}                     
  31.                                       {returns the outdegree of node $v$}
  32. \smallskip
  33. \+\op node       source {edge\ e}               
  34.                                       {returns the source node of edge $e$}
  35. \smallskip
  36. \+\op node       target {edge\ e}               
  37.                                       {returns the target node of edge $e$}
  38. \smallskip
  39. \+\op int        number\_of\_nodes { }
  40.                              {returns the number of nodes in $G$ }
  41. \smallskip
  42. \+\op int        number\_of\_edges { }
  43.                              {returns the number of edges in $G$ }
  44. \smallskip
  45. \+\op list(node) all\_nodes {      }
  46.                              {returns the list of all nodes of $G$}
  47. \smallskip
  48. \+\op list(edge) all\_edges {      }
  49.                              {returns the list of all edges of $G$}
  50. \smallskip
  51. \+\op list(edge) adj\_edges {node\ v}  
  52.                              {returns the list of all edges adjacent to $v$}
  53. \smallskip
  54. \+\op list(node) adj\_nodes {node\ v}  
  55.                              {returns the list of all nodes adjacent to $v$}
  56. \smallskip
  57. \+\op edge   first\_adj\_edge {node\ v}
  58.                            {returns the first edge in the adjacency list of $v$}
  59. \smallskip 
  60. \+\op edge   last\_adj\_edge {node\ v} 
  61.                            {returns the last edge in the adjacency list of $v$}
  62. \smallskip
  63. \+\op edge   adj\_succ {edge\ e}           
  64.                             {returns the successor of edge $e$ in the }
  65. \+\nop                      {adjacency list of $source(e)$ }
  66. \+\nop                      {(nil if it does not exist)}
  67. \smallskip
  68. \+\op edge   adj\_pred {edge\ e}          
  69.                              {returns the predecessor of edge $e$ in the }
  70. \+\nop                       {adjacency list of $source(e)$}
  71. \+\nop                       {(nil if it does not exist)}
  72. \smallskip
  73. \+\op edge   cyclic\_adj\_succ {edge\ e}    
  74.                              {returns the cyclic successor of edge $e$ in the}
  75. \+\nop                       {adjacency list of $source(e)$}
  76. \smallskip
  77. \+\op edge   cyclic\_adj\_pred {edge\ e}    
  78.                              {returns the cyclic predecessor of edge $e$ in the}
  79. \+\nop                       {adjacency list of $source(e)$}
  80. \smallskip
  81. \+\op node   choose\_node   {}
  82.                               {returns a node of $G$ (nil if $G$ is empty)}
  83. \smallskip
  84. \+\op edge   choose\_edge   {}
  85.                               {returns an edge of $G$ (nil if $G$ is empty)}
  86.  
  87. \bigskip
  88. {\bf b) Update operations}
  89. \medskip
  90. \+\op node   new\_node {}   
  91.                              {adds a new node to $G$ and returns it}
  92. \smallskip
  93. \+\op void   del\_node {node\ v}      
  94.                              {deletes $v$ and all edges adjacent to $v$}
  95. \+\nop                       {from $G$. \precond{$indeg(v) = 0$}.}
  96. \smallskip
  97. \+\op edge   new\_edge {node\ v,\ w}
  98.                              {adds a new edge $(v,w)$ to $G$ by appending }
  99. \+\nop                       {it to the adjacency list of $v$ and returns it.}
  100. \smallskip
  101. \+\op edge   new\_edge {edge\ e,\ node\  w,\ rel\_pos\ dir=after} {}
  102. \+\nop                      {adds a new edge $e\' = (source(e),w)$ to $G$ by }
  103. \+\nop                      {inserting it after ($dir$=after) or before ($dir$}
  104. \+\nop                      {=before) edge $e$ into the adjacency list of }
  105. \+\nop                      {$source(e)$, returns $e\'$.}
  106. \smallskip
  107. \+\op void   del\_edge {edge\ e}      
  108.                              {deletes the edge $e$ from $G$}
  109. \smallskip
  110. \+\op void       del\_all\_nodes {}
  111.                              {deletes all nodes from $G$ }
  112. \smallskip
  113. \+\op void       del\_all\_edges {}
  114.                              {deletes all edges from $G$ }
  115. \smallskip
  116. \+\op edge   rev\_edge {edge\ e}      
  117.                              {reverses the edge $e = (v,w)$ by removing it }
  118. \+\nop                       {from $G$ and inserting the edge $e\' = (w,v)$ }
  119. \+\nop                       {into $G$ by appending it to the adjacency list}
  120. \+\nop                       {of $w$, returns $e\'$ }
  121. \smallskip
  122. \+\op void   rev {}                 
  123.                              {all edges in $G$ are reversed}
  124. \smallskip
  125. \+\op void   sort\_nodes {int (*cmp)(node\&,\ node\&)}  {}
  126. \+\nop                       {the nodes of $G$ are sorted according to the}
  127. \+\nop                       {ordering defined by the comparing function}
  128. \+\nop                       {$cmp$. Subsequent executions of forall\_nodes}
  129. \+\nop                       {step through the nodes in this order.}
  130. \+\nop                       { (cf. TOPSORT1 in section 8.1)}
  131. \smallskip
  132. \+\op void   sort\_nodes {node\_array(T)\ A}  {}
  133. \+\nop                       {the nodes of $G$ are sorted according to the}
  134. \+\nop                       {entries of node\_array $A$ (cf. section 5.7)}
  135. \+\nop                       {\precond $T$ must be linearly ordered}
  136. \smallskip
  137. \+\op void   sort\_edges {int (*cmp)(edge\&,\ edge\&)}  {}
  138. \+\nop                       {the edges of $G$ are sorted according to the}
  139. \+\nop                       {ordering defined by the comparing function}
  140. \+\nop                       {$cmp$. Subsequent executions of forall\_edges}
  141. \+\nop                       {step through the edges in this order.}
  142. \+\nop                       { (cf. TOPSORT1 in section 8.1)}
  143. \smallskip
  144. \+\op void   sort\_edges {edge\_array(T)\ A}  {}
  145. \+\nop                       {the edges of $G$ are sorted according to the}
  146. \+\nop                       {entries of edge\_array $A$ (cf. section 5.7)}
  147. \+\nop                       {\precond $T$ must be linearly ordered}
  148. \smallskip
  149. \+\op list(edge) insert\_reverse\_edges {} {}
  150. \+\nop                       {for every edge $(v,w)$ in $G$ the reverse edge}
  151. \+\nop                       {$(w,v)$ is inserted into $G$. The list of all}
  152. \+\nop                       {inserted edges is returned.}
  153. \+\op void   clear {}              
  154.                              {makes $G$ the empty graph}
  155.  
  156. \bigskip
  157. {\bf c) Iterators}
  158. \medskip
  159. With the adjacency list of every node $v$ is associated a list iterator 
  160. called the adjacency iterator of $v$ (cf. list). There are operations to 
  161. initialize the adjacency iterator, to move it to the successor or predecessor
  162. list item, to access its contents (an edge) and to test if it is defined,
  163. ($\ne$ nil). Adjacency iterators are used to implement iteration statements 
  164. (forall\_adj\_edges, forall\_adj\_nodes). 
  165. \bigskip
  166. \+\op void   init\_adj\_iterator {node\ v}         
  167.                       {assigns nil to the adjacency iterator of node $v$}
  168. \smallskip
  169. \+\op bool   current\_adj\_edge {edge\&\ e,\ node\ v}  {}
  170. \+\nop                {if the adjacency iterator of $v$ is defined ($\ne$ nil)} 
  171. \+\nop                {its contents is assigned to $e$ and true is returned}
  172. \+\nop                {else false is returned.}
  173. \smallskip
  174. \+\op bool   next\_adj\_edge {edge\&\ e,\ node\ v}     {}
  175. \+\nop                {moves the adjacency iterator of $v$ forward (to the}
  176. \+\nop                {first item of $adj\_list(v)$ if it is nil) and returns}
  177. \+\nop                {$G$.current\_adj\_edge($e,v$)}
  178. \smallskip
  179. \+\op bool   current\_adj\_node {node\&\ w,\ node\ v}  {}
  180. \+\nop                {if $G$.current\_adj\_edge($e$, $v$) = true then assign}
  181. \+\nop                {$target(e)$ to w and return true, else return}
  182. \+\nop                {false}
  183. \smallskip
  184. \+\op bool   next\_adj\_node {node\&\ w,\ node\ v}     {}
  185. \+\nop                {if $G$.next\_adj\_edge($e$, $v$) = true then assign}
  186. \+\nop                {$target(e)$ to w and return true, else return}
  187. \+\nop                {false}
  188. \smallskip
  189. \+\op void   reset {}                          
  190.                       {assign nil to all adjacency iterators in $G$}
  191. \bigskip
  192.  
  193. \vfill\eject
  194. {\bf d) Miscellaneous operations}
  195. \medskip
  196. \smallskip
  197. \+\op void   write {string\ s}        
  198.                              {writes a compressed representation of $G$ to }
  199. \+\nop                       {the file with name $s$}
  200. \smallskip
  201. \+\op void   read {string\ s}         
  202.                              {read a compressed representation of $G$ from }
  203. \+\nop                       {the file with name $s$}
  204. \smallskip
  205. \+\op void   print\_node {node\ v,\ ostream\ O = cout} {}              
  206. \+\nop                       {writes a readable representation of node $v$ to }
  207. \+\nop                       {the output stream $O$}
  208. \smallskip
  209. \+\op void   print\_edge {edge\ e,\ ostream\ O = cout} {}              
  210. \+\nop                       {writes a readable representation of edge $e$ to}
  211. \+\nop                       {the output stream $O$}
  212. \smallskip
  213. \+\op void   print {ostream\ O = cout}              
  214.                              {writes a readable representation of $G$ to the}
  215. \+\nop                       {output stream $O$}
  216. \smallskip
  217.  
  218. \bigskip
  219. {\bf e) Operators}
  220.  
  221. \+\opb graph\& = G1        
  222.                              {makes a copy of $G1$ and assigns it to $G$.}
  223.  
  224.  
  225. \bigskip
  226. {\bf 3. Iteration}
  227.  
  228.  
  229. {\bf forall\_nodes}($v,G$) 
  230. $\{$ ``the nodes of $G$ are successively assigned to $v$" $\}$
  231.  
  232. {\bf forall\_edges}($e,G$)  
  233. $\{$ ``the edges of $G$ are successively assigned to $e$" $\}$
  234.  
  235. {\bf forall\_adj\_edges}($e,w$) \nl
  236. \phantom{{\bf forall\_edges}($v,G$)}
  237. $\{$ ``the edges adjacent to node w are successively assigned to e" $\}$
  238.  
  239. {\bf forall\_adj\_nodes}($v,w$) \nl  
  240. \phantom{{\bf forall\_edges}($v,G$)}
  241. $\{$ ``the nodes adjacent to node w are successively assigned to v" $\}$
  242.  
  243. \bigskip
  244. {\bf 4. Implementation}
  245.  
  246. Graphs are implemented by adjacency lists. Most operations take constant
  247. time, except of all\_nodes, all\_edges, del\_all\_nodes, del\_all\_edges,
  248. clear, write, and read which take time $O(n+m)$, where $n$ is the current
  249. number of nodes and $m$ is the current number of edges. The space requirement
  250. is $O(n+m)$.
  251.  
  252.  
  253. \bigskip
  254. {\bf 5. Examples}
  255.  
  256. See section 8.1.
  257.  
  258. \vfill\eject
  259.