/*******************************************************************************
+
+  LEDA 3.5
+
+  _graph.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>

//------------------------------------------------------------------------------
// basic graph operations
//
// by S. Naeher (1995,1996)
//------------------------------------------------------------------------------

graph::graph()
{ int sz1 = LEDA::node_data_slots;
  int sz2 = LEDA::edge_data_slots;
  max_n_index = -1;
  max_e_index = -1; 
  max_f_index = -1; 
  parent = 0; 
  undirected = false;
  data_sz[0] = sz1;
  data_sz[1] = sz2;
  data_sz[2] = 0;
  while (sz1) free_data[0].push(sz1--);
  while (sz2) free_data[1].push(sz2--);
  adj_iterator = new graph_map(this,0,0);
  FaceOf = 0;
 }


graph::graph(int sz1, int sz2)
{ max_n_index = -1;
  max_e_index = -1; 
  max_f_index = -1; 
  parent = 0; 
  undirected = false;
  data_sz[0] = sz1;
  data_sz[1] = sz2;
  data_sz[2] = 0;
  while (sz1) free_data[0].push(sz1--);
  while (sz2) free_data[1].push(sz2--);
  adj_iterator = new graph_map(this,0,0);
  FaceOf = 0;
 }


graph_map graph::node_data() { return  graph_map(this,0); }
graph_map graph::edge_data() { return  graph_map(this,1); }
graph_map graph::face_data() { return  graph_map(this,2); }


void graph::copy_all_entries() const
{ node v;
  forall_nodes(v,*this) copy_node_entry(v->data[0]);
  edge e;
  forall_edges(e,*this) copy_edge_entry(e->data[0]);
  // hidden edges
  for(e = (edge)h_list.head(); e; e = (edge)h_list.succ(e)) 
    copy_edge_entry(e->data[0]);
}


void graph::clear_all_entries() const
{ node v;
  forall_nodes(v,*this) clear_node_entry(v->data[0]);
  edge e;
  forall_edges(e,*this) clear_edge_entry(e->data[0]);
  // hidden edges
  for(e = (edge)h_list.head(); e; e = (edge)h_list.succ(e)) 
    clear_edge_entry(e->data[0]);
}



void graph::copy_graph(const graph& G)  
{ 
  int n = G.number_of_nodes();
  //int m = G.number_of_edges();

  for(int k = 0; k < 3; k++)
  { data_sz[k] = G.data_sz[k];
    for(int i=1; i<=data_sz[k]; i++) free_data[k].append(i);
   }

  max_n_index = -1;
  max_e_index = -1;
  max_f_index = -1;

  e_list.clear();

  FaceOf = 0;

  parent = 0;

  if (n == 0) return;

  node* node_vec = new node[G.max_n_index+1];
  edge* edge_vec = new edge[G.max_e_index+1];

  if (node_vec == 0 || edge_vec == 0) 
    error_handler(1," copy_graph: out of memory");

  // allocate a single block of memory for all nodes
  // memory_allocate_block(sizeof(node_struct),n);

  node v;
  forall_nodes(v,G) 
     node_vec[index(v)] = new_node(v->data[0]);

  // allocate a single block of memory for all edges
  // memory_allocate_block(sizeof(edge_struct),m);

  bool loops_deleted = false;

  forall_nodes(v,G) 
  { node a = node_vec[index(v)];
    edge e;
    forall_adj_edges(e,v) 
    { if ( undirected && v == target(e)) //incoming edge 
       { if (v == source(e)) // loop 
           loops_deleted = true; 
        }
      else
       { node b = node_vec[index(target(e))];
         edge_vec[index(e)] = new_edge(a,b,e->data[0]);
        }
     }
   }


  // update reversal information
  edge e;
  forall_edges(e,G) 
    if (e->rev) 
       edge_vec[index(e)]->rev = edge_vec[index(e->rev)];


  // copy faces (if existing)
  face f;
  forall_faces(f,G)
  { face f1 = new_face(f->data[0]); 
    f1->head = edge_vec[index(f->head)];
   }

  delete[] node_vec;
  delete[] edge_vec;

  if ( loops_deleted )
      error_handler(0,"selfloops deleted in ugraph copy constructor");

}


graph::graph(const graph& G)
{ undirected = G.undirected; 
  copy_graph(G); 
  adj_iterator = new graph_map(this,0,0);
 }


graph& graph::operator=(const graph& G)
{ if (&G != this)
  { graph::clear();
    undirected = G.undirected;
    copy_graph(G);
   }
  return *this;
}


void graph::join(graph& G)
{ // moves all objects from G to this graph and clears G

  if (G.undirected != undirected)
        error_handler(1,"graph::join(G): cannot merge directed and undirected graphs.");

  for(int d=0; d<3; d++) {
     if (G.data_sz[d] != data_sz[d])
        error_handler(1,"graph::join(G): cannot merge graphs with different data sizes.");

  }

  node v;
  edge e;
  face f;

  int i = max_n_index;
  forall_nodes(v,G) { v->id = ++i; v->owner = this; }
  max_n_index = i;

  int j = max_e_index;
  forall_edges(e,G) e->id = ++j; 
  max_e_index = j;

  int k = max_f_index;
  forall_faces(f,G) f->id = ++k; 
  max_f_index = k;

  v_list.conc(G.v_list);
  e_list.conc(G.e_list);
  f_list.conc(G.f_list);

  G.max_n_index = -1;
  G.max_e_index = -1;
  G.max_f_index = -1;
}


  



// subgraph constructors  (do not work for undirected graphs)

/*
graph::graph(graph& G, const list<node>& nl, const list<edge>& el)
{ // construct subgraph (nl,el) of graph G

  parent = &G;
  node v,w;
  edge e;

  node* N = new node[G.max_n_index+1];

  forall(v,nl)
   { if (graph_of(v) != parent) 
      error_handler(1,"graph: illegal node in subgraph constructor");
     N[index(v)] = new_node((GenPtr)v);
    }

  forall(e,el)
   { v = source(e);
     w = target(e);
     if ( graph_of(e)!= parent || N[index(v)]==0 || N[index(w)]==0 ) 
      error_handler(1,"graph: illegal edge in subgraph constructor");
     new_edge(N[index(v)],N[index(w)],(GenPtr)e);
    }

  undirected = G.undirected;

  delete[] N;

 }

graph::graph(graph& G, const list<edge>& el)
{ // construct subgraph of graph G with edge set el

  node  v,w;
  edge  e;
  node* N = new node[G.max_n_index+1];

  forall_nodes(v,G) N[index(v)] = 0;

  parent = &G;

  forall(e,el)
   { v = source(e);
     w = target(e);
     if (N[index(v)] == 0) N[index(v)] = new_node((GenPtr)v);
     if (N[index(w)] == 0) N[index(w)] = new_node((GenPtr)w);
     if ( graph_of(e) != parent )
      error_handler(1,"graph: illegal edge in subgraph constructor");
     new_edge(N[index(v)],N[index(w)],(GenPtr)e);
    }

  undirected = G.undirected;

  delete[] N;

 }

*/


