/*******************************************************************************
+
+  LEDA 3.5
+
+  _bl_planar.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
//------------------------------------------------------------------------------
//
// The Booth/Lueker Planarity Test  (based on PQ-Trees)
//
// bool BL_PLANAR(graph& G, bool embed = false);
//
//
// bool BL_PLANAR(graph& G, list<edge>& P, bool embed = false);
//
// R. Hesse, E. Kalliwoda, S. Naeher, D. Ambras   (1996/97)
//
//------------------------------------------------------------------------------


#include <LEDA/graph_alg.h>
#include <LEDA/pq_tree.h>

typedef list<edge> edge_list;


enum { NORMAL = 0, REVERSE = -1 };

static void DFS(graph& G, node v, const node_array<edge_list>& upward,
                                  node_array<int>& st_num, 
                                  list<edge>& embed_list)
{ 
  // I mark visited nodes by setting their st-number to -1
  // ( The graph is st-numbered already. )

  if (st_num[v] < 0) return;
 
  st_num[v] = -1;

  edge e;
  forall_rev(e,upward[v])
  { embed_list.append(G.reversal(e));
    DFS(G,target(e),upward,st_num,embed_list);
   }
}



static void embedding(graph& G, node t, node_array<int>& st_num,
                                        node_array<edge_list>& upward)
{
  // extend upward embedding to an entire embedding using DFS

  list<edge> embed_list;

  node v;
  forall_nodes(v,G)
  { edge e;
    forall(e,upward[v]) embed_list.append(e);
   }

  DFS(G,t,upward,st_num,embed_list);

  G.sort_edges(embed_list);
}


static int TEST_PLANARITY(graph& G, bool embed, node_array<int>& st_num,
                                                list<node>& st_list)
{ // preconditions:
  // G is biconnected and bidirected
  // st_num:  st-numbering of nodes
  // st_list: list of nodes sorted by increasing st-numbers

  // returns st-number of last visited node

  int n = G.number_of_nodes();
  int m = G.number_of_edges();

  if (n < 4)  return n;

  node s = st_list.head();
  node t = st_list.tail();
  

  // interface for pq_tree

  pq_tree  T(m);

  list<int>* AU = new list<int>[n+1];
  
  edge_array<int> e_index(G);  // array of edge indices (--> pq_tree_items)
  edge* EDGE  = new edge[m+1]; // inverse array of e_index
  int   count = 0;
  node  v;
  edge  e;

  forall_edges(e,G)
  { e_index[e] = ++count;
    EDGE[count] = e;
  }
  
  
  // planarity test

  int st;

  forall(v,st_list)
  { 
    list<int> L;

    st = st_num[v];

    if ( v != s)
    { forall_adj_edges(e,v)
        if (st_num[target(e)] < st)  L.push(e_index[e]); 
      if ( !T.reduction(L) )  break;
      T.pert_sequence(AU[st]);
    }
    
    L.clear();

    forall_in_edges(e,v)
      if (st_num[source(e)] > st) L.push(e_index[e]); 

    if ( !T.update(L) ) break;
   }

  //bool is_planar = (st == n);

  if (st == n && embed) 
  {
   // construct adjacency lists of upward embedding

   node_array<edge_list> upward(G); 

   list<int>* au = &AU[n];

   forall_rev(v,st_list)  
   { 
     if (v == s) break;   // for v = t down to s+1

     int stn = st_num[v];
     int l   = au->pop();
     int d   = 1;
     int i;

     if (l == REVERSE)
     { d = -1;
       l = au->pop();
      }

     for(i = 0; i < l; i++)
     { int h = d * au->pop();
       if (h < 0) AU[-h].push(REVERSE);
      }

     if (d > 0)
        forall(i,*au) upward[v].append(EDGE[i]);
     else
        forall(i,*au) upward[v].push(EDGE[i]);

     au--;
    }

   embedding(G,t,st_num,upward);
   G.sort_nodes(st_list);
  }
  
  delete[] EDGE;
  delete[] AU;
  
  return st;
}


static void prepare_graph(graph& G, bool embed, list<edge>& el)
{ if (embed)
   { if ( !G.make_map() )
        error_handler(1,"BL_PLANAR: can only embed bidirected graphs.");
     Make_Biconnected(G,el); 
     edge e;
     forall(e,el)
     { edge x = G.new_edge(target(e),source(e));
       el.push(x);
       G.set_reversal(e,x);
      }
    }
  else
   { Make_Biconnected(G,el); 
     Make_Bidirected(G,el);
    }
}


static void restore_graph(graph& G, list<edge>& el)
{ edge e;
  forall(e,el) G.del_edge(e);
 }



bool BL_PLANAR(graph& G, bool embed) 
{ 
  if (G.number_of_nodes() <= 1)  return true;

  list<edge> el;
  prepare_graph(G,embed,el);

  node_array<int> st_num(G);
  list<node> st_list;
  ST_NUMBERING(G,st_num,st_list);

  int max_st = TEST_PLANARITY(G,embed,st_num,st_list);

  restore_graph(G,el);
  return max_st == G.number_of_nodes();
}



// compute Kuratowski Subdivison

bool BL_PLANAR(graph& G, list<edge>& K, bool embed)
{
  if (BL_PLANAR(G, embed)) return true;

  GRAPH<node,edge> H;
  node_array<node> link(G);
  node v;

  forall_nodes(v, G) link[v] = H.new_node(v);

  int n = G.number_of_nodes();

  edge e;
  forall_edges(e,G)
  { node v = source(e);
    node w = target(e);
    if (v != w)
    { H.new_edge(link[v],link[w],e);
      if (--n < 1 && !BL_PLANAR(H,false)) break;
    }
  }

  K.clear();

  list<edge> L = H.all_edges();
  edge eh;
  forall(eh, L) 
  { e = H[eh];
/*
    node x = G.source(eh);
    node y = G.target(eh);
    H.del_edge(eh);
    if (BL_PLANAR(H,false)) 
    { H.new_edge(x,y,e);
      K.append(e);
     }
*/
    H.hide_edge(eh);
    if (BL_PLANAR(H,false)) 
    { H.restore_edge(eh);
      K.append(e);
     }
  }

  return false;
}

