home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / ugraph2.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  2.9 KB  |  74 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.2 Undirected graphs (ugraph)}
  4.  
  5. An instance $G$ of the data type $ugraph$ consists of a set of nodes $V$ and a 
  6. set of undirected edges $E$. Every edge $e \in E$ is a set of two nodes 
  7. $\{v,w\}$, $v$ and $w$ are called the endpoints of $e$. With every node $v$ is 
  8. associated the list of its adjacent edges 
  9. $adj\_list(v) = \{\ e \in E\ | v \in e\ \}$.
  10.  
  11. \bigskip
  12. \def\name{$ugraph$}
  13. \def\type{ugraph}
  14. {\bf 1. Creation of an undirected graph }
  15.  
  16. \create G {}
  17.  
  18. creates an instance $G$ of type $ugraph$ and initializes it to the
  19. empty undirected graph.
  20.  
  21.  
  22. \bigskip
  23. {\bf 2. \operations }
  24. \medskip
  25. Most operations are the same as for directed graphs. The following operations
  26. are either additional or have different effects.
  27. \medskip
  28. \+\cleartabs & \hskip 1.5truecm & \hskip 5.8truecm &\cr
  29. \+\op node opposite {node\ v,\ edge\ e} 
  30.                                {returns $w$ if $e = \{v,w\}$, nil otherwise}
  31. \smallskip
  32. \+\op int  degree {node\ v} 
  33.                                {returns the degree of node $v$.}
  34. \smallskip
  35. \+\op edge new\_edge {node\ v,\ node\ w}
  36.                              {inserts the undirected edge $\{v,w\}$ into $G$ by}
  37. \+\nop                       {appending it to the adjacency lists of both}
  38. \+\nop                       {$v$ and $w$ and returns it }
  39. \smallskip
  40. \+\op edge new\_edge {node\ v,\ node\ w,\ edge\ e1,\ edge\ e2,\ dir1=after,\ dir2=after} {}
  41. \+\nop                {inserts the undirected edge $\{v,w\}$ after (if $dir1$}
  42. \+\nop                {$=after$) or before (if $dir1=before$) the edge}
  43. \+\nop                {$e1$ into the adjacency list of $v$ and after (if $dir2$}
  44. \+\nop                {$=after$) or before (if $dir2=before$) the edge }
  45. \+\nop                {$e2$ into the adjacency list of $w$ and returns it}
  46. \smallskip
  47. \+\op edge adj\_succ {edge\ e,\ node\ v} 
  48.                              {returns the successor of edge $e$ in the}
  49. \+\nop                       {adjacency list of $v$. }
  50. \smallskip
  51. \+\op edge adj\_pred {edge\ e,\ node\ v} 
  52.                              {returns the predecessor of edge $e$ in the}
  53. \+\nop                       {adjacency list of $v$. }
  54. \smallskip
  55. \+\op edge cyclic\_adj\_succ {edge\ e,\ node\ v} {}
  56. \+\nop                       {returns the cyclic successor of edge $e$ in the}
  57. \+\nop                       {adjacency list of $v$. }
  58. \smallskip
  59. \+\op edge cyclic\_adj\_pred {edge\ e,\ node\ v} {}
  60. \+\nop                       {returns the cyclic predecessor of edge $e$ in the}
  61. \+\nop                       {adjacency list of $v$. }
  62.  
  63. \vfill\eject
  64.  
  65. \bigskip
  66. {\bf 3. Implementation}
  67.  
  68. Undirected graphs are implemented like directed graphs by adjacency lists. 
  69. The adjacency list of a node $v$ contains all edges $\{v,w\}$ of the graph.
  70. Most operations take constant time, except of all\_nodes, all\_edges, 
  71. del\_all\_nodes, del\_all\_edges, clear, write, and read which take time 
  72. $O(n+m)$, where $n$ is the current number of nodes and $m$ is the current 
  73. number of edges. The space requirement is $O(n+m)$.
  74.