Changeset 1909:2d806130e700 in lemon-0.x for lemon/bits/graph_extender.h
- Timestamp:
- 01/26/06 16:42:13 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2484
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bits/graph_extender.h
r1875 r1909 62 62 63 63 template <typename _Base> 64 class U ndirGraphExtender : public _Base {64 class UGraphExtender : public _Base { 65 65 typedef _Base Parent; 66 typedef U ndirGraphExtender Graph;66 typedef UGraphExtender Graph; 67 67 68 68 public: 69 69 70 typedef typename Parent::Edge U ndirEdge;70 typedef typename Parent::Edge UEdge; 71 71 typedef typename Parent::Node Node; 72 72 73 class Edge : public U ndirEdge {74 friend class U ndirGraphExtender;73 class Edge : public UEdge { 74 friend class UGraphExtender; 75 75 76 76 protected: … … 79 79 bool forward; 80 80 81 Edge(const U ndirEdge &ue, bool _forward) :82 U ndirEdge(ue), forward(_forward) {}81 Edge(const UEdge &ue, bool _forward) : 82 UEdge(ue), forward(_forward) {} 83 83 84 84 public: … … 86 86 87 87 /// Invalid edge constructor 88 Edge(Invalid i) : U ndirEdge(i), forward(true) {}88 Edge(Invalid i) : UEdge(i), forward(true) {} 89 89 90 90 bool operator==(const Edge &that) const { 91 return forward==that.forward && U ndirEdge(*this)==UndirEdge(that);91 return forward==that.forward && UEdge(*this)==UEdge(that); 92 92 } 93 93 bool operator!=(const Edge &that) const { 94 return forward!=that.forward || U ndirEdge(*this)!=UndirEdge(that);94 return forward!=that.forward || UEdge(*this)!=UEdge(that); 95 95 } 96 96 bool operator<(const Edge &that) const { 97 97 return forward<that.forward || 98 (!(that.forward<forward) && U ndirEdge(*this)<UndirEdge(that));98 (!(that.forward<forward) && UEdge(*this)<UEdge(that)); 99 99 } 100 100 }; … … 127 127 } 128 128 129 Node oppositeNode(const Node &n, const U ndirEdge &e) const {129 Node oppositeNode(const Node &n, const UEdge &e) const { 130 130 if( n == Parent::source(e)) 131 131 return Parent::target(e); … … 138 138 /// \brief Directed edge from an undirected edge and a source node. 139 139 /// 140 /// Returns a (directed) Edge corresponding to the specified U ndirEdge140 /// Returns a (directed) Edge corresponding to the specified UEdge 141 141 /// and source Node. 142 142 /// 143 Edge direct(const U ndirEdge &ue, const Node &s) const {143 Edge direct(const UEdge &ue, const Node &s) const { 144 144 return Edge(ue, s == source(ue)); 145 145 } … … 147 147 /// \brief Directed edge from an undirected edge. 148 148 /// 149 /// Returns a directed edge corresponding to the specified U ndirEdge.149 /// Returns a directed edge corresponding to the specified UEdge. 150 150 /// If the given bool is true the given undirected edge and the 151 151 /// returned edge have the same source node. 152 Edge direct(const U ndirEdge &ue, bool d) const {152 Edge direct(const UEdge &ue, bool d) const { 153 153 return Edge(ue, d); 154 154 } … … 183 183 void firstOut(Edge &e, const Node &n) const { 184 184 Parent::firstIn(e,n); 185 if( U ndirEdge(e) != INVALID ) {185 if( UEdge(e) != INVALID ) { 186 186 e.forward = false; 187 187 } … … 195 195 Node n = Parent::target(e); 196 196 Parent::nextIn(e); 197 if( U ndirEdge(e) == INVALID ) {197 if( UEdge(e) == INVALID ) { 198 198 Parent::firstOut(e, n); 199 199 e.forward = true; … … 207 207 void firstIn(Edge &e, const Node &n) const { 208 208 Parent::firstOut(e,n); 209 if( U ndirEdge(e) != INVALID ) {209 if( UEdge(e) != INVALID ) { 210 210 e.forward = false; 211 211 } … … 219 219 Node n = Parent::source(e); 220 220 Parent::nextOut(e); 221 if( U ndirEdge(e) == INVALID ) {221 if( UEdge(e) == INVALID ) { 222 222 Parent::firstIn(e, n); 223 223 e.forward = true; … … 229 229 } 230 230 231 void firstInc(U ndirEdge &e, const Node &n) const {231 void firstInc(UEdge &e, const Node &n) const { 232 232 Parent::firstOut(e, n); 233 233 if (e != INVALID) return; 234 234 Parent::firstIn(e, n); 235 235 } 236 void nextInc(U ndirEdge &e, const Node &n) const {236 void nextInc(UEdge &e, const Node &n) const { 237 237 if (Parent::source(e) == n) { 238 238 Parent::nextOut(e); … … 244 244 } 245 245 246 void firstInc(U ndirEdge &e, bool &d, const Node &n) const {246 void firstInc(UEdge &e, bool &d, const Node &n) const { 247 247 d = true; 248 248 Parent::firstOut(e, n); … … 251 251 Parent::firstIn(e, n); 252 252 } 253 void nextInc(U ndirEdge &e, bool &d) const {253 void nextInc(UEdge &e, bool &d) const { 254 254 if (d) { 255 255 Node s = Parent::source(e); … … 276 276 } 277 277 278 int id(const U ndirEdge &e) const {278 int id(const UEdge &e) const { 279 279 return Parent::id(e); 280 280 } … … 292 292 } 293 293 294 int maxU ndirEdgeId() const {294 int maxUEdgeId() const { 295 295 return Parent::maxEdgeId(); 296 296 } … … 303 303 return maxEdgeId(); 304 304 } 305 int maxId(U ndirEdge) const {306 return maxU ndirEdgeId();305 int maxId(UEdge) const { 306 return maxUEdgeId(); 307 307 } 308 308 … … 311 311 } 312 312 313 int u ndirEdgeNum() const {313 int uEdgeNum() const { 314 314 return Parent::edgeNum(); 315 315 } … … 323 323 } 324 324 325 U ndirEdge undirEdgeFromId(int id) const {325 UEdge uEdgeFromId(int id) const { 326 326 return Parent::edgeFromId(id >> 1); 327 327 } … … 335 335 } 336 336 337 U ndirEdge fromId(int id, UndirEdge) const {338 return u ndirEdgeFromId(id);337 UEdge fromId(int id, UEdge) const { 338 return uEdgeFromId(id); 339 339 } 340 340 … … 342 342 Edge findEdge(Node source, Node target, Edge prev) const { 343 343 if (prev == INVALID) { 344 U ndirEdge edge = Parent::findEdge(source, target);344 UEdge edge = Parent::findEdge(source, target); 345 345 if (edge != INVALID) return direct(edge, true); 346 346 edge = Parent::findEdge(target, source); 347 347 if (edge != INVALID) return direct(edge, false); 348 348 } else if (direction(prev)) { 349 U ndirEdge edge = Parent::findEdge(source, target, prev);349 UEdge edge = Parent::findEdge(source, target, prev); 350 350 if (edge != INVALID) return direct(edge, true); 351 351 edge = Parent::findEdge(target, source); 352 352 if (edge != INVALID) return direct(edge, false); 353 353 } else { 354 U ndirEdge edge = Parent::findEdge(target, source, prev);354 UEdge edge = Parent::findEdge(target, source, prev); 355 355 if (edge != INVALID) return direct(edge, false); 356 356 } … … 358 358 } 359 359 360 U ndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {360 UEdge findUEdge(Node source, Node target, UEdge prev) const { 361 361 if (prev == INVALID) { 362 U ndirEdge edge = Parent::findEdge(source, target);362 UEdge edge = Parent::findEdge(source, target); 363 363 if (edge != INVALID) return edge; 364 364 edge = Parent::findEdge(target, source); 365 365 if (edge != INVALID) return edge; 366 366 } else if (Parent::source(prev) == source) { 367 U ndirEdge edge = Parent::findEdge(source, target, prev);367 UEdge edge = Parent::findEdge(source, target, prev); 368 368 if (edge != INVALID) return edge; 369 369 edge = Parent::findEdge(target, source); 370 370 if (edge != INVALID) return edge; 371 371 } else { 372 U ndirEdge edge = Parent::findEdge(target, source, prev);372 UEdge edge = Parent::findEdge(target, source, prev); 373 373 if (edge != INVALID) return edge; 374 374 } … … 380 380 381 381 template <typename _Base> 382 class U ndirBipartiteGraphExtender : public _Base {382 class UBipartiteGraphExtender : public _Base { 383 383 public: 384 384 typedef _Base Parent; 385 typedef U ndirBipartiteGraphExtender Graph;385 typedef UBipartiteGraphExtender Graph; 386 386 387 387 typedef typename Parent::Node Node; 388 typedef typename Parent::Edge U ndirEdge;388 typedef typename Parent::Edge UEdge; 389 389 390 390 using Parent::first; … … 393 393 using Parent::id; 394 394 395 Node source(const U ndirEdge& edge) const {395 Node source(const UEdge& edge) const { 396 396 return upperNode(edge); 397 397 } 398 Node target(const U ndirEdge& edge) const {398 Node target(const UEdge& edge) const { 399 399 return lowerNode(edge); 400 400 } 401 401 402 void firstInc(U ndirEdge& edge, bool& direction, const Node& node) const {402 void firstInc(UEdge& edge, bool& direction, const Node& node) const { 403 403 if (Parent::upper(node)) { 404 404 Parent::firstDown(edge, node); … … 406 406 } else { 407 407 Parent::firstUp(edge, node); 408 direction = static_cast<U ndirEdge&>(edge) == INVALID;409 } 410 } 411 void nextInc(U ndirEdge& edge, bool& direction) const {408 direction = static_cast<UEdge&>(edge) == INVALID; 409 } 410 } 411 void nextInc(UEdge& edge, bool& direction) const { 412 412 if (direction) { 413 413 Parent::nextDown(edge); … … 418 418 } 419 419 420 int maxU ndirEdgeId() const {420 int maxUEdgeId() const { 421 421 return Parent::maxEdgeId(); 422 422 } 423 423 424 U ndirEdge undirEdgeFromId(int id) const {424 UEdge uEdgeFromId(int id) const { 425 425 return Parent::edgeFromId(id); 426 426 } 427 427 428 class Edge : public U ndirEdge {429 friend class U ndirBipartiteGraphExtender;428 class Edge : public UEdge { 429 friend class UBipartiteGraphExtender; 430 430 protected: 431 431 bool forward; 432 432 433 Edge(const U ndirEdge& edge, bool _forward)434 : U ndirEdge(edge), forward(_forward) {}433 Edge(const UEdge& edge, bool _forward) 434 : UEdge(edge), forward(_forward) {} 435 435 436 436 public: 437 437 Edge() {} 438 Edge (Invalid) : U ndirEdge(INVALID), forward(true) {}438 Edge (Invalid) : UEdge(INVALID), forward(true) {} 439 439 bool operator==(const Edge& i) const { 440 return U ndirEdge::operator==(i) && forward == i.forward;440 return UEdge::operator==(i) && forward == i.forward; 441 441 } 442 442 bool operator!=(const Edge& i) const { 443 return U ndirEdge::operator!=(i) || forward != i.forward;443 return UEdge::operator!=(i) || forward != i.forward; 444 444 } 445 445 bool operator<(const Edge& i) const { 446 return U ndirEdge::operator<(i) ||447 (!(i.forward<forward) && U ndirEdge(*this)<UndirEdge(i));446 return UEdge::operator<(i) || 447 (!(i.forward<forward) && UEdge(*this)<UEdge(i)); 448 448 } 449 449 }; 450 450 451 451 void first(Edge& edge) const { 452 Parent::first(static_cast<U ndirEdge&>(edge));452 Parent::first(static_cast<UEdge&>(edge)); 453 453 edge.forward = true; 454 454 } … … 456 456 void next(Edge& edge) const { 457 457 if (!edge.forward) { 458 Parent::next(static_cast<U ndirEdge&>(edge));458 Parent::next(static_cast<UEdge&>(edge)); 459 459 } 460 460 edge.forward = !edge.forward; … … 467 467 } else { 468 468 Parent::firstUp(edge, node); 469 edge.forward = static_cast<U ndirEdge&>(edge) == INVALID;469 edge.forward = static_cast<UEdge&>(edge) == INVALID; 470 470 } 471 471 } … … 475 475 } else { 476 476 Parent::nextUp(edge); 477 edge.forward = static_cast<U ndirEdge&>(edge) == INVALID;477 edge.forward = static_cast<UEdge&>(edge) == INVALID; 478 478 } 479 479 } … … 485 485 } else { 486 486 Parent::firstDown(edge, node); 487 edge.forward = static_cast<U ndirEdge&>(edge) == INVALID;487 edge.forward = static_cast<UEdge&>(edge) == INVALID; 488 488 } 489 489 } … … 493 493 } else { 494 494 Parent::nextDown(edge); 495 edge.forward = static_cast<U ndirEdge&>(edge) == INVALID;495 edge.forward = static_cast<UEdge&>(edge) == INVALID; 496 496 } 497 497 } … … 508 508 } 509 509 510 Edge direct(const U ndirEdge& edge, const Node& node) const {510 Edge direct(const UEdge& edge, const Node& node) const { 511 511 return Edge(edge, node == Parent::source(edge)); 512 512 } 513 513 514 Edge direct(const U ndirEdge& edge, bool direction) const {514 Edge direct(const UEdge& edge, bool direction) const { 515 515 return Edge(edge, direction); 516 516 } 517 517 518 Node oppositeNode(const U ndirEdge& edge, const Node& node) const {518 Node oppositeNode(const UEdge& edge, const Node& node) const { 519 519 return source(edge) == node ? 520 520 target(edge) : source(edge); … … 529 529 } 530 530 Edge edgeFromId(int id) const { 531 return Edge(Parent::fromId(id >> 1, U ndirEdge()), (id & 1) == 0);531 return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0); 532 532 } 533 533 int maxEdgeId() const { 534 return (Parent::maxId(U ndirEdge()) << 1) + 1;534 return (Parent::maxId(UEdge()) << 1) + 1; 535 535 } 536 536 537 537 class UpperNode : public Node { 538 friend class U ndirBipartiteGraphExtender;538 friend class UBipartiteGraphExtender; 539 539 public: 540 540 UpperNode() {} … … 558 558 559 559 class LowerNode : public Node { 560 friend class U ndirBipartiteGraphExtender;560 friend class UBipartiteGraphExtender; 561 561 public: 562 562 LowerNode() {} … … 593 593 return maxEdgeId(); 594 594 } 595 int maxId(U ndirEdge) const {596 return maxU ndirEdgeId();595 int maxId(UEdge) const { 596 return maxUEdgeId(); 597 597 } 598 598 … … 610 610 return edgeFromId(id); 611 611 } 612 U ndirEdge fromId(int id, UndirEdge) const {613 return u ndirEdgeFromId(id);612 UEdge fromId(int id, UEdge) const { 613 return uEdgeFromId(id); 614 614 } 615 615
Note: See TracChangeset
for help on using the changeset viewer.