Changeset 1820:22099ef840d7 in lemon-0.x for lemon/bits/graph_extender.h
- Timestamp:
- 11/21/05 18:48:00 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2370
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bits/graph_extender.h
r1791 r1820 20 20 21 21 #include <lemon/invalid.h> 22 #include <lemon/error.h> 22 23 23 24 namespace lemon { … … 377 378 }; 378 379 380 381 template <typename _Base> 382 class UndirBipartiteGraphExtender : public _Base { 383 public: 384 typedef _Base Parent; 385 typedef UndirBipartiteGraphExtender Graph; 386 387 typedef typename Parent::Node Node; 388 typedef typename Parent::Edge UndirEdge; 389 390 using Parent::first; 391 using Parent::next; 392 393 using Parent::id; 394 395 Node source(const UndirEdge& edge) const { 396 return upperNode(edge); 397 } 398 Node target(const UndirEdge& edge) const { 399 return lowerNode(edge); 400 } 401 402 void firstInc(UndirEdge& edge, bool& direction, const Node& node) const { 403 if (Parent::upper(node)) { 404 Parent::firstDown(edge, node); 405 direction = true; 406 } else { 407 Parent::firstUp(edge, node); 408 direction = static_cast<UndirEdge&>(edge) == INVALID; 409 } 410 } 411 void nextInc(UndirEdge& edge, bool& direction) const { 412 if (direction) { 413 Parent::nextDown(edge); 414 } else { 415 Parent::nextUp(edge); 416 if (edge == INVALID) direction = true; 417 } 418 } 419 420 int maxUndirEdgeId() const { 421 return Parent::maxEdgeId(); 422 } 423 424 UndirEdge undirEdgeFromId(int id) const { 425 return Parent::edgeFromId(id); 426 } 427 428 class Edge : public UndirEdge { 429 friend class UndirBipartiteGraphExtender; 430 protected: 431 bool forward; 432 433 Edge(const UndirEdge& edge, bool _forward) 434 : UndirEdge(edge), forward(_forward) {} 435 436 public: 437 Edge() {} 438 Edge (Invalid) : UndirEdge(INVALID), forward(true) {} 439 bool operator==(const Edge& i) const { 440 return UndirEdge::operator==(i) && forward == i.forward; 441 } 442 bool operator!=(const Edge& i) const { 443 return UndirEdge::operator!=(i) || forward != i.forward; 444 } 445 bool operator<(const Edge& i) const { 446 return UndirEdge::operator<(i) || 447 (!(i.forward<forward) && UndirEdge(*this)<UndirEdge(i)); 448 } 449 }; 450 451 void first(Edge& edge) const { 452 Parent::first(static_cast<UndirEdge&>(edge)); 453 edge.forward = true; 454 } 455 456 void next(Edge& edge) const { 457 if (!edge.forward) { 458 Parent::next(static_cast<UndirEdge&>(edge)); 459 } 460 edge.forward = !edge.forward; 461 } 462 463 void firstOut(Edge& edge, const Node& node) const { 464 if (Parent::upper(node)) { 465 Parent::firstDown(edge, node); 466 edge.forward = true; 467 } else { 468 Parent::firstUp(edge, node); 469 edge.forward = static_cast<UndirEdge&>(edge) == INVALID; 470 } 471 } 472 void nextOut(Edge& edge) const { 473 if (edge.forward) { 474 Parent::nextDown(edge); 475 } else { 476 Parent::nextUp(edge); 477 if (edge == INVALID) { 478 edge.forward = true; 479 } 480 } 481 } 482 483 void firstIn(Edge& edge, const Node& node) const { 484 if (Parent::lower(node)) { 485 Parent::firstUp(edge, node); 486 edge.forward = true; 487 } else { 488 Parent::firstDown(edge, node); 489 edge.forward = static_cast<UndirEdge&>(edge) == INVALID; 490 } 491 } 492 void nextIn(Edge& edge) const { 493 if (edge.forward) { 494 Parent::nextUp(edge); 495 } else { 496 Parent::nextDown(edge); 497 if (edge == INVALID) { 498 edge.forward = true; 499 } 500 } 501 } 502 503 Node source(const Edge& edge) const { 504 return edge.forward ? Parent::upperNode(edge) : Parent::lowerNode(edge); 505 } 506 Node target(const Edge& edge) const { 507 return edge.forward ? Parent::lowerNode(edge) : Parent::upperNode(edge); 508 } 509 510 bool direction(const Edge& edge) const { 511 return edge.forward; 512 } 513 514 Edge direct(const UndirEdge& edge, const Node& node) const { 515 return Edge(edge, node == Parent::source(edge)); 516 } 517 518 Edge direct(const UndirEdge& edge, bool direction) const { 519 return Edge(edge, direction); 520 } 521 522 Node oppositeNode(const UndirEdge& edge, const Node& node) const { 523 return source(edge) == node ? 524 target(edge) : source(edge); 525 } 526 527 Edge oppositeEdge(const Edge& edge) const { 528 return Edge(edge, !edge.forward); 529 } 530 531 int id(const Edge& edge) const { 532 return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1); 533 } 534 Edge edgeFromId(int id) const { 535 return Edge(Parent::fromId(id >> 1, UndirEdge()), (id & 1) == 0); 536 } 537 int maxEdgeId() const { 538 return (Parent::maxId(UndirEdge()) << 1) + 1; 539 } 540 541 class UpperNode : public Node { 542 friend class UndirBipartiteGraphExtender; 543 public: 544 UpperNode() {} 545 UpperNode(const Node& node) : Node(node) { 546 LEMON_ASSERT(Parent::upper(node) || node == INVALID, 547 typename Parent::NodeSetError()); 548 } 549 UpperNode(Invalid) : Node(INVALID) {} 550 }; 551 552 void first(UpperNode& node) const { 553 Parent::firstUpper(static_cast<Node&>(node)); 554 } 555 void next(UpperNode& node) const { 556 Parent::nextUpper(static_cast<Node&>(node)); 557 } 558 559 int id(const UpperNode& node) const { 560 return Parent::upperId(node); 561 } 562 563 class LowerNode : public Node { 564 friend class UndirBipartiteGraphExtender; 565 public: 566 LowerNode() {} 567 LowerNode(const Node& node) : Node(node) { 568 LEMON_ASSERT(Parent::lower(node) || node == INVALID, 569 typename Parent::NodeSetError()); 570 } 571 LowerNode(Invalid) : Node(INVALID) {} 572 }; 573 574 void first(LowerNode& node) const { 575 Parent::firstLower(static_cast<Node&>(node)); 576 } 577 void next(LowerNode& node) const { 578 Parent::nextLower(static_cast<Node&>(node)); 579 } 580 581 int id(const LowerNode& node) const { 582 return Parent::upperId(node); 583 } 584 585 586 587 int maxId(Node) const { 588 return Parent::maxNodeId(); 589 } 590 int maxId(LowerNode) const { 591 return Parent::maxLowerId(); 592 } 593 int maxId(UpperNode) const { 594 return Parent::maxUpperId(); 595 } 596 int maxId(Edge) const { 597 return maxEdgeId(); 598 } 599 int maxId(UndirEdge) const { 600 return maxUndirEdgeId(); 601 } 602 603 604 Node fromId(int id, Node) const { 605 return Parent::nodeFromId(id); 606 } 607 UpperNode fromId(int id, UpperNode) const { 608 return Parent::fromUpperId(id); 609 } 610 LowerNode fromId(int id, LowerNode) const { 611 return Parent::fromLowerId(id); 612 } 613 Edge fromId(int id, Edge) const { 614 return edgeFromId(id); 615 } 616 UndirEdge fromId(int id, UndirEdge) const { 617 return undirEdgeFromId(id); 618 } 619 620 }; 621 379 622 } 380 623
Note: See TracChangeset
for help on using the changeset viewer.