Changeset 2231:06faf3f06d67 in lemon-0.x for lemon/bits/graph_extender.h
- Timestamp:
- 10/03/06 13:46:39 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2973
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bits/graph_extender.h
r2222 r2231 731 731 class BpUGraphExtender : public Base { 732 732 public: 733 733 734 typedef Base Parent; 734 735 typedef BpUGraphExtender Graph; 735 736 736 737 typedef typename Parent::Node Node; 738 typedef typename Parent::ANode ANode; 739 typedef typename Parent::BNode BNode; 740 typedef typename Parent::Edge Edge; 737 741 typedef typename Parent::UEdge UEdge; 738 742 739 743 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 } 918 919 Node oppositeNode(const UEdge& edge, const Node& node) const { 920 return source(edge) == node ? 921 target(edge) : source(edge); 922 } 923 744 Node oppositeNode(const Node& node, const UEdge& edge) const { 745 return Parent::aNode(edge) == node ? 746 Parent::bNode(edge) : Parent::aNode(edge); 747 } 748 749 using Parent::direct; 924 750 Edge direct(const UEdge& edge, const Node& node) const { 925 return Edge(edge, node == Parent::source(edge));751 return Parent::direct(edge, node == Parent::source(edge)); 926 752 } 927 753 928 754 Edge oppositeEdge(const Edge& edge) const { 929 return Parent::direct(edge, !Parent::direction(edge)); 930 } 931 932 755 return direct(edge, !Parent::direction(edge)); 756 } 757 933 758 int maxId(Node) const { 934 759 return Parent::maxNodeId(); … … 941 766 } 942 767 int maxId(Edge) const { 943 return maxEdgeId();768 return Parent::maxEdgeId(); 944 769 } 945 770 int maxId(UEdge) const { … … 952 777 } 953 778 ANode fromId(int id, ANode) const { 954 return Parent:: fromANodeId(id);779 return Parent::nodeFromANodeId(id); 955 780 } 956 781 BNode fromId(int id, BNode) const { 957 return Parent:: fromBNodeId(id);782 return Parent::nodeFromBNodeId(id); 958 783 } 959 784 Edge fromId(int id, Edge) const { … … 1305 1130 NodeMap& operator=(const CMap& cmap) { 1306 1131 checkConcept<concept::ReadMap<Node, _Value>, CMap>(); 1307 const typename Parent::Notifier* notifier = Parent::getNotifier(); 1308 Edge it; 1309 for (graph.first(it); it != INVALID; graph.next(it)) { 1310 Parent::set(it, cmap[it]); 1311 } 1312 return *this; 1132 aNodeMap = cmap; 1133 bNodeMap = cmap; 1134 return *this; 1313 1135 } 1314 1136 … … 1460 1282 1461 1283 std::vector<Edge> edges; 1462 edges.push_back( direct(uedge, true));1463 edges.push_back( direct(uedge, false));1284 edges.push_back(Parent::direct(uedge, true)); 1285 edges.push_back(Parent::direct(uedge, false)); 1464 1286 getNotifier(Edge()).add(edges); 1465 1287 … … 1500 1322 void erase(const UEdge& uedge) { 1501 1323 std::vector<Edge> edges; 1502 edges.push_back( direct(uedge, true));1503 edges.push_back( direct(uedge, false));1324 edges.push_back(Parent::direct(uedge, true)); 1325 edges.push_back(Parent::direct(uedge, false)); 1504 1326 getNotifier(Edge()).erase(edges); 1505 1327 getNotifier(UEdge()).erase(uedge); … … 1527 1349 UEdge uedge = Parent::findUEdge(u, v, prev); 1528 1350 if (uedge != INVALID) { 1529 return direct(uedge, Parent::aNode(u));1351 return Parent::direct(uedge, Parent::aNode(u)); 1530 1352 } else { 1531 1353 return INVALID;
Note: See TracChangeset
for help on using the changeset viewer.