888 }; |
889 }; |
889 |
890 |
890 |
891 |
891 |
892 |
892 SmartBpGraphBase() |
893 SmartBpGraphBase() |
893 : nodes(), arcs(), first_red(-1), first_blue(-1) {} |
894 : nodes(), arcs(), first_red(-1), first_blue(-1), |
|
895 max_red(-1), max_blue(-1) {} |
894 |
896 |
895 typedef True NodeNumTag; |
897 typedef True NodeNumTag; |
896 typedef True EdgeNumTag; |
898 typedef True EdgeNumTag; |
897 typedef True ArcNumTag; |
899 typedef True ArcNumTag; |
898 |
900 |
899 int nodeNum() const { return nodes.size(); } |
901 int nodeNum() const { return nodes.size(); } |
900 int redNum() const { |
902 int redNum() const { return max_red + 1; } |
901 return first_red == -1 ? 0 : nodes[first_red].partition_index + 1; |
903 int blueNum() const { return max_blue + 1; } |
902 } |
|
903 int blueNum() const { |
|
904 return first_blue == -1 ? 0 : nodes[first_blue].partition_index + 1; |
|
905 } |
|
906 int edgeNum() const { return arcs.size() / 2; } |
904 int edgeNum() const { return arcs.size() / 2; } |
907 int arcNum() const { return arcs.size(); } |
905 int arcNum() const { return arcs.size(); } |
908 |
906 |
909 int maxNodeId() const { return nodes.size()-1; } |
907 int maxNodeId() const { return nodes.size()-1; } |
910 int maxRedId() const { |
908 int maxRedId() const { return max_red; } |
911 return first_red == -1 ? -1 : nodes[first_red].partition_index; |
909 int maxBlueId() const { return max_blue; } |
912 } |
|
913 int maxBlueId() const { |
|
914 return first_blue == -1 ? -1 : nodes[first_blue].partition_index; |
|
915 } |
|
916 int maxEdgeId() const { return arcs.size() / 2 - 1; } |
910 int maxEdgeId() const { return arcs.size() / 2 - 1; } |
917 int maxArcId() const { return arcs.size()-1; } |
911 int maxArcId() const { return arcs.size()-1; } |
918 |
912 |
919 bool red(Node n) const { return nodes[n._id].red; } |
913 bool red(Node n) const { return nodes[n._id].red; } |
920 bool blue(Node n) const { return !nodes[n._id].red; } |
914 bool blue(Node n) const { return !nodes[n._id].red; } |
1039 Node addRedNode() { |
1033 Node addRedNode() { |
1040 int n = nodes.size(); |
1034 int n = nodes.size(); |
1041 nodes.push_back(NodeT()); |
1035 nodes.push_back(NodeT()); |
1042 nodes[n].first_out = -1; |
1036 nodes[n].first_out = -1; |
1043 nodes[n].red = true; |
1037 nodes[n].red = true; |
1044 if (first_red == -1) { |
1038 nodes[n].partition_index = ++max_red; |
1045 nodes[n].partition_index = 0; |
|
1046 } else { |
|
1047 nodes[n].partition_index = nodes[first_red].partition_index + 1; |
|
1048 } |
|
1049 nodes[n].partition_next = first_red; |
1039 nodes[n].partition_next = first_red; |
1050 first_red = n; |
1040 first_red = n; |
1051 |
1041 |
1052 return Node(n); |
1042 return Node(n); |
1053 } |
1043 } |
1055 Node addBlueNode() { |
1045 Node addBlueNode() { |
1056 int n = nodes.size(); |
1046 int n = nodes.size(); |
1057 nodes.push_back(NodeT()); |
1047 nodes.push_back(NodeT()); |
1058 nodes[n].first_out = -1; |
1048 nodes[n].first_out = -1; |
1059 nodes[n].red = false; |
1049 nodes[n].red = false; |
1060 if (first_blue == -1) { |
1050 nodes[n].partition_index = ++max_blue; |
1061 nodes[n].partition_index = 0; |
|
1062 } else { |
|
1063 nodes[n].partition_index = nodes[first_blue].partition_index + 1; |
|
1064 } |
|
1065 nodes[n].partition_next = first_blue; |
1051 nodes[n].partition_next = first_blue; |
1066 first_blue = n; |
1052 first_blue = n; |
1067 |
1053 |
1068 return Node(n); |
1054 return Node(n); |
1069 } |
1055 } |
1242 while(s.node_num<nodes.size()) { |
1230 while(s.node_num<nodes.size()) { |
1243 int n=nodes.size()-1; |
1231 int n=nodes.size()-1; |
1244 Node node = nodeFromId(n); |
1232 Node node = nodeFromId(n); |
1245 if (Parent::red(node)) { |
1233 if (Parent::red(node)) { |
1246 first_red = nodes[n].partition_next; |
1234 first_red = nodes[n].partition_next; |
|
1235 if (first_red != -1) { |
|
1236 max_red = nodes[first_red].partition_index; |
|
1237 } else { |
|
1238 max_red = -1; |
|
1239 } |
1247 Parent::notifier(RedNode()).erase(node); |
1240 Parent::notifier(RedNode()).erase(node); |
1248 } else { |
1241 } else { |
1249 first_blue = nodes[n].partition_next; |
1242 first_blue = nodes[n].partition_next; |
|
1243 if (first_blue != -1) { |
|
1244 max_blue = nodes[first_blue].partition_index; |
|
1245 } else { |
|
1246 max_blue = -1; |
|
1247 } |
1250 Parent::notifier(BlueNode()).erase(node); |
1248 Parent::notifier(BlueNode()).erase(node); |
1251 } |
1249 } |
1252 Parent::notifier(Node()).erase(node); |
1250 Parent::notifier(Node()).erase(node); |
1253 nodes.pop_back(); |
1251 nodes.pop_back(); |
1254 } |
1252 } |