//------------------------------------------------------------------------------
// destruction
//------------------------------------------------------------------------------


void graph::del_all_nodes() { clear(); }

void graph::del_all_edges()
{
  edge e;

  e = (edge)e_list.head(); 
  while (e) 
  { edge next = (edge)e_list.succ(e); 
    dealloc_edge(e);
    e = next;
   }

  e = (edge)h_list.head(); 
  while (e) 
  { edge next = (edge)h_list.succ(e); 
    dealloc_edge(e);
    e = next;
   }

  e = (edge)e_free.head(); 
  while (e) 
  { edge next = (edge)e_free.succ(e); 
    dealloc_edge(e);
    e = next;
   }

  e_list.clear();
  h_list.clear();
  e_free.clear();

  max_e_index = -1;

  node v;
  forall_nodes(v,*this) 
    for(int i=0; i<2; i++)
    { v->first_adj_edge[i] = nil;
      v->last_adj_edge[i] = nil;
      v->adj_length[i] = 0;
     }
}


void graph::del_all_faces()
{
  face f = (face)f_list.head(); 
  while (f) 
  { face next = (face)f_list.succ(f); 
    dealloc_face(f);
    f = next;
   }

  f = (face)f_free.head(); 
  while (f) 
  { face next = (face)f_free.succ(f); 
    dealloc_face(f);
    f = next;
   }

  f_free.clear();
  f_list.clear();

  if (FaceOf)
  { delete FaceOf;
    FaceOf = 0;
   }

  max_f_index = -1;
}



