_planar.c

数据类型和算法库LEDA 数据类型和算法库LEDA

/*******************************************************************************
+
+  LEDA  3.0
+
+
+  _planar.c
+
+
+  Copyright (c) 1992  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 6600 Saarbruecken, FRG     
+  All rights reserved.
+ 
*******************************************************************************/




/*******************************************************************************
 *
 *                       int PLANAR(graph& G )
 *
 * testet einen zweifach zusammenhaengenden Graphen auf Planaritaet und
 * berechnet die kombinatorische Einbettung des Graphen.Die Implementierung 
 * basiert auf dem Algorithmus aus Mehlhorn, Band 2.
 * Kommentare beziehen sich fast immer auf die entsprechenden Stellen im Buch.
 * Zur Zeit funktioniert das Programm nur, wenn die Eingabe aus der gerichteten
 * Version eines ungerichteten 2-fach zus.haengenden Graphen besteht !!!
 *
 * Andreas Thieltges 
 *
 ******************************************************************************/


#include <LEDA/graph_alg.h>


struct edge_info
{ // edgeinfo verwaltet zur Kante e die Segmentnr, die aktuelle Blocknr
  // und die aktuelle Plazierung der Kante rechts oder links vom Spine
  edge e;
  int seg_nr;
  int block_nr;
  char plaz;

 LEDA_MEMORY(edge_info)
};

typedef edge_info* ed_inf;

void Clear(ed_inf& x) { delete x; }



struct block 
{ // ein Block besteht aus der Liste der rechten und der Liste der linken
  // Befestigungen (Attachments)
 list<int> L, R;

 LEDA_MEMORY(block)
};

typedef block* blptr;


void Clear(blptr& x)  { delete x; }





void swap_plaz( ed_inf& p ) // tauscht die Plaz. von L/R oder umgekehrt
{
 switch( p->plaz )
      {
       case 'L' : p->plaz = 'R'; break;
       case 'R' : p->plaz = 'L'; break;
       case '=' : p->plaz = '!'; break;
       case '!' : p->plaz = '='; break;
      }
 }


// mirror tauscht rekursiv Basisbefestigungen frueher eingebetter
// Segmente

void mirror(list<ed_inf>* segment, int s_nr)
{
int i = 1;
ed_inf x;

   forall( x, segment[s_nr]) 
      if( i++ == 1 )
          swap_plaz( x );
      else 
          if( x->seg_nr > s_nr ) mirror(segment, x->seg_nr);

}




void flipping( list<ed_inf>* segment, int s_nr, int h)
{
  ed_inf x;
   
     forall( x, segment[s_nr])
      { 
        if( x->block_nr == h )
          { swap_plaz( x );
            if( x->seg_nr > s_nr ) mirror(segment, x->seg_nr);
           }
       }

}


void null_block( list<ed_inf>& s, int h)
{
ed_inf x;
   
    forall( x, s)
      if( x->block_nr == h )
           x->block_nr = 0;

}


void upd_block_ctr( list<ed_inf>& s, int h)
{
ed_inf x;
   
    forall( x, s)
      if( x->block_nr > h )
           x->block_nr = h;

}




void init_segm( list<ed_inf>* segment, int cur_nr, edge e)
{
ed_inf neu = new edge_info;

   neu->e = e;
   neu->block_nr = 0;
   neu->seg_nr = cur_nr;
   neu->plaz = 'L';
   segment[cur_nr].push(neu);
}


void add_edge( list<ed_inf>& s, int s_nr, int h, edge e)
{
ed_inf neu = new edge_info;

   neu->e = e;
   neu->block_nr = h;
   neu->seg_nr = s_nr;
   neu->plaz = '=';

   s.append(neu);
}




// max_L_R berechnet die maximale Befestigung des Blockstack-
// eintrags top

int max_L_R(blptr& top)
{
int lmax, rmax;

 lmax = rmax = 0;

 if( !(top->L).empty() )
    lmax = (top->L).head();
 if(!(top->R).empty() )
    rmax = (top->R).head();

 return  Max(lmax,rmax);
}



