/*******************************************************************************
+
+  LEDA 3.5
+
+  _g_map.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.
+ 
*******************************************************************************/
#include <LEDA/graph.h>

// reversal edges

edge graph::face_cycle_succ(edge e) const 
{ return cyclic_adj_pred(reversal(e)); }

edge graph::face_cycle_pred(edge e) const 
{ return reversal(cyclic_adj_succ(e)); }

edge graph::succ_face_edge(edge e) const 
{ return cyclic_adj_pred(reversal(e)); }

edge graph::pred_face_edge(edge e) const 
{ return reversal(cyclic_adj_succ(e)); }


void graph::set_reversal(edge e, edge r)
{ if ( source(e) != target(r) || target(e) != source(r) )
  error_handler(1,"graph::set_reversal: edges are not reversals of each other");
  e->rev = r;
  r->rev = e;
}


static int map_edge_ord1(const edge& e) { return index(source(e)); }
static int map_edge_ord2(const edge& e) { return index(target(e)); }

bool graph::make_map()     
{
 // computes for every edge e = (v,w) in G its reversal r = (w,v)
 // in G ( nil if not present). Returns true if every edge has a
 // reversal and false otherwise.

  int n     = max_node_index();
  int count = 0;

  list<edge> El1 = all_edges();
  list<edge> El2 = El1;

  edge e;
  forall(e,El1) e->rev = 0;

  El1.bucket_sort(0,n,&map_edge_ord2);
  El1.bucket_sort(0,n,&map_edge_ord1);
  El2.bucket_sort(0,n,&map_edge_ord1);
  El2.bucket_sort(0,n,&map_edge_ord2);


  // merge El1 and El2 to find corresponding edges

  while (! El1.empty() && ! El2.empty())
  { edge e = El1.head();
    edge r = El2.head();
    if (target(r) == source(e))
      if (source(r) == target(e))
         { e->rev = r;
           El2.pop();
           El1.pop();
           count++;
          }
      else
         if (index(source(r)) < index(target(e)))
             El2.pop();
         else
             El1.pop();

    else
      if (index(target(r)) < index(source(e)))
          El2.pop();
      else
          El1.pop();

   }

  return (count == number_of_edges()) ? true : false;
}


void graph::make_map(list<edge>& R)     
{ if (make_map()) return;
  list<edge> el = all_edges();
  edge e;
  forall(e,el)
  { if (e->rev == nil)
    { edge r = new_edge(target(e),source(e));
      e->rev = r;
      r->rev = e;
      R.append(r);
     }
   }
}
   




extern bool PLANAR(graph&, bool=false);

void graph::make_planar_map()
{ if (!graph::make_map())
       error_handler(1,"graph::make_planar_map: graph is not bidirected");
  if (!PLANAR(*this,true)) 
       error_handler(1,"graph::make_planar_map: Graph is not planar."); 
  compute_faces();
}



face  graph::new_face(GenPtr i) 
{ copy_face_entry(i);
  return add_face(i);
 }

face  graph::new_face() 
{ GenPtr i = 0;
  init_face_entry(i);
  return add_face(i);
 }


list<edge> graph::adj_edges(face f) const
{ list<edge> result(f->head);
  edge e1 = face_cycle_succ(f->head);
  while (e1!=f->head)
  { result.append(e1);
    e1 = face_cycle_succ(e1);
   }
  return result;
 }

list<node> graph::adj_nodes(face f) const
{ list<node> result(source(f->head));
  edge e1 = face_cycle_succ(f->head);
  while (e1!=f->head)
  { result.append(source(e1));
    e1 = face_cycle_succ(e1);
   }
  return result;
 }

list<face> graph::adj_faces(node v) const
{ list<face> result;
  edge e;
  forall_out_edges(e,v) result.append(adj_face(e));
  return result;
 }


void graph::print_face(face f) const
{ cout << string("F[%2d]",index(f));
  cout << "(";
  print_face_entry(cout,f->data[0]);
  cout << "): ";
  edge e;
  forall_face_edges(e,f) 
   cout << string("[%2d]",index(target(e)));
 }




void graph::compute_faces()
{ 
  del_all_faces();

  FaceOf = new graph_map(this,1,0);

  edge e;
  forall_edges(e,*this) 
  { if (e->rev == nil) 
      error_handler(1,"graph::compute_faces: no map (reversal edge missing)");
    access_face(e) = nil;
   }


  forall_edges(e,*this)
  { if (access_face(e) != nil) continue;
    face f = new_face();
    f->head = e;
    edge e1 = e;
    int count = 0;
    do { access_face(e1) = f;
         e1 = face_cycle_succ(e1);
         count++;
       } while (e1 != e);
    f->sz = count;
   } 
} 




edge graph::split_map_edge(edge e)
{ 
  /* splits edge e and its reversal by inserting a new node u (node_inf) 
              e                          e           rr
        ----------->                --------->   --------->
     (v)            (w)   ====>  (v)          (u)          (w)
        <-----------                <---------   <---------
              r                          er          r
     returns edge rr
  */

  edge r = e->rev;

  if (r == nil)
    error_handler(1,"graph::split_map_edge(e): reversal of edge e missing.");

  node v = source(e);
  node w = target(e);
  node u = new_node();

  // remove e and r from corresponding in-lists
  w->del_adj_edge(e,1,1);
  v->del_adj_edge(r,1,1);

  // insert e and r in in-list of u
  e->term[1] = u;
  r->term[1] = u;
  u->append_adj_edge(e,1,1);
  u->append_adj_edge(r,1,1);

  // create reverse edges rr and re
  edge rr = graph::new_edge(u,w);
  edge er = graph::new_edge(u,v);

  set_reversal(e,er);
  set_reversal(r,rr);

  access_face(rr) = access_face(e);
  access_face(er) = access_face(r);

  return rr;
}



