|
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 |
|
8 namespace NEGRO |
|
9 { |
|
10 using namespace std; |
|
11 |
|
12 #include "oldgraph.h" |
|
13 |
|
14 template <class N, class E> class Graph : protected OldGraph<N,E> |
|
15 { |
|
16 public: |
|
17 typedef E EdgeType; |
|
18 typedef N NodeType; |
|
19 |
|
20 class EdgePoint |
|
21 { |
|
22 public: |
|
23 NEGRO::EdgePoint e; |
|
24 bool isValid() { return e; } |
|
25 }; |
|
26 |
|
27 class InEdgePoint : public EdgePoint {}; |
|
28 class OutEdgePoint : public EdgePoint {}; |
|
29 class BiEdgePoint : public EdgePoint {}; |
|
30 class SymEdgePoint : public EdgePoint {}; |
|
31 |
|
32 typedef int NodePoint; |
|
33 |
|
34 class NodeIterator; |
|
35 |
|
36 class EdgeIterator; |
|
37 class InEdgeIterator; |
|
38 class OutEdgeIterator; |
|
39 class BiEdgeIterator; |
|
40 class SymEdgeIterator; |
|
41 class AllEdgeIterator; |
|
42 |
|
43 class FirstAnythingTypeNode; |
|
44 |
|
45 friend class NodeIterator; |
|
46 friend class EdgeIterator; |
|
47 friend class InEdgeIterator; |
|
48 friend class OutEdgeIterator; |
|
49 friend class BiEdgeIterator; |
|
50 friend class SymEdgeIterator; |
|
51 friend class AllEdgeIterator; |
|
52 |
|
53 class NodeIterator |
|
54 { |
|
55 Graph<N,E> *G; //operator*() miatt kell!!! |
|
56 int n; //nem kellene, ha itt mutato lenne!! |
|
57 public: |
|
58 |
|
59 NodeIterator() {;} |
|
60 NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;} |
|
61 |
|
62 NodeIterator &GoNext() { n=G->NextNode(n); return *this;} |
|
63 NodeIterator Next() const { return NodeIterator(*this).GoNext();} |
|
64 NodeIterator &operator++() { return GoNext();} |
|
65 NodeIterator operator++(int) |
|
66 {NodeIterator tmp(*this); GoNext(); return tmp;} |
|
67 bool isValid() { return n!=INVALID; } |
|
68 |
|
69 N &operator*() const { return G->Data(n); } |
|
70 N *operator->() const { return &G->Data(n); } |
|
71 |
|
72 bool operator==(const NodeIterator &i) const {return n==i.n;} |
|
73 bool operator!=(const NodeIterator &i) const {return n!=i.n;} |
|
74 |
|
75 friend class Graph; |
|
76 friend class EdgeIterator; |
|
77 friend class InEdgeIterator; |
|
78 friend class OutEdgeIterator; |
|
79 friend class BiEdgeIterator; |
|
80 friend class SymEdgeIterator; |
|
81 friend class AllEdgeIterator; |
|
82 friend class FirstAnythingTypeNode; |
|
83 |
|
84 //Nem kellene egy: |
|
85 // static NodeIterator &GetInvalid(); ? |
|
86 }; |
|
87 |
|
88 class EdgeIterator |
|
89 { |
|
90 |
|
91 Graph<N,E> *G; //Itt baj van!!!!! operator*() miatt kell! |
|
92 //Ez csak kicsit baj, de: |
|
93 // Meg a From() es To() miatt!!!!!!!!!! |
|
94 |
|
95 NEGRO::EdgePoint e; |
|
96 |
|
97 public: |
|
98 EdgeIterator() {;} //Kell inicializalni? (Nem) |
|
99 EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;} |
|
100 |
|
101 // Lehet, hogy ez a ketto nem kell!!! |
|
102 |
|
103 NodeIterator From() const {NodeIterator i;i.G=G;i.n=e->From();return i;} |
|
104 NodeIterator To() const {NodeIterator i;i.G=G;i.n=e->To();return i;} |
|
105 |
|
106 bool isValid() {return e;} |
|
107 E &operator*() const { return G->Data(e); } |
|
108 E *operator->() const { return &G->Data(e); } |
|
109 |
|
110 //operator const OutEdgeIterator (); |
|
111 //operator const InEdgeIterator (); |
|
112 //operator const BiEdgeIterator (); |
|
113 //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal |
|
114 |
|
115 bool operator==(const EdgeIterator &i) const {return e==i.e;} |
|
116 bool operator!=(const EdgeIterator &i) const {return e!=i.e;} |
|
117 |
|
118 friend class Graph; |
|
119 friend class InEdgeIterator; |
|
120 friend class OutEdgeIterator; |
|
121 friend class BiEdgeIterator; |
|
122 friend class SymEdgeIterator; |
|
123 friend class AllEdgeIterator; |
|
124 }; |
|
125 |
|
126 class BiEdgeIterator : public EdgeIterator |
|
127 { |
|
128 public: |
|
129 BiEdgeIterator &GoNextIn() { e=e->NextIn(); return *this;} |
|
130 BiEdgeIterator &GoNextOut() { e=e->NextOut(); return *this;} |
|
131 BiEdgeIterator NextIn() const {return BiEdgeIterator(*this).GoNextIn();} |
|
132 BiEdgeIterator NextOut() const {return BiEdgeIterator(*this).GoNextOut();} |
|
133 |
|
134 operator InEdgeIterator () |
|
135 {InEdgeIterator i; i.G=G;i.e=e;return i;} |
|
136 operator OutEdgeIterator () |
|
137 {OutEdgeIterator i; i.G=G;i.e=e;return i;} |
|
138 //operator const SymEdgeIterator () |
|
139 |
|
140 friend class Graph; |
|
141 }; |
|
142 |
|
143 class InEdgeIterator : public EdgeIterator |
|
144 //Ne a BiEdgeIterator-bol szarmazzon? |
|
145 { |
|
146 public: |
|
147 InEdgeIterator &GoNext() { e=e->NextIn(); return *this;} |
|
148 InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();} |
|
149 InEdgeIterator &operator++() { return GoNext();} |
|
150 InEdgeIterator operator++(int) |
|
151 {InEdgeIterator tmp(*this); GoNext(); return tmp;} |
|
152 |
|
153 operator const OutEdgeIterator () |
|
154 {OutEdgeIterator i; i.G=G;i.e=e;return i;} |
|
155 operator const BiEdgeIterator () |
|
156 {EdgeIterator i; i.G=G;i.e=e;return i;} |
|
157 // operator const SymEdgeIterator (); |
|
158 |
|
159 NodeIterator Anode() const {return To();} |
|
160 NodeIterator Bnode() const {return From();} |
|
161 |
|
162 friend class Graph; |
|
163 }; |
|
164 |
|
165 class OutEdgeIterator : public EdgeIterator |
|
166 { |
|
167 public: |
|
168 OutEdgeIterator &GoNext() { e=e->NextOut(); return *this;} |
|
169 OutEdgeIterator Next() const {return OutEdgeIterator(*this).GoNext();} |
|
170 OutEdgeIterator &operator++() { return GoNext();} |
|
171 OutEdgeIterator operator++(int) |
|
172 {OutEdgeIterator tmp(*this); GoNext(); return tmp;} |
|
173 |
|
174 NodeIterator Anode() const {return From();} |
|
175 NodeIterator Bnode() const {return To();} |
|
176 |
|
177 operator const InEdgeIterator () |
|
178 {InEdgeIterator i; i.G=G;i.e=e;return i;} |
|
179 operator const BiEdgeIterator () |
|
180 {BiEdgeIterator i; i.G=G;i.e=e;return i;} |
|
181 //operator const SymEdgeIterator(); |
|
182 |
|
183 friend class Graph; |
|
184 }; |
|
185 |
|
186 class SymEdgeIterator : public EdgeIterator |
|
187 { |
|
188 NodeIterator n; // Itt ketszer van a G |
|
189 |
|
190 public: |
|
191 SymEdgeIterator &GoNext() { e=e->NextEdge(n.n); return *this;} |
|
192 SymEdgeIterator Next() const {return SymEdgeIterator(*this).GoNext();} |
|
193 SymEdgeIterator &operator++() { return GoNext();} |
|
194 SymEdgeIterator operator++(int) |
|
195 {SymEdgeIterator tmp(*this); GoNext(); return tmp;} |
|
196 |
|
197 NodeIterator Anode() const {return n;} |
|
198 NodeIterator Bnode() const {return n.n==From().n?To():From();} |
|
199 |
|
200 operator const InEdgeIterator () |
|
201 {InEdgeIterator i; i.G=G;i.e=e;return i;} |
|
202 operator const OutEdgeIterator () |
|
203 {OutEdgeIterator i; i.G=G;i.e=e;return i;} |
|
204 operator const BiEdgeIterator () |
|
205 {BiEdgeIterator i; i.G=G;i.e=e;return i;} |
|
206 |
|
207 friend class Graph; |
|
208 }; |
|
209 |
|
210 class AllEdgeIterator : public EdgeIterator |
|
211 { |
|
212 NodeIterator n; // Itt ketszer van a G |
|
213 |
|
214 public: |
|
215 AllEdgeIterator &GoNext() |
|
216 { |
|
217 e=e->NextOut(); |
|
218 if(!e && (++n).isValid()) e=G->OldGraph<N,E>::FirstOut(n.n); |
|
219 return *this; |
|
220 } |
|
221 AllEdgeIterator Next() const {return AllEdgeIterator(*this).GoNext();} |
|
222 AllEdgeIterator &operator++() { return GoNext();} |
|
223 AllEdgeIterator operator++(int) |
|
224 {AllEdgeIterator tmp(*this); GoNext(); return tmp;} |
|
225 |
|
226 |
|
227 NodeIterator Anode() const {return n;} |
|
228 NodeIterator Bnode() const {return n.n==From().n?To():From();} |
|
229 |
|
230 operator const InEdgeIterator () |
|
231 {InEdgeIterator i; i.G=G;i.e=e;return i;} |
|
232 operator const OutEdgeIterator () |
|
233 {OutEdgeIterator i; i.G=G;i.e=e;return i;} |
|
234 operator const BiEdgeIterator () |
|
235 {BiEdgeIterator i; i.G=G;i.e=e;return i;} |
|
236 |
|
237 friend class Graph; |
|
238 }; |
|
239 |
|
240 typedef NodeIterator DeletingNodeIterator; |
|
241 typedef EdgeIterator DeletingEdgeIterator; |
|
242 typedef BiEdgeIterator DeletingBiEdgeIterator; |
|
243 typedef OutEdgeIterator DeletingOutEdgeIterator; |
|
244 typedef InEdgeIterator DeletingInEdgeIterator; |
|
245 typedef SymEdgeIterator DeletingSymEdgeIterator; |
|
246 |
|
247 const NodeIterator &FirstNode() |
|
248 { |
|
249 NodeIterator i; |
|
250 i.G=this;i.n=OldGraph<N,E>::FirstNode(); |
|
251 return i; |
|
252 } |
|
253 |
|
254 void GetFirst(NodePoint &p) { p=OldGraph<N,E>::FirstNode(); } |
|
255 |
|
256 void GetFirst(InEdgePoint &p,const NodePoint &n) |
|
257 { p=OldGraph<N,E>::FirstIn(n); } |
|
258 void GetFirst(OutEdgePoint &p,const NodePoint &n) |
|
259 { p=OldGraph<N,E>::FirstOut(n); } |
|
260 void GetFirst(SymEdgePoint &p,const NodePoint &n) |
|
261 { p=OldGraph<N,E>::FirstEdge(n); } |
|
262 void GetFirst(EdgePoint &p) //Vegigmegy mindenen |
|
263 { p.e=NodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;} |
|
264 |
|
265 void GetFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();} |
|
266 |
|
267 void GetFirst(InEdgeIterator &i,const NodeIterator &n) |
|
268 { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); } |
|
269 void GetFirst(OutEdgeIterator &i,const NodeIterator &n) |
|
270 { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); } |
|
271 void GetFirst(SymEdgeIterator &i,const NodeIterator &n) |
|
272 { i.G=this;i.e=OldGraph<N,E>::FirstSym(n.n); } |
|
273 void GetFirst(AllEdgeIterator &i) //Vegigmegy mindenen |
|
274 { |
|
275 i.G=this; |
|
276 GetFirst(i.n); |
|
277 i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL; |
|
278 } |
|
279 |
|
280 |
|
281 |
|
282 //Vagy beginnode()? |
|
283 const DeletingEdgeIterator &FirstOut(const NodeIterator &n) |
|
284 { |
|
285 EdgeIterator i; |
|
286 i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n); |
|
287 return i; |
|
288 } |
|
289 const DeletingEdgeIterator &FirstIn(const NodeIterator &n) |
|
290 { |
|
291 EdgeIterator i; |
|
292 i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n); |
|
293 return i; |
|
294 } |
|
295 const DeletingSymEdgeIterator &FirstSym(const NodeIterator &n) |
|
296 { |
|
297 EdgeIterator i; |
|
298 i.G=n.G;i.n=n.n; |
|
299 i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n); |
|
300 return i; |
|
301 } |
|
302 |
|
303 // class FirstAnythingType; |
|
304 // friend class FirstAnythingType; |
|
305 |
|
306 class FirstAnythingTypeNode |
|
307 { |
|
308 NodeIterator n; |
|
309 public: |
|
310 FirstAnythingTypeNode(NodeIterator i) : n(i) {} |
|
311 |
|
312 operator const InEdgeIterator () const |
|
313 {InEdgeIterator i; n.G->GetFirst(i,n);return i;} |
|
314 operator const OutEdgeIterator () const |
|
315 {OutEdgeIterator i; n.G->GetFirst(i,n);return i;} |
|
316 operator const SymEdgeIterator () const |
|
317 {SymEdgeIterator i; n.G->GetFirst(i,n);return i;} |
|
318 |
|
319 operator const InEdgePoint () const |
|
320 {InEdgePoint i; n.G->GetFirst(i,n);return i;} |
|
321 operator const OutEdgePoint () const |
|
322 {OutEdgePoint i; n.G->GetFirst(i,n);return i;} |
|
323 operator const SymEdgePoint () const |
|
324 {SymEdgePoint i; n.G->GetFirst(i,n);return i;} |
|
325 }; |
|
326 |
|
327 class FirstAnythingType |
|
328 { |
|
329 Graph<N,E> *G; |
|
330 public: |
|
331 FirstAnythingType(Graph<N,E> *gg) : G(gg) {} |
|
332 |
|
333 operator const AllEdgeIterator () const |
|
334 {AllEdgeIterator i; G->GetFirst(i);return i;} |
|
335 operator const EdgePoint () const |
|
336 {EdgePoint i; G->GetFirst(i);return i;} |
|
337 operator const NodeIterator () const |
|
338 {NodeIterator i; G->GetFirst(i);return i;} |
|
339 operator const NodePoint () const |
|
340 {NodePoint i; G->GetFirst(i);return i;} |
|
341 } _FST; |
|
342 |
|
343 // const NodeIterator First() {NodeIterator i;GetFirst(i); return i;} |
|
344 FirstAnythingTypeNode First(NodeIterator &i) |
|
345 {FirstAnythingTypeNode t(i); return t;} |
|
346 const FirstAnythingType &First() {return _FST;} |
|
347 |
|
348 // LastNode() vagy endnode() stb. Nem kell? |
|
349 |
|
350 DeletingNodeIterator AddNode() |
|
351 { |
|
352 DeletingNodeIterator i; |
|
353 i.G=this; i.n=OldGraph<N,E>::AddNode(); |
|
354 return i; |
|
355 } |
|
356 DeletingEdgeIterator |
|
357 AddEdge(const NodeIterator from,const NodeIterator to) |
|
358 { |
|
359 DeletingEdgeIterator i; |
|
360 i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i; |
|
361 } |
|
362 |
|
363 void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);} |
|
364 void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);} |
|
365 |
|
366 int NodeNum() { OldGraph<N,E>::NodeNum(); } |
|
367 int Clean() { OldGraph<N,E>::Clean(); } |
|
368 |
|
369 Graph() : _FST(this) {} |
|
370 }; |
|
371 |
|
372 /* Ez itt a fiam kommentje: |
|
373 <v n nnnnnnnnnnnnnncncccccccccccccccccvvvvvv |
|
374 vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz |
|
375 << < < < < < < .cx..x.c.cc.c |
|
376 mcmn |
|
377 */ |
|
378 |
|
379 } |
|
380 |
|
381 #endif |