home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph / _g_updat.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  4.0 KB  |  210 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _g_update.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #include <LEDA/graph.h>
  18.  
  19.  
  20. list(edge) graph::insert_reverse_edges()
  21. { list(edge) L = E;
  22.   list(edge) result;
  23.   edge e;
  24.   forall(e,L)
  25.   { result.append(new_edge(e->t,e->s,e->contents));
  26.     copy_edge_entry(e->contents);
  27.    }
  28.   return result;
  29. }
  30.  
  31.  
  32.  
  33. void graph::make_undirected()     
  34. { edge e;
  35.   node v;
  36.   forall(v,V) v->adj_edges.init_iterator();
  37.   forall(e,E)
  38.     if (e->adj_loc2==0)  
  39.         e->adj_loc2 = e->t->adj_edges.append(e);
  40.  }
  41.  
  42. void graph::make_directed()     
  43. { edge e;
  44.   node v;
  45.   forall(v,V) v->adj_edges.init_iterator();
  46.   forall(e,E) 
  47.    if (e->adj_loc2)  
  48.     {  e->t->adj_edges.del(e->adj_loc2);
  49.        e->adj_loc2 = 0;
  50.      }
  51.  }
  52.  
  53.  
  54. /*   // entry for subgraphs
  55.  
  56. ent&  graph::entry(node v)     
  57. { graph* g = this;
  58.   while (g->parent)   // v is subgraph node
  59.   { v = node(v->contents);
  60.     g = g->parent; 
  61.    }
  62.   return v->contents; 
  63.  }
  64.  
  65. ent&  graph::entry(edge e)     
  66. { graph* g = this;
  67.   while (g->parent)   // e is subgraph edge 
  68.   { e = edge(e->contents);
  69.     g = g->parent; 
  70.    }
  71.   return e->contents; 
  72.  }
  73.  
  74. */
  75.  
  76.  
  77. void graph::reset()  const   // reset all iterators
  78. { node v;
  79.   forall(v,V) v->adj_edges.init_iterator();
  80.   V.init_iterator();
  81.   E.init_iterator();
  82. }
  83.  
  84. node graph::new_node(ent i)
  85. { 
  86.   node v = new i_node(i); 
  87.   v->g = this;
  88.   v->i_name = ++max_node_index;
  89.   v->loc = V.append(v);
  90.   return v;
  91. }
  92.  
  93. void graph::del_node(node v)
  94. { if (v->g != this) error_handler(4,"del_node: v is not in G");
  95.  
  96.   // delete adjacent edges
  97.   while (!v->adj_edges.empty()) del_edge(v->adj_edges.head());
  98.  
  99.   list_item loc;
  100.   edge e;
  101.   if (v->indegree) 
  102.   { error_handler(0,
  103.     "del_node: indeg >0 , I delete incoming edges (time: O(|E|))");
  104.  
  105.     loc = E.first();
  106.     while (loc) { e = E[loc];
  107.                   loc = E.succ(loc);
  108.                   if (e->t == v) del_edge(e); } 
  109.    } 
  110.  
  111.   V.del(v->loc);
  112.  
  113.   if (parent==0)   // no subgraph
  114.     clear_node_entry(v->contents);
  115.  
  116.   delete v;
  117. }
  118.  
  119. edge graph::new_edge(node v, node w, ent i)
  120. { // add edge (v,w) to G
  121.  
  122.   if ((v->g!=this) || (w->g!=this)) 
  123.   error_handler(6, "G.new_edge(v,w): v or w not in G");
  124.  
  125.  
  126.   edge e = new i_edge(v,w,i);
  127.  
  128.   e->i_name = ++max_edge_index;
  129.   e->loc = E.append(e);
  130.   e->adj_loc=v->adj_edges.append(e);
  131.   e->adj_loc2 = 0;
  132.   w->indegree++;
  133.   return e ; 
  134. }
  135.  
  136. edge graph::new_edge(edge e1, node w, ent i, int dir=0)  
  137. { //add edge (source(e1),w) e after/before e1 
  138.  
  139.   node v  = e1->s;
  140.  
  141.   if ((v->g!=this) || (w->g!=this)) 
  142.      error_handler(9,"G.new_edge(e,w): e or w not in G");
  143.  
  144.  
  145.   edge e = new i_edge(v,w,i);
  146.  
  147.   e->i_name = ++max_edge_index;
  148.   e->loc = E.append(e);
  149.   e->adj_loc=v->adj_edges.insert(e,e1->adj_loc,dir);
  150.   e->adj_loc2 = 0;
  151.   w->indegree++;
  152.   return e ; 
  153. }
  154.  
  155. void graph::del_edge(edge e)
  156. { node v = e->s;
  157.   node w = e->t;
  158.  
  159.   if (v->g != this) error_handler(10,"del_edge: e is not in G");
  160.      
  161.   E.del(e->loc);
  162.  
  163.   v->adj_edges.del(e->adj_loc);
  164.  
  165.   if (e->adj_loc2)                  //undirected edge
  166.   w->adj_edges.del(e->adj_loc2);
  167.  
  168.   w->indegree--;
  169.  
  170.   e->i_name = -1;
  171.  
  172.   if (parent == 0)  // no subgraph
  173.      clear_edge_entry(e->contents);
  174.  
  175.   delete e; 
  176. }
  177.  
  178. edge graph::rev_edge(edge e)
  179. { if (e->adj_loc2) return e;  //undirected edge
  180.   node v = e->s;
  181.   node w = e->t;
  182.   if (v->g != this) error_handler(11,"rev_edge: e is not in G");
  183.   v->adj_edges.del(e->adj_loc);
  184.   e->adj_loc = w->adj_edges.append(e);
  185.   w->indegree--;
  186.   v->indegree++;
  187.   e->s = w;
  188.   e->t = v;
  189.   return(e); 
  190. }
  191.  
  192. graph& graph::rev()              
  193. { edge e;
  194.   forall(e,E) rev_edge(e);
  195.   return *this; 
  196. }
  197.  
  198. void graph::del_all_nodes() { clear(); }
  199.  
  200. void graph::del_all_edges()
  201. { node v;
  202.   forall(v,V)
  203.   { v->adj_edges.clear();
  204.     v->indegree=0;
  205.    }
  206.   while (!E.empty()) delete E.pop();
  207.   max_edge_index = -1;
  208. }
  209.  
  210.