/*******************************************************************************
+
+  LEDA 3.5
+
+  _ht_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 Hopcroft/Tarjan Planarity Test
//
// bool HT_PLANAR(graph& G, bool embed = false);
// bool HT_PLANAR(graph& G, list<edge>& P, bool embed = false);
//
// K. Mehlhorn (1994)
// S. Naeher   (1995)   (multi-graphs)
//
//------------------------------------------------------------------------------

#include <LEDA/stack.h>
#include <LEDA/graph.h>
#include <LEDA/graph_alg.h>
#include <assert.h>

const int left = 1;
const int right = 2;

class block
{
  list<int>  Latt, Ratt;	// list of attachments 
  list<edge> Lseg, Rseg;	// list of segments represented by their
				// defining edges
  public:

  block(edge e, list<int>& A) 
  { Lseg.append(e);
    Latt.conc(A);
    // the other two lists are empty 
   } 

  ~block() {}


  void flip() 
  { list<int>  ha;
    list<edge> he;

     // we first interchange |Latt| and |Ratt| and then |Lseg| and |Rseg| 

     ha.conc(Ratt);
     Ratt.conc(Latt);
     Latt.conc(ha);
     he.conc(Rseg);
     Rseg.conc(Lseg);
     Lseg.conc(he);
  }

  int head_of_Latt() { return Latt.head(); }
  int head_of_Ratt() { return Ratt.head(); }

  bool empty_Latt() { return Latt.empty(); }
  bool empty_Ratt() { return Ratt.empty(); }

  bool left_interlace(stack<block*>& S) 
  {
    // check for interlacing with the left side of the topmost block of |S|
    assert( ! Latt.empty() );

    return (! S.empty() && !S.top()->empty_Latt()
                     && Latt.tail() < S.top()->head_of_Latt());
  }

  bool right_interlace(stack < block * >&S) 
  {
    // check for interlacing with the right side of the topmost block of |S|
    assert( ! Latt.empty() );

    return ( !S.empty() && !S.top()->empty_Ratt()
                        &&  Latt.tail() < S.top()->head_of_Ratt());
   }


  void combine(block* Bprime) 
  { // add block |Bprime| to the rear of |this| block 
    Latt.conc(Bprime->Latt);
    Ratt.conc(Bprime->Ratt);
    Lseg.conc(Bprime->Lseg);
    Rseg.conc(Bprime->Rseg);
    delete Bprime;
  } 

  bool clean(int dfsnum_w, edge_array<int>& alpha)
  { // remove all attachments to |w|; there may be several

    while (!Latt.empty() && Latt.head() == dfsnum_w) Latt.pop();
    while (!Ratt.empty() && Ratt.head() == dfsnum_w) Ratt.pop();

    if (!Latt.empty() || !Ratt.empty()) return false;

    // |Latt| and |Ratt| are empty; we record the placement of the subsegments
    // in |alpha|.

    edge e;
    forall(e, Lseg) alpha[e] = left;
    forall(e, Rseg) alpha[e] = right;

     return true;
  }


  void add_to_Att(list<int>& Att, int dfsnum_w0, edge_array<int>& alpha)
  { // add the block to the rear of |Att|. Flip if necessary 

    if (!Ratt.empty() && head_of_Ratt() > dfsnum_w0) flip();

    Att.conc(Latt);
    Att.conc(Ratt);

    // This needs some explanation. Note that |Ratt| is either empty or w0. 
    // Also if |Ratt| is non-empty then all subsequent sets are contained
    // in w0. So we indeed compute an ordered set of attachments. 

    edge e;
    forall(e, Lseg) alpha[e] = left;
    forall(e, Rseg) alpha[e] = right;
  }

  LEDA_MEMORY(block)
};



static void copy_graph(const graph& G, GRAPH<node,edge>& H, 
                       node_array<node>& v_in_H, edge_array<edge>& e_in_H)
{
  node v;
  forall_nodes(v,G) v_in_H[v] = H.new_node(v);

  edge e;
  forall_edges(e,G) e_in_H[e] =
      H.new_edge(v_in_H[source(e)],v_in_H[target(e)],e);
}





static void Reorder(graph&, node_array<int>&, node_array<node>&);
// defined later


static bool Strongly_Planar(edge e0, graph & G, list<int>& Att,
                                                edge_array<int>&  alpha,
                                                node_array<int>&  dfsnum,
                                                node_array<node>& parent)
{ node x = source(e0);
  node y = target(e0);
  edge e = G.first_adj_edge(y);
  node wk = y;

  while (dfsnum[target(e)] > dfsnum[wk]) 
  { // e is a tree edge
    wk = target(e);
    e = G.first_adj_edge(wk);
   }

  node w0 = target(e);
  node w  = wk;

  stack<block*> S;

  while (w != x) 
  {
    int count = 0;

    forall_adj_edges(e, w) 
    {
        if (++count == 1) continue; // no action for first edge 

	list <int> A;

	if (dfsnum[w] < dfsnum[target(e)]) // tree edge
          { if ( !Strongly_Planar(e,G,A,alpha,dfsnum,parent) )
            { while ( ! S.empty()) delete S.pop();
  	      return false;
  	     }
  	   }
	else // a back edge
	   A.append(dfsnum[target(e)]);

	block* B = new block(e,A);

	while (true) 
        { 
          if (B->left_interlace(S)) S.top()->flip();

	  if (B->left_interlace(S)) 
          { delete B;
	    while (!S.empty()) delete S.pop();
	    return false;
	   }

	  if (B->right_interlace(S))
	     B->combine(S.pop());
	  else
	     break;
	}			/* end while */

        S.push(B);
    }				/* end forall */

    while (!S.empty() && S.top()->clean(dfsnum[parent[w]],alpha))
      delete S.pop();

    w = parent[w];
  }				/* end while */

  Att.clear();

  while ( !S.empty() )
  {
    block *B = S.pop();

    if ( !B->empty_Latt() && 
         !B->empty_Ratt() && 
          B->head_of_Latt() > dfsnum[w0] && 
          B->head_of_Ratt() > dfsnum[w0]) 
    { delete B;
      while (!S.empty()) delete S.pop();
      return false;
     }

    B->add_to_Att(Att, dfsnum[w0], alpha);

    delete B;
  }				/* end while */

  // Let's not forget (as the book does) that $w0$ is an attachment of $S(e0)$
  // except if $w0 = x$.

  if (w0 != x) Att.append(dfsnum[w0]);

  return true;
}




