_graph.c

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

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



#include <LEDA/graph.h>

// constructors, destructor, operator=, ...

graph::graph() 
{ max_node_index = -1;
  max_edge_index = -1; 
  parent = 0; 
  undirected = false;
 }


graph& graph::operator=(const graph& G)
{ node v,w;
  edge e,e1;

  if (&G == this) return *this;

  node* node_vec = new node[G.max_node_index+1];

  edge* edge_vec = new edge[G.max_edge_index+1];

  clear();

  forall_nodes(v,G) 
    node_vec[v->i_name] = new_node(v->contents);
                             
  forall_edges(e,G) 
   { v = node_vec[e->s->i_name];
     w = node_vec[e->t->i_name];
     edge_vec[e->i_name] = e1 = new i_edge(v,w,e->contents);
     e1->loc = E.append(e1);
     e1->i_name = ++max_edge_index;
     w->indegree++;
    }

  forall_nodes(v,G) 
  forall_adj_edges(e,v)
  { e1 = edge_vec[e->i_name];
    if (v == e->s && e1->adj_loc == nil) 
      e1->adj_loc  = node_vec[v->i_name]->adj_edges.append(e1);
    else 
      e1->adj_loc2 = node_vec[v->i_name]->adj_edges.append(e1);
   }

  forall_nodes(v,*this) init_adj_iterator(v); 

  parent = G.parent;
  undirected = G.undirected;

  delete node_vec;
  delete edge_vec;

  return *this;
}


void graph::copy_all_entries() const
{ node v;
  edge e;
  forall(v,V) copy_node_entry(v->contents);
  forall(e,E) copy_edge_entry(e->contents);
}

void graph::clear_all_entries() const
{ node v;
  edge e;
  forall(v,V) clear_node_entry(v->contents);
  forall(e,E) clear_edge_entry(e->contents);
}


graph::graph(const graph& G)  
{ node v,w;
  edge e,e1;
  node* node_vec = new node[G.max_node_index+1];
  edge* edge_vec = new edge[G.max_edge_index+1];


  max_node_index = max_edge_index = -1;

  forall_nodes(v,G) 
    node_vec[v->i_name] = new_node(v->contents);
                             
  forall_edges(e,G) 
   { v = node_vec[e->s->i_name];
     w = node_vec[e->t->i_name];
     edge_vec[e->i_name] = e1 = new i_edge(v,w,e->contents);
     e1->loc = E.append(e1);
     e1->i_name = ++max_edge_index;
     w->indegree++;
    }

  forall_nodes(v,G) 
  forall_adj_edges(e,v)
  { e1 = edge_vec[e->i_name];
    if (v == e->s && e1->adj_loc == nil) 
      e1->adj_loc  = node_vec[v->i_name]->adj_edges.append(e1);
    else 
      e1->adj_loc2 = node_vec[v->i_name]->adj_edges.append(e1);
   }


  forall_nodes(v,*this) init_adj_iterator(v); 

  parent = G.parent;
  undirected = G.undirected;

  delete node_vec;
  delete edge_vec;

}


// subgraph constructors  (do not work for undirected graphs)

graph::graph(graph& G, const list<node>& nl, const list<edge>& el)
{ // construct subgraph (nl,el) of graph G

  parent = &G;
  node v,w;
  edge e;

  node* N = new node[G.max_node_index+1];

  forall(v,nl)
   { if (graph_of(v) != parent) 
      error_handler(1,"graph: illegal node in subgraph constructor");
     N[v->i_name] = new_node((GenPtr)v);
    }

  forall(e,el)
   { v = source(e);
     w = target(e);
     if ( graph_of(e)!= parent || N[v->i_name]==0 || N[w->i_name]==0 ) 
      error_handler(1,"graph: illegal edge in subgraph constructor");
     new_edge(N[v->i_name],N[w->i_name],(GenPtr)e);
    }

  undirected = G.undirected;

  delete N;

 }

graph::graph(graph& G, const list<edge>& el)
{ /* construct subgraph of graph G with edge set el  */

  node  v,w;
  edge  e;
  node* N = new node[G.max_node_index+1];

  forall(v,G.V) N[v->i_name] = 0;

  parent = &G;

  forall(e,el)
   { v = source(e);
     w = target(e);
     if (N[v->i_name] == 0) N[v->i_name] = new_node((GenPtr)v);
     if (N[w->i_name] == 0) N[w->i_name] = new_node((GenPtr)w);
     if ( graph_of(e) != parent )
      error_handler(1,"graph: illegal edge in subgraph constructor");
     new_edge(N[v->i_name],N[w->i_name],(GenPtr)e);
    }

  undirected = G.undirected;

  delete N;

 }


// destructor

void graph::clear()
{ node v;
  edge e;

  forall(e,E) delete e;

  forall(v,V) 
  { v->adj_edges.clear();
    delete v;
   }

  V.clear();
  E.clear();

  max_node_index = max_edge_index = -1;
}


list<edge> graph::all_edges()       const { return E; }
list<edge> graph::adj_edges(node v) const { return v->adj_edges; }
list<node> graph::all_nodes()       const { return V; }


list<node> graph::adj_nodes(node v) const
{ list<node> result;
  edge e;
  forall(e,v->adj_edges) result.append(target(e));
  return result;
}


int  graph::space() const
{ int vs = sizeof(dlink) + sizeof(i_node);
  int es = 2*sizeof(dlink) + sizeof(i_edge);
  return V.length()*vs + E.length()*es + 48;  
}