[1] | 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 |
---|