static void Embedding(edge e0, int t, GRAPH <node,edge>& G,
                                      edge_array<int>& alpha, 
                                      node_array<int>& dfsnum,
                                      list<edge>& T, 
                                      list<edge>& A, 
                                      int& cur_nr,
                                      edge_array<int>& sort_num,
                                      node_array<edge>& tree_edge_into,
                                      node_array<node>& parent, 
                                      edge_array<edge>& reversal)
{ node x = source(e0);
  node y = target(e0);
  edge e = G.first_adj_edge(y);
  node wk= y;

  tree_edge_into[y] = e0;

  while (dfsnum[target(e)] > dfsnum[wk]) 
  { // e is a tree edge 
    wk = target(e);
    tree_edge_into[wk] = e;
    e = G.first_adj_edge(wk);
   }

  //node w0 = target(e);
  edge back_edge_into_w0 = e;
  node w = wk;

  list<edge> Al;
  list<edge> Ar;
  list<edge> Aprime;
  list<edge> Tprime;

  T.clear();
  T.append(G[e]);		/* |e = (wk,w0)| at this point, line (2) */

  while (w != x)
  { int count = 0;
    forall_adj_edges(e,w) 
    { 
      if (++count == 1) continue;  // no action for first edge 

      if (dfsnum[w] < dfsnum[target(e)])  // tree edge
  	 { int tprime = (t == alpha[e]) ? left : right;
  	   Embedding(e, tprime, G, alpha, dfsnum, Tprime, Aprime, cur_nr, 
                        sort_num, tree_edge_into, parent, reversal);
	  }
      else 
         { // back edge 
	   Tprime.append(G[e]);
	   Aprime.append(reversal[G[e]]);
	  }

      if (t == alpha[e]) 
         { Tprime.conc(T);
  	   T.conc(Tprime);	/* $T = Tprime\ conc\ T$ */
  	   Al.conc(Aprime);	/* $Al = Al\ conc\ Aprime$ */
	  }
      else 
         { T.conc(Tprime);	/* $ T\ = T\ conc\ Tprime $ */
	   Aprime.conc(Ar);
	   Ar.conc(Aprime);	/* $ Ar\ = Aprime\ conc\ Ar$ */
	  }
    }	/* forall_adj_edges */

    T.append(reversal[G[tree_edge_into[w]]]);	/* $(w_{j-1},w_j)$ */

    forall(e, T) sort_num[e] = cur_nr++;

    // |w|'s adjacency list is now computed; we clear |T| and prepare for the
    // next iteration by moving all darts incident to |parent[w]| from |Al| and
    // |Ar| to |T|. These darts are at the rear end of |Al| and at the front
    // end of |Ar|

    T.clear();

    while (!Al.empty() && source(Al.tail()) == G[parent[w]])
    { // |parent[w]| is in |G|, |Al.tail| in |H| */
      T.push(Al.Pop());	// Pop removes from the rear 
     }

    T.append(G[tree_edge_into[w]]);	// push would be equivalent 

    while (!Ar.empty() && source(Ar.head()) == G[parent[w]]) 
    {
      T.append(Ar.pop());  // pop removes from the front
    }

    w = parent[w];

  } /* while */

  A.clear();
  A.conc(Ar);
  A.append(reversal[G[back_edge_into_w0]]);
  A.conc(Al);
}



