758 typedef BpGraphExtender BpGraph; |
758 typedef BpGraphExtender BpGraph; |
759 |
759 |
760 typedef True UndirectedTag; |
760 typedef True UndirectedTag; |
761 |
761 |
762 typedef typename Parent::Node Node; |
762 typedef typename Parent::Node Node; |
|
763 typedef typename Parent::RedNode RedNode; |
|
764 typedef typename Parent::BlueNode BlueNode; |
763 typedef typename Parent::Arc Arc; |
765 typedef typename Parent::Arc Arc; |
764 typedef typename Parent::Edge Edge; |
766 typedef typename Parent::Edge Edge; |
765 |
767 |
766 // BpGraph extension |
768 // BpGraph extension |
767 |
769 |
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; |
770 using Parent::first; |
784 using Parent::next; |
771 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; |
772 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 |
773 |
812 int maxId(Node) const { |
774 int maxId(Node) const { |
813 return Parent::maxNodeId(); |
775 return Parent::maxNodeId(); |
814 } |
776 } |
815 |
777 |
860 using Parent::direct; |
822 using Parent::direct; |
861 Arc direct(const Edge &edge, const Node &node) const { |
823 Arc direct(const Edge &edge, const Node &node) const { |
862 return Parent::direct(edge, Parent::redNode(edge) == node); |
824 return Parent::direct(edge, Parent::redNode(edge) == node); |
863 } |
825 } |
864 |
826 |
|
827 RedNode asRedNode(const Node& node) const { |
|
828 if (node == INVALID || Parent::blue(node)) { |
|
829 return INVALID; |
|
830 } else { |
|
831 return Parent::asRedNodeUnsafe(node); |
|
832 } |
|
833 } |
|
834 |
|
835 BlueNode asBlueNode(const Node& node) const { |
|
836 if (node == INVALID || Parent::red(node)) { |
|
837 return INVALID; |
|
838 } else { |
|
839 return Parent::asBlueNodeUnsafe(node); |
|
840 } |
|
841 } |
|
842 |
|
843 std::pair<RedNode, BlueNode> asRedBlueNode(const Node& node) const { |
|
844 if (node == INVALID) { |
|
845 return std::make_pair(RedNode(INVALID), BlueNode(INVALID)); |
|
846 } else if (Parent::red(node)) { |
|
847 return std::make_pair(Parent::asRedNodeUnsafe(node), BlueNode(INVALID)); |
|
848 } else { |
|
849 return std::make_pair(RedNode(INVALID), Parent::asBlueNodeUnsafe(node)); |
|
850 } |
|
851 } |
|
852 |
865 // Alterable extension |
853 // Alterable extension |
866 |
854 |
867 typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier; |
855 typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier; |
868 typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier; |
856 typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier; |
869 typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier; |
857 typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier; |
923 return *this; |
911 return *this; |
924 } |
912 } |
925 |
913 |
926 }; |
914 }; |
927 |
915 |
928 class RedIt : public Node { |
916 class RedIt : public RedNode { |
929 const BpGraph* _graph; |
917 const BpGraph* _graph; |
930 public: |
918 public: |
931 |
919 |
932 RedIt() {} |
920 RedIt() {} |
933 |
921 |
934 RedIt(Invalid i) : Node(i) { } |
922 RedIt(Invalid i) : RedNode(i) { } |
935 |
923 |
936 explicit RedIt(const BpGraph& graph) : _graph(&graph) { |
924 explicit RedIt(const BpGraph& graph) : _graph(&graph) { |
937 _graph->firstRed(static_cast<Node&>(*this)); |
925 _graph->first(static_cast<RedNode&>(*this)); |
938 } |
926 } |
939 |
927 |
940 RedIt(const BpGraph& graph, const Node& node) |
928 RedIt(const BpGraph& graph, const RedNode& node) |
941 : Node(node), _graph(&graph) { |
929 : RedNode(node), _graph(&graph) {} |
942 LEMON_DEBUG(_graph->red(node), "Node has to be red."); |
|
943 } |
|
944 |
930 |
945 RedIt& operator++() { |
931 RedIt& operator++() { |
946 _graph->nextRed(*this); |
932 _graph->next(static_cast<RedNode&>(*this)); |
947 return *this; |
933 return *this; |
948 } |
934 } |
949 |
935 |
950 }; |
936 }; |
951 |
937 |
952 class BlueIt : public Node { |
938 class BlueIt : public BlueNode { |
953 const BpGraph* _graph; |
939 const BpGraph* _graph; |
954 public: |
940 public: |
955 |
941 |
956 BlueIt() {} |
942 BlueIt() {} |
957 |
943 |
958 BlueIt(Invalid i) : Node(i) { } |
944 BlueIt(Invalid i) : BlueNode(i) { } |
959 |
945 |
960 explicit BlueIt(const BpGraph& graph) : _graph(&graph) { |
946 explicit BlueIt(const BpGraph& graph) : _graph(&graph) { |
961 _graph->firstBlue(static_cast<Node&>(*this)); |
947 _graph->first(static_cast<BlueNode&>(*this)); |
962 } |
948 } |
963 |
949 |
964 BlueIt(const BpGraph& graph, const Node& node) |
950 BlueIt(const BpGraph& graph, const BlueNode& node) |
965 : Node(node), _graph(&graph) { |
951 : BlueNode(node), _graph(&graph) {} |
966 LEMON_DEBUG(_graph->blue(node), "Node has to be blue."); |
|
967 } |
|
968 |
952 |
969 BlueIt& operator++() { |
953 BlueIt& operator++() { |
970 _graph->nextBlue(*this); |
954 _graph->next(static_cast<BlueNode&>(*this)); |
971 return *this; |
955 return *this; |
972 } |
956 } |
973 |
957 |
974 }; |
958 }; |
975 |
959 |
1256 |
1240 |
1257 }; |
1241 }; |
1258 |
1242 |
1259 // Alteration extension |
1243 // Alteration extension |
1260 |
1244 |
1261 Node addRedNode() { |
1245 RedNode addRedNode() { |
1262 Node node = Parent::addRedNode(); |
1246 RedNode node = Parent::addRedNode(); |
1263 notifier(RedNode()).add(node); |
1247 notifier(RedNode()).add(node); |
1264 notifier(Node()).add(node); |
1248 notifier(Node()).add(node); |
1265 return node; |
1249 return node; |
1266 } |
1250 } |
1267 |
1251 |
1268 Node addBlueNode() { |
1252 BlueNode addBlueNode() { |
1269 Node node = Parent::addBlueNode(); |
1253 BlueNode node = Parent::addBlueNode(); |
1270 notifier(BlueNode()).add(node); |
1254 notifier(BlueNode()).add(node); |
1271 notifier(Node()).add(node); |
1255 notifier(Node()).add(node); |
1272 return node; |
1256 return node; |
1273 } |
1257 } |
1274 |
1258 |
1275 Edge addEdge(const Node& from, const Node& to) { |
1259 Edge addEdge(const RedNode& from, const BlueNode& to) { |
1276 Edge edge = Parent::addEdge(from, to); |
1260 Edge edge = Parent::addEdge(from, to); |
1277 notifier(Edge()).add(edge); |
1261 notifier(Edge()).add(edge); |
1278 std::vector<Arc> av; |
1262 std::vector<Arc> av; |
1279 av.push_back(Parent::direct(edge, true)); |
1263 av.push_back(Parent::direct(edge, true)); |
1280 av.push_back(Parent::direct(edge, false)); |
1264 av.push_back(Parent::direct(edge, false)); |
1315 erase(arc); |
1299 erase(arc); |
1316 Parent::firstIn(arc, node); |
1300 Parent::firstIn(arc, node); |
1317 } |
1301 } |
1318 |
1302 |
1319 if (Parent::red(node)) { |
1303 if (Parent::red(node)) { |
1320 notifier(RedNode()).erase(node); |
1304 notifier(RedNode()).erase(this->asRedNodeUnsafe(node)); |
1321 } else { |
1305 } else { |
1322 notifier(BlueNode()).erase(node); |
1306 notifier(BlueNode()).erase(this->asBlueNodeUnsafe(node)); |
1323 } |
1307 } |
1324 |
1308 |
1325 notifier(Node()).erase(node); |
1309 notifier(Node()).erase(node); |
1326 Parent::erase(node); |
1310 Parent::erase(node); |
1327 } |
1311 } |