// Linke und Rechte Attachment-Liste des Blockstackelements werden vertauscht
void swap_at(blptr& top)
{
list<int> tmp = top->L;
 
      if( ! top->R.empty() )
         top->L = top->R;
      else top->L.clear();
      top->R = tmp;
}



/* Test, ob der Graph noch bipartit, analog zum Buch. 
k: Hoehe des Blockstacks + 1, 
zurueckgegeben wird die Anzahl zu verschraenkender Blocks, falls G bipartit,
sonst -1
*/


 
int bipartite_test(list<blptr>& atblock, list<int>& A, int k,
                    list<ed_inf>* segment, int seg_nr)
{
int min_att;
list_item top = atblock.first(); // top zeigt auf oberstes Kellerelement

   min_att = A.tail(); // min. Befestigung der Liste A steht am Ende, da
                       // A absteigend sortiert
   while( top != nil && max_L_R(atblock[top]) > min_att )
    {
     if( !atblock[top]->L.empty() && atblock[top]->L.head() > min_att )
        { // links gibt es im Stack eine Befestigung > min_att
          // printf("vor swap %d %d %d\n",atblock[top]->L.head(),k,seg_nr);
           flipping(segment, seg_nr, k-1 ); // klappen von Segmenten
           swap_at( atblock[top] ); // tausche Att.listen von top
           if( !atblock[top]->L.empty() && atblock[top]->L.head() > min_att )
                 return -1; // Graph ist nicht planar
        }
     k--;
     top = atblock.succ(top);
    }
 return k-1;
}




void update_block_stack(list<blptr>& atblock, int h,int dist,
                        list<int>& A)
{
int i;
list<int> ALB, ARB;
list_item j;
blptr neu;

  for(i=h; i > dist; i--)
    {
      j = atblock.first();
      ALB.conc( atblock[j]->L);
      ARB.conc(atblock[j]->R);

     atblock.pop();
    }
  neu = new  block;  
  A.conc( ALB );
  neu->L = A;
  neu->R = ARB;
  atblock.push(neu); 

}

void remove_node_below(int j,int sp_start,int wr,
                       list<blptr>& atblock, list<ed_inf>& s)
{
int h;
 if( j == sp_start)
     j = wr;
 else --j;
 
 list_item top = atblock.first();

 while(  top != nil && ( !atblock[top]->L.empty() && atblock[top]->L.head() == j 
         ||    !atblock[top]->R.empty() && atblock[top]->R.head() == j ) )
   {
    if( !atblock[top]->L.empty() && atblock[top]->L.head() == j)
        atblock[top]->L.pop();
      
    if( !atblock[top]->R.empty() && atblock[top]->R.head() == j)
        atblock[top]->R.pop();

    if( atblock[top]->L.empty() && atblock[top]->R.empty() )
       {
        h = atblock.length();
        atblock.pop();
        top=atblock.first();
        null_block( s, h);
       }
        
   }

}


int strongly_planar(list<blptr>& atblock, int w0, list<int>& A,
                    list<ed_inf>* segment, int seg_nr)
{
int h;
 A.clear();
 
 h = atblock.length();
 while ( !atblock.empty())
  {
   list_item top = atblock.first();
   if(  !atblock[top]->R.empty() && atblock[top]->R.head() > w0 )
     {
      swap_at( atblock[top] );
      flipping(segment, seg_nr, h);
      if( !atblock[top]->R.empty() && atblock[top]->R.head() > w0 )
           return false;
     }
   
    A.conc( atblock[top]->L );

    A.conc( atblock[top]->R );
 
    atblock.pop();
    h--;
  }
    A.append(w0);
    return true;

}







