_ugraph.c

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

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


#include <LEDA/ugraph.h>


//------------------------------------------------------------------------------
// undirected graphs 
//------------------------------------------------------------------------------

void  ugraph::print_edge(edge e,ostream& o) const
{ o <<   "[" << e->s->i_name << "]==";
  print_edge_entry(o,e->contents);
  o << "==[" << e->t->i_name << "]";
 }

edge ugraph::new_edge(node v, node w, GenPtr i) 
{ 

/*
  if (v==w) error_handler(99,ugraph::new_edge: self-loop");
*/

  if ((v->g!=this) || (w->g!=this)) 
  error_handler(1, "ugraph::new_edge(v,w): v or w  not in G ");

  edge e = graph::new_edge(v,w,i);
  e->adj_loc2 = w->adj_edges.append(e);
  return e;
 }

edge ugraph::new_edge(node v,node w,edge e1,edge e2,GenPtr i,int d1,int d2) 
{ 

/*
  if (v==w) error_handler(99,ugraph::new_edge: self-loop");
*/

  if ((v->g!=this) || (w->g!=this)) 
  error_handler(1, "ugraph::new_edge(v,w): v or w  not in G ");

  edge e = new i_edge(v,w,i);

  e->i_name = ++max_edge_index;
  w->indegree++;
  e->loc = E.append(e);

  if (v==e1->s)
      e->adj_loc=v->adj_edges.insert(e,e1->adj_loc,d1);
  else 
      if (v==e1->t) 
          e->adj_loc=v->adj_edges.insert(e,e1->adj_loc2,d1);
      else 
          error_handler(1,"ugraph::new_edge: e1 not adjacent to v.");


  if (w==e2->s) 
      e->adj_loc2 = w->adj_edges.insert(e,e2->adj_loc,d2);
  else 
      if (w==e2->t) 
          e->adj_loc2 = w->adj_edges.insert(e,e2->adj_loc2,d2);
      else 
          error_handler(1,"ugraph::new_edge: e2 not adjacent to w.");

  return e;
 }



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

// ugraph subgraph constructors:

ugraph::ugraph(ugraph& G, const list<node>& nl, const list<edge>& el)
{ // construct subugraph (nl,el) of ugraph 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,"ugraph: 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,"ugraph: illegal edge in subgraph constructor");
     new_edge(N[v->i_name],N[w->i_name],(GenPtr)e);
    }

  delete N;

 }

ugraph::ugraph(ugraph& G, const list<edge>& el)
{ // construct subgraph of ugraph G with edgelist 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,"ugraph: illegal edge in subgraph constructor");
     new_edge(N[v->i_name],N[w->i_name],(GenPtr)e);
    }

  delete N;

 }

node ugraph::opposite(node v, edge e)  const
{ if (v==e->s) return e->t;
  if (v==e->t) return e->s;
  return 0;
 }

edge ugraph::adj_succ(edge e,node v)  const
{ list_item loc;

  if (e->s == e->t)  
       error_handler(9999,"ugraph::adj_succ: self-loop");

  if (v == e->s) 
    loc = e->s->adj_edges.succ(e->adj_loc);
  else if (v == e->t) 
         loc = e->s->adj_edges.succ(e->adj_loc2);
       else error_handler(9999,"adj_succ: v is no endpoint of e");
  return (loc) ? e->s->adj_edges[loc] : 0;
}

edge ugraph::adj_pred(edge e,node v)  const
{ list_item loc;

  if (e->s == e->t)  
       error_handler(9999,"ugraph::adj_pred: self-loop");

  if (v == e->s) 
     loc = e->s->adj_edges.pred(e->adj_loc);
  else if (v == e->t) 
         loc = e->s->adj_edges.pred(e->adj_loc2);
       else error_handler(9999,"ugraph::adj_pred: v is no endpoint of e");
  return (loc) ? e->s->adj_edges[loc] : 0;
 }

edge ugraph::cyclic_adj_succ(edge e,node v)  const
{ list_item loc;

  if (e->s == e->t)  
       error_handler(9999,"ugraph::cyclic_adj_succ: self-loop");

  if (v == e->s)
    loc =  v->adj_edges.cyclic_succ(e->adj_loc);
  else if (v == e->t)
         loc =  v->adj_edges.cyclic_succ(e->adj_loc2);
       else error_handler(9999,"ugraph::cyclic_adj_succ: v is no endpoint of e");
  return v->adj_edges[loc];
 }

edge ugraph::cyclic_adj_pred(edge e,node v)  const
{ list_item loc;

  if (e->s == e->t)  
       error_handler(9999,"ugraph::cyclic_adj_pred: self-loop");

  if (v == e->s)
    loc =  v->adj_edges.cyclic_pred(e->adj_loc);
  else if (v == e->t)
         loc =  v->adj_edges.cyclic_pred(e->adj_loc2);
       else error_handler(9999,"ugraph::cyclic_adj_pred: v is no endpoint of e");
  return v->adj_edges[loc];
 }