home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph / _ugraph.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  4.9 KB  |  204 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _ugraph.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. #include <LEDA/ugraph.h>
  17.  
  18. //------------------------------------------------------------------------------
  19. // undirected graphs 
  20. //------------------------------------------------------------------------------
  21.  
  22. void  ugraph::print_edge(edge e,ostream& o) const
  23. { o <<   "[" << e->s->i_name << "]==";
  24.   print_edge_entry(o,e->contents);
  25.   o << "==[" << e->t->i_name << "]";
  26.  }
  27.  
  28. edge ugraph::new_edge(node v, node w, ent i) 
  29. { 
  30.  
  31. /*
  32.   if (v==w) error_handler(99,ugraph::new_edge: self-loop");
  33. */
  34.  
  35.   if ((v->g!=this) || (w->g!=this)) 
  36.   error_handler(1, "ugraph::new_edge(v,w): v or w  not in G ");
  37.  
  38.   edge e = graph::new_edge(v,w,i);
  39.   e->adj_loc2 = w->adj_edges.append(e);
  40.   return e;
  41.  }
  42.  
  43. edge ugraph::new_edge(node v,node w,edge e1,edge e2,ent i,int d1,int d2) 
  44. { 
  45.  
  46. /*
  47.   if (v==w) error_handler(99,ugraph::new_edge: self-loop");
  48. */
  49.  
  50.   if ((v->g!=this) || (w->g!=this)) 
  51.   error_handler(1, "ugraph::new_edge(v,w): v or w  not in G ");
  52.  
  53.   edge e = new i_edge(v,w,i);
  54.  
  55.   e->i_name = ++max_edge_index;
  56.   w->indegree++;
  57.   e->loc = E.append(e);
  58.  
  59.   if (v==e1->s)
  60.       e->adj_loc=v->adj_edges.insert(e,e1->adj_loc,d1);
  61.   else 
  62.       if (v==e1->t) 
  63.           e->adj_loc=v->adj_edges.insert(e,e1->adj_loc2,d1);
  64.       else 
  65.           error_handler(1,"ugraph::new_edge: e1 not adjacent to v.");
  66.  
  67.  
  68.   if (w==e2->s) 
  69.       e->adj_loc2 = w->adj_edges.insert(e,e2->adj_loc,d2);
  70.   else 
  71.       if (w==e2->t) 
  72.           e->adj_loc2 = w->adj_edges.insert(e,e2->adj_loc2,d2);
  73.       else 
  74.           error_handler(1,"ugraph::new_edge: e2 not adjacent to w.");
  75.  
  76.   return e;
  77.  }
  78.  
  79.  
  80.  
  81. list(node) ugraph::adj_nodes(node v) const
  82. { list(node) result;
  83.   edge e;
  84.   forall(e,v->adj_edges) result.append(opposite(v,e));
  85.   return result;
  86. }
  87.  
  88. // ugraph subgraph constructors:
  89.  
  90. ugraph::ugraph(ugraph& G, list(node)& nl, list(edge)& el)
  91. { // construct subugraph (nl,el) of ugraph G
  92.  
  93.   parent = &G;
  94.   node v,w;
  95.   edge e;
  96.  
  97.   node* N = new node[G.max_node_index+1];
  98.  
  99.   forall(v,nl)
  100.    { if (graph_of(v) != parent) 
  101.       error_handler(1,"ugraph: illegal node in subgraph constructor");
  102.      N[v->i_name] = new_node((ent)v);
  103.     }
  104.  
  105.   forall(e,el)
  106.    { v = source(e);
  107.      w = target(e);
  108.      if ( graph_of(e)!= parent || N[v->i_name]==0 || N[w->i_name]==0 ) 
  109.       error_handler(1,"ugraph: illegal edge in subgraph constructor");
  110.      new_edge(N[v->i_name],N[w->i_name],(ent)e);
  111.     }
  112.  
  113.   delete N;
  114.  
  115.  }
  116.  
  117. ugraph::ugraph(ugraph& G, list(edge)& el)
  118. { // construct subgraph of ugraph G with edgelist el 
  119.  
  120.   node  v,w;
  121.   edge  e;
  122.   node* N = new node[G.max_node_index+1];
  123.  
  124.   forall(v,G.V) N[v->i_name] = 0;
  125.  
  126.   parent = &G;
  127.  
  128.   forall(e,el)
  129.    { v = source(e);
  130.      w = target(e);
  131.      if (N[v->i_name] == 0) N[v->i_name] = new_node((ent)v);
  132.      if (N[w->i_name] == 0) N[w->i_name] = new_node((ent)w);
  133.      if ( graph_of(e) != parent )
  134.       error_handler(1,"ugraph: illegal edge in subgraph constructor");
  135.      new_edge(N[v->i_name],N[w->i_name],(ent)e);
  136.     }
  137.  
  138.   delete N;
  139.  
  140.  }
  141.  
  142. node ugraph::opposite(node v, edge e)  const
  143. { if (v==e->s) return e->t;
  144.   if (v==e->t) return e->s;
  145.   return 0;
  146.  }
  147.  
  148. edge ugraph::adj_succ(edge e,node v)  const
  149. { list_item loc;
  150.  
  151.   if (e->s == e->t)  
  152.        error_handler(9999,"ugraph::adj_succ: self-loop");
  153.  
  154.   if (v == e->s) 
  155.     loc = e->s->adj_edges.succ(e->adj_loc);
  156.   else if (v == e->t) 
  157.          loc = e->s->adj_edges.succ(e->adj_loc2);
  158.        else error_handler(9999,"adj_succ: v is no endpoint of e");
  159.   return (loc) ? e->s->adj_edges[loc] : 0;
  160. }
  161.  
  162. edge ugraph::adj_pred(edge e,node v)  const
  163. { list_item loc;
  164.  
  165.   if (e->s == e->t)  
  166.        error_handler(9999,"ugraph::adj_pred: self-loop");
  167.  
  168.   if (v == e->s) 
  169.      loc = e->s->adj_edges.pred(e->adj_loc);
  170.   else if (v == e->t) 
  171.          loc = e->s->adj_edges.pred(e->adj_loc2);
  172.        else error_handler(9999,"ugraph::adj_pred: v is no endpoint of e");
  173.   return (loc) ? e->s->adj_edges[loc] : 0;
  174.  }
  175.  
  176. edge ugraph::cyclic_adj_succ(edge e,node v)  const
  177. { list_item loc;
  178.  
  179.   if (e->s == e->t)  
  180.        error_handler(9999,"ugraph::cyclic_adj_succ: self-loop");
  181.  
  182.   if (v == e->s)
  183.     loc =  v->adj_edges.cyclic_succ(e->adj_loc);
  184.   else if (v == e->t)
  185.          loc =  v->adj_edges.cyclic_succ(e->adj_loc2);
  186.        else error_handler(9999,"ugraph::cyclic_adj_succ: v is no endpoint of e");
  187.   return v->adj_edges[loc];
  188.  }
  189.  
  190. edge ugraph::cyclic_adj_pred(edge e,node v)  const
  191. { list_item loc;
  192.  
  193.   if (e->s == e->t)  
  194.        error_handler(9999,"ugraph::cyclic_adj_pred: self-loop");
  195.  
  196.   if (v == e->s)
  197.     loc =  v->adj_edges.cyclic_pred(e->adj_loc);
  198.   else if (v == e->t)
  199.          loc =  v->adj_edges.cyclic_pred(e->adj_loc2);
  200.        else error_handler(9999,"ugraph::cyclic_adj_pred: v is no endpoint of e");
  201.   return v->adj_edges[loc];
  202.  }
  203.  
  204.