# HG changeset patch
# User alpar
# Date 1082008272 0
# Node ID e2f00e438c31b3bc341413ff6bde336326d3656c
# Parent  5fe27632f9ac9d29308af4cc70231f03d1bc6e55
Deprecated...

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