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