home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _planar.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  16.9 KB  |  828 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _planar.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. *  PLANAR  (planarity test)                                                    *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24. #include <LEDA/graph_alg.h>
  25. #include <LEDA/node_set.h>
  26. #include <LEDA/array.h>
  27.  
  28. declare(list,int)
  29.  
  30. struct edge_info
  31. {
  32.  edge e;
  33.  char plaz;
  34.  int  seg_nr;
  35.  int  block_nr;
  36.  
  37. OPERATOR_NEW(4)
  38. OPERATOR_DEL(4)
  39.  
  40. };
  41.  
  42.  
  43. struct block 
  44. {
  45.  list(int) L;
  46.  list(int) R;
  47.  
  48. OPERATOR_NEW(10)
  49. OPERATOR_DEL(10)
  50.  
  51. };
  52.  
  53.  
  54. typedef edge_info* ed_inf;
  55. typedef block* blptr;
  56.  
  57. declare(list,ed_inf)
  58. declare(list,blptr)
  59.  
  60. typedef list(ed_inf)* lsthead;
  61.  
  62. declare(array,lsthead)
  63. declare(array,node)
  64.  
  65. void swap_plaz( ed_inf& p )
  66. {
  67.  switch( p->plaz )
  68.       {
  69.        case 'L' : p->plaz = 'R'; break;
  70.        case 'R' : p->plaz = 'L'; break;
  71.        case '=' : p->plaz = '!'; break;
  72.        case '!' : p->plaz = '='; break;
  73.       }
  74. }
  75.  
  76.  
  77.  
  78. void mirror( array(lsthead)& segment, int s_nr)
  79. {
  80. int i = 1;
  81. ed_inf x;
  82.  
  83.  
  84.    forall( x, *(segment[s_nr])) 
  85.       if( i++ == 1 )
  86.          swap_plaz( x );
  87.       else if( x->seg_nr > s_nr )
  88.              mirror(segment, x->seg_nr);
  89.  
  90. }
  91.  
  92.  
  93.  
  94.  
  95. void flipping( array(lsthead)& segment, int s_nr, int h)
  96. {
  97. ed_inf x;
  98.    
  99.      forall( x, *(segment[s_nr]))
  100.       { 
  101.         if( x->block_nr == h )
  102.           {
  103.            swap_plaz( x );
  104.            if( x->seg_nr > s_nr )
  105.              mirror(segment, x->seg_nr );
  106.           }
  107.        }
  108.  
  109. }
  110.  
  111.  
  112. void null_block( lsthead& s, int h)
  113. {
  114. ed_inf x;
  115.    
  116.     forall( x, *s)
  117.       if( x->block_nr == h )
  118.            x->block_nr = 0;
  119.  
  120. }
  121.  
  122.  
  123. void upd_block_ctr( lsthead& s, int h)
  124. {
  125. ed_inf x;
  126.    
  127.     forall( x, *s)
  128.       if( x->block_nr > h )
  129.            x->block_nr = h;
  130.  
  131. }
  132.  
  133.  
  134.  
  135.  
  136. void init_segm( array(lsthead)& segment, int cur_nr, edge e)
  137. {
  138. ed_inf neu = new edge_info;
  139.  
  140.    neu->e = e;
  141.    neu->block_nr = 0;
  142.    neu->seg_nr = cur_nr;
  143.    neu->plaz = 'L';
  144.  
  145.    (*segment[cur_nr]).push(neu);
  146. }
  147.  
  148. void add_edge( lsthead& s, int s_nr, int h, edge e)
  149. {
  150. ed_inf neu = new edge_info;
  151.  
  152.    neu->e = e;
  153.    neu->block_nr = h;
  154.    neu->seg_nr = s_nr;
  155.    neu->plaz = '=';
  156.  
  157.    (*s).append(neu);
  158. }
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165. int max_L_R(blptr& top)
  166. {
  167. int lmax, rmax;
  168.  
  169.  lmax = rmax = 0;
  170.  
  171.  if( !(top->L).empty() )
  172.     lmax = (top->L).head();
  173.  if(!(top->R).empty() )
  174.     rmax = (top->R).head();
  175.  
  176.  return( Max(lmax,rmax) );
  177. }
  178.  
  179.  
  180.  
  181.  
  182. void swap_at(blptr& top)
  183. {
  184. list(int) tmp = top->L;
  185.  
  186.       top->L = top->R;
  187.       top->R = tmp;
  188. }
  189.  
  190.  
  191. int bipartite_test(list(blptr)& atblock, list(int)& A, int k,
  192.                     array(lsthead)& segment, int seg_nr)
  193. {
  194. int min_att;
  195. list_item top = atblock.first();
  196.  
  197.    min_att = A.tail();
  198.    while( top && max_L_R(atblock[top]) > min_att )
  199.     {
  200.      if( !atblock[top]->L.empty() && atblock[top]->L.head() > min_att )
  201.         {
  202.          //printf("vor swap %d %d %d\n",atblock[top]->L.head(),k,seg_nr);
  203.            flipping(segment, seg_nr, k-1 );
  204.            swap_at( atblock[top] );
  205.            if( !atblock[top]->L.empty() && atblock[top]->L.head() > min_att )
  206.                  return( -1 );
  207.         }
  208.      k--;
  209.      top = atblock.succ(top);
  210.     }
  211.  return( k-1 );
  212. }
  213.  
  214.  
  215.  
  216.  
  217. void update_block_stack(list(blptr)& atblock, int h,int dist,
  218.                         list(int)& A)
  219. {
  220.  
  221. int i;
  222.  
  223. list(int) ALB, ARB;
  224.  
  225.   for(i=h; i > dist; i--)
  226.    { list_item j = atblock.first();
  227.      ALB = ALB + ((atblock[j])->L);
  228.      ARB = ARB + ((atblock[j])->R);
  229.      atblock.pop();
  230.     }
  231.   blptr neu = new  block;  
  232.   neu->L = (A + ALB);
  233.   neu->R = ARB;
  234.   atblock.push(neu);
  235. }
  236.  
  237. void remove_node_below(int j,int sp_start,int wr,
  238.                        list(blptr)& atblock, lsthead& s)
  239. {
  240. int h;
  241.  if( j == sp_start)
  242.      j = wr;
  243.  else --j;
  244.  
  245.  list_item top = atblock.first();
  246.  
  247.  while(  top && ( !(atblock[top]->L).empty() && atblock[top]->L.head() == j 
  248.          ||    !(atblock[top]->R).empty() && atblock[top]->R.head() == j ) )
  249.    {
  250.     if( !(atblock[top]->L).empty() && atblock[top]->L.head() == j)
  251.         atblock[top]->L.pop();
  252.       
  253.     if( !(atblock[top]->R).empty() && atblock[top]->R.head() == j)
  254.         atblock[top]->R.pop();
  255.  
  256.     if( atblock[top]->L.empty() && atblock[top]->R.empty() )
  257.        {
  258.         h = atblock.length();
  259.         atblock.pop();
  260.         top = atblock.first();
  261.         null_block( s, h);
  262.        }
  263.         
  264.    }
  265.  
  266. }
  267.  
  268.  
  269. int strongly_planar(list(blptr)& atblock, int w0, list(int)& A,
  270.                     array(lsthead)& segment, int seg_nr)
  271. {
  272. int h;
  273.  A.clear();
  274.  
  275.  h = atblock.length();
  276.  while ( !atblock.empty())
  277.   {
  278.    list_item top = atblock.first();
  279.    if(  !atblock[top]->R.empty() && atblock[top]->R.head() > w0 )
  280.      {
  281.       swap_at( atblock[top] );
  282.       flipping(segment, seg_nr, h);
  283.       if( !atblock[top]->R.empty() && atblock[top]->R.head() > w0 )
  284.            return( false );
  285.      }
  286.    
  287.     A = A + atblock[top]->L + atblock[top]->R;
  288.     atblock.pop();
  289.     h--;
  290.   }
  291.  
  292.     A += w0;
  293.     return( true );
  294.  
  295. }
  296.  
  297.  
  298.  
  299.  
  300.  
  301.  
  302.  
  303. list(int) plantest(array(node)& Graph_order, 
  304.                    node_array(int)& Dfsnr, edge e,
  305.                    array(lsthead)& segment, int& seg_nr)
  306. {
  307. int i,j, wr = 0, w0, h, dist, sp_start, sp_end, start_nr, cur_nr;
  308. node v, w, spine_node;
  309. edge seg_start;
  310.  
  311. list(int) A;
  312. list(blptr) atblock;
  313.  
  314.   spine_node = target(e);  // target(e) ist 1. Knoten des Spines zu S(e) 
  315.  
  316.   sp_start = Dfsnr[spine_node];
  317.  
  318.   if( sp_start > 1 )  // wr ist der Knoten, an dem S(e) den Stamm verlaesst
  319.      wr = Dfsnr[source(e)];
  320.  
  321.   // finde den Spine: laufe ueber T-Kanten bis zur 1. B-Kante
  322.  
  323.   forall_adj_edges(e,spine_node)
  324.      if( Dfsnr[target(e)] > Dfsnr[spine_node] ) // e ist T-Kante 
  325.         spine_node = target(e);
  326.      else break;
  327.  
  328.   sp_end = Dfsnr[source(e)]; // e ist die Basiskante von S(e)
  329.   w0 = Dfsnr[target(e)];     // w0 ist die Basisbefestigung am Stamm
  330.   cur_nr = seg_nr;
  331.    init_segm( segment, cur_nr, e);
  332.  
  333.  
  334.   for(j = sp_end; j >= sp_start; j--)
  335.    {
  336.      v = Graph_order[j]; // v ist der Knoten mit dfsnum j
  337.      
  338.      i = 1;
  339.      forall_adj_edges(seg_start,v) // betr. alle v verlassenden Kanten ausser
  340.                                    // der ersten Kante 
  341.       {
  342.        start_nr = cur_nr;
  343.        if( i++ > 1)
  344.        {
  345.         w = target(seg_start);
  346.  
  347.         if( Dfsnr[w] > Dfsnr[v] )  // Segment startet mit T-Kante 
  348.          { // teste S(seg_start)
  349.            start_nr = ++seg_nr;
  350.  
  351.            A = plantest(Graph_order, Dfsnr, seg_start, segment, seg_nr);
  352.  
  353.            if( A.empty() )
  354.                return( A );  // wenn A leer: nicht planar
  355.          }
  356.         else
  357.             A = Dfsnr[w]; // Segment besteht nur aus einer B-Kante 
  358.  
  359.         h = atblock.length(); // Anzahl der Eintraege im Blockstack
  360.         // teste, ob Graph noch bipartit, dist liefert Anzahl der zu
  361.         // verschraenkenden Bloecke
  362.  
  363.         if((dist=bipartite_test(atblock,A,h+1,segment,cur_nr)) == -1 )
  364.         { A.clear();
  365.           return( A ); 
  366.          }
  367.  
  368.      /* aktualisiere die Liste der Bloecke, evtl. werden Bloecke mit
  369.         der Liste A zu einem neuen Block verschmolzen */
  370.  
  371.         update_block_stack(atblock, h, dist, A);
  372.  
  373.         h = atblock.length(); // Anzahl der Eintraege im Blockstack
  374.  
  375.         upd_block_ctr(segment[cur_nr], h);
  376.  
  377.         add_edge(segment[cur_nr],start_nr,h,seg_start);
  378.        }
  379.       }
  380.     /* alle wj verlassenden Kanten sind betrachtet, entferne nun
  381.        alle Befestigungen parent( wj ) */
  382.  
  383.     remove_node_below(j,sp_start, wr, atblock,segment[cur_nr]);
  384.    }
  385.  
  386.    /* teste, ob S(e) stark planar */
  387.   if( ! strongly_planar(atblock, w0, A,segment,cur_nr))
  388.            A.clear();
  389.  
  390. null_block(segment[cur_nr],1);
  391.  
  392. //forall(k,A)
  393.   //printf("%d ",k);
  394.  //getchar();
  395.   return ( A );  // liefere Liste der Attachments ab
  396.  
  397. }
  398.  
  399.  
  400.  
  401.  
  402.  
  403.  
  404.  
  405.  
  406. int edge_cost(int vnum, int wnum, int l1, int l2)
  407. {
  408.   if( wnum < vnum )
  409.      return( 2*wnum );
  410.   else if ( l2 >= vnum)
  411.         return( 2*l1 );
  412.        else return ( 2*l1 + 1 );
  413. }
  414.  
  415. void bucket_s ( graph& G, int node_anz,
  416.                 node_array(int)& Dfsnr,
  417.                 node_array(int)& low1, 
  418.                 node_array(int)& low2 )
  419. {
  420.  node v,w;
  421. list(edge)* bucket = new list(edge) [2*node_anz + 1];
  422.  edge e;
  423.  int j, cost_ind;
  424.  
  425.  forall_nodes(v,G)
  426.   {
  427.    forall_adj_edges(e,v)
  428.     {
  429.       w = target(e);
  430.       cost_ind = edge_cost(Dfsnr[v],Dfsnr[w],low1[w],low2[w]);
  431.       bucket[cost_ind].push(e);
  432.     }
  433.   }
  434.  G.del_all_edges();
  435.  for(j=1; j <= 2*node_anz; j++)
  436.    forall(e,bucket[j])
  437.     {
  438.      v = source(e);
  439.      w = target(e);
  440.      G.new_edge(v,w,0);
  441.     }
  442.  
  443. }
  444.  
  445.  
  446.  
  447.  
  448.  
  449.  
  450.  
  451.  
  452.  
  453.  
  454. void low(list(edge)& DEL, node v, node prep,
  455.          int& cur_nr, node_set& reached,node_array(int)& Dfsnr,
  456.          node_array(int)& low1, node_array(int)& low2)
  457. {
  458. node w;
  459. edge e;
  460. int tcan1, tcan2, bcan1, bcan2;
  461.  
  462.   Dfsnr[v] = ++ cur_nr;
  463.   tcan1 = tcan2 = bcan1 = bcan2 = Dfsnr[v];
  464.   reached.insert(v);
  465.   forall_adj_edges(e,v)
  466.     {
  467.      w = target(e);
  468.      if( !reached.member(w) )
  469.       {
  470.        low(DEL,w,v,cur_nr,reached,Dfsnr,low1,low2);
  471.        if( low1[w] < tcan1 )
  472.         {
  473.          tcan2 = tcan1;
  474.          tcan1 = low1[w];
  475.         }
  476.        else if( low1[w] < tcan2 )
  477.               tcan2 = low1[w];
  478.       }
  479.      else if(( Dfsnr[w] >= Dfsnr[v])  || w == prep ) 
  480.                DEL.append(e) ; 
  481.           else if( Dfsnr[w] < bcan1 )
  482.                  { bcan2=bcan1;
  483.                    bcan1 = Dfsnr[w];
  484.                  }
  485.                else if( Dfsnr[w] < bcan2)
  486.                      bcan2 = Dfsnr[w];
  487.      }
  488.  
  489.  
  490.   low1[v] = Min(tcan1,bcan1);
  491.   if( tcan1 == bcan1)
  492.       low2[v] = Min(tcan2,bcan2);
  493.   else if ( tcan1 < bcan1)
  494.          low2[v] = Min(bcan1,tcan2);
  495.        else low2[v] = Min(tcan1,bcan2);
  496.  
  497. }
  498.  
  499.  
  500. void lowstart(graph& G,node_array(int)& Dfsnr,node_array(int)& low1,
  501.           node_array(int)& low2)
  502. {
  503. node v;
  504. node_set reached(G);
  505. int cur_nr = 0;
  506. list(edge) DEL;
  507. edge e;
  508.  
  509. G.reset(); 
  510. forall_nodes(v,G)
  511.   {
  512.     if( !reached.member(v) )
  513.       low(DEL,v,v,cur_nr,reached,Dfsnr,low1,low2);
  514.   }
  515. G.reset();
  516.     forall(e,DEL)
  517.         G.del_edge(e);
  518. }
  519.  
  520.  
  521. void dfs( node v, 
  522.          int& cur_nr, node_set& reached,node_array(int)& Dfsnr)
  523. {
  524. node w;
  525.  
  526.   Dfsnr[v] = ++ cur_nr;
  527.   reached.insert(v);
  528.   forall_adj_nodes(w,v)
  529.      if( !reached.member(w) )
  530.        dfs(w,cur_nr,reached,Dfsnr);
  531.  
  532. }
  533.  
  534. void dfsstart(graph& G,node_array(int)& Dfsnr)
  535. {
  536. node v;
  537. node_set reached(G);
  538. int cur_nr = 0;
  539.  
  540. G.reset(); 
  541. forall_nodes(v,G)
  542.     if( !reached.member(v) )
  543.       dfs(v,cur_nr,reached,Dfsnr);
  544. G.reset();
  545. }
  546.  
  547.  
  548.  
  549. void cycl_embedding(graph& G,graph& Comb_Gr, array(node)& Comb_ord, array(node)& Graph_ord,
  550.                     node_array(int)& Dfsnr, node_array(int)& Comb_D_nr,
  551.                     edge_array(int)& alpha, edge e, edge& grenze)
  552. {
  553. node v, w, spine_node;
  554. edge active, x, seg_start, fst, Lcur, Rcur;
  555. list(edge) Comb_List, Gr_List;
  556. int i, j, k, wr, w0, sp_start, sp_end, pos;
  557.  
  558. if( source(e) != Graph_ord[0] )
  559.   wr = Dfsnr[source(e)];
  560. else wr = 0;
  561.  
  562. sp_start = Dfsnr[target(e)];
  563. pos = alpha[e];
  564. spine_node = target(e);
  565.  
  566. if( wr < sp_start )
  567. {
  568.   forall_adj_edges(e,spine_node)
  569.      if( Dfsnr[target(e)] > Dfsnr[spine_node] ) // e ist T-Kante 
  570.         spine_node = target(e);
  571.      else break;
  572. }  
  573.  
  574.   sp_end = Dfsnr[source(e)]; // e ist die Basiskante von S(e)
  575.   w0 = Dfsnr[target(e)];     // w0 ist die Basisbefestigung am Stamm
  576.  
  577. //printf(" wr %d start %d end %d w0 %d\n",wr,sp_start,sp_end,w0);
  578.  
  579.   for(i= sp_start; i > wr && i < sp_end; i++)
  580.     {
  581.      v = Comb_ord[i];
  582.      if( i > 1 )
  583.       {
  584.         if( i == sp_start )
  585.          w = Comb_ord[wr];
  586.         else w = Comb_ord[i-1];
  587.  
  588.         Comb_Gr.new_edge(v,w);
  589.       }
  590.  
  591.      Comb_Gr.new_edge(v,Comb_ord[i+1]);
  592.     }
  593.  
  594. //Comb_Gr.print();
  595. //getchar();
  596.    if( wr < sp_start )
  597.     {
  598.      if(sp_end == sp_start)
  599.        w = Comb_ord[wr];
  600.      else
  601.        w = Comb_ord[sp_end -1];
  602.  
  603.      Comb_Gr.new_edge(Comb_ord[sp_end], w);
  604.  
  605.      if( wr > 0 )
  606.      {
  607.         v = Comb_ord[wr];
  608.         if( pos == 'L')
  609.           {
  610.             fst = Comb_Gr.first_adj_edge(v);
  611.              Comb_Gr.new_edge(fst,Comb_ord[sp_start],0,after);
  612.           }
  613.         else Comb_Gr.new_edge(v,Comb_ord[sp_start]);
  614.      }
  615.    }
  616.  
  617.  
  618.      v = Comb_ord[sp_end];
  619.      if( pos == 'L')
  620.        {
  621.     fst = Comb_Gr.first_adj_edge(v);
  622.     Comb_Gr.new_edge(fst,Comb_ord[w0],0,after);
  623.        }
  624.      else Comb_Gr.new_edge(v,Comb_ord[w0]);
  625. //Comb_Gr.print();
  626. //getchar();
  627.        v = Comb_ord[w0];
  628.        Comb_List = Comb_Gr.adj_edges(v);
  629.  
  630.      if( wr > 0 )
  631.       {
  632.        w = Graph_ord[w0];
  633.        Gr_List = G.adj_edges(w);
  634.  
  635. //printf(" sg %d tg %d\n",Comb_D_nr[source(grenze)],Comb_D_nr[target(grenze)]);
  636.        k = 0;
  637.        forall(x, Gr_List)
  638.     if( Dfsnr[target(x)] > k && Dfsnr[target(x)] <= wr)
  639.           {  active = x; 
  640.                  k = Dfsnr[target(x)]; 
  641.               }
  642.        forall(x,Comb_List)
  643.          if(Comb_D_nr[target(x)] == Dfsnr[target(active)])
  644.           break;
  645.        active = x;
  646.       }
  647.      else active = Comb_List.head();
  648.  
  649. //printf(" sa %d ta %d\n",Comb_D_nr[source(active)],Comb_D_nr[target(active)]);
  650.      if( w0 != Comb_D_nr[source(grenze)] )
  651.        {
  652.         if( pos == 'L' )
  653.              x = Comb_Gr.new_edge(active,Comb_ord[sp_end],0,before);
  654.         else
  655.              x = Comb_Gr.new_edge(active,Comb_ord[sp_end],0,after);
  656.        }
  657.       else if ( pos == 'R' )
  658.              x = Comb_Gr.new_edge(grenze,Comb_ord[sp_end],0,before);
  659.            else
  660.                 x = Comb_Gr.new_edge(grenze,Comb_ord[sp_end],0,after);
  661.  
  662.       Lcur = Rcur = x;
  663.  
  664.  
  665.       if( wr < sp_start)
  666.          for(j = sp_end; j >= sp_start; j--)
  667.           {
  668.             v = Graph_ord[j];
  669.             i = 1;
  670.             forall_adj_edges(seg_start,v)
  671.               if( i++ > 1)
  672.                {
  673.                  if( alpha[seg_start] == 'L' ) 
  674.                   cycl_embedding(G,Comb_Gr,Comb_ord,Graph_ord,Dfsnr,Comb_D_nr,alpha,seg_start,Lcur);
  675.                  else
  676.                   cycl_embedding(G,Comb_Gr,Comb_ord,Graph_ord,Dfsnr,Comb_D_nr,alpha,seg_start,Rcur);
  677.                }
  678.            }
  679.  
  680.          if( pos == 'R' && Comb_D_nr[source(Rcur)] <= Comb_D_nr[source(grenze)] )
  681.                  grenze = Rcur;
  682.          else
  683.              if( pos == 'L' && Comb_D_nr[source(Lcur)] <= Comb_D_nr[source(grenze)] )
  684.                  grenze = Lcur;
  685.  
  686.  
  687. }   
  688.  
  689. /*
  690.   planar( G, Comb) testet den Graphen G auf Planaritaet und berechnet
  691.   die kombinatorische Einbettung von G. Der Graph mit den zyklischen
  692.   Adjazenzlisten wird in Comb zurueckgeliefert.
  693.   Eingabe G : gerichtete Version eines zweifach  zusammenhaengenden
  694.               ungerichteten Graphen.
  695.   
  696.   planar() liefert true, falls G planar, sonst false
  697. */
  698.  
  699.  
  700.  
  701. int PLANAR( graph& G)
  702. {
  703.  
  704.   error_handler(0,"PLANAR: sorry, not implemented in this version"); 
  705.   return false;
  706.  
  707.  
  708. int i, ed, n=0, seg_num = 0;
  709. char basis;
  710. list(int) A;
  711. node v, w, aux;
  712. edge e, add_ed, grenze;
  713. ed_inf x;
  714.  
  715. graph Comb_Gr;
  716.  
  717. /*
  718. G.insert_reverse_edges();
  719. eliminate_parallel_edges(G);
  720. */
  721.  
  722. node_array(int) Dfsnr(G),
  723.                 low1(G),
  724.                 low2(G);
  725.  
  726.  
  727. lowstart(G,Dfsnr,low1,low2);
  728.  
  729. n = G.number_of_nodes();
  730. ed = G.number_of_edges();
  731. if( ed > 3*n - 6 )
  732.   { //printf(" no of edges : %d  > %d (more than 3*n - 6 edges)\n",ed,3*n - 6);
  733.     return false;
  734.   }
  735.  
  736. G.reset();
  737. bucket_s(G,n,Dfsnr,low1,low2);
  738.  
  739. dfsstart(G,Dfsnr);
  740.  
  741. w = G.first_node();
  742. aux = G.new_node();
  743. add_ed = G.new_edge(aux,w);
  744.  
  745.  
  746. n++;
  747. array(lsthead) segment(n);
  748. for(i =0; i < n; i++)
  749.    segment[i] = new list(ed_inf);
  750.  
  751.  
  752. array(node) Graph_order(0,n);
  753. edge_array(int) alpha(G);
  754. alpha[add_ed] = 'L';
  755.  
  756.  
  757. forall_nodes(w,G)    
  758.   if (w != aux) 
  759.     Graph_order[Dfsnr[w]] = w;
  760.   else Graph_order[0] = aux;
  761.  
  762. A = plantest(Graph_order, Dfsnr, add_ed, segment, seg_num);
  763.  
  764. if( A.empty() )
  765.     return false;
  766.  
  767. for(i=0; i <= seg_num ; i++)
  768.     {
  769.       x = (*segment[i]).head();
  770.       basis = x->plaz;
  771.       forall(x, (*segment[i]) )
  772.          {
  773.            e = x->e;
  774.           if( basis == 'L' )
  775.              {
  776.               if ( x->plaz == 'L' || x->plaz == '=')
  777.                   alpha[e] = 'L';
  778.               else if( x->plaz == '!')
  779.                   alpha[e] = 'R';
  780.              }
  781.            else
  782.                if(x->plaz == 'R' || x->plaz == '=')
  783.                         alpha[e] = 'R';
  784.                else alpha[e] = 'L';
  785.          }
  786.      } 
  787.  
  788. list(node) G_Lst, Comb_Lst;
  789.  
  790. Comb_Gr = G;
  791. n = Comb_Gr.number_of_nodes();
  792. node_array(int) Comb_D_nr(Comb_Gr);
  793. array(node) Comb_ord(0,n);
  794.  
  795. G_Lst = G.all_nodes();
  796. Comb_Lst = Comb_Gr.all_nodes();
  797. list_item topg = G_Lst.first();
  798. list_item topn = Comb_Lst.first();
  799. while ( topg != G_Lst.last())
  800. { 
  801.   Comb_D_nr[Comb_Lst[topn]] = Dfsnr[G_Lst[topg]];
  802.   topg = G_Lst.succ(topg);
  803.   topn = Comb_Lst.succ(topn);
  804. }
  805. aux = Comb_Lst[topn];
  806.  
  807. forall_nodes(w,Comb_Gr)
  808.   if( w != aux )
  809.      Comb_ord[Comb_D_nr[w]] = w;
  810.   else Comb_ord[0] = aux;
  811.  
  812.  
  813.  
  814. v = Comb_ord[2];
  815. grenze = Comb_Gr.first_adj_edge(v);
  816.  
  817. Comb_Gr.del_all_edges();
  818.  
  819.  cycl_embedding(G,Comb_Gr,Comb_ord,Graph_order,Dfsnr,Comb_D_nr,alpha,add_ed,grenze);
  820.  
  821.  Comb_Gr.del_node( aux );
  822.  
  823. G = Comb_Gr;
  824.  
  825. return true;
  826.  
  827. }
  828.