list<int> plantest(node* Graph_order, node_array<int>& Dfsnr, edge e,
                   list<ed_inf>* segment, int& seg_nr)
{

node v, w, spine_node;
edge seg_start;
list<int> A;
list<blptr> atblock;
int i,j, wr = 0, w0, h, dist, sp_start, sp_end,
    start_nr, cur_nr;

  spine_node = target(e);  // target(e) ist 1. Knoten des Spines zu S(e) 

  sp_start = Dfsnr[spine_node];

 // wr ist der Knoten, an dem S(e) den Stamm verlaesst
     wr = Dfsnr[source(e)];

  // finde den Spine: laufe ueber T-Kanten bis zur 1. B-Kante

  forall_adj_edges(e,spine_node)
     if( Dfsnr[target(e)] > Dfsnr[spine_node] ) // e ist T-Kante 
        spine_node = target(e);
     else break;

  sp_end = Dfsnr[source(e)]; // e ist die Basiskante von S(e)
  w0 = Dfsnr[target(e)];     // w0 ist die Basisbefestigung am Stamm
  cur_nr = seg_nr;
   init_segm( segment, cur_nr, e);
 // printf("wr %d sp_st %d end %d w0 %d\n",wr, sp_start,sp_end,w0); 

  for(j = sp_end; j >= sp_start; j--)
   {
     v = Graph_order[j]; // v ist der Knoten mit dfsnum j
      
     i = 1;
     forall_adj_edges(seg_start,v) // betr. alle v verlassenden Kanten ausser
                                   // der ersten Kante 
      {
       start_nr = cur_nr;
       if( i++ > 1)
       {
        w = target(seg_start);
         // printf(" next edge : %d --> %d\n",Dfsnr[v],Dfsnr[w]);
        if( Dfsnr[w] > Dfsnr[v] )  // Segment startet mit T-Kante 
         { // teste S(seg_start)
           start_nr = ++seg_nr;
           A = plantest(Graph_order, Dfsnr, seg_start, segment, seg_nr);
           if( A.empty() )
               return A;  // wenn A leer: nicht planar
         }
        else
          { A.clear();
            A.append(Dfsnr[w]); // Segment besteht nur aus einer B-Kante 
           }

        h = atblock.length(); // Anzahl der Eintraege im Blockstack
        // teste, ob Graph noch bipartit, dist liefert Anzahl der zu
        // verschraenkenden Bloecke

        if((dist=bipartite_test(atblock,A,h+1,segment,cur_nr)) == -1 )
         {  A.clear();
            return A; 
         }
     /* aktualisiere die Liste der Bloecke, evtl. werden Bloecke mit
        der Liste A zu einem neuen Block verschmolzen */
        update_block_stack(atblock, h, dist, A);
        h = atblock.length(); // Anzahl der Eintraege im Blockstack
        upd_block_ctr(segment[cur_nr], h);
        add_edge(segment[cur_nr],start_nr,h,seg_start);
       }
      }
    /* alle wj verlassenden Kanten sind betrachtet, entferne nun
       alle Befestigungen parent( wj ) */
    remove_node_below(j,sp_start, wr, atblock,segment[cur_nr]);
   }

   /* teste, ob S(e) stark planar */
  if( ! strongly_planar(atblock, w0, A,segment,cur_nr))
           A.clear();

null_block(segment[cur_nr],1);
// forall(k,A)
  // printf("%d ",k);

  return A;  // liefere Liste der Attachments ab

}








int edge_cost(int vnum, int wnum, int l1, int l2)
{
  if( wnum < vnum )
     return 2*wnum;
  else if ( l2 >= vnum)
        return 2*l1;
       else return (2*l1 + 1);
}

void bucket_s ( graph& G, 
                const node_array<int>& Dfsnr,
                const node_array<int>& low1, 
                const node_array<int>& low2)
{
 node v,w;
 edge e;
 edge_array<int> cost(G);

 forall_edges(e,G)
 { v = source(e);
   w = target(e);
   cost[e] = edge_cost(Dfsnr[v],Dfsnr[w],low1[w],low2[w]);
  }

  G.sort_edges(cost);
    
}







void low(list<edge>& DEL, node v, node prep,
         int& cur_nr, node_array<int>& reached,node_array<int>& Dfsnr,