Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
_graph.c
Package: leda.tar.gz　[view]
Upload User: gzelex
Upload Date: 2007-01-07
Package Size: 707k
Code Size: 4k
Category:

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

_graph.c：Code Content
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _graph.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  15. #include <LEDA/graph.h>
  17. // constructors, destructor, operator=, ...
  19. graph::graph() 
  20. { max_n_index = -1;
  21.   max_e_index = -1; 
  22.   parent = 0; 
  23.   undirected = false;
  24.  }
  27. graph& graph::operator=(const graph& G)
  28. { 
  29.   if (&G == this) return *this;
  31.   clear();
  33.   node* node_vec = new node[G.max_n_index+1];
  34.   edge* edge_vec = new edge[G.max_e_index+1];
  36.   node v;
  37.   forall_nodes(v,G) 
  38.      node_vec[v->name] = new_node(v->data[0]);
  40.   edge e;
  41.   forall_nodes(v,G) 
  42.     forall_out_edges(e,v) 
  43.        edge_vec[e->name] = new_edge(node_vec[e->s->name],
  44.                                     node_vec[e->t->name], e->data[0]);
  46.   parent = G.parent;
  47.   undirected = G.undirected;
  49.   delete node_vec;
  50.   delete edge_vec;
  52.   return *this;
  53. }
  56. void graph::copy_all_entries() const
  57. { node v;
  58.   forall_nodes(v,*this) copy_node_entry(v->data[0]);
  59.   edge e;
  60.   forall_edges(e,*this) copy_edge_entry(e->data[0]);
  61. }
  63. void graph::clear_all_entries() const
  64. { node v;
  65.   forall_nodes(v,*this) clear_node_entry(v->data[0]);
  66.   edge e;
  67.   forall_edges(e,*this) clear_edge_entry(e->data[0]);
  68. }
  71. graph::graph(const graph& G)  
  72. { 
  73.   node* node_vec = new node[G.max_n_index+1];
  74.   edge* edge_vec = new edge[G.max_e_index+1];
  76.   max_n_index = max_e_index = -1;
  78.   node v;
  79.   forall_nodes(v,G) 
  80.      node_vec[v->name] = new_node(v->data[0]);
  82.   edge e;
  83.   forall_nodes(v,G) 
  84.     forall_out_edges(e,v) 
  85.        edge_vec[e->name] = new_edge(node_vec[e->s->name],
  86.                                     node_vec[e->t->name], e->data[0]);
  88.   parent = G.parent;
  89.   undirected = G.undirected;
  91.   delete node_vec;
  92.   delete edge_vec;
  93. }
  96. // subgraph constructors  (do not work for undirected graphs)
  98. graph::graph(graph& G, const list<node>& nl, const list<edge>& el)
  99. { // construct subgraph (nl,el) of graph G
  101.   parent = &G;
  102.   node v,w;
  103.   edge e;
  105.   node* N = new node[G.max_n_index+1];
  107.   forall(v,nl)
  108.    { if (graph_of(v) != parent) 
  109.       error_handler(1,"graph: illegal node in subgraph constructor");
  110.      N[v->name] = new_node((GenPtr)v);
  111.     }
  113.   forall(e,el)
  114.    { v = source(e);
  115.      w = target(e);
  116.      if ( graph_of(e)!= parent || N[v->name]==0 || N[w->name]==0 ) 
  117.       error_handler(1,"graph: illegal edge in subgraph constructor");
  118.      new_edge(N[v->name],N[w->name],(GenPtr)e);
  119.     }
  121.   undirected = G.undirected;
  123.   delete N;
  125.  }
  127. graph::graph(graph& G, const list<edge>& el)
  128. { /* construct subgraph of graph G with edge set el  */
  130.   node  v,w;
  131.   edge  e;
  132.   node* N = new node[G.max_n_index+1];
  134.   forall_nodes(v,G) N[v->name] = 0;
  136.   parent = &G;
  138.   forall(e,el)
  139.    { v = source(e);
  140.      w = target(e);
  141.      if (N[v->name] == 0) N[v->name] = new_node((GenPtr)v);
  142.      if (N[w->name] == 0) N[w->name] = new_node((GenPtr)w);
  143.      if ( graph_of(e) != parent )
  144.       error_handler(1,"graph: illegal edge in subgraph constructor");
  145.      new_edge(N[v->name],N[w->name],(GenPtr)e);
  146.     }
  148.   undirected = G.undirected;
  150.   delete N;
  152.  }
  155. // destructor
  157. void graph::clear()
  158. { 
  159.   while ( ! E.empty() ) 
  160.     delete edge(edge_link(E.pop()));
  162.   while ( ! V.empty() ) 
  163.   { node v = node(node_link(V.pop()));
  164.     v->adj_edges[0].clear();
  165.     v->adj_edges[1].clear();
  166.     delete v;
  167.    }
  169.   max_n_index = max_e_index = -1;
  170. }
  172. list<node> graph::all_nodes() const
  173. { list<node> result;
  174.   node v;
  175.   forall_nodes(v,*this) result.append(v);
  176.   return result;
  177. }
  179. list<edge> graph::all_edges() const
  180. { list<edge> result;
  181.   edge e;
  182.   forall_edges(e,*this) result.append(e);
  183.   return result;
  184. }
  186. list<edge> graph::adj_edges(node v) const
  187. { list<edge> result;
  188.   edge e;
  189.   forall_adj_edges(e,v) result.append(e);
  190.   return result;
  191. }
  193. list<edge> graph::in_edges(node v) const
  194. { list<edge> result;
  195.   edge e;
  196.   forall_in_edges(e,v) result.append(e);
  197.   return result;
  198. }
  202. list<node> graph::adj_nodes(node v) const
  203. { list<node> result;
  204.   edge e;
  205.   forall_adj_edges(e,v) result.append(opposite(v,e));
  206.   return result;
  207. }
  211. void init_node_data(const graph& G,int i, GenPtr x)
  212. { node v;
  213.   forall_nodes(v,G) v->data[i] = x;
  214.  }