1.1 --- a/src/include/oldgraph.h Wed Apr 14 20:57:58 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,551 +0,0 @@
1.4 -// -*-mode: c++; -*-
1.5 -#ifndef __OLDGRAPH_H_
1.6 -#define __OLDGRAPH_H_
1.7 -
1.8 -#include <stdio.h>
1.9 -
1.10 -//#include <new>
1.11 -
1.12 -#define INVALID -1
1.13 -#define FREE_NODE INVALID
1.14 -
1.15 -#define EDGE_BLOCK_SIZE 100
1.16 -#define INIT_NODES_SIZE 10
1.17 -#define INIT_EDGES_BLOCK_MAX 10
1.18 -
1.19 -#define foreachNode(n,G) for((n)=(G).FirstNode();(n)!=INVALID;(n)=(G).NextNode(n))
1.20 -#define foreachIn(e,G,n) for((e)=(G).FirstIn(n) ;(e);(e)=(G).NextIn(e) )
1.21 -#define foreachOut(e,G,n) for((e)=(G).FirstOut(n);(e);(e)=(G).NextOut(e))
1.22 -#define foreachEdge(e,G,n) for((e)=(G).FirstEdge(n);(e);(e)=(G).NextEdge((n),(e)))
1.23 -
1.24 -struct EdgeIndex { int block,index; };
1.25 -
1.26 -extern EdgeIndex InvalidIndex;
1.27 -
1.28 -class EdgeCorp;
1.29 -typedef EdgeCorp *EdgePoint;
1.30 -
1.31 -class EdgeCorp {
1.32 - public:
1.33 - int from,to; //from==INVALID <=> this is a free edge.
1.34 - EdgePoint previn,nextin,prevout,nextout;
1.35 - EdgeIndex index;
1.36 -
1.37 - int From() { return from; }
1.38 - int To() { return to; }
1.39 - EdgePoint NextIn() { return nextin; }
1.40 - EdgePoint NextOut() { return nextout; }
1.41 -};
1.42 -
1.43 -inline int From(EdgePoint e) { return e->from; }
1.44 -inline int To(EdgePoint e) { return e->to; }
1.45 -inline EdgePoint NextIn(EdgePoint e) { return e->nextin; }
1.46 -inline EdgePoint NextOut(EdgePoint e) { return e->nextout; }
1.47 -
1.48 -
1.49 -//////////////////////////////////////////////////////////////////////
1.50 -// OLDGRAPH TEMPLATE
1.51 -//////////////////////////////////////////////////////////////////////
1.52 -// Copy Constructor should be provided for N
1.53 -
1.54 -//class Graph;
1.55 -//class Graph::NodeIterator; //Nem megy. Disznosag!
1.56 -template <class N, class E> class OldGraph
1.57 -{
1.58 -
1.59 - // friend class NEGRO::Graph::NodeIterator; //Nem megy. Disznosag!
1.60 -
1.61 -
1.62 - class nodes_t;
1.63 - friend class OldGraph::nodes_t;
1.64 - class edge_block;
1.65 - friend class OldGraph::edge_block;
1.66 -
1.67 - class edge_t : public EdgeCorp {
1.68 - public:
1.69 - //edge_t *previn,*nextin,*prevout,*nextout;
1.70 - union {
1.71 - int _align;
1.72 - char data[sizeof(E)];
1.73 - };
1.74 - };
1.75 -
1.76 - class nodes_t {
1.77 - public:
1.78 - union {
1.79 - int _align;
1.80 - char data[sizeof(N)];
1.81 - };
1.82 - int indeg,outdeg; // indeg==FREE_NODE <=> this node is free.
1.83 - EdgePoint firstin, firstout;
1.84 - int prev,next;
1.85 -
1.86 - void Copy(nodes_t &n)
1.87 - {
1.88 - indeg = n.indeg; outdeg = n.outdeg;
1.89 - firstin = n.firstin; firstout = n.firstout;
1.90 - prev = n.prev; next = n.next;
1.91 - if(n.indeg!=FREE_NODE) new(data) N(*(N*)(n.data));
1.92 - // if(n.indeg!=FREE_NODE) {
1.93 - // new(data) N;
1.94 - // (*(N*)(data))=(*(N*)(n.data));
1.95 - // }
1.96 - }
1.97 -
1.98 - } *nodes;
1.99 - int nodenum, nodes_size;
1.100 - int firstnode, freenodes;
1.101 - class edge_block {
1.102 - public:
1.103 - //edge_block *next;
1.104 - // char fields[sizeof(edge_t)*EDGE_BLOCK_SIZE];
1.105 - edge_t fields[EDGE_BLOCK_SIZE];
1.106 - } **edges;
1.107 - int edge_block_num,edge_block_max;
1.108 - EdgePoint freeedges;
1.109 -
1.110 - void setup(int nosi = INIT_NODES_SIZE);
1.111 - void destroy();
1.112 - void inc_nodes_size(int n);
1.113 -
1.114 - public:
1.115 - int NodeNum() {return nodenum;};
1.116 - int EdgeNum();
1.117 - int MaxNode() const {return nodes_size;};
1.118 - int FirstNode() const {return firstnode;};
1.119 - int NextNode(int n) const {return nodes[n].next;};
1.120 - int PrevNode(int n) const {return nodes[n].prev;};
1.121 - N& operator()(int n) const {return *(N*)(nodes[n].data);};
1.122 - N& Data (int n) const {return *(N*)(nodes[n].data);};
1.123 - int AddNode();
1.124 - void AddNodeBlock(int n) const {for(int i=0;i<n;i++) AddNode();}
1.125 - int AddNode(int n);
1.126 - void Delete(int n);
1.127 - int isaNode(int n) const
1.128 - {return n>=0&&n<nodes_size&&nodes[n].indeg!=FREE_NODE;};
1.129 -
1.130 - int InDeg(int n) const {return nodes[n].indeg;};
1.131 - int OutDeg(int n) const {return nodes[n].outdeg;};
1.132 - EdgePoint FirstIn(int n) const {return nodes[n].firstin;};
1.133 - EdgePoint FirstOut(int n) const {return nodes[n].firstout;};
1.134 -
1.135 - E& operator()(EdgePoint e) const {return *(E*)(((edge_t*)e)->data);};
1.136 - E& Data (EdgePoint e) const {return *(E*)(((edge_t*)e)->data);};
1.137 - int From(EdgePoint e) const {return e->from;};
1.138 - int To(EdgePoint e) const {return e->to;};
1.139 - EdgePoint NextIn(EdgePoint e) const
1.140 - {return e->nextin;};
1.141 - EdgePoint NextOut(EdgePoint e)const
1.142 - {return e->nextout;};
1.143 - EdgePoint AddEdge(int f, int t);
1.144 - void Delete(EdgePoint e);
1.145 - EdgePoint Edge(int f,int t);
1.146 - // EdgePoint Edge(E &d)
1.147 - // {return (EdgePoint)(((char*)&d)-(char*)&(((edge_t*)NULL)->data));};
1.148 - E& operator()(int f, int t) const {return *(E*)(((edge_t*)Edge(f,t))->data);};
1.149 - E& Data(int f, int t) const {return *(E*)(((edge_t*)Edge(f,t))->data);};
1.150 - void Delete(int f, int t) {Delete(Edge(f,t));};
1.151 - void Reverse(EdgePoint e);
1.152 -
1.153 - // Functions for EdgeIndex
1.154 -
1.155 - EdgePoint Edge(EdgeIndex i) const
1.156 - { return (EdgePoint)(edges[i.block]->fields+i.index);};
1.157 - EdgeIndex Index(EdgePoint e) const { return e->index;};
1.158 - EdgeIndex Index(int f, int t) const { EdgePoint e; return Edge(f,t)->index; }
1.159 - void Delete(EdgeIndex i) { Delete(Edge(i));};
1.160 - E& operator()(EdgeIndex i) const
1.161 - {return *(E*)(edges[i.block]->fields[i.index].data);};
1.162 - E& Data(EdgeIndex i) const
1.163 - {return *(E*)(edges[i.block]->fields[i.index].data);};
1.164 - EdgePoint AddEdge(int f, int t,EdgeIndex in);
1.165 -
1.166 -
1.167 -
1.168 - // Operators for symmetric graphs:
1.169 -
1.170 - EdgePoint FirstEdge(int n) const
1.171 - { return (EdgePoint)(FirstIn(n)?FirstIn(n):FirstOut(n));};
1.172 - EdgePoint NextEdge(int n,EdgePoint e) const
1.173 - { return From(e)==n?NextOut(e):(NextIn(e)?NextIn(e):FirstOut(n)); };
1.174 - int Opposite(EdgePoint e,int n) const
1.175 - { return From(e)+To(e)-n; };
1.176 -
1.177 - // Initializers, destructors
1.178 -
1.179 - OldGraph() {setup();};
1.180 - OldGraph(int nosi) {setup(nosi);};
1.181 - OldGraph(OldGraph<N,E> &H) {setup();operator=(H);};
1.182 - ~OldGraph() {destroy();};
1.183 - void Clean(int nosi = INIT_NODES_SIZE) {destroy();setup(nosi);};
1.184 - void Clear(int nosi = INIT_NODES_SIZE) {destroy();setup(nosi);};
1.185 -
1.186 - void DeleteEdges();
1.187 -
1.188 - OldGraph<N,E> &operator=(OldGraph<N,E> &H);
1.189 -};
1.190 -
1.191 -//////////////////////////////////////////////////////////////////////
1.192 -// Template Definitions
1.193 -//////////////////////////////////////////////////////////////////////
1.194 -
1.195 -//#include <stdio.h>
1.196 -
1.197 -//**********************************************************************
1.198 -// OldGraph definitions
1.199 -//**********************************************************************
1.200 -
1.201 -template<class N, class E> void OldGraph<N,E>::setup(int nosi) {
1.202 - int i;
1.203 -
1.204 - //Set up nodes
1.205 - nodenum = 0;
1.206 - nodes_size = nosi;
1.207 - // nodes = (nodes_t*) new char[sizeof(nodes_t)*nodes_size];
1.208 - nodes = (nodes_t*) new nodes_t [nodes_size];
1.209 - for(i=0;i<nodes_size;i++)
1.210 - {
1.211 - nodes[i].prev=i-1;
1.212 - nodes[i].next=i+1;
1.213 - nodes[i].indeg=FREE_NODE;
1.214 - nodes[i].outdeg=0;
1.215 - nodes[i].firstin=nodes[i].firstout=NULL;
1.216 - }
1.217 - firstnode=nodes[0].prev=nodes[nodes_size-1].next=INVALID;
1.218 - freenodes=0;
1.219 - //Set up edge-list_template_type;
1.220 - freeedges = NULL;
1.221 -
1.222 - edges = new edge_block* [edge_block_max=INIT_EDGES_BLOCK_MAX];
1.223 - edge_block_num = 0;
1.224 -
1.225 -}
1.226 -
1.227 -template<class N, class E> void OldGraph<N,E>::destroy()
1.228 -{
1.229 - int i;
1.230 -
1.231 - while(firstnode!=INVALID) Delete(firstnode);
1.232 - delete [] nodes;
1.233 - for(i=0;i<edge_block_num;i++) delete edges[i];
1.234 - delete [] edges;
1.235 -}
1.236 -
1.237 -template<class N, class E> void OldGraph<N,E>::inc_nodes_size(int n)
1.238 -{
1.239 - int i;
1.240 - if(n<=nodenum) return;
1.241 -
1.242 - nodes_t *nn;
1.243 -// nn = (nodes_t*) new char [sizeof(nodes_t)*n];
1.244 - nn = (nodes_t*) new nodes_t [n];
1.245 - for(i=0;i<nodes_size;i++)
1.246 - {
1.247 - nn[i].Copy(nodes[i]);
1.248 - if(nodes[i].indeg!=FREE_NODE) ((N*)(nodes[i].data))->~N();
1.249 - }
1.250 -
1.251 - delete [] nodes;
1.252 - nodes = nn;
1.253 - for(i=nodes_size;i<n;i++)
1.254 - {
1.255 - nodes[i].prev=i-1;
1.256 - nodes[i].next=i+1;
1.257 - nodes[i].indeg=FREE_NODE;
1.258 - nodes[i].outdeg=0;
1.259 - nodes[i].firstin=nodes[i].firstout=NULL;
1.260 - }
1.261 - nodes[nodes_size].prev=INVALID;
1.262 - nodes[n-1].next=freenodes;
1.263 - if(freenodes!=INVALID) nodes[freenodes].prev=n-1;
1.264 - freenodes=nodes_size;
1.265 - nodes_size=n;
1.266 -}
1.267 -
1.268 -template<class N, class E> OldGraph<N,E> &OldGraph<N,E>::operator=(OldGraph<N,E> &H)
1.269 -{
1.270 - Clean();
1.271 -
1.272 - int i;
1.273 - EdgePoint e;
1.274 -
1.275 - for(i=H.FirstNode();i!=INVALID;i=H.NextNode(i))
1.276 - {
1.277 - AddNode(i);
1.278 - operator()(i)=H(i);
1.279 - }
1.280 - for(i=H.FirstNode();i!=INVALID;i=H.NextNode(i))
1.281 - for(e=H.FirstOut(i);e;e=H.NextOut(e))
1.282 - operator()(AddEdge(i,H.To(e),H.Index(e)))=H(e);
1.283 -
1.284 - return *this;
1.285 -}
1.286 -
1.287 -template<class N, class E> int OldGraph<N,E>::EdgeNum()
1.288 -{
1.289 - int n=firstnode, m=0;
1.290 - EdgePoint e;
1.291 - while(n != INVALID)
1.292 - {
1.293 - e=FirstOut(n);
1.294 - while (e != NULL)
1.295 - {
1.296 - m++;
1.297 - e=NextOut(e);
1.298 - }
1.299 - n=nodes[n].next;
1.300 - }
1.301 - return m;
1.302 -}
1.303 -
1.304 -template<class N, class E> int OldGraph<N,E>::AddNode()
1.305 -{
1.306 - int i;
1.307 -
1.308 - if(freenodes==INVALID) inc_nodes_size(2*nodes_size);
1.309 -
1.310 - i=freenodes;
1.311 - if(firstnode!=INVALID) nodes[firstnode].prev=i;
1.312 - freenodes=nodes[i].next;
1.313 - new(nodes[i].data) N; //Explicit constructor call
1.314 - nodes[i].next=firstnode;
1.315 - nodes[i].prev=INVALID;
1.316 - nodes[i].indeg=0;
1.317 - firstnode=i;
1.318 - if(freenodes!=INVALID) nodes[freenodes].prev=INVALID;
1.319 - nodenum++;
1.320 - return i;
1.321 -}
1.322 -
1.323 -template<class N, class E> int OldGraph<N,E>::AddNode(int n)
1.324 -{
1.325 - int i;
1.326 -
1.327 - if(n>=nodes_size)
1.328 - {
1.329 - for(i=INIT_NODES_SIZE;i<=n;i*=2) ;
1.330 - inc_nodes_size(i);
1.331 - }
1.332 -
1.333 - if(nodes[n].indeg==FREE_NODE)
1.334 - {
1.335 - new(nodes[n].data) N; //Explicit constructor call
1.336 - if(nodes[n].next!=INVALID) nodes[nodes[n].next].prev = nodes[n].prev;
1.337 - if(nodes[n].prev!=INVALID) nodes[nodes[n].prev].next = nodes[n].next;
1.338 - else freenodes = nodes[n].next;
1.339 -
1.340 - nodes[n].prev = INVALID;
1.341 - if((nodes[n].next = firstnode)!=INVALID) nodes[firstnode].prev=n;
1.342 - firstnode = n;
1.343 - nodenum++;
1.344 - nodes[n].indeg=0;
1.345 - }
1.346 - return n;
1.347 -}
1.348 -
1.349 -template<class N, class E> void OldGraph<N,E>::Delete(int n)
1.350 -{
1.351 - if(n==INVALID||nodes[n].indeg==FREE_NODE) return;
1.352 -
1.353 - EdgePoint e;
1.354 -
1.355 - while(e=FirstIn(n)) Delete(e);
1.356 - while(e=FirstOut(n)) Delete(e);
1.357 -
1.358 - if(n==firstnode) firstnode=nodes[n].next;
1.359 - if(nodes[n].prev!=INVALID) nodes[nodes[n].prev].next=nodes[n].next;
1.360 - if(nodes[n].next!=INVALID) nodes[nodes[n].next].prev=nodes[n].prev;
1.361 - if(freenodes!=INVALID) nodes[freenodes].prev=n;
1.362 - nodes[n].next=freenodes;
1.363 - nodes[n].prev=INVALID;
1.364 - nodes[n].indeg=FREE_NODE;
1.365 - ((N*)(nodes[n].data))->~N(); //Explicit destructor call
1.366 - freenodes=n;
1.367 -
1.368 - nodenum--;
1.369 -}
1.370 -
1.371 -template<class N, class E> EdgePoint OldGraph<N,E>::AddEdge(int f, int t)
1.372 -{
1.373 - int i;
1.374 - edge_block *peb;
1.375 - edge_block **ppeb;
1.376 - edge_t *e;
1.377 -
1.378 - if(!freeedges)
1.379 - {
1.380 - if(edge_block_num>=edge_block_max)
1.381 - {
1.382 - ppeb = new edge_block* [edge_block_max*=2];
1.383 - for(i=0;i<edge_block_num;i++) ppeb[i]=edges[i];
1.384 - delete [] edges;
1.385 - edges = ppeb;
1.386 - }
1.387 - peb = new edge_block;
1.388 - edges[edge_block_num] = peb;
1.389 -
1.390 - for(i=0;i<EDGE_BLOCK_SIZE;i++)
1.391 - {
1.392 - ((edge_t*)peb->fields)[i].nextin=((edge_t*)peb->fields)+(i+1);
1.393 - ((edge_t*)peb->fields)[i].previn=((edge_t*)peb->fields)+(i-1);
1.394 - ((edge_t*)peb->fields)[i].index.block = edge_block_num;
1.395 - ((edge_t*)peb->fields)[i].index.index = i;
1.396 - ((edge_t*)peb->fields)[i].from = INVALID;
1.397 - }
1.398 - ((edge_t*)peb->fields)[0].previn=
1.399 - ((edge_t*)peb->fields)[EDGE_BLOCK_SIZE-1].nextin=NULL;
1.400 - freeedges = (edge_t*)peb->fields;
1.401 - edge_block_num++;
1.402 - }
1.403 -
1.404 - e=(edge_t *)freeedges;
1.405 - new (e->data) E; //Explicit constructor call
1.406 - freeedges=e->nextin;
1.407 - if(freeedges) freeedges->previn=NULL;
1.408 -
1.409 - e->from=f; e->to=t;
1.410 - e->previn=e->prevout=NULL;
1.411 - e->nextin=nodes[t].firstin;
1.412 - e->nextout=nodes[f].firstout;
1.413 - if(nodes[t].firstin) nodes[t].firstin->previn=e;
1.414 - if(nodes[f].firstout) nodes[f].firstout->prevout=e;
1.415 - nodes[t].firstin=nodes[f].firstout=e;
1.416 - nodes[t].indeg++; nodes[f].outdeg++;
1.417 -
1.418 - return (EdgePoint)e;
1.419 -
1.420 -}
1.421 -
1.422 -template<class N, class E>
1.423 -EdgePoint OldGraph<N,E>::AddEdge(int f, int t, EdgeIndex in)
1.424 -{
1.425 - int i;
1.426 - edge_block *peb;
1.427 - edge_block **ppeb;
1.428 - edge_t *e;
1.429 -
1.430 - while(edge_block_num<=in.block)
1.431 - {
1.432 - if(edge_block_num>=edge_block_max)
1.433 - {
1.434 - ppeb = new edge_block* [edge_block_max*=2];
1.435 - for(i=0;i<edge_block_num;i++) ppeb[i]=edges[i];
1.436 - delete [] edges;
1.437 - edges = ppeb;
1.438 - }
1.439 - peb = new edge_block;
1.440 - edges[edge_block_num] = peb;
1.441 -
1.442 - for(i=0;i<EDGE_BLOCK_SIZE;i++)
1.443 - {
1.444 - ((edge_t*)peb->fields)[i].nextin=((edge_t*)peb->fields)+(i+1);
1.445 - ((edge_t*)peb->fields)[i].previn=((edge_t*)peb->fields)+(i-1);
1.446 - ((edge_t*)peb->fields)[i].index.block = edge_block_num;
1.447 - ((edge_t*)peb->fields)[i].index.index = i;
1.448 - ((edge_t*)peb->fields)[i].from = INVALID;
1.449 - }
1.450 - ((edge_t*)peb->fields)[0].previn=NULL;
1.451 - ((edge_t*)peb->fields)[EDGE_BLOCK_SIZE-1].nextin=freeedges;
1.452 - if(freeedges)
1.453 - freeedges->previn = ((edge_t*)peb->fields) + (EDGE_BLOCK_SIZE-1);
1.454 - freeedges = (edge_t*)peb->fields;
1.455 - edge_block_num++;
1.456 - }
1.457 -
1.458 -
1.459 - e=((edge_t*)(edges[in.block]->fields))+in.index;
1.460 - if(e->from==INVALID)
1.461 - {
1.462 - if(e->previn) e->previn->nextin = e->nextin;
1.463 - else freeedges = e->nextin;
1.464 - if(e->nextin) e->nextin->previn = e->previn;
1.465 -
1.466 - new (e->data) E; //Explicit constructor call
1.467 -
1.468 - e->from=f; e->to=t;
1.469 - e->previn=e->prevout=NULL;
1.470 - e->nextin=nodes[t].firstin;
1.471 - e->nextout=nodes[f].firstout;
1.472 - if(nodes[t].firstin) nodes[t].firstin->previn=e;
1.473 - if(nodes[f].firstout) nodes[f].firstout->prevout=e;
1.474 - nodes[t].firstin=nodes[f].firstout=e;
1.475 - nodes[t].indeg++; nodes[f].outdeg++;
1.476 - }
1.477 - return (EdgePoint)e;
1.478 -}
1.479 -
1.480 -template<class N, class E> void OldGraph<N,E>::Delete(EdgePoint e)
1.481 -{
1.482 - if(!e||e->from==INVALID) return;
1.483 -
1.484 - ((E*)(((edge_t*)e)->data))->~E(); //Explicit destructor call
1.485 -
1.486 - nodes[e->from].outdeg--; nodes[e->to].indeg--;
1.487 -
1.488 -
1.489 - if(e->previn)
1.490 - e->previn->nextin=e->nextin;
1.491 - else nodes[e->to].firstin=e->nextin;
1.492 - if(e->prevout)
1.493 - e->prevout->nextout=e->nextout;
1.494 - else nodes[e->from].firstout=e->nextout;
1.495 - if(e->nextin)
1.496 - e->nextin->previn=e->previn;
1.497 - if(e->nextout)
1.498 - e->nextout->prevout=e->prevout;
1.499 -
1.500 - if(freeedges) freeedges->previn=e;
1.501 - e->previn=NULL; e->nextin=freeedges;
1.502 -
1.503 - e->from = INVALID;
1.504 - freeedges=e;
1.505 -}
1.506 -
1.507 -template<class N, class E> EdgePoint OldGraph<N,E>::Edge(int f, int t)
1.508 -{
1.509 - EdgePoint e;
1.510 -
1.511 - for(e=nodes[f].firstout;e&&e->to!=t;e=e->nextout) ;
1.512 -
1.513 - return (EdgePoint) e;
1.514 -}
1.515 -
1.516 -template<class N, class E> void OldGraph<N,E>::Reverse(EdgePoint e)
1.517 -{
1.518 - if(!e) return;
1.519 -
1.520 - nodes[e->from].outdeg--; nodes[e->to].indeg--;
1.521 -
1.522 - if(e->previn)
1.523 - e->previn->nextin=e->nextin;
1.524 - else nodes[e->to].firstin=e->nextin;
1.525 - if(e->prevout)
1.526 - e->prevout->nextout=e->nextout;
1.527 - else nodes[e->from].firstout=e->nextout;
1.528 - if(e->nextin)
1.529 - e->nextin->previn=e->previn;
1.530 - if(e->nextout)
1.531 - e->nextout->prevout=e->prevout;
1.532 -
1.533 - int t,f;
1.534 - f=e->to;e->to=t=e->from;
1.535 - e->from=f;
1.536 -
1.537 - e->previn=e->prevout=NULL;
1.538 - e->nextin=nodes[t].firstin;
1.539 - e->nextout=nodes[f].firstout;
1.540 - if(nodes[t].firstin) nodes[t].firstin->previn=e;
1.541 - if(nodes[f].firstout) nodes[f].firstout->prevout=e;
1.542 - nodes[t].firstin=nodes[f].firstout=e;
1.543 - nodes[t].indeg++; nodes[f].outdeg++;
1.544 -
1.545 -}
1.546 -
1.547 -template<class N, class E> void OldGraph<N,E>::DeleteEdges()
1.548 -{
1.549 - int n;
1.550 - for(n=FirstNode();n!=INVALID;n=NextNode(n))
1.551 - while(FirstOut(n)) Delete(FirstOut(n));
1.552 -}
1.553 -
1.554 -#endif
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/alpar/oldgraph.h Thu Apr 15 05:51:12 2004 +0000
2.3 @@ -0,0 +1,551 @@
2.4 +// -*-mode: c++; -*-
2.5 +#ifndef __OLDGRAPH_H_
2.6 +#define __OLDGRAPH_H_
2.7 +
2.8 +#include <stdio.h>
2.9 +
2.10 +//#include <new>
2.11 +
2.12 +#define INVALID -1
2.13 +#define FREE_NODE INVALID
2.14 +
2.15 +#define EDGE_BLOCK_SIZE 100
2.16 +#define INIT_NODES_SIZE 10
2.17 +#define INIT_EDGES_BLOCK_MAX 10
2.18 +
2.19 +#define foreachNode(n,G) for((n)=(G).FirstNode();(n)!=INVALID;(n)=(G).NextNode(n))
2.20 +#define foreachIn(e,G,n) for((e)=(G).FirstIn(n) ;(e);(e)=(G).NextIn(e) )
2.21 +#define foreachOut(e,G,n) for((e)=(G).FirstOut(n);(e);(e)=(G).NextOut(e))
2.22 +#define foreachEdge(e,G,n) for((e)=(G).FirstEdge(n);(e);(e)=(G).NextEdge((n),(e)))
2.23 +
2.24 +struct EdgeIndex { int block,index; };
2.25 +
2.26 +extern EdgeIndex InvalidIndex;
2.27 +
2.28 +class EdgeCorp;
2.29 +typedef EdgeCorp *EdgePoint;
2.30 +
2.31 +class EdgeCorp {
2.32 + public:
2.33 + int from,to; //from==INVALID <=> this is a free edge.
2.34 + EdgePoint previn,nextin,prevout,nextout;
2.35 + EdgeIndex index;
2.36 +
2.37 + int From() { return from; }
2.38 + int To() { return to; }
2.39 + EdgePoint NextIn() { return nextin; }
2.40 + EdgePoint NextOut() { return nextout; }
2.41 +};
2.42 +
2.43 +inline int From(EdgePoint e) { return e->from; }
2.44 +inline int To(EdgePoint e) { return e->to; }
2.45 +inline EdgePoint NextIn(EdgePoint e) { return e->nextin; }
2.46 +inline EdgePoint NextOut(EdgePoint e) { return e->nextout; }
2.47 +
2.48 +
2.49 +//////////////////////////////////////////////////////////////////////
2.50 +// OLDGRAPH TEMPLATE
2.51 +//////////////////////////////////////////////////////////////////////
2.52 +// Copy Constructor should be provided for N
2.53 +
2.54 +//class Graph;
2.55 +//class Graph::NodeIterator; //Nem megy. Disznosag!
2.56 +template <class N, class E> class OldGraph
2.57 +{
2.58 +
2.59 + // friend class NEGRO::Graph::NodeIterator; //Nem megy. Disznosag!
2.60 +
2.61 +
2.62 + class nodes_t;
2.63 + friend class OldGraph::nodes_t;
2.64 + class edge_block;
2.65 + friend class OldGraph::edge_block;
2.66 +
2.67 + class edge_t : public EdgeCorp {
2.68 + public:
2.69 + //edge_t *previn,*nextin,*prevout,*nextout;
2.70 + union {
2.71 + int _align;
2.72 + char data[sizeof(E)];
2.73 + };
2.74 + };
2.75 +
2.76 + class nodes_t {
2.77 + public:
2.78 + union {
2.79 + int _align;
2.80 + char data[sizeof(N)];
2.81 + };
2.82 + int indeg,outdeg; // indeg==FREE_NODE <=> this node is free.
2.83 + EdgePoint firstin, firstout;
2.84 + int prev,next;
2.85 +
2.86 + void Copy(nodes_t &n)
2.87 + {
2.88 + indeg = n.indeg; outdeg = n.outdeg;
2.89 + firstin = n.firstin; firstout = n.firstout;
2.90 + prev = n.prev; next = n.next;
2.91 + if(n.indeg!=FREE_NODE) new(data) N(*(N*)(n.data));
2.92 + // if(n.indeg!=FREE_NODE) {
2.93 + // new(data) N;
2.94 + // (*(N*)(data))=(*(N*)(n.data));
2.95 + // }
2.96 + }
2.97 +
2.98 + } *nodes;
2.99 + int nodenum, nodes_size;
2.100 + int firstnode, freenodes;
2.101 + class edge_block {
2.102 + public:
2.103 + //edge_block *next;
2.104 + // char fields[sizeof(edge_t)*EDGE_BLOCK_SIZE];
2.105 + edge_t fields[EDGE_BLOCK_SIZE];
2.106 + } **edges;
2.107 + int edge_block_num,edge_block_max;
2.108 + EdgePoint freeedges;
2.109 +
2.110 + void setup(int nosi = INIT_NODES_SIZE);
2.111 + void destroy();
2.112 + void inc_nodes_size(int n);
2.113 +
2.114 + public:
2.115 + int NodeNum() {return nodenum;};
2.116 + int EdgeNum();
2.117 + int MaxNode() const {return nodes_size;};
2.118 + int FirstNode() const {return firstnode;};
2.119 + int NextNode(int n) const {return nodes[n].next;};
2.120 + int PrevNode(int n) const {return nodes[n].prev;};
2.121 + N& operator()(int n) const {return *(N*)(nodes[n].data);};
2.122 + N& Data (int n) const {return *(N*)(nodes[n].data);};
2.123 + int AddNode();
2.124 + void AddNodeBlock(int n) const {for(int i=0;i<n;i++) AddNode();}
2.125 + int AddNode(int n);
2.126 + void Delete(int n);
2.127 + int isaNode(int n) const
2.128 + {return n>=0&&n<nodes_size&&nodes[n].indeg!=FREE_NODE;};
2.129 +
2.130 + int InDeg(int n) const {return nodes[n].indeg;};
2.131 + int OutDeg(int n) const {return nodes[n].outdeg;};
2.132 + EdgePoint FirstIn(int n) const {return nodes[n].firstin;};
2.133 + EdgePoint FirstOut(int n) const {return nodes[n].firstout;};
2.134 +
2.135 + E& operator()(EdgePoint e) const {return *(E*)(((edge_t*)e)->data);};
2.136 + E& Data (EdgePoint e) const {return *(E*)(((edge_t*)e)->data);};
2.137 + int From(EdgePoint e) const {return e->from;};
2.138 + int To(EdgePoint e) const {return e->to;};
2.139 + EdgePoint NextIn(EdgePoint e) const
2.140 + {return e->nextin;};
2.141 + EdgePoint NextOut(EdgePoint e)const
2.142 + {return e->nextout;};
2.143 + EdgePoint AddEdge(int f, int t);
2.144 + void Delete(EdgePoint e);
2.145 + EdgePoint Edge(int f,int t);
2.146 + // EdgePoint Edge(E &d)
2.147 + // {return (EdgePoint)(((char*)&d)-(char*)&(((edge_t*)NULL)->data));};
2.148 + E& operator()(int f, int t) const {return *(E*)(((edge_t*)Edge(f,t))->data);};
2.149 + E& Data(int f, int t) const {return *(E*)(((edge_t*)Edge(f,t))->data);};
2.150 + void Delete(int f, int t) {Delete(Edge(f,t));};
2.151 + void Reverse(EdgePoint e);
2.152 +
2.153 + // Functions for EdgeIndex
2.154 +
2.155 + EdgePoint Edge(EdgeIndex i) const
2.156 + { return (EdgePoint)(edges[i.block]->fields+i.index);};
2.157 + EdgeIndex Index(EdgePoint e) const { return e->index;};
2.158 + EdgeIndex Index(int f, int t) const { EdgePoint e; return Edge(f,t)->index; }
2.159 + void Delete(EdgeIndex i) { Delete(Edge(i));};
2.160 + E& operator()(EdgeIndex i) const
2.161 + {return *(E*)(edges[i.block]->fields[i.index].data);};
2.162 + E& Data(EdgeIndex i) const
2.163 + {return *(E*)(edges[i.block]->fields[i.index].data);};
2.164 + EdgePoint AddEdge(int f, int t,EdgeIndex in);
2.165 +
2.166 +
2.167 +
2.168 + // Operators for symmetric graphs:
2.169 +
2.170 + EdgePoint FirstEdge(int n) const
2.171 + { return (EdgePoint)(FirstIn(n)?FirstIn(n):FirstOut(n));};
2.172 + EdgePoint NextEdge(int n,EdgePoint e) const
2.173 + { return From(e)==n?NextOut(e):(NextIn(e)?NextIn(e):FirstOut(n)); };
2.174 + int Opposite(EdgePoint e,int n) const
2.175 + { return From(e)+To(e)-n; };
2.176 +
2.177 + // Initializers, destructors
2.178 +
2.179 + OldGraph() {setup();};
2.180 + OldGraph(int nosi) {setup(nosi);};
2.181 + OldGraph(OldGraph<N,E> &H) {setup();operator=(H);};
2.182 + ~OldGraph() {destroy();};
2.183 + void Clean(int nosi = INIT_NODES_SIZE) {destroy();setup(nosi);};
2.184 + void Clear(int nosi = INIT_NODES_SIZE) {destroy();setup(nosi);};
2.185 +
2.186 + void DeleteEdges();
2.187 +
2.188 + OldGraph<N,E> &operator=(OldGraph<N,E> &H);
2.189 +};
2.190 +
2.191 +//////////////////////////////////////////////////////////////////////
2.192 +// Template Definitions
2.193 +//////////////////////////////////////////////////////////////////////
2.194 +
2.195 +//#include <stdio.h>
2.196 +
2.197 +//**********************************************************************
2.198 +// OldGraph definitions
2.199 +//**********************************************************************
2.200 +
2.201 +template<class N, class E> void OldGraph<N,E>::setup(int nosi) {
2.202 + int i;
2.203 +
2.204 + //Set up nodes
2.205 + nodenum = 0;
2.206 + nodes_size = nosi;
2.207 + // nodes = (nodes_t*) new char[sizeof(nodes_t)*nodes_size];
2.208 + nodes = (nodes_t*) new nodes_t [nodes_size];
2.209 + for(i=0;i<nodes_size;i++)
2.210 + {
2.211 + nodes[i].prev=i-1;
2.212 + nodes[i].next=i+1;
2.213 + nodes[i].indeg=FREE_NODE;
2.214 + nodes[i].outdeg=0;
2.215 + nodes[i].firstin=nodes[i].firstout=NULL;
2.216 + }
2.217 + firstnode=nodes[0].prev=nodes[nodes_size-1].next=INVALID;
2.218 + freenodes=0;
2.219 + //Set up edge-list_template_type;
2.220 + freeedges = NULL;
2.221 +
2.222 + edges = new edge_block* [edge_block_max=INIT_EDGES_BLOCK_MAX];
2.223 + edge_block_num = 0;
2.224 +
2.225 +}
2.226 +
2.227 +template<class N, class E> void OldGraph<N,E>::destroy()
2.228 +{
2.229 + int i;
2.230 +
2.231 + while(firstnode!=INVALID) Delete(firstnode);
2.232 + delete [] nodes;
2.233 + for(i=0;i<edge_block_num;i++) delete edges[i];
2.234 + delete [] edges;
2.235 +}
2.236 +
2.237 +template<class N, class E> void OldGraph<N,E>::inc_nodes_size(int n)
2.238 +{
2.239 + int i;
2.240 + if(n<=nodenum) return;
2.241 +
2.242 + nodes_t *nn;
2.243 +// nn = (nodes_t*) new char [sizeof(nodes_t)*n];
2.244 + nn = (nodes_t*) new nodes_t [n];
2.245 + for(i=0;i<nodes_size;i++)
2.246 + {
2.247 + nn[i].Copy(nodes[i]);
2.248 + if(nodes[i].indeg!=FREE_NODE) ((N*)(nodes[i].data))->~N();
2.249 + }
2.250 +
2.251 + delete [] nodes;
2.252 + nodes = nn;
2.253 + for(i=nodes_size;i<n;i++)
2.254 + {
2.255 + nodes[i].prev=i-1;
2.256 + nodes[i].next=i+1;
2.257 + nodes[i].indeg=FREE_NODE;
2.258 + nodes[i].outdeg=0;
2.259 + nodes[i].firstin=nodes[i].firstout=NULL;
2.260 + }
2.261 + nodes[nodes_size].prev=INVALID;
2.262 + nodes[n-1].next=freenodes;
2.263 + if(freenodes!=INVALID) nodes[freenodes].prev=n-1;
2.264 + freenodes=nodes_size;
2.265 + nodes_size=n;
2.266 +}
2.267 +
2.268 +template<class N, class E> OldGraph<N,E> &OldGraph<N,E>::operator=(OldGraph<N,E> &H)
2.269 +{
2.270 + Clean();
2.271 +
2.272 + int i;
2.273 + EdgePoint e;
2.274 +
2.275 + for(i=H.FirstNode();i!=INVALID;i=H.NextNode(i))
2.276 + {
2.277 + AddNode(i);
2.278 + operator()(i)=H(i);
2.279 + }
2.280 + for(i=H.FirstNode();i!=INVALID;i=H.NextNode(i))
2.281 + for(e=H.FirstOut(i);e;e=H.NextOut(e))
2.282 + operator()(AddEdge(i,H.To(e),H.Index(e)))=H(e);
2.283 +
2.284 + return *this;
2.285 +}
2.286 +
2.287 +template<class N, class E> int OldGraph<N,E>::EdgeNum()
2.288 +{
2.289 + int n=firstnode, m=0;
2.290 + EdgePoint e;
2.291 + while(n != INVALID)
2.292 + {
2.293 + e=FirstOut(n);
2.294 + while (e != NULL)
2.295 + {
2.296 + m++;
2.297 + e=NextOut(e);
2.298 + }
2.299 + n=nodes[n].next;
2.300 + }
2.301 + return m;
2.302 +}
2.303 +
2.304 +template<class N, class E> int OldGraph<N,E>::AddNode()
2.305 +{
2.306 + int i;
2.307 +
2.308 + if(freenodes==INVALID) inc_nodes_size(2*nodes_size);
2.309 +
2.310 + i=freenodes;
2.311 + if(firstnode!=INVALID) nodes[firstnode].prev=i;
2.312 + freenodes=nodes[i].next;
2.313 + new(nodes[i].data) N; //Explicit constructor call
2.314 + nodes[i].next=firstnode;
2.315 + nodes[i].prev=INVALID;
2.316 + nodes[i].indeg=0;
2.317 + firstnode=i;
2.318 + if(freenodes!=INVALID) nodes[freenodes].prev=INVALID;
2.319 + nodenum++;
2.320 + return i;
2.321 +}
2.322 +
2.323 +template<class N, class E> int OldGraph<N,E>::AddNode(int n)
2.324 +{
2.325 + int i;
2.326 +
2.327 + if(n>=nodes_size)
2.328 + {
2.329 + for(i=INIT_NODES_SIZE;i<=n;i*=2) ;
2.330 + inc_nodes_size(i);
2.331 + }
2.332 +
2.333 + if(nodes[n].indeg==FREE_NODE)
2.334 + {
2.335 + new(nodes[n].data) N; //Explicit constructor call
2.336 + if(nodes[n].next!=INVALID) nodes[nodes[n].next].prev = nodes[n].prev;
2.337 + if(nodes[n].prev!=INVALID) nodes[nodes[n].prev].next = nodes[n].next;
2.338 + else freenodes = nodes[n].next;
2.339 +
2.340 + nodes[n].prev = INVALID;
2.341 + if((nodes[n].next = firstnode)!=INVALID) nodes[firstnode].prev=n;
2.342 + firstnode = n;
2.343 + nodenum++;
2.344 + nodes[n].indeg=0;
2.345 + }
2.346 + return n;
2.347 +}
2.348 +
2.349 +template<class N, class E> void OldGraph<N,E>::Delete(int n)
2.350 +{
2.351 + if(n==INVALID||nodes[n].indeg==FREE_NODE) return;
2.352 +
2.353 + EdgePoint e;
2.354 +
2.355 + while(e=FirstIn(n)) Delete(e);
2.356 + while(e=FirstOut(n)) Delete(e);
2.357 +
2.358 + if(n==firstnode) firstnode=nodes[n].next;
2.359 + if(nodes[n].prev!=INVALID) nodes[nodes[n].prev].next=nodes[n].next;
2.360 + if(nodes[n].next!=INVALID) nodes[nodes[n].next].prev=nodes[n].prev;
2.361 + if(freenodes!=INVALID) nodes[freenodes].prev=n;
2.362 + nodes[n].next=freenodes;
2.363 + nodes[n].prev=INVALID;
2.364 + nodes[n].indeg=FREE_NODE;
2.365 + ((N*)(nodes[n].data))->~N(); //Explicit destructor call
2.366 + freenodes=n;
2.367 +
2.368 + nodenum--;
2.369 +}
2.370 +
2.371 +template<class N, class E> EdgePoint OldGraph<N,E>::AddEdge(int f, int t)
2.372 +{
2.373 + int i;
2.374 + edge_block *peb;
2.375 + edge_block **ppeb;
2.376 + edge_t *e;
2.377 +
2.378 + if(!freeedges)
2.379 + {
2.380 + if(edge_block_num>=edge_block_max)
2.381 + {
2.382 + ppeb = new edge_block* [edge_block_max*=2];
2.383 + for(i=0;i<edge_block_num;i++) ppeb[i]=edges[i];
2.384 + delete [] edges;
2.385 + edges = ppeb;
2.386 + }
2.387 + peb = new edge_block;
2.388 + edges[edge_block_num] = peb;
2.389 +
2.390 + for(i=0;i<EDGE_BLOCK_SIZE;i++)
2.391 + {
2.392 + ((edge_t*)peb->fields)[i].nextin=((edge_t*)peb->fields)+(i+1);
2.393 + ((edge_t*)peb->fields)[i].previn=((edge_t*)peb->fields)+(i-1);
2.394 + ((edge_t*)peb->fields)[i].index.block = edge_block_num;
2.395 + ((edge_t*)peb->fields)[i].index.index = i;
2.396 + ((edge_t*)peb->fields)[i].from = INVALID;
2.397 + }
2.398 + ((edge_t*)peb->fields)[0].previn=
2.399 + ((edge_t*)peb->fields)[EDGE_BLOCK_SIZE-1].nextin=NULL;
2.400 + freeedges = (edge_t*)peb->fields;
2.401 + edge_block_num++;
2.402 + }
2.403 +
2.404 + e=(edge_t *)freeedges;
2.405 + new (e->data) E; //Explicit constructor call
2.406 + freeedges=e->nextin;
2.407 + if(freeedges) freeedges->previn=NULL;
2.408 +
2.409 + e->from=f; e->to=t;
2.410 + e->previn=e->prevout=NULL;
2.411 + e->nextin=nodes[t].firstin;
2.412 + e->nextout=nodes[f].firstout;
2.413 + if(nodes[t].firstin) nodes[t].firstin->previn=e;
2.414 + if(nodes[f].firstout) nodes[f].firstout->prevout=e;
2.415 + nodes[t].firstin=nodes[f].firstout=e;
2.416 + nodes[t].indeg++; nodes[f].outdeg++;
2.417 +
2.418 + return (EdgePoint)e;
2.419 +
2.420 +}
2.421 +
2.422 +template<class N, class E>
2.423 +EdgePoint OldGraph<N,E>::AddEdge(int f, int t, EdgeIndex in)
2.424 +{
2.425 + int i;
2.426 + edge_block *peb;
2.427 + edge_block **ppeb;
2.428 + edge_t *e;
2.429 +
2.430 + while(edge_block_num<=in.block)
2.431 + {
2.432 + if(edge_block_num>=edge_block_max)
2.433 + {
2.434 + ppeb = new edge_block* [edge_block_max*=2];
2.435 + for(i=0;i<edge_block_num;i++) ppeb[i]=edges[i];
2.436 + delete [] edges;
2.437 + edges = ppeb;
2.438 + }
2.439 + peb = new edge_block;
2.440 + edges[edge_block_num] = peb;
2.441 +
2.442 + for(i=0;i<EDGE_BLOCK_SIZE;i++)
2.443 + {
2.444 + ((edge_t*)peb->fields)[i].nextin=((edge_t*)peb->fields)+(i+1);
2.445 + ((edge_t*)peb->fields)[i].previn=((edge_t*)peb->fields)+(i-1);
2.446 + ((edge_t*)peb->fields)[i].index.block = edge_block_num;
2.447 + ((edge_t*)peb->fields)[i].index.index = i;
2.448 + ((edge_t*)peb->fields)[i].from = INVALID;
2.449 + }
2.450 + ((edge_t*)peb->fields)[0].previn=NULL;
2.451 + ((edge_t*)peb->fields)[EDGE_BLOCK_SIZE-1].nextin=freeedges;
2.452 + if(freeedges)
2.453 + freeedges->previn = ((edge_t*)peb->fields) + (EDGE_BLOCK_SIZE-1);
2.454 + freeedges = (edge_t*)peb->fields;
2.455 + edge_block_num++;
2.456 + }
2.457 +
2.458 +
2.459 + e=((edge_t*)(edges[in.block]->fields))+in.index;
2.460 + if(e->from==INVALID)
2.461 + {
2.462 + if(e->previn) e->previn->nextin = e->nextin;
2.463 + else freeedges = e->nextin;
2.464 + if(e->nextin) e->nextin->previn = e->previn;
2.465 +
2.466 + new (e->data) E; //Explicit constructor call
2.467 +
2.468 + e->from=f; e->to=t;
2.469 + e->previn=e->prevout=NULL;
2.470 + e->nextin=nodes[t].firstin;
2.471 + e->nextout=nodes[f].firstout;
2.472 + if(nodes[t].firstin) nodes[t].firstin->previn=e;
2.473 + if(nodes[f].firstout) nodes[f].firstout->prevout=e;
2.474 + nodes[t].firstin=nodes[f].firstout=e;
2.475 + nodes[t].indeg++; nodes[f].outdeg++;
2.476 + }
2.477 + return (EdgePoint)e;
2.478 +}
2.479 +
2.480 +template<class N, class E> void OldGraph<N,E>::Delete(EdgePoint e)
2.481 +{
2.482 + if(!e||e->from==INVALID) return;
2.483 +
2.484 + ((E*)(((edge_t*)e)->data))->~E(); //Explicit destructor call
2.485 +
2.486 + nodes[e->from].outdeg--; nodes[e->to].indeg--;
2.487 +
2.488 +
2.489 + if(e->previn)
2.490 + e->previn->nextin=e->nextin;
2.491 + else nodes[e->to].firstin=e->nextin;
2.492 + if(e->prevout)
2.493 + e->prevout->nextout=e->nextout;
2.494 + else nodes[e->from].firstout=e->nextout;
2.495 + if(e->nextin)
2.496 + e->nextin->previn=e->previn;
2.497 + if(e->nextout)
2.498 + e->nextout->prevout=e->prevout;
2.499 +
2.500 + if(freeedges) freeedges->previn=e;
2.501 + e->previn=NULL; e->nextin=freeedges;
2.502 +
2.503 + e->from = INVALID;
2.504 + freeedges=e;
2.505 +}
2.506 +
2.507 +template<class N, class E> EdgePoint OldGraph<N,E>::Edge(int f, int t)
2.508 +{
2.509 + EdgePoint e;
2.510 +
2.511 + for(e=nodes[f].firstout;e&&e->to!=t;e=e->nextout) ;
2.512 +
2.513 + return (EdgePoint) e;
2.514 +}
2.515 +
2.516 +template<class N, class E> void OldGraph<N,E>::Reverse(EdgePoint e)
2.517 +{
2.518 + if(!e) return;
2.519 +
2.520 + nodes[e->from].outdeg--; nodes[e->to].indeg--;
2.521 +
2.522 + if(e->previn)
2.523 + e->previn->nextin=e->nextin;
2.524 + else nodes[e->to].firstin=e->nextin;
2.525 + if(e->prevout)
2.526 + e->prevout->nextout=e->nextout;
2.527 + else nodes[e->from].firstout=e->nextout;
2.528 + if(e->nextin)
2.529 + e->nextin->previn=e->previn;
2.530 + if(e->nextout)
2.531 + e->nextout->prevout=e->prevout;
2.532 +
2.533 + int t,f;
2.534 + f=e->to;e->to=t=e->from;
2.535 + e->from=f;
2.536 +
2.537 + e->previn=e->prevout=NULL;
2.538 + e->nextin=nodes[t].firstin;
2.539 + e->nextout=nodes[f].firstout;
2.540 + if(nodes[t].firstin) nodes[t].firstin->previn=e;
2.541 + if(nodes[f].firstout) nodes[f].firstout->prevout=e;
2.542 + nodes[t].firstin=nodes[f].firstout=e;
2.543 + nodes[t].indeg++; nodes[f].outdeg++;
2.544 +
2.545 +}
2.546 +
2.547 +template<class N, class E> void OldGraph<N,E>::DeleteEdges()
2.548 +{
2.549 + int n;
2.550 + for(n=FirstNode();n!=INVALID;n=NextNode(n))
2.551 + while(FirstOut(n)) Delete(FirstOut(n));
2.552 +}
2.553 +
2.554 +#endif