_planar.c

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

         node_array<int>& low1, node_array<int>& low2, node_array<int>& father)
{
node w;
edge e;
int tcan1, tcan2, bcan1, bcan2, vnum;

  Dfsnr[v] = ++ cur_nr;
  tcan1 = tcan2 = bcan1 = bcan2 = vnum = Dfsnr[v];
  reached[v] = true;
  forall_adj_edges(e,v)
    {
     w = target(e);
     if( !reached[w] )
      {
       father[w] = vnum;
       low(DEL,w,v,cur_nr,reached,Dfsnr,low1,low2,father);
       if( low1[w] < tcan1 )
        {
         tcan2 = tcan1;
         tcan1 = low1[w];
        }
       else if( low1[w] < tcan2 )
              tcan2 = low1[w];
      }
     else if(( Dfsnr[w] >= Dfsnr[v])  || w == prep ) 
               DEL.append(e) ; 
          else if( Dfsnr[w] < bcan1 )
                 { bcan2=bcan1;
                   bcan1 = Dfsnr[w];
                 }
               else if( Dfsnr[w] < bcan2)
                     bcan2 = Dfsnr[w];
     }


  low1[v] = Min(tcan1,bcan1);
  if( tcan1 == bcan1)
      low2[v] = Min(tcan2,bcan2);
  else if ( tcan1 < bcan1)
         low2[v] = Min(bcan1,tcan2);
       else low2[v] = Min(tcan1,bcan2);

  if( vnum > 2 && low1[v] == father[v] )
      error_handler(1,"PLANAR: graph is not biconnected");


}


void lowstart(graph& G,node_array<int>& Dfsnr,node_array<int>& low1,
          node_array<int>& low2)
{
node v;
node_array<int> reached(G,false);
int cur_nr = 0;
list<edge> DEL;
node_array<int> father(G);
edge e;

G.reset(); 
forall_nodes(v,G)
  {
    if( !reached[v] )
      low(DEL,v,v,cur_nr,reached,Dfsnr,low1,low2,father);
  }
G.reset();
    forall(e,DEL)
    { 
        G.del_edge(e);
    }
}


void dfs( node v, 
         int& cur_nr, node_array<int>& reached,node_array<int>& Dfsnr)
{
node w;
edge e;

  Dfsnr[v] = ++ cur_nr;
  reached[v] = true;
  forall_adj_edges(e,v)
   {
     w = target(e);
     if( !reached[w] )
       dfs(w,cur_nr,reached,Dfsnr);
   }
}

void dfsstart(graph& G,node_array<int>& Dfsnr)
{
node v;
node_array<int> reached(G,false);
int cur_nr = 0;

G.reset(); 
forall_nodes(v,G)
    if( !reached[v] )
      dfs(v,cur_nr,reached,Dfsnr);
G.reset();
}


/* cycl_embedding() berechnet die zykl. Adjazenzlisten des Eingabegraphen
   Or ( Original ). Alle Ad.listen stehen in der Kantenliste cyc_lst.
   Die Kopie des Eingabegraphen Cp enthaelt die wie sie fuer den
   Planaritaetstest benoetigt wird 
*/

