852 bool operator==(const Node& node) const {return _id == node._id;} |
852 bool operator==(const Node& node) const {return _id == node._id;} |
853 bool operator!=(const Node& node) const {return _id != node._id;} |
853 bool operator!=(const Node& node) const {return _id != node._id;} |
854 bool operator<(const Node& node) const {return _id < node._id;} |
854 bool operator<(const Node& node) const {return _id < node._id;} |
855 }; |
855 }; |
856 |
856 |
|
857 class RedNode : public Node { |
|
858 friend class SmartBpGraphBase; |
|
859 protected: |
|
860 |
|
861 explicit RedNode(int pid) : Node(pid) {} |
|
862 |
|
863 public: |
|
864 RedNode() {} |
|
865 RedNode(const RedNode& node) : Node(node) {} |
|
866 RedNode(Invalid) : Node(INVALID){} |
|
867 }; |
|
868 |
|
869 class BlueNode : public Node { |
|
870 friend class SmartBpGraphBase; |
|
871 protected: |
|
872 |
|
873 explicit BlueNode(int pid) : Node(pid) {} |
|
874 |
|
875 public: |
|
876 BlueNode() {} |
|
877 BlueNode(const BlueNode& node) : Node(node) {} |
|
878 BlueNode(Invalid) : Node(INVALID){} |
|
879 }; |
|
880 |
857 class Edge { |
881 class Edge { |
858 friend class SmartBpGraphBase; |
882 friend class SmartBpGraphBase; |
859 protected: |
883 protected: |
860 |
884 |
861 int _id; |
885 int _id; |
911 int maxArcId() const { return arcs.size()-1; } |
935 int maxArcId() const { return arcs.size()-1; } |
912 |
936 |
913 bool red(Node n) const { return nodes[n._id].red; } |
937 bool red(Node n) const { return nodes[n._id].red; } |
914 bool blue(Node n) const { return !nodes[n._id].red; } |
938 bool blue(Node n) const { return !nodes[n._id].red; } |
915 |
939 |
|
940 static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); } |
|
941 static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); } |
|
942 |
916 Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); } |
943 Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); } |
917 Node target(Arc a) const { return Node(arcs[a._id].target); } |
944 Node target(Arc a) const { return Node(arcs[a._id].target); } |
918 |
945 |
919 Node redNode(Edge e) const { return Node(arcs[2 * e._id].target); } |
946 RedNode redNode(Edge e) const { |
920 Node blueNode(Edge e) const { return Node(arcs[2 * e._id + 1].target); } |
947 return RedNode(arcs[2 * e._id].target); |
|
948 } |
|
949 BlueNode blueNode(Edge e) const { |
|
950 return BlueNode(arcs[2 * e._id + 1].target); |
|
951 } |
921 |
952 |
922 static bool direction(Arc a) { |
953 static bool direction(Arc a) { |
923 return (a._id & 1) == 1; |
954 return (a._id & 1) == 1; |
924 } |
955 } |
925 |
956 |
933 |
964 |
934 static void next(Node& node) { |
965 static void next(Node& node) { |
935 --node._id; |
966 --node._id; |
936 } |
967 } |
937 |
968 |
938 void firstRed(Node& node) const { |
969 void first(RedNode& node) const { |
939 node._id = first_red; |
970 node._id = first_red; |
940 } |
971 } |
941 |
972 |
942 void nextRed(Node& node) const { |
973 void next(RedNode& node) const { |
943 node._id = nodes[node._id].partition_next; |
974 node._id = nodes[node._id].partition_next; |
944 } |
975 } |
945 |
976 |
946 void firstBlue(Node& node) const { |
977 void first(BlueNode& node) const { |
947 node._id = first_blue; |
978 node._id = first_blue; |
948 } |
979 } |
949 |
980 |
950 void nextBlue(Node& node) const { |
981 void next(BlueNode& node) const { |
951 node._id = nodes[node._id].partition_next; |
982 node._id = nodes[node._id].partition_next; |
952 } |
983 } |
953 |
984 |
954 void first(Arc& arc) const { |
985 void first(Arc& arc) const { |
955 arc._id = arcs.size() - 1; |
986 arc._id = arcs.size() - 1; |
1003 d = true; |
1034 d = true; |
1004 } |
1035 } |
1005 } |
1036 } |
1006 |
1037 |
1007 static int id(Node v) { return v._id; } |
1038 static int id(Node v) { return v._id; } |
1008 int redId(Node v) const { |
1039 int id(RedNode v) const { return nodes[v._id].partition_index; } |
1009 LEMON_DEBUG(nodes[v._id].red, "Node has to be red"); |
1040 int id(BlueNode v) const { return nodes[v._id].partition_index; } |
1010 return nodes[v._id].partition_index; |
|
1011 } |
|
1012 int blueId(Node v) const { |
|
1013 LEMON_DEBUG(!nodes[v._id].red, "Node has to be blue"); |
|
1014 return nodes[v._id].partition_index; |
|
1015 } |
|
1016 static int id(Arc e) { return e._id; } |
1041 static int id(Arc e) { return e._id; } |
1017 static int id(Edge e) { return e._id; } |
1042 static int id(Edge e) { return e._id; } |
1018 |
1043 |
1019 static Node nodeFromId(int id) { return Node(id);} |
1044 static Node nodeFromId(int id) { return Node(id);} |
1020 static Arc arcFromId(int id) { return Arc(id);} |
1045 static Arc arcFromId(int id) { return Arc(id);} |
1028 } |
1053 } |
1029 bool valid(Edge e) const { |
1054 bool valid(Edge e) const { |
1030 return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size()); |
1055 return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size()); |
1031 } |
1056 } |
1032 |
1057 |
1033 Node addRedNode() { |
1058 RedNode addRedNode() { |
1034 int n = nodes.size(); |
1059 int n = nodes.size(); |
1035 nodes.push_back(NodeT()); |
1060 nodes.push_back(NodeT()); |
1036 nodes[n].first_out = -1; |
1061 nodes[n].first_out = -1; |
1037 nodes[n].red = true; |
1062 nodes[n].red = true; |
1038 nodes[n].partition_index = ++max_red; |
1063 nodes[n].partition_index = ++max_red; |
1039 nodes[n].partition_next = first_red; |
1064 nodes[n].partition_next = first_red; |
1040 first_red = n; |
1065 first_red = n; |
1041 |
1066 |
1042 return Node(n); |
1067 return RedNode(n); |
1043 } |
1068 } |
1044 |
1069 |
1045 Node addBlueNode() { |
1070 BlueNode addBlueNode() { |
1046 int n = nodes.size(); |
1071 int n = nodes.size(); |
1047 nodes.push_back(NodeT()); |
1072 nodes.push_back(NodeT()); |
1048 nodes[n].first_out = -1; |
1073 nodes[n].first_out = -1; |
1049 nodes[n].red = false; |
1074 nodes[n].red = false; |
1050 nodes[n].partition_index = ++max_blue; |
1075 nodes[n].partition_index = ++max_blue; |
1051 nodes[n].partition_next = first_blue; |
1076 nodes[n].partition_next = first_blue; |
1052 first_blue = n; |
1077 first_blue = n; |
1053 |
1078 |
1054 return Node(n); |
1079 return BlueNode(n); |
1055 } |
1080 } |
1056 |
1081 |
1057 Edge addEdge(Node u, Node v) { |
1082 Edge addEdge(RedNode u, BlueNode v) { |
1058 int n = arcs.size(); |
1083 int n = arcs.size(); |
1059 arcs.push_back(ArcT()); |
1084 arcs.push_back(ArcT()); |
1060 arcs.push_back(ArcT()); |
1085 arcs.push_back(ArcT()); |
1061 |
1086 |
1062 arcs[n].target = u._id; |
1087 arcs[n].target = u._id; |
1122 |
1147 |
1123 /// \brief Add a new red node to the graph. |
1148 /// \brief Add a new red node to the graph. |
1124 /// |
1149 /// |
1125 /// This function adds a red new node to the graph. |
1150 /// This function adds a red new node to the graph. |
1126 /// \return The new node. |
1151 /// \return The new node. |
1127 Node addRedNode() { return Parent::addRedNode(); } |
1152 RedNode addRedNode() { return Parent::addRedNode(); } |
1128 |
1153 |
1129 /// \brief Add a new blue node to the graph. |
1154 /// \brief Add a new blue node to the graph. |
1130 /// |
1155 /// |
1131 /// This function adds a blue new node to the graph. |
1156 /// This function adds a blue new node to the graph. |
1132 /// \return The new node. |
1157 /// \return The new node. |
1133 Node addBlueNode() { return Parent::addBlueNode(); } |
1158 BlueNode addBlueNode() { return Parent::addBlueNode(); } |
1134 |
1159 |
1135 /// \brief Add a new edge to the graph. |
1160 /// \brief Add a new edge to the graph. |
1136 /// |
1161 /// |
1137 /// This function adds a new edge to the graph between nodes |
1162 /// This function adds a new edge to the graph between nodes |
1138 /// \c u and \c v with inherent orientation from node \c u to |
1163 /// \c u and \c v with inherent orientation from node \c u to |
1139 /// node \c v. |
1164 /// node \c v. |
1140 /// \return The new edge. |
1165 /// \return The new edge. |
1141 Edge addEdge(Node red, Node blue) { |
1166 Edge addEdge(RedNode u, BlueNode v) { |
1142 LEMON_DEBUG(Parent::red(red) && Parent::blue(blue), |
1167 return Parent::addEdge(u, v); |
1143 "Edge has to be formed by a red and a blue nodes"); |
1168 } |
1144 return Parent::addEdge(red, blue); |
1169 Edge addEdge(BlueNode v, RedNode u) { |
|
1170 return Parent::addEdge(u, v); |
1145 } |
1171 } |
1146 |
1172 |
1147 /// \brief Node validity check |
1173 /// \brief Node validity check |
1148 /// |
1174 /// |
1149 /// This function gives back \c true if the given node is valid, |
1175 /// This function gives back \c true if the given node is valid, |
1235 if (first_red != -1) { |
1261 if (first_red != -1) { |
1236 max_red = nodes[first_red].partition_index; |
1262 max_red = nodes[first_red].partition_index; |
1237 } else { |
1263 } else { |
1238 max_red = -1; |
1264 max_red = -1; |
1239 } |
1265 } |
1240 Parent::notifier(RedNode()).erase(node); |
1266 Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node)); |
1241 } else { |
1267 } else { |
1242 first_blue = nodes[n].partition_next; |
1268 first_blue = nodes[n].partition_next; |
1243 if (first_blue != -1) { |
1269 if (first_blue != -1) { |
1244 max_blue = nodes[first_blue].partition_index; |
1270 max_blue = nodes[first_blue].partition_index; |
1245 } else { |
1271 } else { |
1246 max_blue = -1; |
1272 max_blue = -1; |
1247 } |
1273 } |
1248 Parent::notifier(BlueNode()).erase(node); |
1274 Parent::notifier(BlueNode()).erase(asBlueNodeUnsafe(node)); |
1249 } |
1275 } |
1250 Parent::notifier(Node()).erase(node); |
1276 Parent::notifier(Node()).erase(node); |
1251 nodes.pop_back(); |
1277 nodes.pop_back(); |
1252 } |
1278 } |
1253 } |
1279 } |