void graph::clear()
{ 
  pre_clear_handler();

  for(int k=0; k<3; k++)
  { graph_map* m;
    forall(m,map_list[k])
      if (m->g_index > 0) m->clear_table();
   }

  del_all_faces();
  del_all_edges();

  node v = (node)v_list.head(); 
  while (v) 
  { node next = (node)v_list.succ(v); 
    dealloc_node(v);
    v = next;
   }

  v = (node)v_free.head(); 
  while (v) 
  { node next = (node)v_free.succ(v); 
    dealloc_node(v);
    v = next;
   }

  v_list.clear();
  v_free.clear();

  max_n_index = -1;

  post_clear_handler();
}


graph::~graph()
{ clear();
  for(int k=0; k<3; k++)
  { graph_map* m;
    forall(m,map_list[k]) m->g = 0;
   }
  delete adj_iterator;
}


//------------------------------------------------------------------------------
// accessing node and edge lists
//------------------------------------------------------------------------------


const list<node>& graph::all_nodes() const 
{ ((list<node>&)v_list_tmp).clear();
  node v;
  forall_nodes(v,*this)
      ((list<node>&)v_list_tmp).append(v);
  return v_list_tmp;
}


const list<edge>& graph::all_edges() const 
{ ((list<edge>&)e_list_tmp).clear();
  edge e;
  forall_edges(e,*this)
      ((list<edge>&)e_list_tmp).append(e);
  return e_list_tmp;
}

const list<face>& graph::all_faces() const 
{ ((list<face>&)f_list_tmp).clear();
  face f;
  forall_faces(f,*this)
      ((list<face>&)f_list_tmp).append(f);
  return f_list_tmp;
}



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


list<edge> graph::in_edges(node v) const
{ list<edge> result;
  edge e;
  forall_in_edges(e,v) result.append(e);
  return result;
}

list<edge> graph::adj_edges(node v) const
{ list<edge> result;
  edge e;
  forall_adj_edges(e,v) result.append(e);
  return result;
}


list<node> graph::adj_nodes(node v) const
{ list<node> result;
  edge e;
  forall_adj_edges(e,v) result.append(opposite(v,e));
  return result;
}



//------------------------------------------------------------------------------
// update operations
//------------------------------------------------------------------------------


list<edge> graph::insert_reverse_edges()
{ list<edge> L;
  edge e = first_edge();

  if (e != nil)
  { L.append(new_edge(target(e),source(e),e->data[0]));
    copy_edge_entry(e->data[0]);
    e = succ_edge(e);
   }

  edge stop = last_edge();

  while (e != stop)
  { L.append(new_edge(target(e),source(e),e->data[0]));
    copy_edge_entry(e->data[0]);
    e = succ_edge(e);
   } 

  return L;
}



face graph::add_face(GenPtr inf)
{ face f;
  if ( f_free.empty() )
    { f = (face)std_memory.allocate_bytes(face_bytes());
      new (f) face_struct(inf);
      f->owner = this;
      f->id = ++max_f_index;
     }
  else
    { f = (face)f_free.pop();
      f->data[0] = inf;
     }

  f_list.append(f);

  graph_map* m;
  forall(m,map_list[2]) m->re_init_entry(f);

  return f;
}

void graph::dealloc_face(face f)
{ std_memory.deallocate_bytes(f,face_bytes()); }

void graph::del_face(face f) 
{ f_list.remove(f); 
  f_free.append(f);
  graph_map* m;
  forall(m,map_list[2]) 
  { int i = m->g_index;
    if (i > 0) m->clear_entry(f->data[i]);
   }
 }



node graph::add_node(GenPtr inf)
{ node v;
  if ( v_free.empty() )
    { v = (node)std_memory.allocate_bytes(node_bytes());
      new (v) node_struct(inf);
      v->owner = this;
      v->id = ++max_n_index;
      v->succ_link = nil;
     }
  else
    { v = (node)v_free.pop();
      v->data[0] = inf;
     }

  v_list.append(v);

  graph_map* m;
  forall(m,map_list[0]) m->re_init_entry(v);

  return v;
}


void graph::dealloc_node(node v)
{ std_memory.deallocate_bytes(v,node_bytes()); }



node graph::new_node()
{ GenPtr x = 0;
  pre_new_node_handler();
  init_node_entry(x);
  node v = add_node(x);
  post_new_node_handler(v);
  return v;
}


node graph::new_node(GenPtr i)
{ pre_new_node_handler();
  node v = add_node(i);
  post_new_node_handler(v);
  return v;
}


