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