Changeset 70:851ca9a60e90 in lemon0.x for src/include/graph.h
 Timestamp:
 02/10/04 14:29:15 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@86
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/include/graph.h
r8 r70 19 19 typedef N NodeType; 20 20 21 class Edge Point21 class EdgeIt 22 22 { 23 23 public: 24 24 NEGRO::EdgePoint e; 25 bool isValid() { return e; } 26 }; 27 28 class InEdgePoint : public EdgePoint {}; 29 class OutEdgePoint : public EdgePoint {}; 30 class BiEdgePoint : public EdgePoint {}; 31 class SymEdgePoint : public EdgePoint {}; 32 33 typedef int NodePoint; 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; 34 36 35 37 class NodeIterator; … … 50 52 friend class BiEdgeIterator; 51 53 friend class SymEdgeIterator; 52 friend class AllEdgeIterator;54 friend class EachEdgeIterator; 53 55 54 56 class NodeIterator … … 63 65 NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;} 64 66 65 NodeIterator & GoNext() { n=G>NextNode(n); return *this;}66 NodeIterator Next() const { return NodeIterator(*this).GoNext();}67 NodeIterator &operator++() { return GoNext();}67 NodeIterator &goNext() { n=G>NextNode(n); return *this;} 68 NodeIterator next() const { return NodeIterator(*this).goNext();} 69 NodeIterator &operator++() { return goNext();} 68 70 NodeIterator operator++(int) 69 {NodeIterator tmp(*this); GoNext(); return tmp;}70 bool isValid() { return n!=INVALID; }71 {NodeIterator tmp(*this); goNext(); return tmp;} 72 bool valid() { return n!=INVALID; } 71 73 72 74 N &operator*() const { return G>Data(n); } … … 76 78 bool operator!=(const NodeIterator &i) const {return n!=i.n;} 77 79 78 int Index() const { return n; } //If the nodes are indexable80 int index() const { return n; } //If the nodes are indexable 79 81 friend class Graph; 80 82 friend class EdgeIterator; … … 83 85 friend class BiEdgeIterator; 84 86 friend class SymEdgeIterator; 85 friend class AllEdgeIterator;87 friend class EachEdgeIterator; 86 88 friend class FirstAnythingTypeNode; 87 89 … … 97 99 // Meg a From() es To() miatt!!!!!!!!!! 98 100 99 NEGRO::Edge Point e;101 NEGRO::EdgeIt e; 100 102 101 103 public: … … 105 107 // Lehet, hogy ez a ketto nem kell!!! 106 108 107 NodeIterator From() const {NodeIterator i;i.G=G;i.n=e>From();return i;} 108 NodeIterator To() const {NodeIterator i;i.G=G;i.n=e>To();return i;} 109 110 bool isValid() {return e;} 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;} 111 115 E &operator*() const { return G>Data(e); } 112 116 E *operator>() const { return &G>Data(e); } … … 120 124 bool operator!=(const EdgeIterator &i) const {return e!=i.e;} 121 125 122 int Index() const { return e.index.block*EDGE_BLOCK_SIZE+e.index.index;}126 int Index() const {return e>index.block*EDGE_BLOCK_SIZE+e>index.index;} 123 127 //If the edges are indexable 124 128 … … 128 132 friend class BiEdgeIterator; 129 133 friend class SymEdgeIterator; 130 friend class AllEdgeIterator;134 friend class EachEdgeIterator; 131 135 }; 132 136 … … 134 138 { 135 139 public: 136 BiEdgeIterator & GoNextIn() { e=e>NextIn(); return *this;}137 BiEdgeIterator & GoNextOut() { e=e>NextOut(); return *this;}138 BiEdgeIterator NextIn() const {return BiEdgeIterator(*this).GoNextIn();}139 BiEdgeIterator NextOut() const {return BiEdgeIterator(*this).GoNextOut();}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();} 140 144 141 145 operator InEdgeIterator () … … 153 157 public: 154 158 InEdgeIterator() {} 155 InEdgeIterator( constGraph<N,E> &Gr,const NodeIterator &n)159 InEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n) 156 160 { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);} 157 161 … … 181 185 { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);} 182 186 183 OutEdgeIterator & GoNext() { e=e>NextOut(); return *this;}184 OutEdgeIterator Next() const {return OutEdgeIterator(*this).GoNext();}185 OutEdgeIterator &operator++() { return GoNext();}187 OutEdgeIterator &goNext() { e=e>NextOut(); return *this;} 188 OutEdgeIterator next() const {return OutEdgeIterator(*this).goNext();} 189 OutEdgeIterator &operator++() { return goNext();} 186 190 OutEdgeIterator operator++(int) 187 {OutEdgeIterator tmp(*this); GoNext(); return tmp;}188 189 NodeIterator Anode() const {return From();}190 NodeIterator Bnode() const {return To();}191 {OutEdgeIterator tmp(*this); goNext(); return tmp;} 192 193 NodeIterator aNode() const {return tail();} 194 NodeIterator bNode() const {return head();} 191 195 192 196 operator const InEdgeIterator () … … 205 209 public: 206 210 SymEdgeIterator() {} 207 SymEdgeIterator( constGraph<N,E> &Gr,const NodeIterator &nn)208 { G=&Gr; n=nn; e=Gr. FirstSym(nn.n); }209 210 SymEdgeIterator & GoNext() { e=e>NextEdge(n.n); return *this;}211 SymEdgeIterator Next() const {return SymEdgeIterator(*this).GoNext();}212 SymEdgeIterator &operator++() { return GoNext();}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();} 213 217 SymEdgeIterator operator++(int) 214 {SymEdgeIterator tmp(*this); GoNext(); return tmp;}215 216 NodeIterator Anode() const {return n;}217 NodeIterator Bnode() const {return n.n==From().n?To():From();}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();} 218 222 219 223 operator const InEdgeIterator () … … 227 231 }; 228 232 229 class AllEdgeIterator : public EdgeIterator233 class EachEdgeIterator : public EdgeIterator 230 234 { 231 235 NodeIterator n; // Itt ketszer van a G 232 236 233 237 public: 234 AllEdgeIterator() {}235 AllEdgeIterator(Graph<N,E> &Gr) : n(Gr)238 EachEdgeIterator() {} 239 EachEdgeIterator(Graph<N,E> &Gr) : n(Gr) 236 240 { 237 e=n. isValid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;241 e=n.valid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL; 238 242 } 239 243 240 AllEdgeIterator &GoNext()244 EachEdgeIterator &goNext() 241 245 { 242 246 e=e>NextOut(); 243 if(!e && (++n). isValid()) e=G>OldGraph<N,E>::FirstOut(n.n);247 if(!e && (++n).valid()) e=G>OldGraph<N,E>::FirstOut(n.n); 244 248 return *this; 245 249 } 246 AllEdgeIterator Next() const {return AllEdgeIterator(*this).GoNext();} 247 AllEdgeIterator &operator++() { return GoNext();} 248 AllEdgeIterator operator++(int) 249 {AllEdgeIterator tmp(*this); GoNext(); return tmp;} 250 251 252 NodeIterator Anode() const {return n;} 253 NodeIterator Bnode() const {return n.n==From().n?To():From();} 254 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;} 255 261 operator const InEdgeIterator () 256 262 {InEdgeIterator i; i.G=G;i.e=e;return i;} … … 270 276 typedef SymEdgeIterator DeletingSymEdgeIterator; 271 277 272 const NodeIterator FirstNode()278 const NodeIterator firstNode() 273 279 { 274 280 NodeIterator i; … … 277 283 } 278 284 279 void GetFirst(NodePoint &p) { p=OldGraph<N,E>::FirstNode(); }280 281 void GetFirst(InEdgePoint &p,const NodePoint &n)285 void getFirst(NodeIt &p) { p=OldGraph<N,E>::FirstNode(); } 286 287 void getFirst(InEdgeIt &p,const NodeIt &n) 282 288 { p=OldGraph<N,E>::FirstIn(n); } 283 void GetFirst(OutEdgePoint &p,const NodePoint &n)289 void getFirst(OutEdgeIt &p,const NodeIt &n) 284 290 { p=OldGraph<N,E>::FirstOut(n); } 285 void GetFirst(SymEdgePoint &p,const NodePoint &n)291 void getFirst(SymEdgeIt &p,const NodeIt &n) 286 292 { p=OldGraph<N,E>::FirstEdge(n); } 287 void GetFirst(EdgePoint &p) //Vegigmegy mindenen288 { p.e= NodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}289 290 void GetFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}291 292 void GetFirst(InEdgeIterator &i,const NodeIterator &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) 293 299 { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); } 294 void GetFirst(OutEdgeIterator &i,const NodeIterator &n)300 void getFirst(OutEdgeIterator &i,const NodeIterator &n) 295 301 { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); } 296 void GetFirst(SymEdgeIterator &i,const NodeIterator &n)297 { i.G=this;i.e=OldGraph<N,E>::First Sym(n.n); }298 void GetFirst(AllEdgeIterator &i) //Vegigmegy mindenen302 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 299 305 { 300 306 i.G=this; 301 GetFirst(i.n);307 getFirst(i.n); 302 308 i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL; 303 309 } … … 306 312 307 313 //Vagy beginnode()? 308 const DeletingEdgeIterator FirstOut(const NodeIterator &n)314 const DeletingEdgeIterator firstOut(const NodeIterator &n) 309 315 { 310 316 EdgeIterator i; … … 312 318 return i; 313 319 } 314 const DeletingEdgeIterator FirstIn(const NodeIterator &n)320 const DeletingEdgeIterator firstIn(const NodeIterator &n) 315 321 { 316 322 EdgeIterator i; … … 318 324 return i; 319 325 } 320 const DeletingSymEdgeIterator FirstSym(const NodeIterator &n)326 const DeletingSymEdgeIterator firstSym(const NodeIterator &n) 321 327 { 322 328 EdgeIterator i; … … 342 348 {SymEdgeIterator i; n.G>GetFirst(i,n);return i;} 343 349 344 operator const InEdge Point () const345 {InEdge Point i; n.G>GetFirst(i,n);return i;}346 operator const OutEdge Point () const347 {OutEdge Point i; n.G>GetFirst(i,n);return i;}348 operator const SymEdge Point () const349 {SymEdge Point i; n.G>GetFirst(i,n);return i;}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;} 350 356 }; 351 357 … … 356 362 FirstAnythingType(Graph<N,E> *gg) : G(gg) {} 357 363 358 operator const AllEdgeIterator () const359 { AllEdgeIterator i; G>GetFirst(i);return i;}360 operator const Edge Point () const361 {Edge Point i; G>GetFirst(i);return i;}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;} 362 368 operator const NodeIterator () const 363 369 {NodeIterator i; G>GetFirst(i);return i;} 364 operator const Node Point () const365 {Node Point i; G>GetFirst(i);return i;}370 operator const NodeIt () const 371 {NodeIt i; G>GetFirst(i);return i;} 366 372 } _FST; 367 373 368 374 // const NodeIterator First() {NodeIterator i;GetFirst(i); return i;} 369 FirstAnythingTypeNode First(NodeIterator &i)375 FirstAnythingTypeNode first(NodeIterator &i) 370 376 {FirstAnythingTypeNode t(i); return t;} 371 const FirstAnythingType & First() {return _FST;}377 const FirstAnythingType &first() {return _FST;} 372 378 373 379 // LastNode() vagy endnode() stb. Nem kell? 374 380 375 DeletingNodeIterator AddNode()381 DeletingNodeIterator addNode() 376 382 { 377 383 DeletingNodeIterator i; … … 380 386 } 381 387 DeletingEdgeIterator 382 AddEdge(const NodeIterator from,const NodeIterator to)388 addEdge(const NodeIterator from,const NodeIterator to) 383 389 { 384 390 DeletingEdgeIterator i; … … 389 395 void Delete(DeletingEdgeIterator e) {e.G>OldGraph<N,E>::Delete(e.e);} 390 396 391 int NodeNum() { OldGraph<N,E>::NodeNum(); }392 void Clean() { OldGraph<N,E>::Clean(); }397 int nodeNum() { OldGraph<N,E>::NodeNum(); } 398 void clean() { OldGraph<N,E>::Clean(); } 393 399 394 400 Graph() : _FST(this) {} … … 402 408 public: 403 409 typedef T value_type; 404 void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}405 T Get(const NodeIterator i) const {return map[i.Index()];}410 void put(const NodeIterator i, const T &t) {map[i.Index()]=t;} 411 T get(const NodeIterator i) const {return map[i.Index()];} 406 412 T operator[](NodeIterator i) {return map[i.Index()];} 407 413 … … 409 415 410 416 NodeMap() {} 411 void SetG(Graph<N,E> &Gr) { G=&Gr; update();}417 void setG(Graph<N,E> &Gr) { G=&Gr; update();} 412 418 }; 413 419 … … 419 425 public: 420 426 typedef T value_type; 421 void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}422 T &Get(const NodeIterator i){return map[i.Index()];}423 T &operator[]( NodeIterator i) {return map[i.Index()];}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()];} 424 430 425 431 void update() … … 427 433 428 434 EdgeMap() {} 429 void SetG(Graph<N,E> &Gr)435 void setG(Graph<N,E> &Gr) 430 436 { G=&Gr ;update();} 431 437 … … 433 439 434 440 435 int MaxNode() { return OldGraph<N,E>::MaxNode();} 436 int MaxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;} 437 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 graphtype 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[n1]?path[n1].tail():path[n1].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()); } 438 483 }; 439 484 … … 444 489 mcmn 445 490 */ 446 447 } 491 }; 448 492 449 493 #endif
Note: See TracChangeset
for help on using the changeset viewer.