// used later for bucket sorting edges
static node_array<int> node_ord;
static int source_ord(const edge& e) { return node_ord[source(e)]; }
static int target_ord(const edge& e) { return node_ord[target(e)]; }




bool HT_PLANAR(graph& Gin, bool embed)
{

/* |Gin| is a directed graph. |planar| decides whether |Gin| is planar.
 * If it is and |embed == true| then it also computes a
 * combinatorial embedding of |Gin| by suitably reordering
 * its adjacency lists. |Gin| must be bidirected and simple in that case.
 */

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

  if (n <= 3) return true;

  // An undirected planar graph has at most $3n-6$ edges; a directed graph may
  // have twice as many

  if (m > 6 * n - 12) return false;

  GRAPH <node,edge> G;
  edge_array <edge> companion_in_G(Gin);
  node_array <node> link(Gin);

  copy_graph(Gin,G,link,companion_in_G);


  // remove self-loops from G

  Delete_Loops(G);


  // make G simple and assign all parallel edges in Gin to a 
  // single remaining companion in G

  list<edge> el = G.all_edges();
  node_ord.init(G,0);
  int  nr = 0;

  node v;
  forall_nodes(v,G) node_ord[v] = nr++;
  el.bucket_sort(0,n-1,&source_ord);
  el.bucket_sort(0,n-1,&target_ord);

  // now parallel edges are adjacent in el
  
  edge e0 = el.pop();
  edge e;
  forall(e,el)  
    if (source(e0) == source(e) && target(e0) == target(e)) 
     { companion_in_G[G[e]] = e0;
       G.del_edge(e);
      }
    else e0 = e;


  // Finally, we make G biconnected and bidirected.

  el = Make_Biconnected(G);

  forall(e,el) G.new_edge(target(e),source(e));

  el = Make_Bidirected(G);

  bool Gin_is_bidirected = el.empty();


  GRAPH<node,edge> H;
  edge_array<edge> companion_in_H(Gin);
  { node v;
    edge e;
    forall_nodes(v, G) G[v] = H.new_node(v);
    forall_edges(e, G) G[e] = H.new_edge(G[source(e)],G[target(e)],e);
    forall_edges(e, Gin) companion_in_H[e] = G[companion_in_G[e]];
   }


  node_array<int>  dfsnum(G);
  node_array<node> parent(G,nil);

  Reorder(G,dfsnum,parent);

  edge_array<int> alpha(G, 0);
  list<int> Att;

  e0 = G.first_adj_edge(G.first_node());
  alpha[e0] = left;

  if ( ! Strongly_Planar(e0, G, Att, alpha, dfsnum, parent) ) return false;


  if (embed) 
  { 
    if ( ! Gin_is_bidirected) 
      error_handler(2, "HT_PLANAR: sorry, can only embed bidirected graphs.");

    edge_array<edge> reversal(H);
    if ( ! Is_Bidirected(H,reversal) ) 
      error_handler(1,"HT_PLANAR (internal error): H is not bidirected.");


      list <edge> T;	/* lists of edges of |H| */
      list <edge> A;	

      int cur_nr = 0;
      edge_array<int>  sort_num(H);
      node_array<edge> tree_edge_into(G);

      Embedding(e0, left, G, alpha, dfsnum, T, A, cur_nr, sort_num, 
                tree_edge_into, parent, reversal);

      /* |T| contains all edges incident to the first node except the 
         cycle edge into it.  That edge comprises |A| */

      T.conc(A);
      
      edge e;
      forall(e,T) sort_num[e] = cur_nr++;

      edge_array<int> sort_Gin(Gin,0);

      forall_edges(e, Gin) 
         if (source(e) != target(e))
                sort_Gin[e] = sort_num[companion_in_H[e]];

      Gin.bucket_sort_edges(sort_Gin);
    }

  return true;
}



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

