A bit better msg.
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;
26 typedef EdgeCorp *EdgePoint;
30 int from,to; //from==INVALID <=> this is a free edge.
31 EdgePoint previn,nextin,prevout,nextout;
34 int From() { return from; }
35 int To() { return to; }
36 EdgePoint NextIn() { return nextin; }
37 EdgePoint NextOut() { return nextout; }
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 //////////////////////////////////////////////////////////////////////
48 //////////////////////////////////////////////////////////////////////
49 // Copy Constructor should be provided for N
52 //class Graph::NodeIterator; //Nem megy. Disznosag!
53 template <class N, class E> class OldGraph
56 // friend class NEGRO::Graph::NodeIterator; //Nem megy. Disznosag!
60 friend class OldGraph::nodes_t;
62 friend class OldGraph::edge_block;
64 class edge_t : public EdgeCorp {
66 //edge_t *previn,*nextin,*prevout,*nextout;
79 int indeg,outdeg; // indeg==FREE_NODE <=> this node is free.
80 EdgePoint firstin, firstout;
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) {
91 // (*(N*)(data))=(*(N*)(n.data));
96 int nodenum, nodes_size;
97 int firstnode, freenodes;
101 // char fields[sizeof(edge_t)*EDGE_BLOCK_SIZE];
102 edge_t fields[EDGE_BLOCK_SIZE];
104 int edge_block_num,edge_block_max;
107 void setup(int nosi = INIT_NODES_SIZE);
109 void inc_nodes_size(int n);
112 int NodeNum() {return nodenum;};
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);};
121 void AddNodeBlock(int n) const {for(int i=0;i<n;i++) AddNode();}
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
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);};
185 OldGraph<N,E> &operator=(OldGraph<N,E> &H);
188 //////////////////////////////////////////////////////////////////////
189 // Template Definitions
190 //////////////////////////////////////////////////////////////////////
194 //**********************************************************************
195 // OldGraph definitions
196 //**********************************************************************
198 template<class N, class E> void OldGraph<N,E>::setup(int 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++)
210 nodes[i].indeg=FREE_NODE;
212 nodes[i].firstin=nodes[i].firstout=NULL;
214 firstnode=nodes[0].prev=nodes[nodes_size-1].next=INVALID;
216 //Set up edge-list_template_type;
219 edges = new edge_block* [edge_block_max=INIT_EDGES_BLOCK_MAX];
224 template<class N, class E> void OldGraph<N,E>::destroy()
228 while(firstnode!=INVALID) Delete(firstnode);
230 for(i=0;i<edge_block_num;i++) delete edges[i];
234 template<class N, class E> void OldGraph<N,E>::inc_nodes_size(int n)
237 if(n<=nodenum) return;
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++)
244 nn[i].Copy(nodes[i]);
245 if(nodes[i].indeg!=FREE_NODE) ((N*)(nodes[i].data))->~N();
250 for(i=nodes_size;i<n;i++)
254 nodes[i].indeg=FREE_NODE;
256 nodes[i].firstin=nodes[i].firstout=NULL;
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;
265 template<class N, class E> OldGraph<N,E> &OldGraph<N,E>::operator=(OldGraph<N,E> &H)
272 for(i=H.FirstNode();i!=INVALID;i=H.NextNode(i))
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);
284 template<class N, class E> int OldGraph<N,E>::EdgeNum()
286 int n=firstnode, m=0;
301 template<class N, class E> int OldGraph<N,E>::AddNode()
305 if(freenodes==INVALID) inc_nodes_size(2*nodes_size);
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;
315 if(freenodes!=INVALID) nodes[freenodes].prev=INVALID;
320 template<class N, class E> int OldGraph<N,E>::AddNode(int n)
326 for(i=INIT_NODES_SIZE;i<=n;i*=2) ;
330 if(nodes[n].indeg==FREE_NODE)
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;
346 template<class N, class E> void OldGraph<N,E>::Delete(int n)
348 if(n==INVALID||nodes[n].indeg==FREE_NODE) return;
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
368 template<class N, class E> EdgePoint OldGraph<N,E>::AddEdge(int f, int t)
377 if(edge_block_num>=edge_block_max)
379 ppeb = new edge_block* [edge_block_max*=2];
380 for(i=0;i<edge_block_num;i++) ppeb[i]=edges[i];
384 peb = new edge_block;
385 edges[edge_block_num] = peb;
387 for(i=0;i<EDGE_BLOCK_SIZE;i++)
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;
395 ((edge_t*)peb->fields)[0].previn=
396 ((edge_t*)peb->fields)[EDGE_BLOCK_SIZE-1].nextin=NULL;
397 freeedges = (edge_t*)peb->fields;
401 e=(edge_t *)freeedges;
402 new (e->data) E; //Explicit constructor call
404 if(freeedges) freeedges->previn=NULL;
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++;
419 template<class N, class E>
420 EdgePoint OldGraph<N,E>::AddEdge(int f, int t, EdgeIndex in)
427 while(edge_block_num<=in.block)
429 if(edge_block_num>=edge_block_max)
431 ppeb = new edge_block* [edge_block_max*=2];
432 for(i=0;i<edge_block_num;i++) ppeb[i]=edges[i];
436 peb = new edge_block;
437 edges[edge_block_num] = peb;
439 for(i=0;i<EDGE_BLOCK_SIZE;i++)
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;
447 ((edge_t*)peb->fields)[0].previn=NULL;
448 ((edge_t*)peb->fields)[EDGE_BLOCK_SIZE-1].nextin=freeedges;
450 freeedges->previn = ((edge_t*)peb->fields) + (EDGE_BLOCK_SIZE-1);
451 freeedges = (edge_t*)peb->fields;
456 e=((edge_t*)(edges[in.block]->fields))+in.index;
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
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++;
477 template<class N, class E> void OldGraph<N,E>::Delete(EdgePoint e)
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--;
487 e->previn->nextin=e->nextin;
488 else nodes[e->to].firstin=e->nextin;
490 e->prevout->nextout=e->nextout;
491 else nodes[e->from].firstout=e->nextout;
493 e->nextin->previn=e->previn;
495 e->nextout->prevout=e->prevout;
497 if(freeedges) freeedges->previn=e;
498 e->previn=NULL; e->nextin=freeedges;
504 template<class N, class E> EdgePoint OldGraph<N,E>::Edge(int f, int t)
508 for(e=nodes[f].firstout;e&&e->to!=t;e=e->nextout) ;
510 return (EdgePoint) e;
513 template<class N, class E> void OldGraph<N,E>::Reverse(EdgePoint e)
517 nodes[e->from].outdeg--; nodes[e->to].indeg--;
520 e->previn->nextin=e->nextin;
521 else nodes[e->to].firstin=e->nextin;
523 e->prevout->nextout=e->nextout;
524 else nodes[e->from].firstout=e->nextout;
526 e->nextin->previn=e->previn;
528 e->nextout->prevout=e->prevout;
531 f=e->to;e->to=t=e->from;
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++;
544 template<class N, class E> void OldGraph<N,E>::DeleteEdges()
547 for(n=FirstNode();n!=INVALID;n=NextNode(n))
548 while(FirstOut(n)) Delete(FirstOut(n));