744 node_notifier.clear(); |
744 node_notifier.clear(); |
745 } |
745 } |
746 |
746 |
747 }; |
747 }; |
748 |
748 |
|
749 // \ingroup _graphbits |
|
750 // |
|
751 // \brief Extender for the BpGraphs |
|
752 template <typename Base> |
|
753 class BpGraphExtender : public Base { |
|
754 typedef Base Parent; |
|
755 |
|
756 public: |
|
757 |
|
758 typedef BpGraphExtender BpGraph; |
|
759 |
|
760 typedef True UndirectedTag; |
|
761 |
|
762 typedef typename Parent::Node Node; |
|
763 typedef typename Parent::Arc Arc; |
|
764 typedef typename Parent::Edge Edge; |
|
765 |
|
766 // BpGraph extension |
|
767 |
|
768 class RedNode : public Node { |
|
769 public: |
|
770 RedNode() {} |
|
771 RedNode(const RedNode& node) : Node(node) {} |
|
772 RedNode(Invalid) : Node(INVALID){} |
|
773 RedNode(const Node& node) : Node(node) {} |
|
774 }; |
|
775 class BlueNode : public Node { |
|
776 public: |
|
777 BlueNode() {} |
|
778 BlueNode(const BlueNode& node) : Node(node) {} |
|
779 BlueNode(Invalid) : Node(INVALID){} |
|
780 BlueNode(const Node& node) : Node(node) {} |
|
781 }; |
|
782 |
|
783 using Parent::first; |
|
784 using Parent::next; |
|
785 |
|
786 void first(RedNode& node) const { |
|
787 Parent::firstRed(node); |
|
788 } |
|
789 |
|
790 void next(RedNode& node) const { |
|
791 Parent::nextRed(node); |
|
792 } |
|
793 |
|
794 void first(BlueNode& node) const { |
|
795 Parent::firstBlue(node); |
|
796 } |
|
797 |
|
798 void next(BlueNode& node) const { |
|
799 Parent::nextBlue(node); |
|
800 } |
|
801 |
|
802 using Parent::id; |
|
803 |
|
804 int id(const RedNode& node) const { |
|
805 return Parent::redId(node); |
|
806 } |
|
807 |
|
808 int id(const BlueNode& node) const { |
|
809 return Parent::blueId(node); |
|
810 } |
|
811 |
|
812 int maxId(Node) const { |
|
813 return Parent::maxNodeId(); |
|
814 } |
|
815 |
|
816 int maxId(RedNode) const { |
|
817 return Parent::maxRedId(); |
|
818 } |
|
819 |
|
820 int maxId(BlueNode) const { |
|
821 return Parent::maxBlueId(); |
|
822 } |
|
823 |
|
824 int maxId(Arc) const { |
|
825 return Parent::maxArcId(); |
|
826 } |
|
827 |
|
828 int maxId(Edge) const { |
|
829 return Parent::maxEdgeId(); |
|
830 } |
|
831 |
|
832 static Node fromId(int id, Node) { |
|
833 return Parent::nodeFromId(id); |
|
834 } |
|
835 |
|
836 static Arc fromId(int id, Arc) { |
|
837 return Parent::arcFromId(id); |
|
838 } |
|
839 |
|
840 static Edge fromId(int id, Edge) { |
|
841 return Parent::edgeFromId(id); |
|
842 } |
|
843 |
|
844 Node oppositeNode(const Node &n, const Edge &e) const { |
|
845 if( n == Parent::u(e)) |
|
846 return Parent::v(e); |
|
847 else if( n == Parent::v(e)) |
|
848 return Parent::u(e); |
|
849 else |
|
850 return INVALID; |
|
851 } |
|
852 |
|
853 Arc oppositeArc(const Arc &arc) const { |
|
854 return Parent::direct(arc, !Parent::direction(arc)); |
|
855 } |
|
856 |
|
857 using Parent::direct; |
|
858 Arc direct(const Edge &edge, const Node &node) const { |
|
859 return Parent::direct(edge, Parent::u(edge) == node); |
|
860 } |
|
861 |
|
862 // Alterable extension |
|
863 |
|
864 typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier; |
|
865 typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier; |
|
866 typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier; |
|
867 typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier; |
|
868 typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier; |
|
869 |
|
870 |
|
871 protected: |
|
872 |
|
873 mutable NodeNotifier node_notifier; |
|
874 mutable RedNodeNotifier red_node_notifier; |
|
875 mutable BlueNodeNotifier blue_node_notifier; |
|
876 mutable ArcNotifier arc_notifier; |
|
877 mutable EdgeNotifier edge_notifier; |
|
878 |
|
879 public: |
|
880 |
|
881 NodeNotifier& notifier(Node) const { |
|
882 return node_notifier; |
|
883 } |
|
884 |
|
885 RedNodeNotifier& notifier(RedNode) const { |
|
886 return red_node_notifier; |
|
887 } |
|
888 |
|
889 BlueNodeNotifier& notifier(BlueNode) const { |
|
890 return blue_node_notifier; |
|
891 } |
|
892 |
|
893 ArcNotifier& notifier(Arc) const { |
|
894 return arc_notifier; |
|
895 } |
|
896 |
|
897 EdgeNotifier& notifier(Edge) const { |
|
898 return edge_notifier; |
|
899 } |
|
900 |
|
901 |
|
902 |
|
903 class NodeIt : public Node { |
|
904 const BpGraph* _graph; |
|
905 public: |
|
906 |
|
907 NodeIt() {} |
|
908 |
|
909 NodeIt(Invalid i) : Node(i) { } |
|
910 |
|
911 explicit NodeIt(const BpGraph& graph) : _graph(&graph) { |
|
912 _graph->first(static_cast<Node&>(*this)); |
|
913 } |
|
914 |
|
915 NodeIt(const BpGraph& graph, const Node& node) |
|
916 : Node(node), _graph(&graph) {} |
|
917 |
|
918 NodeIt& operator++() { |
|
919 _graph->next(*this); |
|
920 return *this; |
|
921 } |
|
922 |
|
923 }; |
|
924 |
|
925 class RedIt : public Node { |
|
926 const BpGraph* _graph; |
|
927 public: |
|
928 |
|
929 RedIt() {} |
|
930 |
|
931 RedIt(Invalid i) : Node(i) { } |
|
932 |
|
933 explicit RedIt(const BpGraph& graph) : _graph(&graph) { |
|
934 _graph->firstRed(static_cast<Node&>(*this)); |
|
935 } |
|
936 |
|
937 RedIt(const BpGraph& graph, const Node& node) |
|
938 : Node(node), _graph(&graph) { |
|
939 LEMON_DEBUG(_graph->red(node), "Node has to be red."); |
|
940 } |
|
941 |
|
942 RedIt& operator++() { |
|
943 _graph->nextRed(*this); |
|
944 return *this; |
|
945 } |
|
946 |
|
947 }; |
|
948 |
|
949 class BlueIt : public Node { |
|
950 const BpGraph* _graph; |
|
951 public: |
|
952 |
|
953 BlueIt() {} |
|
954 |
|
955 BlueIt(Invalid i) : Node(i) { } |
|
956 |
|
957 explicit BlueIt(const BpGraph& graph) : _graph(&graph) { |
|
958 _graph->firstBlue(static_cast<Node&>(*this)); |
|
959 } |
|
960 |
|
961 BlueIt(const BpGraph& graph, const Node& node) |
|
962 : Node(node), _graph(&graph) { |
|
963 LEMON_DEBUG(_graph->blue(node), "Node has to be blue."); |
|
964 } |
|
965 |
|
966 BlueIt& operator++() { |
|
967 _graph->nextBlue(*this); |
|
968 return *this; |
|
969 } |
|
970 |
|
971 }; |
|
972 |
|
973 |
|
974 class ArcIt : public Arc { |
|
975 const BpGraph* _graph; |
|
976 public: |
|
977 |
|
978 ArcIt() { } |
|
979 |
|
980 ArcIt(Invalid i) : Arc(i) { } |
|
981 |
|
982 explicit ArcIt(const BpGraph& graph) : _graph(&graph) { |
|
983 _graph->first(static_cast<Arc&>(*this)); |
|
984 } |
|
985 |
|
986 ArcIt(const BpGraph& graph, const Arc& arc) : |
|
987 Arc(arc), _graph(&graph) { } |
|
988 |
|
989 ArcIt& operator++() { |
|
990 _graph->next(*this); |
|
991 return *this; |
|
992 } |
|
993 |
|
994 }; |
|
995 |
|
996 |
|
997 class OutArcIt : public Arc { |
|
998 const BpGraph* _graph; |
|
999 public: |
|
1000 |
|
1001 OutArcIt() { } |
|
1002 |
|
1003 OutArcIt(Invalid i) : Arc(i) { } |
|
1004 |
|
1005 OutArcIt(const BpGraph& graph, const Node& node) |
|
1006 : _graph(&graph) { |
|
1007 _graph->firstOut(*this, node); |
|
1008 } |
|
1009 |
|
1010 OutArcIt(const BpGraph& graph, const Arc& arc) |
|
1011 : Arc(arc), _graph(&graph) {} |
|
1012 |
|
1013 OutArcIt& operator++() { |
|
1014 _graph->nextOut(*this); |
|
1015 return *this; |
|
1016 } |
|
1017 |
|
1018 }; |
|
1019 |
|
1020 |
|
1021 class InArcIt : public Arc { |
|
1022 const BpGraph* _graph; |
|
1023 public: |
|
1024 |
|
1025 InArcIt() { } |
|
1026 |
|
1027 InArcIt(Invalid i) : Arc(i) { } |
|
1028 |
|
1029 InArcIt(const BpGraph& graph, const Node& node) |
|
1030 : _graph(&graph) { |
|
1031 _graph->firstIn(*this, node); |
|
1032 } |
|
1033 |
|
1034 InArcIt(const BpGraph& graph, const Arc& arc) : |
|
1035 Arc(arc), _graph(&graph) {} |
|
1036 |
|
1037 InArcIt& operator++() { |
|
1038 _graph->nextIn(*this); |
|
1039 return *this; |
|
1040 } |
|
1041 |
|
1042 }; |
|
1043 |
|
1044 |
|
1045 class EdgeIt : public Parent::Edge { |
|
1046 const BpGraph* _graph; |
|
1047 public: |
|
1048 |
|
1049 EdgeIt() { } |
|
1050 |
|
1051 EdgeIt(Invalid i) : Edge(i) { } |
|
1052 |
|
1053 explicit EdgeIt(const BpGraph& graph) : _graph(&graph) { |
|
1054 _graph->first(static_cast<Edge&>(*this)); |
|
1055 } |
|
1056 |
|
1057 EdgeIt(const BpGraph& graph, const Edge& edge) : |
|
1058 Edge(edge), _graph(&graph) { } |
|
1059 |
|
1060 EdgeIt& operator++() { |
|
1061 _graph->next(*this); |
|
1062 return *this; |
|
1063 } |
|
1064 |
|
1065 }; |
|
1066 |
|
1067 class IncEdgeIt : public Parent::Edge { |
|
1068 friend class BpGraphExtender; |
|
1069 const BpGraph* _graph; |
|
1070 bool _direction; |
|
1071 public: |
|
1072 |
|
1073 IncEdgeIt() { } |
|
1074 |
|
1075 IncEdgeIt(Invalid i) : Edge(i), _direction(false) { } |
|
1076 |
|
1077 IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) { |
|
1078 _graph->firstInc(*this, _direction, node); |
|
1079 } |
|
1080 |
|
1081 IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node) |
|
1082 : _graph(&graph), Edge(edge) { |
|
1083 _direction = (_graph->source(edge) == node); |
|
1084 } |
|
1085 |
|
1086 IncEdgeIt& operator++() { |
|
1087 _graph->nextInc(*this, _direction); |
|
1088 return *this; |
|
1089 } |
|
1090 }; |
|
1091 |
|
1092 // \brief Base node of the iterator |
|
1093 // |
|
1094 // Returns the base node (ie. the source in this case) of the iterator |
|
1095 Node baseNode(const OutArcIt &arc) const { |
|
1096 return Parent::source(static_cast<const Arc&>(arc)); |
|
1097 } |
|
1098 // \brief Running node of the iterator |
|
1099 // |
|
1100 // Returns the running node (ie. the target in this case) of the |
|
1101 // iterator |
|
1102 Node runningNode(const OutArcIt &arc) const { |
|
1103 return Parent::target(static_cast<const Arc&>(arc)); |
|
1104 } |
|
1105 |
|
1106 // \brief Base node of the iterator |
|
1107 // |
|
1108 // Returns the base node (ie. the target in this case) of the iterator |
|
1109 Node baseNode(const InArcIt &arc) const { |
|
1110 return Parent::target(static_cast<const Arc&>(arc)); |
|
1111 } |
|
1112 // \brief Running node of the iterator |
|
1113 // |
|
1114 // Returns the running node (ie. the source in this case) of the |
|
1115 // iterator |
|
1116 Node runningNode(const InArcIt &arc) const { |
|
1117 return Parent::source(static_cast<const Arc&>(arc)); |
|
1118 } |
|
1119 |
|
1120 // Base node of the iterator |
|
1121 // |
|
1122 // Returns the base node of the iterator |
|
1123 Node baseNode(const IncEdgeIt &edge) const { |
|
1124 return edge._direction ? this->u(edge) : this->v(edge); |
|
1125 } |
|
1126 // Running node of the iterator |
|
1127 // |
|
1128 // Returns the running node of the iterator |
|
1129 Node runningNode(const IncEdgeIt &edge) const { |
|
1130 return edge._direction ? this->v(edge) : this->u(edge); |
|
1131 } |
|
1132 |
|
1133 // Mappable extension |
|
1134 |
|
1135 template <typename _Value> |
|
1136 class NodeMap |
|
1137 : public MapExtender<DefaultMap<BpGraph, Node, _Value> > { |
|
1138 typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent; |
|
1139 |
|
1140 public: |
|
1141 explicit NodeMap(const BpGraph& bpgraph) |
|
1142 : Parent(bpgraph) {} |
|
1143 NodeMap(const BpGraph& bpgraph, const _Value& value) |
|
1144 : Parent(bpgraph, value) {} |
|
1145 |
|
1146 private: |
|
1147 NodeMap& operator=(const NodeMap& cmap) { |
|
1148 return operator=<NodeMap>(cmap); |
|
1149 } |
|
1150 |
|
1151 template <typename CMap> |
|
1152 NodeMap& operator=(const CMap& cmap) { |
|
1153 Parent::operator=(cmap); |
|
1154 return *this; |
|
1155 } |
|
1156 |
|
1157 }; |
|
1158 |
|
1159 template <typename _Value> |
|
1160 class RedMap |
|
1161 : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > { |
|
1162 typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent; |
|
1163 |
|
1164 public: |
|
1165 explicit RedMap(const BpGraph& bpgraph) |
|
1166 : Parent(bpgraph) {} |
|
1167 RedMap(const BpGraph& bpgraph, const _Value& value) |
|
1168 : Parent(bpgraph, value) {} |
|
1169 |
|
1170 private: |
|
1171 RedMap& operator=(const RedMap& cmap) { |
|
1172 return operator=<RedMap>(cmap); |
|
1173 } |
|
1174 |
|
1175 template <typename CMap> |
|
1176 RedMap& operator=(const CMap& cmap) { |
|
1177 Parent::operator=(cmap); |
|
1178 return *this; |
|
1179 } |
|
1180 |
|
1181 }; |
|
1182 |
|
1183 template <typename _Value> |
|
1184 class BlueMap |
|
1185 : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > { |
|
1186 typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent; |
|
1187 |
|
1188 public: |
|
1189 explicit BlueMap(const BpGraph& bpgraph) |
|
1190 : Parent(bpgraph) {} |
|
1191 BlueMap(const BpGraph& bpgraph, const _Value& value) |
|
1192 : Parent(bpgraph, value) {} |
|
1193 |
|
1194 private: |
|
1195 BlueMap& operator=(const BlueMap& cmap) { |
|
1196 return operator=<BlueMap>(cmap); |
|
1197 } |
|
1198 |
|
1199 template <typename CMap> |
|
1200 BlueMap& operator=(const CMap& cmap) { |
|
1201 Parent::operator=(cmap); |
|
1202 return *this; |
|
1203 } |
|
1204 |
|
1205 }; |
|
1206 |
|
1207 template <typename _Value> |
|
1208 class ArcMap |
|
1209 : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > { |
|
1210 typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent; |
|
1211 |
|
1212 public: |
|
1213 explicit ArcMap(const BpGraph& graph) |
|
1214 : Parent(graph) {} |
|
1215 ArcMap(const BpGraph& graph, const _Value& value) |
|
1216 : Parent(graph, value) {} |
|
1217 |
|
1218 private: |
|
1219 ArcMap& operator=(const ArcMap& cmap) { |
|
1220 return operator=<ArcMap>(cmap); |
|
1221 } |
|
1222 |
|
1223 template <typename CMap> |
|
1224 ArcMap& operator=(const CMap& cmap) { |
|
1225 Parent::operator=(cmap); |
|
1226 return *this; |
|
1227 } |
|
1228 }; |
|
1229 |
|
1230 |
|
1231 template <typename _Value> |
|
1232 class EdgeMap |
|
1233 : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > { |
|
1234 typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent; |
|
1235 |
|
1236 public: |
|
1237 explicit EdgeMap(const BpGraph& graph) |
|
1238 : Parent(graph) {} |
|
1239 |
|
1240 EdgeMap(const BpGraph& graph, const _Value& value) |
|
1241 : Parent(graph, value) {} |
|
1242 |
|
1243 private: |
|
1244 EdgeMap& operator=(const EdgeMap& cmap) { |
|
1245 return operator=<EdgeMap>(cmap); |
|
1246 } |
|
1247 |
|
1248 template <typename CMap> |
|
1249 EdgeMap& operator=(const CMap& cmap) { |
|
1250 Parent::operator=(cmap); |
|
1251 return *this; |
|
1252 } |
|
1253 |
|
1254 }; |
|
1255 |
|
1256 // Alteration extension |
|
1257 |
|
1258 Node addRedNode() { |
|
1259 Node node = Parent::addRedNode(); |
|
1260 notifier(RedNode()).add(node); |
|
1261 notifier(Node()).add(node); |
|
1262 return node; |
|
1263 } |
|
1264 |
|
1265 Node addBlueNode() { |
|
1266 Node node = Parent::addBlueNode(); |
|
1267 notifier(BlueNode()).add(node); |
|
1268 notifier(Node()).add(node); |
|
1269 return node; |
|
1270 } |
|
1271 |
|
1272 Edge addEdge(const Node& from, const Node& to) { |
|
1273 Edge edge = Parent::addEdge(from, to); |
|
1274 notifier(Edge()).add(edge); |
|
1275 std::vector<Arc> av; |
|
1276 av.push_back(Parent::direct(edge, true)); |
|
1277 av.push_back(Parent::direct(edge, false)); |
|
1278 notifier(Arc()).add(av); |
|
1279 return edge; |
|
1280 } |
|
1281 |
|
1282 void clear() { |
|
1283 notifier(Arc()).clear(); |
|
1284 notifier(Edge()).clear(); |
|
1285 notifier(Node()).clear(); |
|
1286 notifier(BlueNode()).clear(); |
|
1287 notifier(RedNode()).clear(); |
|
1288 Parent::clear(); |
|
1289 } |
|
1290 |
|
1291 template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap> |
|
1292 void build(const BpGraph& graph, NodeRefMap& nodeRef, |
|
1293 EdgeRefMap& edgeRef) { |
|
1294 Parent::build(graph, nodeRef, edgeRef); |
|
1295 notifier(RedNode()).build(); |
|
1296 notifier(BlueNode()).build(); |
|
1297 notifier(Node()).build(); |
|
1298 notifier(Edge()).build(); |
|
1299 notifier(Arc()).build(); |
|
1300 } |
|
1301 |
|
1302 void erase(const Node& node) { |
|
1303 Arc arc; |
|
1304 Parent::firstOut(arc, node); |
|
1305 while (arc != INVALID ) { |
|
1306 erase(arc); |
|
1307 Parent::firstOut(arc, node); |
|
1308 } |
|
1309 |
|
1310 Parent::firstIn(arc, node); |
|
1311 while (arc != INVALID ) { |
|
1312 erase(arc); |
|
1313 Parent::firstIn(arc, node); |
|
1314 } |
|
1315 |
|
1316 if (Parent::red(node)) { |
|
1317 notifier(RedNode()).erase(node); |
|
1318 } else { |
|
1319 notifier(BlueNode()).erase(node); |
|
1320 } |
|
1321 |
|
1322 notifier(Node()).erase(node); |
|
1323 Parent::erase(node); |
|
1324 } |
|
1325 |
|
1326 void erase(const Edge& edge) { |
|
1327 std::vector<Arc> av; |
|
1328 av.push_back(Parent::direct(edge, true)); |
|
1329 av.push_back(Parent::direct(edge, false)); |
|
1330 notifier(Arc()).erase(av); |
|
1331 notifier(Edge()).erase(edge); |
|
1332 Parent::erase(edge); |
|
1333 } |
|
1334 |
|
1335 BpGraphExtender() { |
|
1336 red_node_notifier.setContainer(*this); |
|
1337 blue_node_notifier.setContainer(*this); |
|
1338 node_notifier.setContainer(*this); |
|
1339 arc_notifier.setContainer(*this); |
|
1340 edge_notifier.setContainer(*this); |
|
1341 } |
|
1342 |
|
1343 ~BpGraphExtender() { |
|
1344 edge_notifier.clear(); |
|
1345 arc_notifier.clear(); |
|
1346 node_notifier.clear(); |
|
1347 blue_node_notifier.clear(); |
|
1348 red_node_notifier.clear(); |
|
1349 } |
|
1350 |
|
1351 }; |
|
1352 |
749 } |
1353 } |
750 |
1354 |
751 #endif |
1355 #endif |