/* We work on a copy |H| of |G| since the procedure alters |G|; we link every
 * vertex and edge of |H| with its original. For the vertices we also have the
 * reverse links. */

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

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

/* This requires some explanation. |H.new_node(v)| adds a new node to
 * |H|, returns the new node, and makes |v| the information associated
 * with the new node. So the statement creates a copy of |v| and
 * bidirectionally links it with |v| */

  int N = G.number_of_nodes();

  edge e;

  forall_edges(e,G)
  if (G.source(e) != G.target(e))
  { H.new_edge(link[G.source(e)], link[G.target(e)], e);
    if (--N < 1 && !HT_PLANAR(H)) break;
   }

/* |link[source(e)]| and |link[target(e)]| are the copies of |source(e)|
 * and |target(e)| in |H|. The operation |H.new_edge| creates a new edge
 * with these endpoints, returns it, and makes |e| the information of that
 * edge. So the effect of the loop is to make the edge set of |H| a copy
 * of the edge set of |G| and to let every edge of |H| know its original.
 * We can now determine a minimal non-planar subgraph of |H| */

  list<edge> L = H.all_edges();

  edge eh;

  forall(eh, L) {
    e = H[eh];			/* the edge in |G| corresponding to |eh| */
    node x = G.source(eh);
    node y = G.target(eh);
    H.del_edge(eh);
    if (HT_PLANAR(H))
      H.new_edge(x, y, e);	/* put a new version of |eh| back in and *
				 * establish the correspondence */

  }

/* |H| is now a homeomorph of either $K_5$ or $K_{3,3}$. We still need
 * to translate back to |G|. */

  P.clear();

  forall_edges(eh, H) P.append(H[eh]);

  return false;

}



// Reorder


static void dfs_in_reorder(list<edge>& Del, node v, int& dfs_count,
                           node_array<bool>& reached,
                           node_array<int>&  dfsnum,
                           node_array<int>&  lowpt1, 
                           node_array<int>&  lowpt2,
                           node_array<node>& parent)
{
  edge e;

  dfsnum[v] = dfs_count++;
  lowpt1[v] = dfsnum[v];
  lowpt2[v] = dfsnum[v];
  reached[v] = true;

  forall_adj_edges(e,v) 
  { 
    node w = target(e);

    if ( !reached[w] ) // e is a tree edge
      { parent[w] = v;
        dfs_in_reorder(Del,w,dfs_count,reached,dfsnum,lowpt1,lowpt2,parent);
        lowpt1[v] = Min(lowpt1[v],lowpt1[w]);
       }				
    else
      { // no effect for forward edges
        lowpt1[v] = Min(lowpt1[v],dfsnum[w]);	
        if (dfsnum[w] >= dfsnum[v] || w == parent[v]) {
	  // forward edge or reversal of tree edge
	  Del.append(e);
         }
       }
   }			

  // we know |lowpt1[v]| at this point and now make a second pass over all
  // adjacent edges of |v| to compute |lowpt2| 

  forall_adj_edges(e,v) 
  { 
    node w = target(e);

    if (parent[w] == v)	// tree edge 
     { if (lowpt1[w] != lowpt1[v]) lowpt2[v] = Min(lowpt2[v],lowpt1[w]);
       lowpt2[v] = Min(lowpt2[v], lowpt2[w]);
      }
    else // all other edges 
       if (lowpt1[v] != dfsnum[w]) lowpt2[v] = Min(lowpt2[v],dfsnum[w]);
   }
}


static void Reorder(graph& G,node_array<int>& dfsnum,node_array<node>& parent)
{
  node_array<bool> reached(G, false);
  node_array<int>  lowpt1(G);
  node_array<int>  lowpt2(G);
  list<edge> Del;
  int dfs_count = 0;
  node v = G.first_node();
  edge e;

  dfs_in_reorder(Del,v,dfs_count,reached,dfsnum,lowpt1,lowpt2,parent);

  // remove forward and reversals of tree edges 
  forall(e,Del) G.del_edge(e);

  // we now reorder adjacency lists as described in \cite[page 101]{Me:book} 

  edge_array<int> cost(G);
  forall_edges(e, G) 
  { node v = source(e);
    node w = target(e);
    cost[e] = (dfsnum[w] <  dfsnum[v]) ?  2*dfsnum[w] :
              (lowpt2[w] >= dfsnum[v]) ?  2*lowpt1[w] : 2*lowpt1[w]+1;
   }

  //G.sort_edges(cost);
  G.bucket_sort_edges(cost);
}