void cycl_embedding(list<edge>& cyc_lst, graph& Or, graph& Cp, 
                    node* Or_ord, node* Cp_ord,
                    node_array<int>& Or_dfs, node_array<int>& Cp_dfs,
                    edge_array<int>& alpha, edge e, edge& grenze)
{
node v, w, spine_node,att;
edge x, y,seg_start, Lcur, Rcur;
list<edge> Cp_List, E_List;
list_item i, anf, end;
int j, k, wr, w0, sp_start, sp_end;
char pos;

wr = Cp_dfs[source(e)];

sp_start = Cp_dfs[target(e)];
pos = alpha[e];
spine_node = target(e);

if( wr < sp_start )  // suche Spine in Kopie
{
  forall_adj_edges(e,spine_node)
     if( Cp_dfs[target(e)] > Cp_dfs[spine_node] ) // e ist T-Kante 
        spine_node = target(e);
     else break;
}  

  sp_end = Cp_dfs[source(e)]; // e ist die Basiskante von S(e)
  w0 = Cp_dfs[target(e)];     // w0 ist die Basisbefestigung am Stamm

// printf("cyc: wr %d sp_st %d sp_end %d w0 %d pos %c\n",wr,sp_start,sp_end,w0,pos);
  E_List = Or.adj_edges(Or_ord[wr]);
  forall(x, E_List)
     if( Or_dfs[target( x )] == sp_start) // suche (wr,sp_start) in Original
     break;

  if( wr == 1)  // cyc_lst ist leer
    anf = end = cyc_lst.push(x);
 else 
   forall_list_items(i,cyc_lst) // suche 1.Kante in cyc_lst mit source = wr
        if( Or_dfs[source(cyc_lst[i])] == wr)
          {   anf = end = i; // merke Kante in anf 
              break; 
          }

 att = Cp_ord[w0];  // merke Befestigungsknoten
 if( wr < sp_start && wr > 1)
   {
    if( pos == 'L')  // (wr,sp_start) wird in cyc_lst eingefuegt
        cyc_lst.insert(x,anf,after);
    else
     {
      i = anf;
      for( ; i!=nil  && Or_dfs[source(cyc_lst[i])] == wr; )
           i = cyc_lst.succ(i);

      if( i != nil )
         cyc_lst.insert(x,i,before);
      else cyc_lst.append(x);
     }

   }

 if( wr < sp_start )
  for(j= sp_start; j < sp_end; j++) // alle T-Knoten sp_start.. sp_end
    {
     if( j == sp_start )
         w = Or_ord[wr];
     else w = Or_ord[j-1];

     E_List = Or.adj_edges(Or_ord[j]);
     forall_list_items(i,E_List)
        if( Or_dfs[target(E_List[i])] == Or_dfs[w])
           break;
       
     cyc_lst.append(E_List[i]); // anhaengen von (wj, wj-1)
     w = Or_ord[j+1];
     forall_list_items(i,E_List)
       if( Or_dfs[target(E_List[i])] == Or_dfs[w])
          break;

     cyc_lst.append(E_List[i]);

    }

  if( wr < sp_start )
    {
     E_List = Or.adj_edges( Or_ord[sp_end] );
     if(sp_end == sp_start)
       w = Or_ord[wr];
     else
       w = Or_ord[sp_end -1];
     forall(x,E_List)    // suche (sp_end, sp_end-1)
       if( Or_dfs[target(x)] == Or_dfs[w])
         break;
      
     end = cyc_lst.append(x); // anhaengen von (sp_end,sp_end-1)

     w = Or_ord[w0];
     E_List = Or.adj_edges( Or_ord[sp_end] );
     forall(x,E_List)
        if( Or_dfs[target(x)] == Or_dfs[w])
          break;
    }

  if( pos == 'L' )  // einfuegen von (sp_end, w0)
     cyc_lst.insert(x,end,after);
  else
  {
   i = end;
   for(; i != nil && Or_dfs[source(cyc_lst[i])] == sp_end; )
          i = cyc_lst.succ(i); 
      
   if( i != nil)
      cyc_lst.insert(x,i,before);
   else cyc_lst.append(x);
  }


 w = Or_ord[sp_end];
 E_List = Or.adj_edges(Or_ord[w0]);
 forall(x,E_List)  // suche (w0, sp_end)
  if(Or_dfs[target(x)] == Or_dfs[w])
    break;

 if( w0 != Or_dfs[source(grenze) ])
  {
   if( wr == 1 )
     k = 2;
   else
    {
     Cp_List = Cp.adj_edges( att ); // suche in Kopie die Aktivkante (w0,w1) des Stamms
     k = Cp_dfs[att];
     forall(y, Cp_List)
        if( (j=Cp_dfs[target(y)]) > k && j <= wr )
            k = j;
    }
   
    forall_list_items(i,cyc_lst) // suche "gleiche" Kante auch in Or
       {
         y = cyc_lst[i];
         if( Or_dfs[source(y)] == w0 && Or_dfs[target(y)] == k )
            break;
       }

  
  if( pos == 'L' )  // einfuegen von (w0, sp_end) vor/nach Aktivkante
     cyc_lst.insert(x,i,before);
  else
     cyc_lst.insert(x,i,after);

   }


 else { 
      i = cyc_lst.search(grenze);
      if(pos == 'L') // einfuegen von (w0,sp_end) vor/nach grenze
        cyc_lst.insert(x,i,after);
      else cyc_lst.insert(x,i,before);
      }

 Lcur = Rcur = x; // merke (w0,sp_end)


  if( wr < sp_start) // rek. Durchmusterung analog zum Test
         for(j = sp_end; j >= sp_start; j--)
          {
            v = Cp_ord[j];
            k = 1;
            forall_adj_edges(seg_start,v) // betrachte Kanten aus Cp !!
              if( k++ > 1)
               {
                 if( alpha[seg_start] == 'L' ) 
                  cycl_embedding(cyc_lst,Or,Cp,Or_ord,Cp_ord,Or_dfs,Cp_dfs,alpha,seg_start,Lcur);
                 else
                   cycl_embedding(cyc_lst,Or,Cp,Or_ord,Cp_ord,Or_dfs,Cp_dfs,alpha,seg_start,Rcur);
               }
           }

      // aktualisiere Grenzkante, falls erforderlich
         if( pos == 'R' && Or_dfs[source(Rcur)] <= Or_dfs[source(grenze)] )
                 grenze = Rcur;
         else
             if( pos == 'L' && Or_dfs[source(Lcur)] <= Or_dfs[source(grenze)] )
                 grenze = Lcur;


}   