void graph::del_node(node v)
{ 
  if (v->owner != this) 
        error_handler(4,"del_node(v): v is not in G");

  pre_del_node_handler(v);

  // delete adjacent edges

  edge  e;
  while ((e=v->first_adj_edge[0]) != nil) del_edge(e);

  if (!undirected)
     while ((e=v->first_adj_edge[1]) != nil) del_edge(e);

  if (parent==0) clear_node_entry(v->data[0]);
 
  v_list.remove(v);
  v_free.append(v);

  graph_map* m;
  forall(m,map_list[0])
  { int i = m->g_index;
    if (i > 0) m->clear_entry(v->data[i]);
   }

  post_del_node_handler();
}


node graph::merge_nodes(node v1, node v2)
{ 
  if (undirected)
    error_handler(1,"merge_nodes not implemented for undirected graphs.");


  for(int i=0; i<2; i++)
  { 

    if (v1->last_adj_edge[i])
        v1->last_adj_edge[i]->succ_adj_edge[i]  = v2->first_adj_edge[i];
    else
        v1->first_adj_edge[i] = v2->first_adj_edge[i];

    if (v2->first_adj_edge[i])
    {  v2->first_adj_edge[i]->pred_adj_edge[i] = v1->last_adj_edge[i];
       v1->last_adj_edge[i] = v2->last_adj_edge[i];
     }

    v1->adj_length[i] += v2->adj_length[i];

    v2->adj_length[i] = 0;
    v2->first_adj_edge[i] = 0;
    v2->last_adj_edge[i] = 0;
   }

  del_node(v2);
  return v1;
}





edge graph::add_edge(node v, node w, GenPtr inf)
{ edge e;

  if (v->owner != this)
     error_handler(6, "new_edge(v,w): v not in graph");
  if (w->owner != this) 
     error_handler(6, "new_edge(v,w): w not in graph");


  if ( e_free.empty() )
    { e = (edge)std_memory.allocate_bytes(edge_bytes());
      new (e) edge_struct(v,w,inf);
      e->id = ++max_e_index;
     }
  else
    { e = (edge)e_free.pop();
      e->data[0] = inf;
      e->term[0] = v;
      e->term[1] = w;
      e->rev = nil;
      e->succ_adj_edge[0] = nil;
      e->succ_adj_edge[1] = nil;
      e->pred_adj_edge[0] = nil;
      e->pred_adj_edge[1] = nil;
    }

  e_list.append(e);

  graph_map* m;
  forall(m,map_list[1]) m->re_init_entry(e);

  return e;
}


void graph::dealloc_edge(edge e)
{ std_memory.deallocate_bytes(e,edge_bytes()); }



void graph::del_adj_edge(edge e, node v, node w)
{ if (undirected)
    { v->del_adj_edge(e,0,0);
      w->del_adj_edge(e,0,1);
     }
  else
    { v->del_adj_edge(e,0,0);
      w->del_adj_edge(e,1,1);
     }
 }



void graph::ins_adj_edge(edge e, node v, edge e1, node w, edge e2,int d1,int d2)
{ 
  // insert edge e
  // after(if d1=0)/before(if d1=1) e1 to adj_list of v
  // after(if d2=0)/before(if d2=1) e2 to in_list (adj_list) of w
  // (most general form of new_edge)

  if ( undirected ) 
   { if (v == w)  
        error_handler(1,"new_edge(v,e1,w,e2): selfloop in undirected graph.");
     if (e1 && v != source(e1) && v != target(e1)) 
        error_handler(1,"new_edge(v,e1,w,e2): v is not adjacent to e1.");
     if (e2 && w != source(e2) && w != target(e2)) 
        error_handler(1,"new_edge(v,e1,w,e2): w is not adjacent to e2.");

     v->insert_adj_edge(e,e1,0,0,d1);
     w->insert_adj_edge(e,e2,0,1,d2);
   }
  else
   { if (e1 && v != source(e1)) 
        error_handler(1,"new_edge(v,e1,w,e2): v is not source of e1.");
     if (e2 && w != source(e2) && w != target(e2)) 
        error_handler(1,"new_edge(v,e1,w,e2): w is not target of e2.");

     v->insert_adj_edge(e,e1,0,0,d1);
     w->insert_adj_edge(e,e2,1,1,d2);
    }
}



