home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph / _graph.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  4.9 KB  |  234 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _graph.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. // constructors, destructor, operator=, ...
  20.  
  21. graph::graph() 
  22. { max_node_index = -1;
  23.   max_edge_index = -1; 
  24.   parent = 0; 
  25.   undirected = false;
  26.  }
  27.  
  28.  
  29. graph& graph::operator=(const graph& G)
  30. { node v,w;
  31.   edge e,e1;
  32.   node* node_vec = new node[G.max_node_index+1];
  33.  
  34.   edge* edge_vec = new edge[G.max_edge_index+1];
  35.  
  36.   clear();
  37.  
  38.  
  39.   forall_nodes(v,G) 
  40.   { copy_node_entry(v->contents);
  41.     node_vec[v->i_name] = new_node(v->contents);
  42.    }
  43.                              
  44.   forall_edges(e,G) 
  45.    { v = node_vec[e->s->i_name];
  46.      w = node_vec[e->t->i_name];
  47.      copy_edge_entry(e->contents);
  48.      edge_vec[e->i_name] = e1 = new i_edge(v,w,e->contents);
  49.      e1->loc = E.append(e1);
  50.      e1->i_name = ++max_edge_index;
  51.      w->indegree++;
  52.     }
  53.  
  54.   forall_nodes(v,G) 
  55.   forall_adj_edges(e,v)
  56.   { e1 = edge_vec[e->i_name];
  57.     if (v == e->s && e1->adj_loc == nil) 
  58.       e1->adj_loc  = node_vec[v->i_name]->adj_edges.append(e1);
  59.     else 
  60.       e1->adj_loc2 = node_vec[v->i_name]->adj_edges.append(e1);
  61.    }
  62.  
  63.   forall_nodes(v,*this) init_adj_iterator(v); 
  64.  
  65.   parent = G.parent;
  66.   undirected = G.undirected;
  67.  
  68.   delete node_vec;
  69.   delete edge_vec;
  70.  
  71.   return *this;
  72. }
  73.  
  74.  
  75. void graph::copy_all_entries()
  76. { node v;
  77.   edge e;
  78.   forall(v,V) copy_node_entry(v->contents);
  79.   forall(e,E) copy_edge_entry(e->contents);
  80. }
  81.  
  82.  
  83. graph::graph(const graph& G)  
  84. { node v,w;
  85.   edge e,e1;
  86.   node* node_vec = new node[G.max_node_index+1];
  87.   edge* edge_vec = new edge[G.max_edge_index+1];
  88.  
  89.  
  90.   max_node_index = max_edge_index = -1;
  91.  
  92.   forall_nodes(v,G) node_vec[v->i_name] = new_node(v->contents);
  93.                              
  94.   forall_edges(e,G) 
  95.    { v = node_vec[e->s->i_name];
  96.      w = node_vec[e->t->i_name];
  97.      copy_edge_entry(e->contents);
  98.      edge_vec[e->i_name] = e1 = new i_edge(v,w,e->contents);
  99.      e1->loc = E.append(e1);
  100.      e1->i_name = ++max_edge_index;
  101.      w->indegree++;
  102.     }
  103.  
  104.   forall_nodes(v,G) 
  105.   forall_adj_edges(e,v)
  106.   { e1 = edge_vec[e->i_name];
  107.     if (v == e->s && e1->adj_loc == nil) 
  108.       e1->adj_loc  = node_vec[v->i_name]->adj_edges.append(e1);
  109.     else 
  110.       e1->adj_loc2 = node_vec[v->i_name]->adj_edges.append(e1);
  111.    }
  112.  
  113.  
  114.   forall_nodes(v,*this) init_adj_iterator(v); 
  115.  
  116.   parent = G.parent;
  117.   undirected = G.undirected;
  118.  
  119.   delete node_vec;
  120.   delete edge_vec;
  121.  
  122. }
  123.  
  124.  
  125. // subgraph constructors  (do not work for undirected graphs)
  126.  
  127. graph::graph(graph& G, list(node)& nl, list(edge)& el)
  128. { // construct subgraph (nl,el) of graph G
  129.  
  130.   parent = &G;
  131.   node v,w;
  132.   edge e;
  133.  
  134.   node* N = new node[G.max_node_index+1];
  135.  
  136.   forall(v,nl)
  137.    { if (graph_of(v) != parent) 
  138.       error_handler(1,"graph: illegal node in subgraph constructor");
  139.      N[v->i_name] = new_node((ent)v);
  140.     }
  141.  
  142.   forall(e,el)
  143.    { v = source(e);
  144.      w = target(e);
  145.      if ( graph_of(e)!= parent || N[v->i_name]==0 || N[w->i_name]==0 ) 
  146.       error_handler(1,"graph: illegal edge in subgraph constructor");
  147.      new_edge(N[v->i_name],N[w->i_name],(ent)e);
  148.     }
  149.  
  150.   undirected = G.undirected;
  151.  
  152.   delete N;
  153.  
  154.  }
  155.  
  156. graph::graph(graph& G, list(edge)& el)
  157. { /* construct subgraph of graph G with edge set el  */
  158.  
  159.   node  v,w;
  160.   edge  e;
  161.   node* N = new node[G.max_node_index+1];
  162.  
  163.   forall(v,G.V) N[v->i_name] = 0;
  164.  
  165.   parent = &G;
  166.  
  167.   forall(e,el)
  168.    { v = source(e);
  169.      w = target(e);
  170.      if (N[v->i_name] == 0) N[v->i_name] = new_node((ent)v);
  171.      if (N[w->i_name] == 0) N[w->i_name] = new_node((ent)w);
  172.      if ( graph_of(e) != parent )
  173.       error_handler(1,"graph: illegal edge in subgraph constructor");
  174.      new_edge(N[v->i_name],N[w->i_name],(ent)e);
  175.     }
  176.  
  177.   undirected = G.undirected;
  178.  
  179.   delete N;
  180.  
  181.  }
  182.  
  183.  
  184. // destructor
  185.  
  186. void graph::clear()
  187. { node v;
  188.   edge e;
  189.  
  190.   if (parent==0)  // no subgraph
  191.   {
  192.    forall(e,E) { clear_edge_entry(e->contents);
  193.                  delete e;
  194.                 }
  195.    forall(v,V) { clear_node_entry(v->contents);
  196.                  v->adj_edges.clear();
  197.                  delete v;
  198.                 }
  199.   }
  200.   else           // subgraph
  201.   { 
  202.     forall(e,E) delete e;
  203.     forall(v,V) { v->adj_edges.clear();
  204.                   delete v;
  205.                  }
  206.    }
  207.  
  208.   V.clear();
  209.   E.clear();
  210.  
  211.   max_node_index = max_edge_index = -1;
  212. }
  213.  
  214.  
  215. list(node) graph::all_nodes()       const { return V; }
  216. list(edge) graph::all_edges()       const { return E; }
  217. list(edge) graph::adj_edges(node v) const { return v->adj_edges; }
  218.  
  219.  
  220. list(node) graph::adj_nodes(node v) const
  221. { list(node) result;
  222.   edge e;
  223.   forall(e,v->adj_edges) result.append(target(e));
  224.   return result;
  225. }
  226.  
  227.  
  228. int  graph::space() const
  229. { int vs = sizeof(dlink) + sizeof(i_node);
  230.   int es = 2*sizeof(dlink) + sizeof(i_edge);
  231.   return V.length()*vs + E.length()*es + 48;  
  232. }
  233.  
  234.