649 bool operator==(const Node& node) const {return _id == node._id;} |
649 bool operator==(const Node& node) const {return _id == node._id;} |
650 bool operator!=(const Node& node) const {return _id != node._id;} |
650 bool operator!=(const Node& node) const {return _id != node._id;} |
651 bool operator<(const Node& node) const {return _id < node._id;} |
651 bool operator<(const Node& node) const {return _id < node._id;} |
652 }; |
652 }; |
653 |
653 |
|
654 class RedNode : public Node { |
|
655 friend class FullBpGraphBase; |
|
656 protected: |
|
657 |
|
658 explicit RedNode(int pid) : Node(pid) {} |
|
659 |
|
660 public: |
|
661 RedNode() {} |
|
662 RedNode(const RedNode& node) : Node(node) {} |
|
663 RedNode(Invalid) : Node(INVALID){} |
|
664 }; |
|
665 |
|
666 class BlueNode : public Node { |
|
667 friend class FullBpGraphBase; |
|
668 protected: |
|
669 |
|
670 explicit BlueNode(int pid) : Node(pid) {} |
|
671 |
|
672 public: |
|
673 BlueNode() {} |
|
674 BlueNode(const BlueNode& node) : Node(node) {} |
|
675 BlueNode(Invalid) : Node(INVALID){} |
|
676 }; |
|
677 |
654 class Edge { |
678 class Edge { |
655 friend class FullBpGraphBase; |
679 friend class FullBpGraphBase; |
656 protected: |
680 protected: |
657 |
681 |
658 int _id; |
682 int _id; |
715 int maxArcId() const { return 2 * _edge_num - 1; } |
739 int maxArcId() const { return 2 * _edge_num - 1; } |
716 |
740 |
717 bool red(Node n) const { return n._id < _red_num; } |
741 bool red(Node n) const { return n._id < _red_num; } |
718 bool blue(Node n) const { return n._id >= _red_num; } |
742 bool blue(Node n) const { return n._id >= _red_num; } |
719 |
743 |
|
744 static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); } |
|
745 static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); } |
|
746 |
720 Node source(Arc a) const { |
747 Node source(Arc a) const { |
721 if (a._id & 1) { |
748 if (a._id & 1) { |
722 return Node((a._id >> 1) % _red_num); |
749 return Node((a._id >> 1) % _red_num); |
723 } else { |
750 } else { |
724 return Node((a._id >> 1) / _red_num + _red_num); |
751 return Node((a._id >> 1) / _red_num + _red_num); |
730 } else { |
757 } else { |
731 return Node((a._id >> 1) % _red_num); |
758 return Node((a._id >> 1) % _red_num); |
732 } |
759 } |
733 } |
760 } |
734 |
761 |
735 Node redNode(Edge e) const { |
762 RedNode redNode(Edge e) const { |
736 return Node(e._id % _red_num); |
763 return RedNode(e._id % _red_num); |
737 } |
764 } |
738 Node blueNode(Edge e) const { |
765 BlueNode blueNode(Edge e) const { |
739 return Node(e._id / _red_num + _red_num); |
766 return BlueNode(e._id / _red_num + _red_num); |
740 } |
767 } |
741 |
768 |
742 static bool direction(Arc a) { |
769 static bool direction(Arc a) { |
743 return (a._id & 1) == 1; |
770 return (a._id & 1) == 1; |
744 } |
771 } |
753 |
780 |
754 static void next(Node& node) { |
781 static void next(Node& node) { |
755 --node._id; |
782 --node._id; |
756 } |
783 } |
757 |
784 |
758 void firstRed(Node& node) const { |
785 void first(RedNode& node) const { |
759 node._id = _red_num - 1; |
786 node._id = _red_num - 1; |
760 } |
787 } |
761 |
788 |
762 static void nextRed(Node& node) { |
789 static void next(RedNode& node) { |
763 --node._id; |
790 --node._id; |
764 } |
791 } |
765 |
792 |
766 void firstBlue(Node& node) const { |
793 void first(BlueNode& node) const { |
767 if (_red_num == _node_num) node._id = -1; |
794 if (_red_num == _node_num) node._id = -1; |
768 else node._id = _node_num - 1; |
795 else node._id = _node_num - 1; |
769 } |
796 } |
770 |
797 |
771 void nextBlue(Node& node) const { |
798 void next(BlueNode& node) const { |
772 if (node._id == _red_num) node._id = -1; |
799 if (node._id == _red_num) node._id = -1; |
773 else --node._id; |
800 else --node._id; |
774 } |
801 } |
775 |
802 |
776 void first(Arc& arc) const { |
803 void first(Arc& arc) const { |
840 if (e._id % _red_num == 0) e._id = -1; |
867 if (e._id % _red_num == 0) e._id = -1; |
841 else --e._id; |
868 else --e._id; |
842 } |
869 } |
843 } |
870 } |
844 |
871 |
845 static int id(Node v) { return v._id; } |
872 static int id(const Node& v) { return v._id; } |
846 int redId(Node v) const { |
873 int id(const RedNode& v) const { return v._id; } |
847 LEMON_DEBUG(v._id < _red_num, "Node has to be red"); |
874 int id(const BlueNode& v) const { return v._id - _red_num; } |
848 return v._id; |
|
849 } |
|
850 int blueId(Node v) const { |
|
851 LEMON_DEBUG(v._id >= _red_num, "Node has to be blue"); |
|
852 return v._id - _red_num; |
|
853 } |
|
854 static int id(Arc e) { return e._id; } |
875 static int id(Arc e) { return e._id; } |
855 static int id(Edge e) { return e._id; } |
876 static int id(Edge e) { return e._id; } |
856 |
877 |
857 static Node nodeFromId(int id) { return Node(id);} |
878 static Node nodeFromId(int id) { return Node(id);} |
858 static Arc arcFromId(int id) { return Arc(id);} |
879 static Arc arcFromId(int id) { return Arc(id);} |
866 } |
887 } |
867 bool valid(Edge e) const { |
888 bool valid(Edge e) const { |
868 return e._id >= 0 && e._id < _edge_num; |
889 return e._id >= 0 && e._id < _edge_num; |
869 } |
890 } |
870 |
891 |
871 Node redNode(int index) const { |
892 RedNode redNode(int index) const { |
872 return Node(index); |
893 return RedNode(index); |
873 } |
894 } |
874 |
895 |
875 int redIndex(Node n) const { |
896 int index(RedNode n) const { |
876 return n._id; |
897 return n._id; |
877 } |
898 } |
878 |
899 |
879 Node blueNode(int index) const { |
900 BlueNode blueNode(int index) const { |
880 return Node(index + _red_num); |
901 return BlueNode(index + _red_num); |
881 } |
902 } |
882 |
903 |
883 int blueIndex(Node n) const { |
904 int index(BlueNode n) const { |
884 return n._id - _red_num; |
905 return n._id - _red_num; |
885 } |
906 } |
886 |
907 |
887 void clear() { |
908 void clear() { |
888 _red_num = 0; _blue_num = 0; |
909 _red_num = 0; _blue_num = 0; |
998 /// |
1019 /// |
999 /// Returns the red node with the given index. Since this |
1020 /// Returns the red node with the given index. Since this |
1000 /// structure is completely static, the red nodes can be indexed |
1021 /// structure is completely static, the red nodes can be indexed |
1001 /// with integers from the range <tt>[0..redNum()-1]</tt>. |
1022 /// with integers from the range <tt>[0..redNum()-1]</tt>. |
1002 /// \sa redIndex() |
1023 /// \sa redIndex() |
1003 Node redNode(int index) const { return Parent::redNode(index); } |
1024 RedNode redNode(int index) const { return Parent::redNode(index); } |
1004 |
1025 |
1005 /// \brief Returns the index of the given red node. |
1026 /// \brief Returns the index of the given red node. |
1006 /// |
1027 /// |
1007 /// Returns the index of the given red node. Since this structure |
1028 /// Returns the index of the given red node. Since this structure |
1008 /// is completely static, the red nodes can be indexed with |
1029 /// is completely static, the red nodes can be indexed with |
1009 /// integers from the range <tt>[0..redNum()-1]</tt>. |
1030 /// integers from the range <tt>[0..redNum()-1]</tt>. |
1010 /// |
1031 /// |
1011 /// \sa operator()() |
1032 /// \sa operator()() |
1012 int redIndex(Node node) const { return Parent::redIndex(node); } |
1033 int index(RedNode node) const { return Parent::index(node); } |
1013 |
1034 |
1014 /// \brief Returns the blue node with the given index. |
1035 /// \brief Returns the blue node with the given index. |
1015 /// |
1036 /// |
1016 /// Returns the blue node with the given index. Since this |
1037 /// Returns the blue node with the given index. Since this |
1017 /// structure is completely static, the blue nodes can be indexed |
1038 /// structure is completely static, the blue nodes can be indexed |
1018 /// with integers from the range <tt>[0..blueNum()-1]</tt>. |
1039 /// with integers from the range <tt>[0..blueNum()-1]</tt>. |
1019 /// \sa blueIndex() |
1040 /// \sa blueIndex() |
1020 Node blueNode(int index) const { return Parent::blueNode(index); } |
1041 BlueNode blueNode(int index) const { return Parent::blueNode(index); } |
1021 |
1042 |
1022 /// \brief Returns the index of the given blue node. |
1043 /// \brief Returns the index of the given blue node. |
1023 /// |
1044 /// |
1024 /// Returns the index of the given blue node. Since this structure |
1045 /// Returns the index of the given blue node. Since this structure |
1025 /// is completely static, the blue nodes can be indexed with |
1046 /// is completely static, the blue nodes can be indexed with |
1026 /// integers from the range <tt>[0..blueNum()-1]</tt>. |
1047 /// integers from the range <tt>[0..blueNum()-1]</tt>. |
1027 /// |
1048 /// |
1028 /// \sa operator()() |
1049 /// \sa operator()() |
1029 int blueIndex(Node node) const { return Parent::blueIndex(node); } |
1050 int index(BlueNode node) const { return Parent::index(node); } |
1030 |
1051 |
1031 /// \brief Returns the edge which connects the given nodes. |
1052 /// \brief Returns the edge which connects the given nodes. |
1032 /// |
1053 /// |
1033 /// Returns the edge which connects the given nodes. |
1054 /// Returns the edge which connects the given nodes. |
1034 Edge edge(const Node& u, const Node& v) const { |
1055 Edge edge(const Node& u, const Node& v) const { |