732 public: |
732 public: |
733 typedef Base Parent; |
733 typedef Base Parent; |
734 typedef BpUGraphExtender Graph; |
734 typedef BpUGraphExtender Graph; |
735 |
735 |
736 typedef typename Parent::Node Node; |
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 typedef typename Parent::UEdge UEdge; |
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 Node oppositeNode(const UEdge& edge, const Node& node) const { |
919 Node oppositeNode(const UEdge& edge, const Node& node) const { |
743 return source(edge) == node ? |
920 return source(edge) == node ? |
744 target(edge) : source(edge); |
921 target(edge) : source(edge); |
745 } |
922 } |
746 |
923 |
747 using Parent::direct; |
|
748 Edge direct(const UEdge& edge, const Node& node) const { |
924 Edge direct(const UEdge& edge, const Node& node) const { |
749 return Edge(edge, node == Parent::source(edge)); |
925 return Edge(edge, node == Parent::source(edge)); |
750 } |
926 } |
751 |
927 |
752 Edge oppositeEdge(const Edge& edge) const { |
928 Edge oppositeEdge(const Edge& edge) const { |