_g_update.c

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

/*******************************************************************************
+
+  LEDA  3.0
+
+
+  _g_update.c
+
+
+  Copyright (c) 1992  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 6600 Saarbruecken, FRG     
+  All rights reserved.
+ 
*******************************************************************************/



#include <LEDA/graph.h>


list<edge> graph::insert_reverse_edges()
{ list<edge> L = E;
  list<edge> result;
  edge e;
  forall(e,L)
  { result.append(new_edge(e->t,e->s,e->contents));
    copy_edge_entry(e->contents);
   }
  return result;
}



void graph::make_undirected()     
{ edge e;
  reset();
  forall(e,E)
    if (e->adj_loc2==0)  
      e->adj_loc2 = e->t->adj_edges.append(e);
 }

void graph::make_directed()     
{ edge e;
  reset();
  forall(e,E) 
   if (e->adj_loc2)  
    { e->t->adj_edges.del(e->adj_loc2);
      e->adj_loc2 = 0;
     }
 }


/*   // entry for subgraphs

ent&  graph::entry(node v)     
{ graph* g = this;
  while (g->parent)   // v is subgraph node
  { v = node(v->contents);
    g = g->parent; 
   }
  return v->contents; 
 }

ent&  graph::entry(edge e)     
{ graph* g = this;
  while (g->parent)   // e is subgraph edge 
  { e = edge(e->contents);
    g = g->parent; 
   }
  return e->contents; 
 }

*/


void graph::reset()  const   // reset all iterators
{ node v;
  forall(v,V) v->adj_edges.reset();
  V.reset();
  E.reset();
}

node graph::new_node(GenPtr i)
{ 
  node v = new i_node(i); 
  v->g = this;
  v->i_name = ++max_node_index;
  v->loc = V.append(v);
  return v;
}

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

  // delete adjacent edges
  while (!v->adj_edges.empty()) del_edge(v->adj_edges.head());

  list_item loc;
  edge e;
  if (v->indegree) 
  { error_handler(0,
    "del_node: indeg >0 , I delete incoming edges (time: O(|E|))");

    loc = E.first();
    while (loc) { e = E[loc];
                  loc = E.succ(loc);
                  if (e->t == v) del_edge(e); } 
   } 

  V.del(v->loc);

  if (parent==0)   // no subgraph
    clear_node_entry(v->contents);
 
  delete v;
}

edge graph::new_edge(node v, node w, GenPtr i)
{ // add edge (v,w) to G

  if ((v->g!=this) || (w->g!=this)) 
  error_handler(6, "G.new_edge(v,w): v or w not in G");


  edge e = new i_edge(v,w,i);

  e->i_name = ++max_edge_index;
  e->loc = E.append(e);
  e->adj_loc=v->adj_edges.append(e);
  e->adj_loc2 = 0;
  w->indegree++;
  return e ; 
}

edge graph::new_edge(edge e1, node w, GenPtr i, int dir=0)  
{ //add edge (source(e1),w) e after/before e1 

  node v  = e1->s;

  if ((v->g!=this) || (w->g!=this)) 
     error_handler(9,"G.new_edge(e,w): e or w not in G");


  edge e = new i_edge(v,w,i);

  e->i_name = ++max_edge_index;
  e->loc = E.append(e);
  e->adj_loc=v->adj_edges.insert(e,e1->adj_loc,dir);
  e->adj_loc2 = 0;
  w->indegree++;
  return e ; 
}

void graph::del_edge(edge e)
{ node v = e->s;
  node w = e->t;

  if (v->g != this) error_handler(10,"del_edge: e is not in G");
     
  E.del(e->loc);

  v->adj_edges.del(e->adj_loc);

  if (e->adj_loc2)                  //undirected edge
  w->adj_edges.del(e->adj_loc2);

  w->indegree--;

  e->i_name = -1;

  if (parent == 0)  // no subgraph
     clear_edge_entry(e->contents);

  delete e; 
}

edge graph::rev_edge(edge e)
{ if (e->adj_loc2) return e;  //undirected edge
  node v = e->s;
  node w = e->t;
  if (v->g != this) error_handler(11,"rev_edge: e is not in G");
  v->adj_edges.del(e->adj_loc);
  e->adj_loc = w->adj_edges.append(e);
  w->indegree--;
  v->indegree++;
  e->s = w;
  e->t = v;
  return(e); 
}

graph& graph::rev()              
{ edge e;
  forall(e,E) rev_edge(e);
  return *this; 
}

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

void graph::del_all_edges()
{ node v;
  forall(v,V)
  { v->adj_edges.clear();
    v->indegree=0;
   }
  while (!E.empty()) delete E.pop();
  max_edge_index = -1;
}