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 | |
---|
21 | struct EdgeIndex { int block,index; }; |
---|
22 | |
---|
23 | extern EdgeIndex InvalidIndex; |
---|
24 | |
---|
25 | class EdgeCorp; |
---|
26 | typedef EdgeCorp *EdgePoint; |
---|
27 | |
---|
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; |
---|
33 | |
---|
34 | int From() { return from; } |
---|
35 | int To() { return to; } |
---|
36 | EdgePoint NextIn() { return nextin; } |
---|
37 | EdgePoint NextOut() { return nextout; } |
---|
38 | }; |
---|
39 | |
---|
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; } |
---|
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! |
---|
53 | template <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 | |
---|
197 | template<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 | |
---|
223 | template<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 | |
---|
234 | template<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 | |
---|
265 | template<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 | |
---|
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 | } |
---|
300 | |
---|
301 | template<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 | |
---|
320 | template<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 | |
---|
346 | template<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 | |
---|
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; |
---|
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 | |
---|
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; |
---|
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 | |
---|
477 | template<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 | |
---|
504 | template<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 | |
---|
513 | template<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 | |
---|
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 | } |
---|
550 | |
---|
551 | #endif |
---|