728 /// |
728 /// |
729 /// \brief Extender for the BpUGraphs |
729 /// \brief Extender for the BpUGraphs |
730 template <typename Base> |
730 template <typename Base> |
731 class BpUGraphExtender : public Base { |
731 class BpUGraphExtender : public Base { |
732 public: |
732 public: |
|
733 |
733 typedef Base Parent; |
734 typedef Base Parent; |
734 typedef BpUGraphExtender Graph; |
735 typedef BpUGraphExtender Graph; |
735 |
736 |
736 typedef typename Parent::Node Node; |
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 typedef typename Parent::UEdge UEdge; |
741 typedef typename Parent::UEdge UEdge; |
738 |
742 |
739 |
743 |
740 using Parent::first; |
744 Node oppositeNode(const Node& node, const UEdge& edge) const { |
741 using Parent::next; |
745 return Parent::aNode(edge) == node ? |
742 |
746 Parent::bNode(edge) : Parent::aNode(edge); |
743 using Parent::id; |
747 } |
744 |
748 |
745 class ANode : public Node { |
749 using Parent::direct; |
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 |
|
924 Edge direct(const UEdge& edge, const Node& node) const { |
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 Edge oppositeEdge(const Edge& edge) const { |
754 Edge oppositeEdge(const Edge& edge) const { |
929 return Parent::direct(edge, !Parent::direction(edge)); |
755 return direct(edge, !Parent::direction(edge)); |
930 } |
756 } |
931 |
757 |
932 |
|
933 int maxId(Node) const { |
758 int maxId(Node) const { |
934 return Parent::maxNodeId(); |
759 return Parent::maxNodeId(); |
935 } |
760 } |
936 int maxId(BNode) const { |
761 int maxId(BNode) const { |
937 return Parent::maxBNodeId(); |
762 return Parent::maxBNodeId(); |
938 } |
763 } |
939 int maxId(ANode) const { |
764 int maxId(ANode) const { |
940 return Parent::maxANodeId(); |
765 return Parent::maxANodeId(); |
941 } |
766 } |
942 int maxId(Edge) const { |
767 int maxId(Edge) const { |
943 return maxEdgeId(); |
768 return Parent::maxEdgeId(); |
944 } |
769 } |
945 int maxId(UEdge) const { |
770 int maxId(UEdge) const { |
946 return Parent::maxUEdgeId(); |
771 return Parent::maxUEdgeId(); |
947 } |
772 } |
948 |
773 |
949 |
774 |
950 Node fromId(int id, Node) const { |
775 Node fromId(int id, Node) const { |
951 return Parent::nodeFromId(id); |
776 return Parent::nodeFromId(id); |
952 } |
777 } |
953 ANode fromId(int id, ANode) const { |
778 ANode fromId(int id, ANode) const { |
954 return Parent::fromANodeId(id); |
779 return Parent::nodeFromANodeId(id); |
955 } |
780 } |
956 BNode fromId(int id, BNode) const { |
781 BNode fromId(int id, BNode) const { |
957 return Parent::fromBNodeId(id); |
782 return Parent::nodeFromBNodeId(id); |
958 } |
783 } |
959 Edge fromId(int id, Edge) const { |
784 Edge fromId(int id, Edge) const { |
960 return Parent::edgeFromId(id); |
785 return Parent::edgeFromId(id); |
961 } |
786 } |
962 UEdge fromId(int id, UEdge) const { |
787 UEdge fromId(int id, UEdge) const { |