COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/oldgraph.h @ 2:37117ebbabe2

Last change on this file since 2:37117ebbabe2 was 1:207fb3c727cb, checked in by Alpar Juttner, 17 years ago

src/demo/graph.h: a proposal for a graph implementation
src/demo/graphdemo.cc: a simle demo using graph.h

File size: 14.4 KB
Line 
1// -*-mode: c++; -*-
2#ifndef __OLDGRAPH_H_
3#define __OLDGRAPH_H_
4
5#include <stdio.h>
6
7//#include <new>
8
9#define INVALID -1
10#define FREE_NODE INVALID
11
12#define EDGE_BLOCK_SIZE 100
13#define INIT_NODES_SIZE 10
14#define INIT_EDGES_BLOCK_MAX 10
15
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)))
20
21struct EdgeIndex { int block,index; };
22
23extern EdgeIndex InvalidIndex;
24
25class EdgeCorp;
26typedef EdgeCorp *EdgePoint;
27
28class EdgeCorp {
29 public:
30  int from,to;      //from==INVALID <=> this is a free edge.
31  EdgePoint previn,nextin,prevout,nextout;
32  EdgeIndex index;
33
34  int From() { return from; }
35  int To() { return to; }
36  EdgePoint NextIn() { return nextin; }
37  EdgePoint NextOut() { return nextout; }
38};
39
40inline int From(EdgePoint e) { return e->from; }
41inline int To(EdgePoint e) { return e->to; }
42inline EdgePoint NextIn(EdgePoint e) { return e->nextin; }
43inline EdgePoint NextOut(EdgePoint e) { return e->nextout; }
44
45
46//////////////////////////////////////////////////////////////////////
47//   OLDGRAPH TEMPLATE
48//////////////////////////////////////////////////////////////////////
49// Copy Constructor should be provided for N
50
51//class Graph;
52//class Graph::NodeIterator; //Nem megy. Disznosag!
53template <class N, class E> class OldGraph
54{
55
56  //  friend class NEGRO::Graph::NodeIterator; //Nem megy. Disznosag!
57
58
59  class nodes_t;
60  friend class OldGraph::nodes_t;
61  class edge_block;
62  friend class OldGraph::edge_block;
63 
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  };
72
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;
82
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    }
94   
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;
106
107  void setup(int nosi = INIT_NODES_SIZE);
108  void destroy();
109  void inc_nodes_size(int n);
110 
111 public:
112  int NodeNum() {return nodenum;};
113  int EdgeNum();
114  int MaxNode() {return nodes_size;};
115  int FirstNode() {return firstnode;};
116  int NextNode(int n) {return nodes[n].next;};
117  int PrevNode(int n) {return nodes[n].prev;};
118  N& operator()(int n) {return *(N*)(nodes[n].data);};
119  N& Data      (int n) {return *(N*)(nodes[n].data);};
120  int AddNode();
121  void AddNodeBlock(int n) {for(int i=0;i<n;i++) AddNode();}
122  int AddNode(int n);
123  void Delete(int n);
124  int isaNode(int n) {return n>=0&&n<nodes_size&&nodes[n].indeg!=FREE_NODE;};
125 
126  int InDeg(int n) {return nodes[n].indeg;};
127  int OutDeg(int n) {return nodes[n].outdeg;};
128  EdgePoint FirstIn(int n) {return nodes[n].firstin;};
129  EdgePoint FirstOut(int n) {return nodes[n].firstout;};
130
131  E& operator()(EdgePoint e) {return *(E*)(((edge_t*)e)->data);};
132  E& Data      (EdgePoint e) {return *(E*)(((edge_t*)e)->data);};
133  int From(EdgePoint e) {return e->from;};
134  int To(EdgePoint e) {return e->to;};
135  EdgePoint NextIn(EdgePoint e)
136    {return e->nextin;};
137  EdgePoint NextOut(EdgePoint e)
138    {return e->nextout;};
139  EdgePoint AddEdge(int f, int t);
140  void Delete(EdgePoint e);
141  EdgePoint Edge(int f,int t);
142  //  EdgePoint Edge(E &d)
143  //    {return (EdgePoint)(((char*)&d)-(char*)&(((edge_t*)NULL)->data));};
144  E& operator()(int f, int t) {return *(E*)(((edge_t*)Edge(f,t))->data);};
145  E& Data(int f, int t) {return *(E*)(((edge_t*)Edge(f,t))->data);};
146  void Delete(int f, int t) {Delete(Edge(f,t));};
147  void Reverse(EdgePoint e);
148
149  // Functions for EdgeIndex
150 
151  EdgePoint Edge(EdgeIndex i)
152    { return (EdgePoint)(edges[i.block]->fields+i.index);};
153  EdgeIndex Index(EdgePoint e) { return e->index;};
154  EdgeIndex Index(int f, int t) { EdgePoint e; return Edge(f,t)->index; }
155  void Delete(EdgeIndex i) { Delete(Edge(i));};
156  E& operator()(EdgeIndex i)
157     {return *(E*)(edges[i.block]->fields[i.index].data);};
158  E& Data(EdgeIndex i)
159     {return *(E*)(edges[i.block]->fields[i.index].data);};
160  EdgePoint AddEdge(int f, int t,EdgeIndex in);
161 
162
163 
164  // Operators for symmetric graphs:
165
166  EdgePoint FirstEdge(int n)
167    { return (EdgePoint)(FirstIn(n)?FirstIn(n):FirstOut(n));};
168  EdgePoint NextEdge(int n,EdgePoint e)
169    { return From(e)==n?NextOut(e):(NextIn(e)?NextIn(e):FirstOut(n)); };
170  int Opposite(EdgePoint e,int n)
171    { return From(e)+To(e)-n; };
172 
173  // Initializers, destructors
174       
175  OldGraph() {setup();};
176  OldGraph(int nosi) {setup(nosi);};
177  OldGraph(OldGraph<N,E> &H) {setup();operator=(H);};
178  ~OldGraph() {destroy();}; 
179  void Clean(int nosi = INIT_NODES_SIZE) {destroy();setup(nosi);};
180  void Clear(int nosi = INIT_NODES_SIZE) {destroy();setup(nosi);};
181
182  void DeleteEdges();
183   
184  OldGraph<N,E> &operator=(OldGraph<N,E> &H);
185};
186
187//////////////////////////////////////////////////////////////////////
188// Template Definitions
189//////////////////////////////////////////////////////////////////////
190
191//#include <stdio.h>
192
193//**********************************************************************
194//                          OldGraph definitions
195//**********************************************************************
196
197template<class N, class E> void OldGraph<N,E>::setup(int nosi) {
198  int i;
199
200  //Set up nodes
201  nodenum = 0;
202  nodes_size = nosi;
203  // nodes = (nodes_t*) new char[sizeof(nodes_t)*nodes_size];
204  nodes = (nodes_t*) new nodes_t [nodes_size];
205  for(i=0;i<nodes_size;i++)
206    {
207      nodes[i].prev=i-1;
208      nodes[i].next=i+1;
209      nodes[i].indeg=FREE_NODE;
210      nodes[i].outdeg=0;
211      nodes[i].firstin=nodes[i].firstout=NULL;
212    }
213  firstnode=nodes[0].prev=nodes[nodes_size-1].next=INVALID;
214  freenodes=0;
215  //Set up edge-list_template_type;
216  freeedges = NULL;
217 
218  edges = new edge_block* [edge_block_max=INIT_EDGES_BLOCK_MAX];
219  edge_block_num = 0;
220 
221}
222
223template<class N, class E> void OldGraph<N,E>::destroy()
224{
225  edge_block *oe;
226  int i;
227 
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}
233
234template<class N, class E> void OldGraph<N,E>::inc_nodes_size(int n)
235{
236  int i;
237  if(n<=nodenum) return;
238 
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    }
247 
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}
264
265template<class N, class E> OldGraph<N,E> &OldGraph<N,E>::operator=(OldGraph<N,E> &H)
266{
267  Clean();
268
269  int i;
270  EdgePoint e;
271 
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);
280
281   return *this;
282}
283
284template<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}
300
301template<class N, class E> int OldGraph<N,E>::AddNode()
302{
303  int i;
304 
305  if(freenodes==INVALID) inc_nodes_size(2*nodes_size);
306 
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}
319
320template<class N, class E> int OldGraph<N,E>::AddNode(int n)
321{
322  int i;
323 
324  if(n>=nodes_size)
325    {
326      for(i=INIT_NODES_SIZE;i<=n;i*=2) ;
327      inc_nodes_size(i);
328    }
329 
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;
336     
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}
345
346template<class N, class E> void OldGraph<N,E>::Delete(int n)
347{
348  if(n==INVALID||nodes[n].indeg==FREE_NODE) return;
349
350  EdgePoint e;
351 
352  while(e=FirstIn(n)) Delete(e);
353  while(e=FirstOut(n)) Delete(e);
354 
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;
364
365  nodenum--;
366}
367
368template<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;
374 
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;
386     
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    }
400 
401  e=(edge_t *)freeedges;
402  new (e->data) E;  //Explicit constructor call
403  freeedges=e->nextin;
404  if(freeedges) freeedges->previn=NULL;
405 
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++;
414
415  return (EdgePoint)e;
416 
417}
418
419template<class N, class E>
420EdgePoint 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;
426 
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;
438     
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    }
454 
455 
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;
462
463      new (e->data) E;  //Explicit constructor call
464     
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}
476
477template<class N, class E> void OldGraph<N,E>::Delete(EdgePoint e)
478{
479  if(!e||e->from==INVALID) return;
480 
481  ((E*)(((edge_t*)e)->data))->~E();  //Explicit destructor call
482 
483  nodes[e->from].outdeg--; nodes[e->to].indeg--;
484
485 
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;
496 
497  if(freeedges) freeedges->previn=e;
498  e->previn=NULL; e->nextin=freeedges;
499
500  e->from = INVALID;
501  freeedges=e;
502}
503
504template<class N, class E> EdgePoint OldGraph<N,E>::Edge(int f, int t)
505{
506  EdgePoint e;
507 
508  for(e=nodes[f].firstout;e&&e->to!=t;e=e->nextout) ;
509 
510  return (EdgePoint) e;
511}
512
513template<class N, class E> void OldGraph<N,E>::Reverse(EdgePoint e)
514{
515  if(!e) return;
516
517  nodes[e->from].outdeg--; nodes[e->to].indeg--;
518 
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;
529 
530  int t,f;
531  f=e->to;e->to=t=e->from;
532  e->from=f;
533
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++;
541
542}
543
544template<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}
550
551#endif
Note: See TracBrowser for help on using the repository browser.