edge graph::new_edge(node v, edge e1, node w, edge e2, GenPtr i,int d1,int d2)
{ 
  // add edge (v,w,i)
  // after(if d1=0)/before(if d1=1) e1 to adj_list of v
  // after(if d2=0)/before(if d2=1) e2 to in_list (adj_list) of w
  // (most general form of new_edge)

  if ( undirected ) 
   { if (v == w)  
        error_handler(1,"new_edge(v,e1,w,e2): selfloop in undirected graph.");
     if (e1 && v != source(e1) && v != target(e1)) 
        error_handler(1,"new_edge(v,e1,w,e2): v is not adjacent to e1.");
     if (e2 && w != source(e2) && w != target(e2)) 
        error_handler(1,"new_edge(v,e1,w,e2): w is not adjacent to e2.");
   }
  else
   { if (e1 && v != source(e1)) 
        error_handler(1,"new_edge(v,e1,w,e2): v is not source of e1.");
     if (e2 && w != source(e2) && w != target(e2)) 
        error_handler(1,"new_edge(v,e1,w,e2): w is not target of e2.");
    }

  pre_new_edge_handler(v,w);
  edge e = add_edge(v,w,i);
  ins_adj_edge(e,v,e1,w,e2,d1,d2);
  post_new_edge_handler(e);
  return e ; 
}

edge graph::new_edge(node v, edge e1, node w, GenPtr i,int d)
{
  // add edge (v,w) after/before e1 to adj_list of v
  // append it to in_list (adj_list) of w

  return new_edge(v,e1,w,nil,i,d,0); 
}

edge graph::new_edge(node v, node w, edge e2, GenPtr i,int d)
{
  // append edge (v,w) to adj_list of v
  // insert it after/before e2 to in_list (adj_list) of w

  return new_edge(v,nil,w,e2,i,d,0); 
}

edge graph::new_edge(edge e1, node w, GenPtr i, int dir)  
{ 
  // add edge (source(e1),w) after/before e1 to adj_list of source(e1)
  // append it to in_list (adj_list) of w

  return new_edge(source(e1),e1,w,nil,i,dir,0);
 }

edge graph::new_edge(node v, edge e2, GenPtr i, int dir)  
{ 
  // append edge(v,target(e2))  to adj_list of v
  // insert it after/before e2 to in_list (adj_list) of target(e2)

  return new_edge(v,nil,target(e2),e2,i,0,dir);
 }

edge graph::new_edge(edge e1, edge e2, GenPtr i, int dir1, int dir2)  
{ 
  //add edge (source(e1),target(e2)) 
  //after(dir=0)/before(dir=1) e1 to adj_list of source(e1)
  //after(dir=1)/before(dir=1) e2 to in_list (adj_list) of target(e2)

  return new_edge(source(e1),e1,target(e2),e2,i,dir1,dir2);
 }


edge graph::new_edge(node v, node w, GenPtr i)
{ 
  // append (v,w) it to adj_list of v and to in_list (adj_list) of w

  return new_edge(v,nil,w,nil,i,0,0); 
 }






node graph::split_edge(edge e, GenPtr node_inf, edge& e1, edge& e2)
{
   // splits e into e1 and e2 by putting new node v on e 


  //node v = source(e);
  node w = target(e);
  node u = add_node(node_inf); 

  e1 = e;
  e2 = add_edge(u,w,e->data[0]);

  copy_edge_entry(e2->data[0]);

  if (undirected)
    { u->append_adj_edge(e2,0,0);
      w->insert_adj_edge(e2,e,0,1,0);
      w->del_adj_edge(e,0,1);
      e->term[1] = u;
      u->append_adj_edge(e,0,1);
     }
  else
    { u->append_adj_edge(e2,0,0);
      w->insert_adj_edge(e2,e,1,1,0);
      w->del_adj_edge(e,1,1);
      e->term[1] = u;
      u->append_adj_edge(e,1,1);
     }

 return u;
}




void graph::del_edge(edge e)
{ node v = source(e);
  node w = target(e);

  if (v->owner != this) error_handler(10,"del_edge(e): e is not in G");

  pre_del_edge_handler(e);

  if (is_hidden(e)) restore_edge(e);

  del_adj_edge(e,v,w);

  if (parent == 0) clear_edge_entry(e->data[0]);

  e_list.remove(e);
  e_free.append(e);

  graph_map* m;
  forall(m,map_list[1]) 
  { int i = m->g_index;
    if (i > 0) m->clear_entry(e->data[i]);
   }

  post_del_edge_handler(v,w);
}

 
void graph::hide_edge(edge e)
{
  if (is_hidden(e))  
    error_handler(1,"graph::hide_edge: edge is already hidden.");

  pre_hide_edge_handler(e);


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

  del_adj_edge(e,v,w);

  e_list.remove(e);
  h_list.append(e);

  e->id |= 0x80000000;

  post_hide_edge_handler(e);
 }


