1 // -*-mode: c++; -*- |
|
2 #ifndef __GRAPH_H_ |
|
3 #define __GRAPH_H_ |
|
4 |
|
5 //inline void *operator new(size_t s, void *p) { return p; } |
|
6 #include <new> |
|
7 #include <vector> |
|
8 |
|
9 namespace NEGRO |
|
10 { |
|
11 using namespace std; |
|
12 |
|
13 #include "oldgraph.h" |
|
14 |
|
15 template <class N, class E> class Graph : protected OldGraph<N,E> |
|
16 { |
|
17 public: |
|
18 typedef E EdgeType; |
|
19 typedef N NodeType; |
|
20 |
|
21 class EdgeIt |
|
22 { |
|
23 public: |
|
24 NEGRO::EdgePoint e; |
|
25 bool valid() { return e; } |
|
26 }; |
|
27 |
|
28 class InEdgeIt : public EdgeIt {}; |
|
29 class OutEdgeIt : public EdgeIt {}; |
|
30 class BiEdgeIt : public EdgeIt {}; |
|
31 class SymEdgeIt : public EdgeIt {}; |
|
32 |
|
33 typedef int NodeIt; |
|
34 |
|
35 typedef NodeIt EachNodeIt; |
|
36 |
|
37 class NodeIterator; |
|
38 |
|
39 class EdgeIterator; |
|
40 class InEdgeIterator; |
|
41 class OutEdgeIterator; |
|
42 class BiEdgeIterator; |
|
43 class SymEdgeIterator; |
|
44 class AllEdgeIterator; |
|
45 |
|
46 class FirstAnythingTypeNode; //Required by the unified First() function. |
|
47 |
|
48 friend class NodeIterator; |
|
49 friend class EdgeIterator; |
|
50 friend class InEdgeIterator; |
|
51 friend class OutEdgeIterator; |
|
52 friend class BiEdgeIterator; |
|
53 friend class SymEdgeIterator; |
|
54 friend class EachEdgeIterator; |
|
55 |
|
56 class NodeIterator |
|
57 { |
|
58 Graph<N,E> *G; //operator*() miatt kell!!! |
|
59 int n; //nem kellene, ha itt mutato lenne!! |
|
60 public: |
|
61 |
|
62 NodeIterator() {;} |
|
63 NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong. |
|
64 {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();} |
|
65 NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;} |
|
66 |
|
67 NodeIterator &goNext() { n=G->NextNode(n); return *this;} |
|
68 NodeIterator next() const { return NodeIterator(*this).goNext();} |
|
69 NodeIterator &operator++() { return goNext();} |
|
70 NodeIterator operator++(int) |
|
71 {NodeIterator tmp(*this); goNext(); return tmp;} |
|
72 bool valid() { return n!=INVALID; } |
|
73 |
|
74 N &operator*() const { return G->Data(n); } |
|
75 N *operator->() const { return &G->Data(n); } |
|
76 |
|
77 bool operator==(const NodeIterator &i) const {return n==i.n;} |
|
78 bool operator!=(const NodeIterator &i) const {return n!=i.n;} |
|
79 |
|
80 int index() const { return n; } //If the nodes are indexable |
|
81 friend class Graph; |
|
82 friend class EdgeIterator; |
|
83 friend class InEdgeIterator; |
|
84 friend class OutEdgeIterator; |
|
85 friend class BiEdgeIterator; |
|
86 friend class SymEdgeIterator; |
|
87 friend class EachEdgeIterator; |
|
88 friend class FirstAnythingTypeNode; |
|
89 |
|
90 //Nem kellene egy: |
|
91 // static NodeIterator &GetInvalid(); ? |
|
92 }; |
|
93 |
|
94 class EdgeIterator |
|
95 { |
|
96 |
|
97 Graph<N,E> *G; //Itt baj van!!!!! operator*() miatt kell! |
|
98 //Ez csak kicsit baj, de: |
|
99 // Meg a From() es To() miatt!!!!!!!!!! |
|
100 |
|
101 NEGRO::EdgeIt e; |
|
102 |
|
103 public: |
|
104 EdgeIterator() {;} //Kell inicializalni? (Nem) |
|
105 EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;} |
|
106 |
|
107 // Lehet, hogy ez a ketto nem kell!!! |
|
108 |
|
109 NodeIterator tail() const {NodeIterator i;i.G=G;i.n=e->From();return i;} |
|
110 NodeIterator head() const {NodeIterator i;i.G=G;i.n=e->To();return i;} |
|
111 NodeIterator opposite(const NodeIterator &n) const |
|
112 {return n==tail()?head():tail();} |
|
113 |
|
114 bool valid() {return e;} |
|
115 E &operator*() const { return G->Data(e); } |
|
116 E *operator->() const { return &G->Data(e); } |
|
117 |
|
118 //operator const OutEdgeIterator (); |
|
119 //operator const InEdgeIterator (); |
|
120 //operator const BiEdgeIterator (); |
|
121 //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal |
|
122 |
|
123 bool operator==(const EdgeIterator &i) const {return e==i.e;} |
|
124 bool operator!=(const EdgeIterator &i) const {return e!=i.e;} |
|
125 |
|
126 int Index() const {return e->index.block*EDGE_BLOCK_SIZE+e->index.index;} |
|
127 //If the edges are indexable |
|
128 |
|
129 friend class Graph; |
|
130 friend class InEdgeIterator; |
|
131 friend class OutEdgeIterator; |
|
132 friend class BiEdgeIterator; |
|
133 friend class SymEdgeIterator; |
|
134 friend class EachEdgeIterator; |
|
135 }; |
|
136 |
|
137 class BiEdgeIterator : public EdgeIterator |
|
138 { |
|
139 public: |
|
140 BiEdgeIterator &goNextIn() { e=e->NextIn(); return *this;} |
|
141 BiEdgeIterator &goNextOut() { e=e->NextOut(); return *this;} |
|
142 BiEdgeIterator nextIn() const {return BiEdgeIterator(*this).goNextIn();} |
|
143 BiEdgeIterator nextOut() const {return BiEdgeIterator(*this).goNextOut();} |
|
144 |
|
145 operator InEdgeIterator () |
|
146 {InEdgeIterator i; i.G=G;i.e=e;return i;} |
|
147 operator OutEdgeIterator () |
|
148 {OutEdgeIterator i; i.G=G;i.e=e;return i;} |
|
149 //operator const SymEdgeIterator () |
|
150 |
|
151 friend class Graph; |
|
152 }; |
|
153 |
|
154 class InEdgeIterator : public EdgeIterator |
|
155 //Ne a BiEdgeIterator-bol szarmazzon? |
|
156 { |
|
157 public: |
|
158 InEdgeIterator() {} |
|
159 InEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n) |
|
160 { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);} |
|
161 |
|
162 InEdgeIterator &GoNext() { e=e->NextIn(); return *this;} |
|
163 InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();} |
|
164 InEdgeIterator &operator++() { return GoNext();} |
|
165 InEdgeIterator operator++(int) |
|
166 {InEdgeIterator tmp(*this); GoNext(); return tmp;} |
|
167 |
|
168 operator const OutEdgeIterator () |
|
169 {OutEdgeIterator i; i.G=G;i.e=e;return i;} |
|
170 operator const BiEdgeIterator () |
|
171 {EdgeIterator i; i.G=G;i.e=e;return i;} |
|
172 // operator const SymEdgeIterator (); |
|
173 |
|
174 NodeIterator Anode() const {return To();} |
|
175 NodeIterator Bnode() const {return From();} |
|
176 |
|
177 friend class Graph; |
|
178 }; |
|
179 |
|
180 class OutEdgeIterator : public EdgeIterator |
|
181 { |
|
182 public: |
|
183 OutEdgeIterator() {} |
|
184 OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n) |
|
185 { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);} |
|
186 |
|
187 OutEdgeIterator &goNext() { e=e->NextOut(); return *this;} |
|
188 OutEdgeIterator next() const {return OutEdgeIterator(*this).goNext();} |
|
189 OutEdgeIterator &operator++() { return goNext();} |
|
190 OutEdgeIterator operator++(int) |
|
191 {OutEdgeIterator tmp(*this); goNext(); return tmp;} |
|
192 |
|
193 NodeIterator aNode() const {return tail();} |
|
194 NodeIterator bNode() const {return head();} |
|
195 |
|
196 operator const InEdgeIterator () |
|
197 {InEdgeIterator i; i.G=G;i.e=e;return i;} |
|
198 operator const BiEdgeIterator () |
|
199 {BiEdgeIterator i; i.G=G;i.e=e;return i;} |
|
200 //operator const SymEdgeIterator(); |
|
201 |
|
202 friend class Graph; |
|
203 }; |
|
204 |
|
205 class SymEdgeIterator : public EdgeIterator |
|
206 { |
|
207 NodeIterator n; // Itt ketszer van a G |
|
208 |
|
209 public: |
|
210 SymEdgeIterator() {} |
|
211 SymEdgeIterator(Graph<N,E> &Gr,const NodeIterator &nn) |
|
212 { G=&Gr; n=nn; e=Gr.OldGraph<N,E>::FirstEdge(nn.n); } |
|
213 |
|
214 SymEdgeIterator &goNext() { e=G->NextEdge(n.n,e); return *this;} |
|
215 SymEdgeIterator next() const {return SymEdgeIterator(*this).goNext();} |
|
216 SymEdgeIterator &operator++() { return goNext();} |
|
217 SymEdgeIterator operator++(int) |
|
218 {SymEdgeIterator tmp(*this); goNext(); return tmp;} |
|
219 |
|
220 NodeIterator aNode() const {return n;} |
|
221 NodeIterator bNode() const {return n.n==tail().n?head():tail();} |
|
222 |
|
223 operator const InEdgeIterator () |
|
224 {InEdgeIterator i; i.G=G;i.e=e;return i;} |
|
225 operator const OutEdgeIterator () |
|
226 {OutEdgeIterator i; i.G=G;i.e=e;return i;} |
|
227 operator const BiEdgeIterator () |
|
228 {BiEdgeIterator i; i.G=G;i.e=e;return i;} |
|
229 |
|
230 friend class Graph; |
|
231 }; |
|
232 |
|
233 class EachEdgeIterator : public EdgeIterator |
|
234 { |
|
235 NodeIterator n; // Itt ketszer van a G |
|
236 |
|
237 public: |
|
238 EachEdgeIterator() {} |
|
239 EachEdgeIterator(Graph<N,E> &Gr) : n(Gr) |
|
240 { |
|
241 e=n.valid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL; |
|
242 } |
|
243 |
|
244 EachEdgeIterator &goNext() |
|
245 { |
|
246 e=e->NextOut(); |
|
247 if(!e && (++n).valid()) e=G->OldGraph<N,E>::FirstOut(n.n); |
|
248 return *this; |
|
249 } |
|
250 EachEdgeIterator next() const {return EachEdgeIterator(*this).goNext();} |
|
251 EachEdgeIterator &operator++() { return goNext();} |
|
252 EachEdgeIterator operator++(int) |
|
253 {EachEdgeIterator tmp(*this); goNext(); return tmp;} |
|
254 |
|
255 |
|
256 NodeIterator aNode() const {return n;} |
|
257 NodeIterator bNode() const {return n.n==tail().n?head():tail();} |
|
258 |
|
259 operator const EdgeIterator () |
|
260 {EdgeIterator i; i.G=G;i.e=e;return i;} |
|
261 operator const InEdgeIterator () |
|
262 {InEdgeIterator i; i.G=G;i.e=e;return i;} |
|
263 operator const OutEdgeIterator () |
|
264 {OutEdgeIterator i; i.G=G;i.e=e;return i;} |
|
265 operator const BiEdgeIterator () |
|
266 {BiEdgeIterator i; i.G=G;i.e=e;return i;} |
|
267 |
|
268 friend class Graph; |
|
269 }; |
|
270 |
|
271 typedef NodeIterator DeletingNodeIterator; |
|
272 typedef EdgeIterator DeletingEdgeIterator; |
|
273 typedef BiEdgeIterator DeletingBiEdgeIterator; |
|
274 typedef OutEdgeIterator DeletingOutEdgeIterator; |
|
275 typedef InEdgeIterator DeletingInEdgeIterator; |
|
276 typedef SymEdgeIterator DeletingSymEdgeIterator; |
|
277 |
|
278 const NodeIterator firstNode() |
|
279 { |
|
280 NodeIterator i; |
|
281 i.G=this;i.n=OldGraph<N,E>::FirstNode(); |
|
282 return i; |
|
283 } |
|
284 |
|
285 void getFirst(NodeIt &p) { p=OldGraph<N,E>::FirstNode(); } |
|
286 |
|
287 void getFirst(InEdgeIt &p,const NodeIt &n) |
|
288 { p=OldGraph<N,E>::FirstIn(n); } |
|
289 void getFirst(OutEdgeIt &p,const NodeIt &n) |
|
290 { p=OldGraph<N,E>::FirstOut(n); } |
|
291 void getFirst(SymEdgeIt &p,const NodeIt &n) |
|
292 { p=OldGraph<N,E>::FirstEdge(n); } |
|
293 void getFirst(EdgeIt &p) //Vegigmegy mindenen |
|
294 { p.e=nodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;} |
|
295 |
|
296 void getFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();} |
|
297 |
|
298 void getFirst(InEdgeIterator &i,const NodeIterator &n) |
|
299 { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); } |
|
300 void getFirst(OutEdgeIterator &i,const NodeIterator &n) |
|
301 { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); } |
|
302 void getFirst(SymEdgeIterator &i,const NodeIterator &n) |
|
303 { i.G=this;i.e=OldGraph<N,E>::FirstEdge(n.n); } |
|
304 void getFirst(EachEdgeIterator &i) //Vegigmegy mindenen |
|
305 { |
|
306 i.G=this; |
|
307 getFirst(i.n); |
|
308 i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL; |
|
309 } |
|
310 |
|
311 |
|
312 |
|
313 //Vagy beginnode()? |
|
314 const DeletingEdgeIterator firstOut(const NodeIterator &n) |
|
315 { |
|
316 EdgeIterator i; |
|
317 i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n); |
|
318 return i; |
|
319 } |
|
320 const DeletingEdgeIterator firstIn(const NodeIterator &n) |
|
321 { |
|
322 EdgeIterator i; |
|
323 i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n); |
|
324 return i; |
|
325 } |
|
326 const DeletingSymEdgeIterator firstSym(const NodeIterator &n) |
|
327 { |
|
328 EdgeIterator i; |
|
329 i.G=n.G;i.n=n.n; |
|
330 i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n); |
|
331 return i; |
|
332 } |
|
333 |
|
334 // class FirstAnythingType; |
|
335 // friend class FirstAnythingType; |
|
336 |
|
337 class FirstAnythingTypeNode |
|
338 { |
|
339 NodeIterator n; |
|
340 public: |
|
341 FirstAnythingTypeNode(NodeIterator i) : n(i) {} |
|
342 |
|
343 operator const InEdgeIterator () const |
|
344 {InEdgeIterator i; n.G->GetFirst(i,n);return i;} |
|
345 operator const OutEdgeIterator () const |
|
346 {OutEdgeIterator i; n.G->GetFirst(i,n);return i;} |
|
347 operator const SymEdgeIterator () const |
|
348 {SymEdgeIterator i; n.G->GetFirst(i,n);return i;} |
|
349 |
|
350 operator const InEdgeIt () const |
|
351 {InEdgeIt i; n.G->GetFirst(i,n);return i;} |
|
352 operator const OutEdgeIt () const |
|
353 {OutEdgeIt i; n.G->GetFirst(i,n);return i;} |
|
354 operator const SymEdgeIt () const |
|
355 {SymEdgeIt i; n.G->GetFirst(i,n);return i;} |
|
356 }; |
|
357 |
|
358 class FirstAnythingType |
|
359 { |
|
360 Graph<N,E> *G; |
|
361 public: |
|
362 FirstAnythingType(Graph<N,E> *gg) : G(gg) {} |
|
363 |
|
364 operator const EachEdgeIterator () const |
|
365 {EachEdgeIterator i; G->GetFirst(i);return i;} |
|
366 operator const EdgeIt () const |
|
367 {EdgeIt i; G->GetFirst(i);return i;} |
|
368 operator const NodeIterator () const |
|
369 {NodeIterator i; G->GetFirst(i);return i;} |
|
370 operator const NodeIt () const |
|
371 {NodeIt i; G->GetFirst(i);return i;} |
|
372 } _FST; |
|
373 |
|
374 // const NodeIterator First() {NodeIterator i;GetFirst(i); return i;} |
|
375 FirstAnythingTypeNode first(NodeIterator &i) |
|
376 {FirstAnythingTypeNode t(i); return t;} |
|
377 const FirstAnythingType &first() {return _FST;} |
|
378 |
|
379 // LastNode() vagy endnode() stb. Nem kell? |
|
380 |
|
381 DeletingNodeIterator addNode() |
|
382 { |
|
383 DeletingNodeIterator i; |
|
384 i.G=this; i.n=OldGraph<N,E>::AddNode(); |
|
385 return i; |
|
386 } |
|
387 DeletingEdgeIterator |
|
388 addEdge(const NodeIterator from,const NodeIterator to) |
|
389 { |
|
390 DeletingEdgeIterator i; |
|
391 i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i; |
|
392 } |
|
393 |
|
394 void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);} |
|
395 void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);} |
|
396 |
|
397 int nodeNum() { OldGraph<N,E>::NodeNum(); } |
|
398 void clean() { OldGraph<N,E>::Clean(); } |
|
399 |
|
400 Graph() : _FST(this) {} |
|
401 |
|
402 // MAPS: |
|
403 template<class T> class NodeMap |
|
404 { |
|
405 Graph<N,E> *G; |
|
406 vector<T> map; |
|
407 |
|
408 public: |
|
409 typedef T value_type; |
|
410 void put(const NodeIterator i, const T &t) {map[i.Index()]=t;} |
|
411 T get(const NodeIterator i) const {return map[i.Index()];} |
|
412 T operator[](NodeIterator i) {return map[i.Index()];} |
|
413 |
|
414 void update() { map.resize(G->MaxNode());} |
|
415 |
|
416 NodeMap() {} |
|
417 void setG(Graph<N,E> &Gr) { G=&Gr; update();} |
|
418 }; |
|
419 |
|
420 template<class T> class EdgeMap |
|
421 { |
|
422 Graph<N,E> *G; |
|
423 vector<T> map; |
|
424 |
|
425 public: |
|
426 typedef T value_type; |
|
427 void put(const EdgeIterator i, const T &t) {map[i.Index()]=t;} |
|
428 T get(const EdgeIterator i) const {return map[i.Index()];} |
|
429 T &operator[](EdgeIterator i) {return map[i.Index()];} |
|
430 |
|
431 void update() |
|
432 { map.resize(G->MaxEdge());} |
|
433 |
|
434 EdgeMap() {} |
|
435 void setG(Graph<N,E> &Gr) |
|
436 { G=&Gr ;update();} |
|
437 |
|
438 }; |
|
439 |
|
440 |
|
441 int maxNode() { return OldGraph<N,E>::MaxNode();} |
|
442 int maxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;} |
|
443 |
|
444 }; |
|
445 |
|
446 template <class G> //G is a graph-type |
|
447 class Path |
|
448 { |
|
449 public: |
|
450 typedef G Graph; |
|
451 typedef typename G::NodeIterator NodeIterator; |
|
452 typedef typename G::EdgeIterator EdgeIterator; |
|
453 typedef typename G::SymEdgeIterator SymEdgeIterator; |
|
454 |
|
455 private: |
|
456 std::vector<EdgeIterator> path; |
|
457 std::vector<bool> reversed; |
|
458 |
|
459 public: |
|
460 void setLength(int n) { path.resize(n);reversed.resize(n);} |
|
461 int getLength() { return path.size(); } |
|
462 EdgeIterator &operator[](int n) {return path[n];} |
|
463 NodeIterator GetNode(int n) // What about path of length 1? |
|
464 { |
|
465 return n? |
|
466 reversed[n-1]?path[n-1].tail():path[n-1].head(): |
|
467 reversed[0]?path[0].head():path[0].tail(); |
|
468 } |
|
469 void setRevert(int n,bool r=true) {reversed[n]=r;} |
|
470 void setEdge(int n,SymEdgeIterator i) |
|
471 { |
|
472 path[n]=i; |
|
473 reversed[n] = i.head()==i.aNode(); |
|
474 } |
|
475 void setEdge(int n,EdgeIterator i,bool r) |
|
476 { |
|
477 path[n]=i; |
|
478 reversed[n] = r; |
|
479 } |
|
480 |
|
481 NodeIterator tail() { return getNode(0); } |
|
482 NodeIterator head() { return getNode(getLength()); } |
|
483 }; |
|
484 |
|
485 /* Ez itt a fiam kommentje: |
|
486 <v n nnnnnnnnnnnnnncncccccccccccccccccvvvvvv |
|
487 vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz |
|
488 << < < < < < < .cx..x.c.cc.c |
|
489 mcmn |
|
490 */ |
|
491 }; |
|
492 |
|
493 #endif |
|