lemon-0.x: src/work/alpar/oldgraph.h@751ed145bdae

     1 // -*-mode: c++; -*-

     2 #ifndef __OLDGRAPH_H_

     3 #define __OLDGRAPH_H_

     5 #include <stdio.h>

     7 //#include <new>

     9 #define INVALID -1

    10 #define FREE_NODE INVALID

    12 #define EDGE_BLOCK_SIZE 100

    13 #define INIT_NODES_SIZE 10

    14 #define INIT_EDGES_BLOCK_MAX 10

    16 #define foreachNode(n,G) for((n)=(G).FirstNode();(n)!=INVALID;(n)=(G).NextNode(n))

    17 #define foreachIn(e,G,n)  for((e)=(G).FirstIn(n) ;(e);(e)=(G).NextIn(e) )

    18 #define foreachOut(e,G,n) for((e)=(G).FirstOut(n);(e);(e)=(G).NextOut(e))

    19 #define foreachEdge(e,G,n) for((e)=(G).FirstEdge(n);(e);(e)=(G).NextEdge((n),(e)))

    21 struct EdgeIndex { int block,index; };

    23 extern EdgeIndex InvalidIndex;

    25 class EdgeCorp;

    26 typedef EdgeCorp *EdgePoint;

    28 class EdgeCorp {

    29  public:

    30   int from,to;      //from==INVALID <=> this is a free edge.

    31   EdgePoint previn,nextin,prevout,nextout;

    32   EdgeIndex index;

    34   int From() { return from; }

    35   int To() { return to; }

    36   EdgePoint NextIn() { return nextin; }

    37   EdgePoint NextOut() { return nextout; }

    38 };

    40 inline int From(EdgePoint e) { return e->from; }

    41 inline int To(EdgePoint e) { return e->to; }

    42 inline EdgePoint NextIn(EdgePoint e) { return e->nextin; }

    43 inline EdgePoint NextOut(EdgePoint e) { return e->nextout; }

    46 //////////////////////////////////////////////////////////////////////

    47 //   OLDGRAPH TEMPLATE

    48 //////////////////////////////////////////////////////////////////////

    49 // Copy Constructor should be provided for N

    51 //class Graph;

    52 //class Graph::NodeIterator; //Nem megy. Disznosag!

    53 template <class N, class E> class OldGraph

    54 {

    56   //  friend class NEGRO::Graph::NodeIterator; //Nem megy. Disznosag!

    59   class nodes_t;

    60   friend class OldGraph::nodes_t;

    61   class edge_block;

    62   friend class OldGraph::edge_block;

    64   class edge_t : public EdgeCorp {

    65   public:

    66     //edge_t *previn,*nextin,*prevout,*nextout;

    67     union {

    68       int _align;

    69       char data[sizeof(E)];

    70     };

    71   };

    73   class nodes_t {

    74   public:

    75     union {

    76       int _align;

    77       char data[sizeof(N)];

    78     };

    79     int indeg,outdeg;           // indeg==FREE_NODE <=> this node is free.

    80     EdgePoint firstin, firstout;

    81     int prev,next;

    83     void Copy(nodes_t &n)

    84     {

    85       indeg = n.indeg; outdeg = n.outdeg;

    86       firstin = n.firstin; firstout = n.firstout;

    87       prev = n.prev; next = n.next;

    88       if(n.indeg!=FREE_NODE) new(data) N(*(N*)(n.data));

    89       //      if(n.indeg!=FREE_NODE) {

    90       //	new(data) N;

    91       //	(*(N*)(data))=(*(N*)(n.data));

    92       //      }

    93     }

    95   } *nodes;

    96   int nodenum, nodes_size;

    97   int firstnode, freenodes;

    98   class edge_block {

    99   public:

   100     //edge_block *next;

   101     //    char fields[sizeof(edge_t)*EDGE_BLOCK_SIZE];

   102     edge_t fields[EDGE_BLOCK_SIZE];

   103   } **edges;

   104   int edge_block_num,edge_block_max;

   105   EdgePoint freeedges;

   107   void setup(int nosi = INIT_NODES_SIZE);

   108   void destroy();

   109   void inc_nodes_size(int n);

   111  public:

   112   int NodeNum() {return nodenum;};

   113   int EdgeNum();

   114   int MaxNode() const {return nodes_size;};

   115   int FirstNode() const {return firstnode;};

   116   int NextNode(int n) const {return nodes[n].next;};

   117   int PrevNode(int n) const {return nodes[n].prev;};

   118   N& operator()(int n) const {return *(N*)(nodes[n].data);};

   119   N& Data      (int n) const {return *(N*)(nodes[n].data);};

   120   int AddNode();

   121   void AddNodeBlock(int n) const {for(int i=0;i<n;i++) AddNode();}

   122   int AddNode(int n);

   123   void Delete(int n);

   124   int isaNode(int n) const

   125         {return n>=0&&n<nodes_size&&nodes[n].indeg!=FREE_NODE;};

   127   int InDeg(int n) const {return nodes[n].indeg;};

   128   int OutDeg(int n) const {return nodes[n].outdeg;};

   129   EdgePoint FirstIn(int n) const {return nodes[n].firstin;};

   130   EdgePoint FirstOut(int n) const {return nodes[n].firstout;};

   132   E& operator()(EdgePoint e) const {return *(E*)(((edge_t*)e)->data);};

   133   E& Data      (EdgePoint e) const {return *(E*)(((edge_t*)e)->data);};

   134   int From(EdgePoint e) const {return e->from;};

   135   int To(EdgePoint e) const {return e->to;};

   136   EdgePoint NextIn(EdgePoint e) const

   137     {return e->nextin;};

   138   EdgePoint NextOut(EdgePoint e)const

   139     {return e->nextout;};

   140   EdgePoint AddEdge(int f, int t);

   141   void Delete(EdgePoint e);

   142   EdgePoint Edge(int f,int t);

   143   //  EdgePoint Edge(E &d)

   144   //    {return (EdgePoint)(((char*)&d)-(char*)&(((edge_t*)NULL)->data));};

   145   E& operator()(int f, int t) const {return *(E*)(((edge_t*)Edge(f,t))->data);};

   146   E& Data(int f, int t) const {return *(E*)(((edge_t*)Edge(f,t))->data);};

   147   void Delete(int f, int t) {Delete(Edge(f,t));};

   148   void Reverse(EdgePoint e);

   150   // Functions for EdgeIndex

   152   EdgePoint Edge(EdgeIndex i) const

   153     { return (EdgePoint)(edges[i.block]->fields+i.index);};

   154   EdgeIndex Index(EdgePoint e) const { return e->index;};

   155   EdgeIndex Index(int f, int t) const { EdgePoint e; return Edge(f,t)->index; }

   156   void Delete(EdgeIndex i) { Delete(Edge(i));};

   157   E& operator()(EdgeIndex i) const

   158      {return *(E*)(edges[i.block]->fields[i.index].data);};

   159   E& Data(EdgeIndex i) const

   160      {return *(E*)(edges[i.block]->fields[i.index].data);};

   161   EdgePoint AddEdge(int f, int t,EdgeIndex in);

   165   // Operators for symmetric graphs:

   167   EdgePoint FirstEdge(int n) const

   168     { return (EdgePoint)(FirstIn(n)?FirstIn(n):FirstOut(n));};

   169   EdgePoint NextEdge(int n,EdgePoint e) const

   170     { return From(e)==n?NextOut(e):(NextIn(e)?NextIn(e):FirstOut(n)); };

   171   int Opposite(EdgePoint e,int n) const

   172     { return From(e)+To(e)-n; };

   174   // Initializers, destructors

   176   OldGraph() {setup();};

   177   OldGraph(int nosi) {setup(nosi);};

   178   OldGraph(OldGraph<N,E> &H) {setup();operator=(H);};

   179   ~OldGraph() {destroy();};

   180   void Clean(int nosi = INIT_NODES_SIZE) {destroy();setup(nosi);};

   181   void Clear(int nosi = INIT_NODES_SIZE) {destroy();setup(nosi);};

   183   void DeleteEdges();

   185   OldGraph<N,E> &operator=(OldGraph<N,E> &H);

   186 };

   188 //////////////////////////////////////////////////////////////////////

   189 // Template Definitions

   190 //////////////////////////////////////////////////////////////////////

   192 //#include <stdio.h>

   194 //**********************************************************************

   195 //                          OldGraph definitions

   196 //**********************************************************************

   198 template<class N, class E> void OldGraph<N,E>::setup(int nosi) {

   199   int i;

   201   //Set up nodes

   202   nodenum = 0;

   203   nodes_size = nosi;

   204   // nodes = (nodes_t*) new char[sizeof(nodes_t)*nodes_size];

   205   nodes = (nodes_t*) new nodes_t [nodes_size];

   206   for(i=0;i<nodes_size;i++)

   207     {

   208       nodes[i].prev=i-1;

   209       nodes[i].next=i+1;

   210       nodes[i].indeg=FREE_NODE;

   211       nodes[i].outdeg=0;

   212       nodes[i].firstin=nodes[i].firstout=NULL;

   213     }

   214   firstnode=nodes[0].prev=nodes[nodes_size-1].next=INVALID;

   215   freenodes=0;

   216   //Set up edge-list_template_type;

   217   freeedges = NULL;

   219   edges = new edge_block* [edge_block_max=INIT_EDGES_BLOCK_MAX];

   220   edge_block_num = 0;

   222 }

   224 template<class N, class E> void OldGraph<N,E>::destroy()

   225 {

   226   int i;

   228   while(firstnode!=INVALID) Delete(firstnode);

   229   delete [] nodes;

   230   for(i=0;i<edge_block_num;i++) delete edges[i];

   231   delete [] edges;

   232 }

   234 template<class N, class E> void OldGraph<N,E>::inc_nodes_size(int n)

   235 {

   236   int i;

   237   if(n<=nodenum) return;

   239   nodes_t *nn;

   240 //  nn = (nodes_t*) new char [sizeof(nodes_t)*n];

   241   nn = (nodes_t*) new nodes_t [n];

   242   for(i=0;i<nodes_size;i++)

   243     {

   244       nn[i].Copy(nodes[i]);

   245       if(nodes[i].indeg!=FREE_NODE) ((N*)(nodes[i].data))->~N();

   246     }

   248   delete [] nodes;

   249   nodes = nn;

   250   for(i=nodes_size;i<n;i++)

   251     {

   252       nodes[i].prev=i-1;

   253       nodes[i].next=i+1;

   254       nodes[i].indeg=FREE_NODE;

   255       nodes[i].outdeg=0;

   256       nodes[i].firstin=nodes[i].firstout=NULL;

   257     }

   258   nodes[nodes_size].prev=INVALID;

   259   nodes[n-1].next=freenodes;

   260   if(freenodes!=INVALID) nodes[freenodes].prev=n-1;

   261   freenodes=nodes_size;

   262   nodes_size=n;

   263 }

   265 template<class N, class E> OldGraph<N,E> &OldGraph<N,E>::operator=(OldGraph<N,E> &H)

   266 {

   267   Clean();

   269   int i;

   270   EdgePoint e;

   272   for(i=H.FirstNode();i!=INVALID;i=H.NextNode(i))

   273     {

   274       AddNode(i);

   275       operator()(i)=H(i);

   276     }

   277   for(i=H.FirstNode();i!=INVALID;i=H.NextNode(i))

   278     for(e=H.FirstOut(i);e;e=H.NextOut(e))

   279       operator()(AddEdge(i,H.To(e),H.Index(e)))=H(e);

   281    return *this;

   282 }

   284 template<class N, class E> int OldGraph<N,E>::EdgeNum()

   285 {

   286   int n=firstnode, m=0;

   287   EdgePoint e;

   288   while(n != INVALID)

   289   {

   290     e=FirstOut(n);

   291     while (e != NULL)

   292     {

   293       m++;

   294       e=NextOut(e);

   295     }

   296     n=nodes[n].next;

   297   }

   298   return m;

   299 }

   301 template<class N, class E> int OldGraph<N,E>::AddNode()

   302 {

   303   int i;

   305   if(freenodes==INVALID) inc_nodes_size(2*nodes_size);

   307   i=freenodes;

   308   if(firstnode!=INVALID) nodes[firstnode].prev=i;

   309   freenodes=nodes[i].next;

   310   new(nodes[i].data) N;  //Explicit constructor call

   311   nodes[i].next=firstnode;

   312   nodes[i].prev=INVALID;

   313   nodes[i].indeg=0;

   314   firstnode=i;

   315   if(freenodes!=INVALID) nodes[freenodes].prev=INVALID;

   316   nodenum++;

   317   return i;

   318 }

   320 template<class N, class E> int OldGraph<N,E>::AddNode(int n)

   321 {

   322   int i;

   324   if(n>=nodes_size)

   325     {

   326       for(i=INIT_NODES_SIZE;i<=n;i*=2) ;

   327       inc_nodes_size(i);

   328     }

   330   if(nodes[n].indeg==FREE_NODE)

   331     {

   332       new(nodes[n].data) N;  //Explicit constructor call

   333       if(nodes[n].next!=INVALID) nodes[nodes[n].next].prev = nodes[n].prev;

   334       if(nodes[n].prev!=INVALID) nodes[nodes[n].prev].next = nodes[n].next;

   335       else freenodes = nodes[n].next;

   337       nodes[n].prev = INVALID;

   338       if((nodes[n].next = firstnode)!=INVALID) nodes[firstnode].prev=n;

   339       firstnode = n;

   340       nodenum++;

   341       nodes[n].indeg=0;

   342     }

   343   return n;

   344 }

   346 template<class N, class E> void OldGraph<N,E>::Delete(int n)

   347 {

   348   if(n==INVALID||nodes[n].indeg==FREE_NODE) return;

   350   EdgePoint e;

   352   while(e=FirstIn(n)) Delete(e);

   353   while(e=FirstOut(n)) Delete(e);

   355   if(n==firstnode) firstnode=nodes[n].next;

   356   if(nodes[n].prev!=INVALID) nodes[nodes[n].prev].next=nodes[n].next;

   357   if(nodes[n].next!=INVALID) nodes[nodes[n].next].prev=nodes[n].prev;

   358   if(freenodes!=INVALID) nodes[freenodes].prev=n;

   359   nodes[n].next=freenodes;

   360   nodes[n].prev=INVALID;

   361   nodes[n].indeg=FREE_NODE;

   362   ((N*)(nodes[n].data))->~N();  //Explicit destructor call

   363   freenodes=n;

   365   nodenum--;

   366 }

   368 template<class N, class E> EdgePoint OldGraph<N,E>::AddEdge(int f, int t)

   369 {

   370   int i;

   371   edge_block *peb;

   372   edge_block **ppeb;

   373   edge_t *e;

   375   if(!freeedges)

   376     {

   377       if(edge_block_num>=edge_block_max)

   378 	{

   379 	  ppeb = new edge_block* [edge_block_max*=2];

   380 	  for(i=0;i<edge_block_num;i++) ppeb[i]=edges[i];

   381 	  delete [] edges;

   382 	  edges = ppeb;

   383 	}

   384       peb = new edge_block;

   385       edges[edge_block_num] = peb;

   387       for(i=0;i<EDGE_BLOCK_SIZE;i++)

   388 	{

   389 	  ((edge_t*)peb->fields)[i].nextin=((edge_t*)peb->fields)+(i+1);

   390 	  ((edge_t*)peb->fields)[i].previn=((edge_t*)peb->fields)+(i-1);

   391 	  ((edge_t*)peb->fields)[i].index.block = edge_block_num;

   392 	  ((edge_t*)peb->fields)[i].index.index = i;

   393 	  ((edge_t*)peb->fields)[i].from = INVALID;

   394 	}

   395       ((edge_t*)peb->fields)[0].previn=

   396 	((edge_t*)peb->fields)[EDGE_BLOCK_SIZE-1].nextin=NULL;

   397       freeedges = (edge_t*)peb->fields;

   398       edge_block_num++;

   399     }

   401   e=(edge_t *)freeedges;

   402   new (e->data) E;  //Explicit constructor call

   403   freeedges=e->nextin;

   404   if(freeedges) freeedges->previn=NULL;

   406   e->from=f; e->to=t;

   407   e->previn=e->prevout=NULL;

   408   e->nextin=nodes[t].firstin;

   409   e->nextout=nodes[f].firstout;

   410   if(nodes[t].firstin) nodes[t].firstin->previn=e;

   411   if(nodes[f].firstout) nodes[f].firstout->prevout=e;

   412   nodes[t].firstin=nodes[f].firstout=e;

   413   nodes[t].indeg++; nodes[f].outdeg++;

   415   return (EdgePoint)e;

   417 }

   419 template<class N, class E>

   420 EdgePoint OldGraph<N,E>::AddEdge(int f, int t, EdgeIndex in)

   421 {

   422   int i;

   423   edge_block *peb;

   424   edge_block **ppeb;

   425   edge_t *e;

   427   while(edge_block_num<=in.block)

   428     {

   429       if(edge_block_num>=edge_block_max)

   430 	{

   431 	  ppeb = new edge_block* [edge_block_max*=2];

   432 	  for(i=0;i<edge_block_num;i++) ppeb[i]=edges[i];

   433 	  delete [] edges;

   434 	  edges = ppeb;

   435 	}

   436       peb = new edge_block;

   437       edges[edge_block_num] = peb;

   439       for(i=0;i<EDGE_BLOCK_SIZE;i++)

   440 	{

   441 	  ((edge_t*)peb->fields)[i].nextin=((edge_t*)peb->fields)+(i+1);

   442 	  ((edge_t*)peb->fields)[i].previn=((edge_t*)peb->fields)+(i-1);

   443 	  ((edge_t*)peb->fields)[i].index.block = edge_block_num;

   444 	  ((edge_t*)peb->fields)[i].index.index = i;

   445 	  ((edge_t*)peb->fields)[i].from = INVALID;

   446 	}

   447       ((edge_t*)peb->fields)[0].previn=NULL;

   448       ((edge_t*)peb->fields)[EDGE_BLOCK_SIZE-1].nextin=freeedges;

   449       if(freeedges)

   450 	freeedges->previn = ((edge_t*)peb->fields) + (EDGE_BLOCK_SIZE-1);

   451       freeedges = (edge_t*)peb->fields;

   452       edge_block_num++;

   453     }

   456   e=((edge_t*)(edges[in.block]->fields))+in.index;

   457   if(e->from==INVALID)

   458     {

   459       if(e->previn) e->previn->nextin = e->nextin;

   460                else freeedges = e->nextin;

   461       if(e->nextin) e->nextin->previn = e->previn;

   463       new (e->data) E;  //Explicit constructor call

   465       e->from=f; e->to=t;

   466       e->previn=e->prevout=NULL;

   467       e->nextin=nodes[t].firstin;

   468       e->nextout=nodes[f].firstout;

   469       if(nodes[t].firstin) nodes[t].firstin->previn=e;

   470       if(nodes[f].firstout) nodes[f].firstout->prevout=e;

   471       nodes[t].firstin=nodes[f].firstout=e;

   472       nodes[t].indeg++; nodes[f].outdeg++;

   473     }

   474   return (EdgePoint)e;

   475 }

   477 template<class N, class E> void OldGraph<N,E>::Delete(EdgePoint e)

   478 {

   479   if(!e||e->from==INVALID) return;

   481   ((E*)(((edge_t*)e)->data))->~E();  //Explicit destructor call

   483   nodes[e->from].outdeg--; nodes[e->to].indeg--;

   486   if(e->previn)

   487     e->previn->nextin=e->nextin;

   488   else nodes[e->to].firstin=e->nextin;

   489   if(e->prevout)

   490     e->prevout->nextout=e->nextout;

   491   else nodes[e->from].firstout=e->nextout;

   492   if(e->nextin)

   493     e->nextin->previn=e->previn;

   494   if(e->nextout)

   495     e->nextout->prevout=e->prevout;

   497   if(freeedges) freeedges->previn=e;

   498   e->previn=NULL; e->nextin=freeedges;

   500   e->from = INVALID;

   501   freeedges=e;

   502 }

   504 template<class N, class E> EdgePoint OldGraph<N,E>::Edge(int f, int t)

   505 {

   506   EdgePoint e;

   508   for(e=nodes[f].firstout;e&&e->to!=t;e=e->nextout) ;

   510   return (EdgePoint) e;

   511 }

   513 template<class N, class E> void OldGraph<N,E>::Reverse(EdgePoint e)

   514 {

   515   if(!e) return;

   517   nodes[e->from].outdeg--; nodes[e->to].indeg--;

   519   if(e->previn)

   520     e->previn->nextin=e->nextin;

   521   else nodes[e->to].firstin=e->nextin;

   522   if(e->prevout)

   523     e->prevout->nextout=e->nextout;

   524   else nodes[e->from].firstout=e->nextout;

   525   if(e->nextin)

   526     e->nextin->previn=e->previn;

   527   if(e->nextout)

   528     e->nextout->prevout=e->prevout;

   530   int t,f;

   531   f=e->to;e->to=t=e->from;

   532   e->from=f;

   534   e->previn=e->prevout=NULL;

   535   e->nextin=nodes[t].firstin;

   536   e->nextout=nodes[f].firstout;

   537   if(nodes[t].firstin) nodes[t].firstin->previn=e;

   538   if(nodes[f].firstout) nodes[f].firstout->prevout=e;

   539   nodes[t].firstin=nodes[f].firstout=e;

   540   nodes[t].indeg++; nodes[f].outdeg++;

   542 }

   544 template<class N, class E> void OldGraph<N,E>::DeleteEdges()

   545 {

   546   int n;

   547   for(n=FirstNode();n!=INVALID;n=NextNode(n))

   548     while(FirstOut(n)) Delete(FirstOut(n));

   549 }

   551 #endif

author	marci
	Tue, 28 Sep 2004 13:45:39 +0000
changeset 915	751ed145bdae
parent 3	272a5677bd6d
permissions	-rw-r--r--