home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph / _p_embed.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  7.3 KB  |  253 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _p_embedding.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #include <LEDA/planar_map.h>
  18.  
  19.  
  20. //-----------------------------------------------------------------------------
  21. //
  22. // Straight Line Embedding
  23. //
  24. //-----------------------------------------------------------------------------
  25.  
  26. /* declare(node_array,int)  declared in header file */
  27.  
  28. declare(node_array,list_item)
  29. declare(node_array,node)
  30.  
  31. static
  32. void label_node( planar_map& G, list(node)& L, 
  33.                                 node_array(int)& ord,
  34.                                 int& count,
  35.                                 node_array(int)& labelled,
  36.                                 list(node)& Al,
  37.                                 list(node)& Bl,
  38.                                 list(node)*& Il,
  39.                                 node_array(int)& Class,
  40.                                 node_array(list_item)& Classloc,
  41.                                 node_array(node)& first, 
  42.                                 node_array(node)& second,
  43.                                 node_array(node)& last,
  44.                                 int A, 
  45.                                 int B, 
  46.                                 node v, 
  47.                                 node c)
  48.  
  49. { // labels the node v; c is the special node which is to be labelled
  50.   // last; the details are described in lemma 10
  51.   edge e;
  52.   L.append(v);
  53.   ord[v]=count++; 
  54.   labelled[v]=1;
  55.   forall_adj_edges(e,v)
  56.   { edge e1 = G.reverse(e);
  57.     node tt = target(e);
  58.     int i;
  59.     if (labelled[tt] && !labelled[target(G.cyclic_adj_succ(e))])
  60.        {first[v]=tt; 
  61.         second[v]=target(G.cyclic_adj_pred(e));
  62.        };
  63.     if (labelled[tt] && !labelled[target(G.cyclic_adj_pred(e))])
  64.        last[v]=tt;
  65.     if (!labelled[tt] && (tt != c))
  66.        {if (Class[tt] == A) { Al.del(Classloc[tt]); 
  67.                             Classloc[tt] = Bl.push(tt);
  68.                             Class[tt]=B;
  69.                           }  
  70.         else {if (Class[tt] == B) { Bl.del(Classloc[tt]);
  71.             /* geaendert wegen */ int x=labelled[target(G.cyclic_adj_succ(e1))];
  72.             /*  inline Fehler  */ int y=labelled[target(G.cyclic_adj_pred(e1))];
  73.                                   i=2-x-y;
  74.                                    }
  75.              else { i=Class[tt];
  76.                     Il[i].del(Classloc[tt]);
  77.                     i=i+1-labelled[target(G.cyclic_adj_succ(e1))]
  78.                          -labelled[target(G.cyclic_adj_pred(e1))];
  79.                   }//end if Class[tt] = B
  80.              Class[tt]=i;
  81.              Classloc[tt]=Il[i].push(tt);
  82.              }//end else case
  83.       }//end if
  84.   }//end 
  85. }//end of label_node
  86.  
  87.  
  88. static
  89. void compute_labelling(planar_map& G, list(node)& L, list(node)& Pi,
  90.                                       node_array(int)&  ord,
  91.                                       node_array(node)& first, 
  92.                                       node_array(node)& second,
  93.                                       node_array(node)& last)
  94.  
  95. { /* computes the ordering of lemma 10 in List L ,the sequence pi
  96.      in List Pi, the function L^-1(v) in Array ord, and the functions
  97.      first,second,last of lemma 11 in the corresponding Arrays
  98.    */
  99.   node v,a,b,c;
  100.  
  101.   /* zuerst berechne ich die drei Knoten,die am Rand des aeusseren 
  102.      Gebiets liegen sollen
  103.    */
  104.  
  105.   a=G.first_node(); 
  106.   edgelist temp = G.adj_edges(a);
  107.   b = target(temp.pop());
  108.   c = target(temp.pop());
  109.  
  110.  
  111.   node_array(int) labelled(G);
  112.   forall_nodes(v,G) labelled[v]=0;
  113.   int count = 0;
  114.   
  115.   const int A = -2; const int B = -1; 
  116.   list(node) Al ;
  117.   node_array(int) Class(G); 
  118.   node_array(list_item) Classloc(G);
  119.   list(node) knoten = G.all_nodes();
  120.   forall(v,knoten) {Classloc[v] = Al.push(v);Class[v]=A;}
  121.   list(node) Bl;
  122.   list(node)* Il = new list(node)[G.number_of_nodes()];
  123.   
  124.   label_node(G, L,ord,count,labelled,Al,Bl,Il,Class,Classloc,
  125.              first,second,last,A,B,a,c);
  126.  
  127.   label_node(G, L,ord,count,labelled,Al,Bl,Il,Class,Classloc,
  128.              first,second,last,A,B,b,c);
  129.  
  130.   while (v=Il[1].pop()) 
  131.      label_node(G, L,ord,count,labelled,Al,Bl,Il,Class, Classloc,
  132.                 first, second,last,A,B,v,c);
  133.  
  134.   label_node(G, L,ord,count,labelled,Al,Bl,Il,Class,Classloc,
  135.              first,second,last,A,B,c,c);
  136.  
  137.    //nun berechne ich noch first second und last des Knoten c 
  138.   first[c]=a;
  139.   last[c]=b;
  140.  
  141.   edge e;
  142.   forall_adj_edges(e,c) if (target(e)==a) second[c]=target(G.cyclic_adj_pred(e));
  143.   
  144.  //nun die Folge Pi
  145.   node_array(list_item) Piloc(G);
  146.   Piloc[a] = Pi.push(a);
  147.   Piloc[b] = Pi.append(b);
  148.   forall(v,L) if (v != a && v != b) Piloc[v] = Pi.insert(v,Piloc[second[v]],-1);
  149.  
  150. }//end of compute_labelling 
  151.  
  152. int planar_map::straight_line_embedding(node_array(int)& x, node_array(int)& y)
  153. {
  154.  // computes a straight-line embedding of the planar map into
  155.  // the 2n by n grid. The coordinates of the nodes are returned
  156.  // in the Arrays x and y. Returns the maximal coordinate.
  157.  
  158. list(node) L;
  159. list(node) Pi;
  160. edgelist TL;
  161.  
  162. node v;
  163. edge e;
  164. int maxcoord=0;
  165.  
  166. node_array(int)  ord(*this);
  167. node_array(node) first(*this), second(*this), last(*this);
  168.  
  169. TL = triangulate();
  170.  
  171.  
  172. compute_labelling(*this,L,Pi,ord,first,second,last);
  173. /* computes the ordering of lemma 10 in List L ,the sequence pi
  174.    in list Pi, the function pi^-1(v) in Array ord, and the functions
  175.    first,second,last of lemma 11 in the corresponding Arrays
  176.  */
  177.  
  178. //I now embed the first three nodes
  179.  
  180. v = L.pop();
  181. x[v]=y[v]=0;
  182.  
  183. v=L.pop();
  184. x[v]=2;y[v]=0;
  185.  
  186. v=L.pop();
  187. x[v]=y[v]=1;
  188.  
  189. //I now embed the remaining nodes
  190.  
  191. while (v=L.pop())
  192.  { // I first move the nodes depending on second[v] by one unit
  193.    // and the the nodes depending on last[v] by another unit to the 
  194.    // right, i.e.,
  195.  
  196.  
  197.   //I increase the x-coordinate of all nodes which follow second[v] in 
  198.   //List Pi and precede v in List L,i.e., have a smaller ord value than v
  199.  
  200.   bool seen = false;
  201.   node z;
  202.   forall(z,Pi)
  203.   { if (z==second[v]) seen = true;
  204.     if (seen && (ord[z]<ord[v])) x[z]=x[z]+1;
  205.   }
  206.  
  207.   //I increase the x-coordinate of all nodes which follow last[v] in 
  208.   //List Pi and precede v in List L,i.e., have a smaller ord value than v
  209.  
  210.   seen = false;
  211.   forall(z,Pi)
  212.   { if (z==last[v]) seen = true;
  213.     if (seen && (ord[z]<ord[v])) x[z]=x[z]+1;
  214.   }
  215.  
  216.  
  217.    // I now embed v at the intersection of the line with slope +1
  218.    // through first[v] and the line with slope -1 through last[v]
  219.  
  220.    int x_first_v = x[first[v]];
  221.    int x_last_v =  x[last[v]];
  222.    int y_first_v = y[first[v]];
  223.    int y_last_v =  y[last[v]];
  224.  
  225.    x[v]=(y_last_v - y_first_v + x_first_v + x_last_v)/2;
  226.    y[v]=(x_last_v - x_first_v + y_first_v + y_last_v)/2;
  227.  }
  228.  
  229. // delete triangulation edges
  230.  
  231. forall(e,TL) del_edge(e);
  232.  
  233. forall_nodes(v,*this) maxcoord = Max(maxcoord,Max(x[v],y[v]));
  234. return maxcoord;
  235.  
  236. } //end of straight_embedding
  237.  
  238.  
  239. /*
  240. real planar_map::straight_line_embedding(node_array(real)& x, 
  241.                                          node_array(real)& y)
  242. { node v;
  243.   node_array(int) x0(*this), y0(*this);
  244.  
  245.   real result = straight_line_embedding(x0,y0);
  246.  
  247.   forall_nodes(v,*this) { x[v] = x0[v];
  248.                           y[v] = y0[v]; 
  249.                          }
  250.   return result;
  251. }
  252. */
  253.