/*
  Planar(G) testet den Graphen G auf Planaritaet und berechnet
  die kombinatorische Einbettung von G. Der Graph enthaelt am Ende
  die zyklischen
  Adjazenzlisten zu allen Knoten.
  Eingabe G : gerichtete Version eines zweifach  zusammenhaengenden
              ungerichteten Graphen.
  
  Planar() liefert true, falls G planar, sonst false
*/



int PLANAR(graph& Or )
{
int N;
int i, ed, n=0, seg_num = 0;
char basis;
node v, w;
edge e, grenze;
ed_inf x;

list<edge> cyc_lst;
list<int> A;
list_item t;


//insert reverse edges, if not present

list<edge> RE = Or.insert_reverse_edges();

eliminate_parallel_edges(Or);  //not ok, should eliminate only edges from RE


graph G = Or;  // teste Planaritaet auf einer Kopie der Eingabe

edge_array<edge> Rev(G);

node_array<int> Or_dfs(Or), 
                Dfsnr(G),
                low1(G),
                low2(G);

if(! compute_correspondence(G, Rev) )
 error_handler(1,"PLANAR: graph must be directed version of undirected graph");

lowstart(G,Dfsnr,low1,low2); // berechne low1 und low2 aller Knoten

N = G.number_of_nodes();
ed = G.number_of_edges();
// printf("n: %d, e: %d\n",n,ed);


if( ed  > 3*N - 6 ) return false;

G.reset();
bucket_s(G,Dfsnr,low1,low2);  // sortiere Kanten nach ihren low-Werten


dfsstart(G,Dfsnr);  // dfs auf umgeordneten Ad.listen
G.reset();


list<ed_inf>* segment = new list<ed_inf>[2*N];


node*  Graph_order = new node[N+1];
edge_array<int> alpha(G);

forall_nodes(w,G)
  Graph_order[Dfsnr[w]] = w;

G.reset();
v = Graph_order[1];
e = G.first_adj_edge( v );


// starte Test mit Kante (1,2)

A = plantest(Graph_order, Dfsnr, e, segment, seg_num);

if( A.empty()) 
{ for(i=0; i<2*N; i++) segment[i].clear();
  delete segment; 
  delete Graph_order;
  return false;
}


// eintragen der Segmentplazierung in Kantenfeld alpha. alpha[e] ist L oder R

for(i=0; i <= seg_num ; i++)
    {
      x = segment[i].head();
      basis = x->plaz;
      forall(x, segment[i])
         {
           e = x->e;
          if( basis == 'L' )
             {
              if ( x->plaz == 'L' || x->plaz == '=')
                  alpha[e] = 'L';
              else if( x->plaz == '!')
                  alpha[e] = 'R';
             }
           else
               if(x->plaz == 'R' || x->plaz == '=')
                        alpha[e] = 'R';
               else alpha[e] = 'L';
         }
     } 
 
list<node> G_Lst, Or_Lst;


n = Or.number_of_nodes();
node* Or_ord = new node[n+1];

G_Lst = G.all_nodes();
Or_Lst = Or.all_nodes();
list_item topn = Or_Lst.first();

forall_list_items(t, G_Lst)
{ 
  Or_dfs[Or_Lst[topn]] = Dfsnr[G_Lst[t]];
  topn = Or_Lst.succ(topn);
}

forall_nodes(w,Or)
     Or_ord[Or_dfs[w]] = w;

 
v = Or_ord[2];
grenze = Or.first_adj_edge(v); // init. Grenzkante mit grenze = (2,x)
 
e = G.first_adj_edge(Graph_order[1]);
alpha[e] = 'L'; // Plaz. des Basissegments

// berechne komb. Einbettung von G. Ergebnis steht in cyc_lst

cycl_embedding(cyc_lst,Or,G,Or_ord,Graph_order,Or_dfs,Dfsnr,alpha,e,grenze);

edge_array<int> ord_in_cycl_emb(Or);


n = 0;
forall(e,cyc_lst) ord_in_cycl_emb[e] = n++;

// Umordnen der Ad.listen des Eingabegraphen
Or.sort_edges(ord_in_cycl_emb);

for (i=0; i<2*N; i++) segment[i].clear();
delete segment; 
delete Graph_order;
delete Or_ord;

return true;

}