Changeset 2076:10681ee9d8ae in lemon-0.x for lemon/bits
- Timestamp:
- 05/12/06 11:51:45 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2739
- Location:
- lemon/bits
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bits/base_extender.h
r2031 r2076 38 38 /// \brief BaseExtender for the UGraphs 39 39 template <typename Base> 40 class U GraphBaseExtender : public Base {40 class UndirGraphExtender : public Base { 41 41 42 42 public: … … 49 49 50 50 class Edge : public UEdge { 51 friend class U GraphBaseExtender;51 friend class UndirGraphExtender; 52 52 53 53 protected: … … 276 276 }; 277 277 278 279 /// \ingroup graphbits280 ///281 /// \brief BaseExtender for the BpUGraphs282 template <typename Base>283 class BpUGraphBaseExtender : public Base {284 public:285 typedef Base Parent;286 typedef BpUGraphBaseExtender Graph;287 288 typedef typename Parent::Node Node;289 typedef typename Parent::Edge UEdge;290 291 292 using Parent::first;293 using Parent::next;294 295 using Parent::id;296 297 class ANode : public Node {298 friend class BpUGraphBaseExtender;299 public:300 ANode() {}301 ANode(const Node& node) : Node(node) {302 LEMON_ASSERT(Parent::aNode(node) || node == INVALID,303 typename Parent::NodeSetError());304 }305 ANode(Invalid) : Node(INVALID) {}306 };307 308 void first(ANode& node) const {309 Parent::firstANode(static_cast<Node&>(node));310 }311 void next(ANode& node) const {312 Parent::nextANode(static_cast<Node&>(node));313 }314 315 int id(const ANode& node) const {316 return Parent::aNodeId(node);317 }318 319 class BNode : public Node {320 friend class BpUGraphBaseExtender;321 public:322 BNode() {}323 BNode(const Node& node) : Node(node) {324 LEMON_ASSERT(Parent::bNode(node) || node == INVALID,325 typename Parent::NodeSetError());326 }327 BNode(Invalid) : Node(INVALID) {}328 };329 330 void first(BNode& node) const {331 Parent::firstBNode(static_cast<Node&>(node));332 }333 void next(BNode& node) const {334 Parent::nextBNode(static_cast<Node&>(node));335 }336 337 int id(const BNode& node) const {338 return Parent::aNodeId(node);339 }340 341 Node source(const UEdge& edge) const {342 return aNode(edge);343 }344 Node target(const UEdge& edge) const {345 return bNode(edge);346 }347 348 void firstInc(UEdge& edge, bool& direction, const Node& node) const {349 if (Parent::aNode(node)) {350 Parent::firstOut(edge, node);351 direction = true;352 } else {353 Parent::firstIn(edge, node);354 direction = static_cast<UEdge&>(edge) == INVALID;355 }356 }357 void nextInc(UEdge& edge, bool& direction) const {358 if (direction) {359 Parent::nextOut(edge);360 } else {361 Parent::nextIn(edge);362 if (edge == INVALID) direction = true;363 }364 }365 366 int maxUEdgeId() const {367 return Parent::maxEdgeId();368 }369 370 UEdge uEdgeFromId(int id) const {371 return Parent::edgeFromId(id);372 }373 374 class Edge : public UEdge {375 friend class BpUGraphBaseExtender;376 protected:377 bool forward;378 379 Edge(const UEdge& edge, bool _forward)380 : UEdge(edge), forward(_forward) {}381 382 public:383 Edge() {}384 Edge (Invalid) : UEdge(INVALID), forward(true) {}385 bool operator==(const Edge& i) const {386 return UEdge::operator==(i) && forward == i.forward;387 }388 bool operator!=(const Edge& i) const {389 return UEdge::operator!=(i) || forward != i.forward;390 }391 bool operator<(const Edge& i) const {392 return UEdge::operator<(i) ||393 (!(i.forward<forward) && UEdge(*this)<UEdge(i));394 }395 };396 397 void first(Edge& edge) const {398 Parent::first(static_cast<UEdge&>(edge));399 edge.forward = true;400 }401 402 void next(Edge& edge) const {403 if (!edge.forward) {404 Parent::next(static_cast<UEdge&>(edge));405 }406 edge.forward = !edge.forward;407 }408 409 void firstOut(Edge& edge, const Node& node) const {410 if (Parent::aNode(node)) {411 Parent::firstOut(edge, node);412 edge.forward = true;413 } else {414 Parent::firstIn(edge, node);415 edge.forward = static_cast<UEdge&>(edge) == INVALID;416 }417 }418 void nextOut(Edge& edge) const {419 if (edge.forward) {420 Parent::nextOut(edge);421 } else {422 Parent::nextIn(edge);423 edge.forward = static_cast<UEdge&>(edge) == INVALID;424 }425 }426 427 void firstIn(Edge& edge, const Node& node) const {428 if (Parent::bNode(node)) {429 Parent::firstIn(edge, node);430 edge.forward = true;431 } else {432 Parent::firstOut(edge, node);433 edge.forward = static_cast<UEdge&>(edge) == INVALID;434 }435 }436 void nextIn(Edge& edge) const {437 if (edge.forward) {438 Parent::nextIn(edge);439 } else {440 Parent::nextOut(edge);441 edge.forward = static_cast<UEdge&>(edge) == INVALID;442 }443 }444 445 Node source(const Edge& edge) const {446 return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);447 }448 Node target(const Edge& edge) const {449 return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);450 }451 452 int id(const Edge& edge) const {453 return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);454 }455 Edge edgeFromId(int id) const {456 return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);457 }458 int maxEdgeId() const {459 return (Parent::maxId(UEdge()) << 1) + 1;460 }461 462 bool direction(const Edge& edge) const {463 return edge.forward;464 }465 466 Edge direct(const UEdge& edge, bool direction) const {467 return Edge(edge, direction);468 }469 470 int edgeNum() const {471 return 2 * Parent::edgeNum();472 }473 474 int uEdgeNum() const {475 return Parent::edgeNum();476 }477 478 };479 480 278 } 481 279 -
lemon/bits/graph_adaptor_extender.h
r2041 r2076 454 454 typedef typename Parent::UEdge UEdge; 455 455 456 Node oppositeNode(const UEdge& edge, const Node& node) const {457 return source(edge) == node ?458 target(edge) : source(edge);459 }460 461 456 462 457 int maxId(Node) const { -
lemon/bits/graph_extender.h
r2046 r2076 735 735 736 736 typedef typename Parent::Node Node; 737 typedef typename Parent::BNode BNode;738 typedef typename Parent::ANode ANode;739 typedef typename Parent::Edge Edge;740 737 typedef typename Parent::UEdge UEdge; 738 739 740 using Parent::first; 741 using Parent::next; 742 743 using Parent::id; 744 745 class ANode : public Node { 746 friend class BpUGraphExtender; 747 public: 748 ANode() {} 749 ANode(const Node& node) : Node(node) { 750 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 751 typename Parent::NodeSetError()); 752 } 753 ANode(Invalid) : Node(INVALID) {} 754 }; 755 756 void first(ANode& node) const { 757 Parent::firstANode(static_cast<Node&>(node)); 758 } 759 void next(ANode& node) const { 760 Parent::nextANode(static_cast<Node&>(node)); 761 } 762 763 int id(const ANode& node) const { 764 return Parent::aNodeId(node); 765 } 766 767 class BNode : public Node { 768 friend class BpUGraphExtender; 769 public: 770 BNode() {} 771 BNode(const Node& node) : Node(node) { 772 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, 773 typename Parent::NodeSetError()); 774 } 775 BNode(Invalid) : Node(INVALID) {} 776 }; 777 778 void first(BNode& node) const { 779 Parent::firstBNode(static_cast<Node&>(node)); 780 } 781 void next(BNode& node) const { 782 Parent::nextBNode(static_cast<Node&>(node)); 783 } 784 785 int id(const BNode& node) const { 786 return Parent::aNodeId(node); 787 } 788 789 Node source(const UEdge& edge) const { 790 return aNode(edge); 791 } 792 Node target(const UEdge& edge) const { 793 return bNode(edge); 794 } 795 796 void firstInc(UEdge& edge, bool& direction, const Node& node) const { 797 if (Parent::aNode(node)) { 798 Parent::firstFromANode(edge, node); 799 direction = true; 800 } else { 801 Parent::firstFromBNode(edge, node); 802 direction = static_cast<UEdge&>(edge) == INVALID; 803 } 804 } 805 void nextInc(UEdge& edge, bool& direction) const { 806 if (direction) { 807 Parent::nextFromANode(edge); 808 } else { 809 Parent::nextFromBNode(edge); 810 if (edge == INVALID) direction = true; 811 } 812 } 813 814 class Edge : public UEdge { 815 friend class BpUGraphExtender; 816 protected: 817 bool forward; 818 819 Edge(const UEdge& edge, bool _forward) 820 : UEdge(edge), forward(_forward) {} 821 822 public: 823 Edge() {} 824 Edge (Invalid) : UEdge(INVALID), forward(true) {} 825 bool operator==(const Edge& i) const { 826 return UEdge::operator==(i) && forward == i.forward; 827 } 828 bool operator!=(const Edge& i) const { 829 return UEdge::operator!=(i) || forward != i.forward; 830 } 831 bool operator<(const Edge& i) const { 832 return UEdge::operator<(i) || 833 (!(i.forward<forward) && UEdge(*this)<UEdge(i)); 834 } 835 }; 836 837 void first(Edge& edge) const { 838 Parent::first(static_cast<UEdge&>(edge)); 839 edge.forward = true; 840 } 841 842 void next(Edge& edge) const { 843 if (!edge.forward) { 844 Parent::next(static_cast<UEdge&>(edge)); 845 } 846 edge.forward = !edge.forward; 847 } 848 849 void firstOut(Edge& edge, const Node& node) const { 850 if (Parent::aNode(node)) { 851 Parent::firstFromANode(edge, node); 852 edge.forward = true; 853 } else { 854 Parent::firstFromBNode(edge, node); 855 edge.forward = static_cast<UEdge&>(edge) == INVALID; 856 } 857 } 858 void nextOut(Edge& edge) const { 859 if (edge.forward) { 860 Parent::nextFromANode(edge); 861 } else { 862 Parent::nextFromBNode(edge); 863 edge.forward = static_cast<UEdge&>(edge) == INVALID; 864 } 865 } 866 867 void firstIn(Edge& edge, const Node& node) const { 868 if (Parent::bNode(node)) { 869 Parent::firstFromBNode(edge, node); 870 edge.forward = true; 871 } else { 872 Parent::firstFromANode(edge, node); 873 edge.forward = static_cast<UEdge&>(edge) == INVALID; 874 } 875 } 876 void nextIn(Edge& edge) const { 877 if (edge.forward) { 878 Parent::nextFromBNode(edge); 879 } else { 880 Parent::nextFromANode(edge); 881 edge.forward = static_cast<UEdge&>(edge) == INVALID; 882 } 883 } 884 885 Node source(const Edge& edge) const { 886 return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge); 887 } 888 Node target(const Edge& edge) const { 889 return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge); 890 } 891 892 int id(const Edge& edge) const { 893 return (Parent::id(static_cast<const UEdge&>(edge)) << 1) + 894 (edge.forward ? 0 : 1); 895 } 896 Edge edgeFromId(int id) const { 897 return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0); 898 } 899 int maxEdgeId() const { 900 return (Parent::maxUEdgeId(UEdge()) << 1) + 1; 901 } 902 903 bool direction(const Edge& edge) const { 904 return edge.forward; 905 } 906 907 Edge direct(const UEdge& edge, bool direction) const { 908 return Edge(edge, direction); 909 } 910 911 int edgeNum() const { 912 return 2 * Parent::uEdgeNum(); 913 } 914 915 int uEdgeNum() const { 916 return Parent::uEdgeNum(); 917 } 741 918 742 919 Node oppositeNode(const UEdge& edge, const Node& node) const { … … 745 922 } 746 923 747 using Parent::direct;748 924 Edge direct(const UEdge& edge, const Node& node) const { 749 925 return Edge(edge, node == Parent::source(edge)); … … 765 941 } 766 942 int maxId(Edge) const { 767 return Parent::maxEdgeId();943 return maxEdgeId(); 768 944 } 769 945 int maxId(UEdge) const {
Note: See TracChangeset
for help on using the changeset viewer.