edge graph::new_map_edge(edge e1, edge e2)
{ edge e = graph::new_edge(e1,source(e2));
  edge r = graph::new_edge(e2,source(e1));
  set_reversal(e,r);
  return e;
}


edge graph::split_face(edge e1, edge e2)
{ 
  face f1 = access_face(e1);
  face f2 = access_face(e2);

  if (f1 != f2)
    error_handler(1,"planar_map::new_edge: new edge must lie in a face."); 

  f2 = new_face();

  edge x = graph::new_edge(e1,source(e2));
  edge y = graph::new_edge(e2,source(e1));
  set_reversal(x,y);

  f1->head = x;
  f2->head = y;

  access_face(x) = f1;

  do { access_face(y) = f2;
       y = face_cycle_succ(y);
     } while (y != f2->head);

  return x;
}


list<edge> graph::triangulate_map()
{ 
/* G is a planar map. This procedure triangulates all faces of G
   without introducing multiple edges. The algorithm was suggested by 
   Christian Uhrig and Torben Hagerup. 

   Description:

   Triangulating a planar graph G, i.e., adding edges
   to G to obtain a chordal planar graph, in linear time:
   
   1) Compute a (combinatorial) embedding of G.
   
   2) Step through the vertices of G. For each vertex u,
   triangulate those faces incident on u that have not
   already been triangulated. For each vertex u, this
   consists of the following:
   
     a) Mark the neighbours of u. During the processing
   of u, a vertex will be marked exactly if it is a
   neighbour of u.
   
     b) Process in any order those faces incident on u
   that have not already been triangulated. For each such
   face with boundary vertices u=x_1,...,x_n,
        I)   If n=3, do nothing; otherwise
        II)  If x_3 is not marked, add an edge {x_1,x_3},
             mark x_3 and continue triangulating the face
             with boundary vertices x_1,x_3,x_4,...,x_n.
        III) If x_3 is marked, add an edge {x_2,x_4} and
             continue triangulating the face with boundary
             vertices x_1,x_2,x_4,x_5,...,x_n.
   
     c) Unmark the neighbours of x_1.
   
   Proof of correctness:
   
   A) All faces are triangulated.
   This is rather obvious.
   
   B) There will be no multiple edges.
   During the processing of a vertex u, the marks on
   neighbours of u clearly prevent us from adding a multiple
   edge with endpoint u. After the processing of u, such an
   edge is not added because all faces incident on u have
   been triangulated. This takes care of edges added in
   step II).
   Whenever an edge {x_2,x_4} is added in step III), the
   presence of an edge {x_1,x_3} implies, by a topological
   argument, that x_2 and x_4 are incident on exactly one
   common face, namely the face currently being processed.
   Hence we never add another edge {x_2,x_4}.
*/
   
  node v;
  edge x;
  list<edge> L;

  node_array<int>  marked(*this,0);

  if ( !make_map() ) 
  error_handler(1,"TRIANGULATE_PLANAR_MAP: graph is not a map.");

  forall_nodes(v,*this)
  {
    list<edge> El = adj_edges(v);
    edge e,e1,e2,e3;
 
    forall(e1,El) marked[target(e1)]=1;

    forall(e,El)
    { 
      e1 = e;
      e2 = face_cycle_succ(e1);
      e3 = face_cycle_succ(e2);

      while (target(e3) != v)
      // e1,e2 and e3 are the first three edges in a clockwise 
      // traversal of a face incident to v and t(e3) is not equal
      // to v.
       if ( !marked[target(e2)] )
        { // we mark w and add the edge {v,w} inside F, i.e., after
          // dart e1 at v and after dart e3 at w.
 
          marked[target(e2)] = 1;
          L.append(x  = new_edge(e3,source(e1)));
          L.append(e1 = new_edge(e1,source(e3)));
          set_reversal(x,e1);
          e2 = e3;
          e3 = face_cycle_succ(e2);
        }
        else
        { // we add the edge {source(e2),target(e3)} inside F, i.e.,
          // after dart e2 at source(e2) and before dart 
          // reversal_of[e3] at target(e3).

          e3 = face_cycle_succ(e3); 
          L.append(x  = new_edge(e3,source(e2)));
          L.append(e2 = new_edge(e2,source(e3)));
          set_reversal(x,e2);
        }
     //end of while

    } //end of stepping through incident faces

   node w; 
   forall_adj_nodes(w,v) marked[w] = 0;

  } // end of stepping through nodes

 return L;

}


face graph::join_faces(edge x)
{
  edge y  = reversal(x);

  if (y == nil)
      error_handler(1,"join_faces: graph must be a map.");

  if (access_face(x) == nil || access_face(y) == nil)
      error_handler(1,"join_faces: no face associated with edges.");

  edge e  = face_cycle_succ(y);
  face F1 = adj_face(x);
  face F2 = adj_face(y);

  if (F1 != F2)
  { edge e = face_cycle_succ(y);
    F1->head = e;
    while ( e != y )
    { access_face(e) = F1;
      e = face_cycle_succ(e);
     }
    clear_face_entry(F2->data[0]);
    del_face(F2);
   }
  else
  { e = face_cycle_succ(e);
    if (e != y) // no isolated edge
      F1->head = e;   
    else 
      { clear_face_entry(F1->data[0]);
        del_face(F1);
        F1 = F2;
       }
   }

  graph::del_edge(x);
  graph::del_edge(y);

  return F1;
}




void graph::make_bidirected(list<edge>& L) 
{ Make_Bidirected(*this,L); }

bool graph::is_bidirected() const
{ edge_array<edge> rev(*this,0);
  return Is_Bidirected(*this,rev);
}

bool graph::is_map() const  
{ return Is_Map(*this); }