void graph::restore_edge(edge e)
{
  if (!is_hidden(e))  
    error_handler(1,"graph::restore_edge: edge is not hidden.");

  pre_restore_edge_handler(e);

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

  h_list.remove(e);
  e_list.append(e);

  if (undirected)
    { v->append_adj_edge(e,0,0);
      w->append_adj_edge(e,0,1);
     }
  else
    { v->append_adj_edge(e,0,0);
      w->append_adj_edge(e,1,1);
     }

  e->id = index(e);

  post_restore_edge_handler(e);
}


void graph::restore_all_edges()
{ for(edge e = (edge)h_list.head(); e; e = (edge)h_list.succ(e)) 
    restore_edge(e);
 }



void graph::move_edge(edge e,edge e1,edge e2,int d1,int d2)
{ if (is_hidden(e)) 
       error_handler(1,"graph::move_edge:  cannot move hidden edge.");
  node v0 = source(e);
  node w0 = target(e);
  node v = source(e1);
  node w = target(e2);
  pre_move_edge_handler(e,v,w);
  del_adj_edge(e,source(e),target(e));
  e->term[0] = v;
  e->term[1] = w;
  ins_adj_edge(e,v,e1,w,e2,d1,d2);
  post_move_edge_handler(e,v0,w0);
 }

void graph::move_edge(edge e,edge e1,node w,int dir)
{ if (is_hidden(e)) 
       error_handler(1,"graph::move_edge:  cannot move hidden edge.");
  node v0 = source(e);
  node w0 = target(e);
  node v = source(e1);
  pre_move_edge_handler(e,v,w);
  del_adj_edge(e,source(e),target(e));
  e->term[0] = v;
  e->term[1] = w;
  ins_adj_edge(e,source(e1),e1,w,nil,dir,0);
  post_move_edge_handler(e,v0,w0);
}

void graph::move_edge(edge e, node v, node w)
{ if (is_hidden(e)) 
       error_handler(1,"graph::move_edge:  cannot move hidden edge.");
  node v0 = source(e);
  node w0 = target(e);
  pre_move_edge_handler(e,v,w);
  del_adj_edge(e,source(e),target(e));
  e->term[0] = v;
  e->term[1] = w;
  ins_adj_edge(e,v,nil,w,nil,0,0);
  post_move_edge_handler(e,v0,w0);
 }


edge graph::rev_edge(edge e)
{ if (is_hidden(e)) 
       error_handler(1,"graph::move_edge:  cannot move hidden edge.");
  node v = source(e);
  node w = target(e);

  pre_move_edge_handler(e,w,v);

  if (is_hidden(e)) // e hidden
  { e->term[0] = w;
    e->term[1] = v;
    return e;
   }

  if (undirected)
  { edge s = e->succ_adj_edge[0];
    edge p = e->pred_adj_edge[0];
    e->succ_adj_edge[0] = e->succ_adj_edge[1]; 
    e->pred_adj_edge[0] = e->pred_adj_edge[1]; 
    e->succ_adj_edge[1] = s;
    e->pred_adj_edge[1] = p;
    e->term[0] = w;
    e->term[1] = v;
   }
  else
  { del_adj_edge(e,v,w);
    e->term[0] = w;
    e->term[1] = v;
    ins_adj_edge(e,w,nil,v,nil,0,0);
   }

  post_move_edge_handler(e,v,w);

  return e; 
}


void graph::rev_all_edges()              
{ if (!undirected) 
  { list<edge> L = all_edges();
    edge e;
    forall(e,L) rev_edge(e);
   }
}


void graph::del_nodes(const list<node>& L) 
{ node v;
  forall(v,L) del_node(v);
 }

void graph::del_edges(const list<edge>& L) 
{ edge e;
  forall(e,L) del_edge(e);
 }

