alpar@1: // -*-mode: c++; -*-
alpar@1: #ifndef __OLDGRAPH_H_
alpar@1: #define __OLDGRAPH_H_
alpar@1: 
alpar@1: #include <stdio.h>
alpar@1: 
alpar@1: //#include <new>
alpar@1: 
alpar@1: #define INVALID -1
alpar@1: #define FREE_NODE INVALID
alpar@1: 
alpar@1: #define EDGE_BLOCK_SIZE 100
alpar@1: #define INIT_NODES_SIZE 10
alpar@1: #define INIT_EDGES_BLOCK_MAX 10
alpar@1: 
alpar@1: #define foreachNode(n,G) for((n)=(G).FirstNode();(n)!=INVALID;(n)=(G).NextNode(n))
alpar@1: #define foreachIn(e,G,n)  for((e)=(G).FirstIn(n) ;(e);(e)=(G).NextIn(e) )
alpar@1: #define foreachOut(e,G,n) for((e)=(G).FirstOut(n);(e);(e)=(G).NextOut(e))
alpar@1: #define foreachEdge(e,G,n) for((e)=(G).FirstEdge(n);(e);(e)=(G).NextEdge((n),(e)))
alpar@1: 
alpar@1: struct EdgeIndex { int block,index; };
alpar@1: 
alpar@1: extern EdgeIndex InvalidIndex;
alpar@1: 
alpar@1: class EdgeCorp;
alpar@1: typedef EdgeCorp *EdgePoint;
alpar@1: 
alpar@1: class EdgeCorp {
alpar@1:  public:
alpar@1:   int from,to;      //from==INVALID <=> this is a free edge.
alpar@1:   EdgePoint previn,nextin,prevout,nextout;
alpar@1:   EdgeIndex index;
alpar@1: 
alpar@1:   int From() { return from; }
alpar@1:   int To() { return to; }
alpar@1:   EdgePoint NextIn() { return nextin; }
alpar@1:   EdgePoint NextOut() { return nextout; }
alpar@1: };
alpar@1: 
alpar@1: inline int From(EdgePoint e) { return e->from; }
alpar@1: inline int To(EdgePoint e) { return e->to; }
alpar@1: inline EdgePoint NextIn(EdgePoint e) { return e->nextin; }
alpar@1: inline EdgePoint NextOut(EdgePoint e) { return e->nextout; }
alpar@1: 
alpar@1: 
alpar@1: //////////////////////////////////////////////////////////////////////
alpar@1: //   OLDGRAPH TEMPLATE
alpar@1: //////////////////////////////////////////////////////////////////////
alpar@1: // Copy Constructor should be provided for N
alpar@1: 
alpar@1: //class Graph;
alpar@1: //class Graph::NodeIterator; //Nem megy. Disznosag!
alpar@1: template <class N, class E> class OldGraph
alpar@1: {
alpar@1: 
alpar@1:   //  friend class NEGRO::Graph::NodeIterator; //Nem megy. Disznosag!
alpar@1: 
alpar@1: 
alpar@1:   class nodes_t;
alpar@1:   friend class OldGraph::nodes_t;
alpar@1:   class edge_block;
alpar@1:   friend class OldGraph::edge_block;
alpar@1:   
alpar@1:   class edge_t : public EdgeCorp {
alpar@1:   public:
alpar@1:     //edge_t *previn,*nextin,*prevout,*nextout;
alpar@1:     union {
alpar@1:       int _align;
alpar@1:       char data[sizeof(E)];
alpar@1:     };
alpar@1:   };
alpar@1: 
alpar@1:   class nodes_t {
alpar@1:   public:
alpar@1:     union {
alpar@1:       int _align;
alpar@1:       char data[sizeof(N)];
alpar@1:     };
alpar@1:     int indeg,outdeg;           // indeg==FREE_NODE <=> this node is free.
alpar@1:     EdgePoint firstin, firstout;
alpar@1:     int prev,next;
alpar@1: 
alpar@1:     void Copy(nodes_t &n) 
alpar@1:     {
alpar@1:       indeg = n.indeg; outdeg = n.outdeg;
alpar@1:       firstin = n.firstin; firstout = n.firstout;
alpar@1:       prev = n.prev; next = n.next;
alpar@1:       if(n.indeg!=FREE_NODE) new(data) N(*(N*)(n.data));
alpar@1:       //      if(n.indeg!=FREE_NODE) {
alpar@1:       //	new(data) N;
alpar@1:       //	(*(N*)(data))=(*(N*)(n.data));
alpar@1:       //      }
alpar@1:     }
alpar@1:     
alpar@1:   } *nodes;
alpar@1:   int nodenum, nodes_size;
alpar@1:   int firstnode, freenodes;
alpar@1:   class edge_block {
alpar@1:   public:
alpar@1:     //edge_block *next;
alpar@1:     //    char fields[sizeof(edge_t)*EDGE_BLOCK_SIZE];
alpar@1:     edge_t fields[EDGE_BLOCK_SIZE];    
alpar@1:   } **edges;
alpar@1:   int edge_block_num,edge_block_max;
alpar@1:   EdgePoint freeedges;
alpar@1: 
alpar@1:   void setup(int nosi = INIT_NODES_SIZE);
alpar@1:   void destroy();
alpar@1:   void inc_nodes_size(int n);
alpar@1:   
alpar@1:  public:
alpar@1:   int NodeNum() {return nodenum;};
alpar@1:   int EdgeNum();
alpar@3:   int MaxNode() const {return nodes_size;};
alpar@3:   int FirstNode() const {return firstnode;};
alpar@3:   int NextNode(int n) const {return nodes[n].next;};
alpar@3:   int PrevNode(int n) const {return nodes[n].prev;};
alpar@3:   N& operator()(int n) const {return *(N*)(nodes[n].data);};
alpar@3:   N& Data      (int n) const {return *(N*)(nodes[n].data);};
alpar@1:   int AddNode();
alpar@3:   void AddNodeBlock(int n) const {for(int i=0;i<n;i++) AddNode();}
alpar@1:   int AddNode(int n);
alpar@1:   void Delete(int n);
alpar@3:   int isaNode(int n) const 
alpar@3:         {return n>=0&&n<nodes_size&&nodes[n].indeg!=FREE_NODE;};
alpar@1:   
alpar@3:   int InDeg(int n) const {return nodes[n].indeg;};
alpar@3:   int OutDeg(int n) const {return nodes[n].outdeg;};
alpar@3:   EdgePoint FirstIn(int n) const {return nodes[n].firstin;};
alpar@3:   EdgePoint FirstOut(int n) const {return nodes[n].firstout;};
alpar@1: 
alpar@3:   E& operator()(EdgePoint e) const {return *(E*)(((edge_t*)e)->data);};
alpar@3:   E& Data      (EdgePoint e) const {return *(E*)(((edge_t*)e)->data);};
alpar@3:   int From(EdgePoint e) const {return e->from;};
alpar@3:   int To(EdgePoint e) const {return e->to;};
alpar@3:   EdgePoint NextIn(EdgePoint e) const 
alpar@1:     {return e->nextin;};
alpar@3:   EdgePoint NextOut(EdgePoint e)const 
alpar@1:     {return e->nextout;};
alpar@1:   EdgePoint AddEdge(int f, int t);
alpar@1:   void Delete(EdgePoint e);
alpar@1:   EdgePoint Edge(int f,int t);
alpar@1:   //  EdgePoint Edge(E &d)
alpar@1:   //    {return (EdgePoint)(((char*)&d)-(char*)&(((edge_t*)NULL)->data));};
alpar@3:   E& operator()(int f, int t) const {return *(E*)(((edge_t*)Edge(f,t))->data);};
alpar@3:   E& Data(int f, int t) const {return *(E*)(((edge_t*)Edge(f,t))->data);};
alpar@1:   void Delete(int f, int t) {Delete(Edge(f,t));};
alpar@1:   void Reverse(EdgePoint e);
alpar@1: 
alpar@1:   // Functions for EdgeIndex
alpar@1:   
alpar@3:   EdgePoint Edge(EdgeIndex i) const 
alpar@1:     { return (EdgePoint)(edges[i.block]->fields+i.index);};
alpar@3:   EdgeIndex Index(EdgePoint e) const { return e->index;};
alpar@3:   EdgeIndex Index(int f, int t) const { EdgePoint e; return Edge(f,t)->index; }
alpar@1:   void Delete(EdgeIndex i) { Delete(Edge(i));};
alpar@3:   E& operator()(EdgeIndex i) const 
alpar@1:      {return *(E*)(edges[i.block]->fields[i.index].data);};
alpar@3:   E& Data(EdgeIndex i) const 
alpar@1:      {return *(E*)(edges[i.block]->fields[i.index].data);};
alpar@1:   EdgePoint AddEdge(int f, int t,EdgeIndex in);
alpar@1:   
alpar@1: 
alpar@1:   
alpar@1:   // Operators for symmetric graphs:
alpar@1: 
alpar@3:   EdgePoint FirstEdge(int n) const 
alpar@1:     { return (EdgePoint)(FirstIn(n)?FirstIn(n):FirstOut(n));};
alpar@3:   EdgePoint NextEdge(int n,EdgePoint e) const 
alpar@1:     { return From(e)==n?NextOut(e):(NextIn(e)?NextIn(e):FirstOut(n)); };
alpar@3:   int Opposite(EdgePoint e,int n) const 
alpar@1:     { return From(e)+To(e)-n; };
alpar@1:   
alpar@1:   // Initializers, destructors
alpar@1:        
alpar@1:   OldGraph() {setup();};
alpar@1:   OldGraph(int nosi) {setup(nosi);};
alpar@1:   OldGraph(OldGraph<N,E> &H) {setup();operator=(H);};
alpar@1:   ~OldGraph() {destroy();};  
alpar@1:   void Clean(int nosi = INIT_NODES_SIZE) {destroy();setup(nosi);};
alpar@1:   void Clear(int nosi = INIT_NODES_SIZE) {destroy();setup(nosi);};
alpar@1: 
alpar@1:   void DeleteEdges();
alpar@1:     
alpar@1:   OldGraph<N,E> &operator=(OldGraph<N,E> &H);
alpar@1: };
alpar@1: 
alpar@1: //////////////////////////////////////////////////////////////////////
alpar@1: // Template Definitions
alpar@1: //////////////////////////////////////////////////////////////////////
alpar@1: 
alpar@1: //#include <stdio.h>
alpar@1: 
alpar@1: //**********************************************************************
alpar@1: //                          OldGraph definitions
alpar@1: //**********************************************************************
alpar@1: 
alpar@1: template<class N, class E> void OldGraph<N,E>::setup(int nosi) {
alpar@1:   int i;
alpar@1: 
alpar@1:   //Set up nodes
alpar@1:   nodenum = 0;
alpar@1:   nodes_size = nosi;
alpar@1:   // nodes = (nodes_t*) new char[sizeof(nodes_t)*nodes_size];
alpar@1:   nodes = (nodes_t*) new nodes_t [nodes_size];
alpar@1:   for(i=0;i<nodes_size;i++)
alpar@1:     {
alpar@1:       nodes[i].prev=i-1;
alpar@1:       nodes[i].next=i+1;
alpar@1:       nodes[i].indeg=FREE_NODE;
alpar@1:       nodes[i].outdeg=0;
alpar@1:       nodes[i].firstin=nodes[i].firstout=NULL;
alpar@1:     }
alpar@1:   firstnode=nodes[0].prev=nodes[nodes_size-1].next=INVALID;
alpar@1:   freenodes=0;
alpar@1:   //Set up edge-list_template_type;
alpar@1:   freeedges = NULL;
alpar@1:   
alpar@1:   edges = new edge_block* [edge_block_max=INIT_EDGES_BLOCK_MAX];
alpar@1:   edge_block_num = 0;
alpar@1:   
alpar@1: }
alpar@1: 
alpar@1: template<class N, class E> void OldGraph<N,E>::destroy()
alpar@1: {
alpar@1:   int i;
alpar@1:   
alpar@1:   while(firstnode!=INVALID) Delete(firstnode);
alpar@1:   delete [] nodes;
alpar@1:   for(i=0;i<edge_block_num;i++) delete edges[i];
alpar@1:   delete [] edges;
alpar@1: }
alpar@1: 
alpar@1: template<class N, class E> void OldGraph<N,E>::inc_nodes_size(int n)
alpar@1: {
alpar@1:   int i;
alpar@1:   if(n<=nodenum) return;
alpar@1:   
alpar@1:   nodes_t *nn;
alpar@1: //  nn = (nodes_t*) new char [sizeof(nodes_t)*n];
alpar@1:   nn = (nodes_t*) new nodes_t [n];
alpar@1:   for(i=0;i<nodes_size;i++)
alpar@1:     {
alpar@1:       nn[i].Copy(nodes[i]);
alpar@1:       if(nodes[i].indeg!=FREE_NODE) ((N*)(nodes[i].data))->~N();
alpar@1:     }
alpar@1:   
alpar@1:   delete [] nodes;
alpar@1:   nodes = nn;
alpar@1:   for(i=nodes_size;i<n;i++)
alpar@1:     {
alpar@1:       nodes[i].prev=i-1;
alpar@1:       nodes[i].next=i+1;
alpar@1:       nodes[i].indeg=FREE_NODE;
alpar@1:       nodes[i].outdeg=0;
alpar@1:       nodes[i].firstin=nodes[i].firstout=NULL;
alpar@1:     }
alpar@1:   nodes[nodes_size].prev=INVALID;
alpar@1:   nodes[n-1].next=freenodes;
alpar@1:   if(freenodes!=INVALID) nodes[freenodes].prev=n-1;
alpar@1:   freenodes=nodes_size;
alpar@1:   nodes_size=n;
alpar@1: }
alpar@1: 
alpar@1: template<class N, class E> OldGraph<N,E> &OldGraph<N,E>::operator=(OldGraph<N,E> &H)
alpar@1: {
alpar@1:   Clean();
alpar@1: 
alpar@1:   int i;
alpar@1:   EdgePoint e;
alpar@1:   
alpar@1:   for(i=H.FirstNode();i!=INVALID;i=H.NextNode(i))
alpar@1:     {
alpar@1:       AddNode(i);
alpar@1:       operator()(i)=H(i);
alpar@1:     }
alpar@1:   for(i=H.FirstNode();i!=INVALID;i=H.NextNode(i))
alpar@1:     for(e=H.FirstOut(i);e;e=H.NextOut(e))
alpar@1:       operator()(AddEdge(i,H.To(e),H.Index(e)))=H(e);
alpar@1: 
alpar@1:    return *this;
alpar@1: }
alpar@1: 
alpar@1: template<class N, class E> int OldGraph<N,E>::EdgeNum()
alpar@1: {
alpar@1:   int n=firstnode, m=0;
alpar@1:   EdgePoint e;
alpar@1:   while(n != INVALID)
alpar@1:   {    
alpar@1:     e=FirstOut(n);
alpar@1:     while (e != NULL)
alpar@1:     {
alpar@1:       m++;
alpar@1:       e=NextOut(e);
alpar@1:     }
alpar@1:     n=nodes[n].next;
alpar@1:   }
alpar@1:   return m;
alpar@1: }
alpar@1: 
alpar@1: template<class N, class E> int OldGraph<N,E>::AddNode()
alpar@1: {
alpar@1:   int i;
alpar@1:   
alpar@1:   if(freenodes==INVALID) inc_nodes_size(2*nodes_size);
alpar@1:   
alpar@1:   i=freenodes;
alpar@1:   if(firstnode!=INVALID) nodes[firstnode].prev=i;
alpar@1:   freenodes=nodes[i].next;
alpar@1:   new(nodes[i].data) N;  //Explicit constructor call
alpar@1:   nodes[i].next=firstnode;
alpar@1:   nodes[i].prev=INVALID;
alpar@1:   nodes[i].indeg=0;
alpar@1:   firstnode=i;
alpar@1:   if(freenodes!=INVALID) nodes[freenodes].prev=INVALID;
alpar@1:   nodenum++;
alpar@1:   return i;
alpar@1: }
alpar@1: 
alpar@1: template<class N, class E> int OldGraph<N,E>::AddNode(int n)
alpar@1: {
alpar@1:   int i;
alpar@1:   
alpar@1:   if(n>=nodes_size)
alpar@1:     {
alpar@1:       for(i=INIT_NODES_SIZE;i<=n;i*=2) ;
alpar@1:       inc_nodes_size(i);
alpar@1:     }
alpar@1:   
alpar@1:   if(nodes[n].indeg==FREE_NODE)
alpar@1:     {
alpar@1:       new(nodes[n].data) N;  //Explicit constructor call
alpar@1:       if(nodes[n].next!=INVALID) nodes[nodes[n].next].prev = nodes[n].prev;
alpar@1:       if(nodes[n].prev!=INVALID) nodes[nodes[n].prev].next = nodes[n].next;
alpar@1:       else freenodes = nodes[n].next;
alpar@1:       
alpar@1:       nodes[n].prev = INVALID;
alpar@1:       if((nodes[n].next = firstnode)!=INVALID) nodes[firstnode].prev=n;
alpar@1:       firstnode = n;
alpar@1:       nodenum++;
alpar@1:       nodes[n].indeg=0;
alpar@1:     }
alpar@1:   return n;
alpar@1: }
alpar@1: 
alpar@1: template<class N, class E> void OldGraph<N,E>::Delete(int n)
alpar@1: {
alpar@1:   if(n==INVALID||nodes[n].indeg==FREE_NODE) return;
alpar@1: 
alpar@1:   EdgePoint e;
alpar@1:   
alpar@1:   while(e=FirstIn(n)) Delete(e);
alpar@1:   while(e=FirstOut(n)) Delete(e);
alpar@1:   
alpar@1:   if(n==firstnode) firstnode=nodes[n].next;
alpar@1:   if(nodes[n].prev!=INVALID) nodes[nodes[n].prev].next=nodes[n].next;
alpar@1:   if(nodes[n].next!=INVALID) nodes[nodes[n].next].prev=nodes[n].prev;
alpar@1:   if(freenodes!=INVALID) nodes[freenodes].prev=n;
alpar@1:   nodes[n].next=freenodes;
alpar@1:   nodes[n].prev=INVALID;
alpar@1:   nodes[n].indeg=FREE_NODE;
alpar@1:   ((N*)(nodes[n].data))->~N();  //Explicit destructor call
alpar@1:   freenodes=n;
alpar@1: 
alpar@1:   nodenum--;
alpar@1: }
alpar@1: 
alpar@1: template<class N, class E> EdgePoint OldGraph<N,E>::AddEdge(int f, int t)
alpar@1: {
alpar@1:   int i;
alpar@1:   edge_block *peb;
alpar@1:   edge_block **ppeb;
alpar@1:   edge_t *e;
alpar@1:   
alpar@1:   if(!freeedges)
alpar@1:     {
alpar@1:       if(edge_block_num>=edge_block_max)
alpar@1: 	{
alpar@1: 	  ppeb = new edge_block* [edge_block_max*=2];
alpar@1: 	  for(i=0;i<edge_block_num;i++) ppeb[i]=edges[i];
alpar@1: 	  delete [] edges;
alpar@1: 	  edges = ppeb;
alpar@1: 	}
alpar@1:       peb = new edge_block;
alpar@1:       edges[edge_block_num] = peb;
alpar@1:       
alpar@1:       for(i=0;i<EDGE_BLOCK_SIZE;i++)
alpar@1: 	{
alpar@1: 	  ((edge_t*)peb->fields)[i].nextin=((edge_t*)peb->fields)+(i+1);
alpar@1: 	  ((edge_t*)peb->fields)[i].previn=((edge_t*)peb->fields)+(i-1);
alpar@1: 	  ((edge_t*)peb->fields)[i].index.block = edge_block_num;
alpar@1: 	  ((edge_t*)peb->fields)[i].index.index = i;
alpar@1: 	  ((edge_t*)peb->fields)[i].from = INVALID;
alpar@1: 	}
alpar@1:       ((edge_t*)peb->fields)[0].previn=
alpar@1: 	((edge_t*)peb->fields)[EDGE_BLOCK_SIZE-1].nextin=NULL;
alpar@1:       freeedges = (edge_t*)peb->fields;
alpar@1:       edge_block_num++;
alpar@1:     }
alpar@1:   
alpar@1:   e=(edge_t *)freeedges;
alpar@1:   new (e->data) E;  //Explicit constructor call
alpar@1:   freeedges=e->nextin;
alpar@1:   if(freeedges) freeedges->previn=NULL;
alpar@1:   
alpar@1:   e->from=f; e->to=t;
alpar@1:   e->previn=e->prevout=NULL;
alpar@1:   e->nextin=nodes[t].firstin;
alpar@1:   e->nextout=nodes[f].firstout;
alpar@1:   if(nodes[t].firstin) nodes[t].firstin->previn=e;
alpar@1:   if(nodes[f].firstout) nodes[f].firstout->prevout=e;
alpar@1:   nodes[t].firstin=nodes[f].firstout=e;
alpar@1:   nodes[t].indeg++; nodes[f].outdeg++;
alpar@1: 
alpar@1:   return (EdgePoint)e;
alpar@1:   
alpar@1: }
alpar@1: 
alpar@1: template<class N, class E>
alpar@1: EdgePoint OldGraph<N,E>::AddEdge(int f, int t, EdgeIndex in)
alpar@1: {
alpar@1:   int i;
alpar@1:   edge_block *peb;
alpar@1:   edge_block **ppeb;
alpar@1:   edge_t *e;
alpar@1:   
alpar@1:   while(edge_block_num<=in.block)
alpar@1:     {
alpar@1:       if(edge_block_num>=edge_block_max)
alpar@1: 	{
alpar@1: 	  ppeb = new edge_block* [edge_block_max*=2];
alpar@1: 	  for(i=0;i<edge_block_num;i++) ppeb[i]=edges[i];
alpar@1: 	  delete [] edges;
alpar@1: 	  edges = ppeb;
alpar@1: 	}
alpar@1:       peb = new edge_block;
alpar@1:       edges[edge_block_num] = peb;
alpar@1:       
alpar@1:       for(i=0;i<EDGE_BLOCK_SIZE;i++)
alpar@1: 	{
alpar@1: 	  ((edge_t*)peb->fields)[i].nextin=((edge_t*)peb->fields)+(i+1);
alpar@1: 	  ((edge_t*)peb->fields)[i].previn=((edge_t*)peb->fields)+(i-1);
alpar@1: 	  ((edge_t*)peb->fields)[i].index.block = edge_block_num;
alpar@1: 	  ((edge_t*)peb->fields)[i].index.index = i;
alpar@1: 	  ((edge_t*)peb->fields)[i].from = INVALID;
alpar@1: 	}
alpar@1:       ((edge_t*)peb->fields)[0].previn=NULL;
alpar@1:       ((edge_t*)peb->fields)[EDGE_BLOCK_SIZE-1].nextin=freeedges;
alpar@1:       if(freeedges)
alpar@1: 	freeedges->previn = ((edge_t*)peb->fields) + (EDGE_BLOCK_SIZE-1);
alpar@1:       freeedges = (edge_t*)peb->fields;
alpar@1:       edge_block_num++;
alpar@1:     }
alpar@1:   
alpar@1:   
alpar@1:   e=((edge_t*)(edges[in.block]->fields))+in.index;
alpar@1:   if(e->from==INVALID)
alpar@1:     {
alpar@1:       if(e->previn) e->previn->nextin = e->nextin;
alpar@1:                else freeedges = e->nextin;
alpar@1:       if(e->nextin) e->nextin->previn = e->previn;
alpar@1: 
alpar@1:       new (e->data) E;  //Explicit constructor call
alpar@1:       
alpar@1:       e->from=f; e->to=t;
alpar@1:       e->previn=e->prevout=NULL;
alpar@1:       e->nextin=nodes[t].firstin;
alpar@1:       e->nextout=nodes[f].firstout;
alpar@1:       if(nodes[t].firstin) nodes[t].firstin->previn=e;
alpar@1:       if(nodes[f].firstout) nodes[f].firstout->prevout=e;
alpar@1:       nodes[t].firstin=nodes[f].firstout=e;
alpar@1:       nodes[t].indeg++; nodes[f].outdeg++;
alpar@1:     }
alpar@1:   return (EdgePoint)e;
alpar@1: }
alpar@1: 
alpar@1: template<class N, class E> void OldGraph<N,E>::Delete(EdgePoint e)
alpar@1: {
alpar@1:   if(!e||e->from==INVALID) return;
alpar@1:   
alpar@1:   ((E*)(((edge_t*)e)->data))->~E();  //Explicit destructor call
alpar@1:   
alpar@1:   nodes[e->from].outdeg--; nodes[e->to].indeg--;
alpar@1: 
alpar@1:   
alpar@1:   if(e->previn)
alpar@1:     e->previn->nextin=e->nextin;
alpar@1:   else nodes[e->to].firstin=e->nextin;
alpar@1:   if(e->prevout)
alpar@1:     e->prevout->nextout=e->nextout;
alpar@1:   else nodes[e->from].firstout=e->nextout;
alpar@1:   if(e->nextin)
alpar@1:     e->nextin->previn=e->previn;
alpar@1:   if(e->nextout)
alpar@1:     e->nextout->prevout=e->prevout;
alpar@1:   
alpar@1:   if(freeedges) freeedges->previn=e;
alpar@1:   e->previn=NULL; e->nextin=freeedges;
alpar@1: 
alpar@1:   e->from = INVALID;
alpar@1:   freeedges=e;
alpar@1: }
alpar@1: 
alpar@1: template<class N, class E> EdgePoint OldGraph<N,E>::Edge(int f, int t)
alpar@1: {
alpar@1:   EdgePoint e;
alpar@1:   
alpar@1:   for(e=nodes[f].firstout;e&&e->to!=t;e=e->nextout) ;
alpar@1:   
alpar@1:   return (EdgePoint) e;
alpar@1: }
alpar@1: 
alpar@1: template<class N, class E> void OldGraph<N,E>::Reverse(EdgePoint e)
alpar@1: {
alpar@1:   if(!e) return;
alpar@1: 
alpar@1:   nodes[e->from].outdeg--; nodes[e->to].indeg--;
alpar@1:   
alpar@1:   if(e->previn)
alpar@1:     e->previn->nextin=e->nextin;
alpar@1:   else nodes[e->to].firstin=e->nextin;
alpar@1:   if(e->prevout)
alpar@1:     e->prevout->nextout=e->nextout;
alpar@1:   else nodes[e->from].firstout=e->nextout;
alpar@1:   if(e->nextin)
alpar@1:     e->nextin->previn=e->previn;
alpar@1:   if(e->nextout)
alpar@1:     e->nextout->prevout=e->prevout;
alpar@1:   
alpar@1:   int t,f;
alpar@1:   f=e->to;e->to=t=e->from;
alpar@1:   e->from=f;
alpar@1: 
alpar@1:   e->previn=e->prevout=NULL;
alpar@1:   e->nextin=nodes[t].firstin;
alpar@1:   e->nextout=nodes[f].firstout;
alpar@1:   if(nodes[t].firstin) nodes[t].firstin->previn=e;
alpar@1:   if(nodes[f].firstout) nodes[f].firstout->prevout=e;
alpar@1:   nodes[t].firstin=nodes[f].firstout=e;
alpar@1:   nodes[t].indeg++; nodes[f].outdeg++;
alpar@1: 
alpar@1: }
alpar@1: 
alpar@1: template<class N, class E> void OldGraph<N,E>::DeleteEdges()
alpar@1: {
alpar@1:   int n;
alpar@1:   for(n=FirstNode();n!=INVALID;n=NextNode(n))
alpar@1:     while(FirstOut(n)) Delete(FirstOut(n));
alpar@1: }
alpar@1: 
alpar@1: #endif