home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / planar_m.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  4.2 KB  |  107 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.3 Planar Maps (planar\_map)}
  4.  
  5. An instance $M$ of the data type $planar\_map$ is the combinatorial
  6. embedding of a planar graph.
  7.  
  8. \def\name{$planar\_map$}
  9. \def\type{planar\_map}
  10.  
  11. \bigskip
  12. {\bf 1. Creation of a planar\_map}
  13.  
  14. \create M (graph\ G)
  15.  
  16. creates an instance $M$ of type $planar\_map$ and initializes it to 
  17. the planar map represented by the directed graph $G$. \precond $G$ 
  18. represents an undirected planar map, i.e. for every edge $(v,w)$ in $G$
  19. the reverse edge $(w,v)$ is also in $G$ and there is a planar embedding
  20. of $G$ such that for every node $v$ the ordering of the edges in the 
  21. adjacency list of $v$ corresponds to the counter-clockwise ordering of
  22. these edges around $v$ in the embedding. 
  23.  
  24.  
  25. \bigskip
  26. {\bf 2. \operations}
  27. \medskip
  28. Most operations are the same as for directed graphs. The following operations
  29. are either additional or have different effects.
  30. \medskip
  31. \+\cleartabs & \hskip 2truecm & \hskip 5.5truecm &\cr
  32. \+\op face       adj\_face  {edge\ e}
  33.                                {returns the face of \var\ to the right of $e$.}
  34. \smallskip
  35. \+\op list(face) all\_faces {}
  36.                                {returns the list of all faces of \var.}
  37. \smallskip
  38. \+\op list(face) adj\_faces {node\ v}
  39.                                {returns the list of all faces of \var\ adjacent}
  40. \+\nop                         {to node $v$ in counter-clockwise order.}
  41. \smallskip
  42. \+\op list(edge) adj\_edges {face\ f}
  43.                                {returns the list of all edges of \var\ bounding}
  44. \+\nop                         {face $f$ in clockwise order.}
  45. \smallskip
  46. \+\op list(node) adj\_nodes {face\ f}
  47.                                {returns the list of all nodes of \var\ adjacent}
  48. \+\nop                         {to face $f$ in clockwise order.}
  49. \smallskip
  50. \+\op edge       reverse   {edge\ e}
  51.                                  {returns the reversal of edge $e$ in \var. }
  52. \smallskip
  53. \+\op edge       first\_face\_edge {}
  54.                                  {returns the first edge of face $f$ in \var. }
  55. \smallskip
  56. \+\op edge       succ\_face\_edge {edge\ e}
  57.                                {returns the successor edge of $e$ in face $f$}
  58. \+\nop                         {i.e., the next edge in clockwise order.}
  59. \smallskip
  60. \+\op edge       pred\_face\_edge {edge\ e}
  61.                               {returns the predecessor edge of $e$ in face $f$,}
  62. \+\nop                        {i.e., the next edge in counter-clockwise order.}
  63. \smallskip
  64. \+\op edge new\_edge {edge\ e_1,\ edge\ e_2} {}
  65. \+\nop                        {inserts the edge $e=(source(e_1),source(e_2))$}
  66. \+\nop                        {and its reversal edge into $M$. \precond }
  67. \+\nop                        {$e_1$ and $e_2$ are bounding the same face $F$.}
  68. \+\nop                        {The operation splits $F$ into two new faces.}
  69. \smallskip
  70. \+\op edge del\_edge {edge\ e}
  71.                               {deletes the edge $e$ from \var. The two faces}
  72. \+\nop                        {adjacent to $e$ are united to one face.}
  73. \smallskip
  74. \+\op list(edge) triangulate {}
  75.                              {triangulates all faces of \var\ by inserting new}
  76. \+\nop                       {edges. The list of inserted edges is is returned.}
  77. \smallskip
  78. \+\op void straight\_line\_embedding {node\_array(int)\ xcoord,\ node\_array(int)\ ycoord} {}
  79. \+\nop                    {computes a straight line embedding for $M$ with}
  80. \+\nop                    {integer coordinates $xcoord[v]$, $ycoord[v])$ in the}
  81. \+\nop                    {range $0\dots 2(n-1)$ for every node $v$ of $M$.}
  82.  
  83.  
  84. \bigskip
  85. {\bf 3. Iteration}
  86.  
  87. Additional iteration macros are
  88.  
  89. {\bf forall\_faces}($f,M$)  
  90. $\{$ ``the faces of $M$ are successively assigned to $f$" $\}$
  91.  
  92. {\bf forall\_adj\_edges}($e,f$) \nl
  93. \phantom{{\bf forall\_edges}($v,M$)}
  94. $\{$ ``the edges adjacent to face f are successively assigned to e" $\}$
  95.  
  96. \bigskip
  97. {\bf 4. Implementation}
  98.  
  99. Planar maps are implemented by parameterized directed graphs.
  100. All operations take constant time, except of, new\_edge and del\_edge
  101. which take time $O(f)$ where $f$ is the number of edges in the created
  102. faces, and triangulate and straight\_line\_embedding take time $O(n)$
  103. where $n$ is the current size (number of edges) of the planar map.
  104.  
  105. \vfill\eject
  106.  
  107.