void graph::make_undirected()
{
  if (undirected) return; 

  list<edge> loops;
  edge e;
 
  forall_edges(e,*this)
    if (source(e) == target(e))  loops.append(e);
 
  if ( ! loops.empty() )
      error_handler(0,"selfloops deleted in ugraph constructor");

  forall(e,loops) del_edge(e);


  /* adj_list(v) = out_list(v) + in_list(v) forall nodes v  */

  node v;
  forall_nodes(v,*this)
  { 
    // append in_list to adj_list

    if (v->first_adj_edge[1] == nil) continue;


    if (v->first_adj_edge[0] == nil) // move in_list to adj_list
      { v->first_adj_edge[0] = v->first_adj_edge[1];
        v->last_adj_edge[0]  = v->last_adj_edge[1];
        v->adj_length[0]     = v->adj_length[1];
       }
    else // both lists are non-empty
      { v->last_adj_edge[0]->succ_adj_edge[0] = v->first_adj_edge[1];
        v->first_adj_edge[1]->pred_adj_edge[1] = v->last_adj_edge[0];
        v->last_adj_edge[0] = v->last_adj_edge[1];
        v->adj_length[0] += v->adj_length[1];
       }

    v->first_adj_edge[1] = nil;
    v->last_adj_edge[1] = nil;
    v->adj_length[1] = 0;

   }

  undirected = true; 
}


void graph::make_directed()
{ 
  if (!undirected) return;

  // for every node v delete entering edges from adj_list(v)
  // and put them back into in_list(v)

  node v;
  forall_nodes(v,*this)
  { edge e = v->first_adj_edge[0];
    while (e)
      if (v == target(e))
         { edge e1 = e->succ_adj_edge[1];
           v->del_adj_edge(e,0,1);
           v->append_adj_edge(e,1,1); 
           e = e1;
          }
      else 
         e = e->succ_adj_edge[0];
   }

  undirected = false; 

}



void init_node_data(const graph& G,int i, GenPtr x)
{ node v;
  forall_nodes(v,G) v->data[i] = x;
 }



int graph::register_map(graph_map* M)
{ int k = M->kind;

  M->g_loc = map_list[k].append(M);

#if defined(LEDA_GRAPH_DATA)
  if  (free_data[k].empty())  
     error_handler(1,
        string("graph::register_map: all data (%d) slots used",data_sz[k]));
#endif

  return (free_data[k].empty()) ? -1 : free_data[k].pop(); 
}


void graph::unregister_map(graph_map* M)
{ int k = M->kind;
  map_list[k].del_item(M->g_loc);
  if (M->g_index > 0) free_data[k].push(M->g_index);
}




node graph::choose_node() const
{ int n = number_of_nodes();
  if (n == 0) return nil;
  int r = rand_int(0,n-1);
  node v = first_node();
  while (r--) v = succ_node(v);
  return v;
}


edge graph::choose_edge() const
{ int m = number_of_edges();
  if (m == 0) return nil;
  int r = rand_int(0,m-1);
  edge e = first_edge();
  while (r--) e = succ_edge(e);
  return e;
}


face graph::choose_face() const
{ int l = number_of_faces();
  if (l == 0) return nil;
  int r = rand_int(0,l-1);
  face f = first_face();
  while (r--) f = succ_face(f);
  return f;
}



//------------------------------------------------------------------------------
// old iterator stuff
//------------------------------------------------------------------------------

void graph::init_adj_iterator(node v) const 
{ adj_iterator->map_access(v) = nil; }

bool  graph::current_adj_edge(edge& e, node v) const 
{ return (e = (edge)adj_iterator->map_access(v)) != nil;}

bool  graph::next_adj_edge(edge& e, node v) const 
{ edge cur = (edge)adj_iterator->map_access(v);
  e = (cur) ? adj_succ(cur) : first_adj_edge(v);
  adj_iterator->map_access(v) = e;
  return  (e) ? true : false;
 }

bool graph::next_adj_node(node& w, node v)  const
{ edge e;
  if (next_adj_edge(e,v))
  { w = opposite(v,e);
    return true; 
   }
  else return false;
 }
   
bool graph::current_adj_node(node& w, node v)  const
{ edge e;
  if (current_adj_edge(e,v))
  { w = opposite(v,e);
    w = target(e);
    return true; 
   }
  else return false;
}
   

void graph::reset()  const   // reset all iterators
{ adj_iterator->init(this,max_n_index+1,0); 
  node v;
  forall_nodes(v,*this) adj_iterator->map_access(v) = nil;
}
 
