1010 }; |
1010 }; |
1011 |
1011 |
1012 |
1012 |
1013 |
1013 |
1014 |
1014 |
1015 // ///\brief A wrapper for composing bidirected graph from a directed one. |
1015 template<typename Graph> |
1016 // /// experimental, for fezso's sake. |
1016 class OldBidirGraphWrapper : public GraphWrapper<Graph> { |
1017 // /// |
1017 public: |
1018 // /// A wrapper for composing bidirected graph from a directed one. |
1018 typedef GraphWrapper<Graph> Parent; |
1019 // /// experimental, for fezso's sake. |
1019 protected: |
1020 // /// A bidirected graph is composed over the directed one without physical |
1020 //const CapacityMap* capacity; |
1021 // /// storage. As the oppositely directed edges are logically different ones |
1021 //FlowMap* flow; |
1022 // /// the maps are able to attach different values for them. |
1022 |
1023 // template<typename Graph> |
1023 OldBidirGraphWrapper() : GraphWrapper<Graph>()/*, |
1024 // class BidirGraphWrapper : public GraphWrapper<Graph> { |
1024 capacity(0), flow(0)*/ { } |
1025 // public: |
1025 // void setCapacityMap(const CapacityMap& _capacity) { |
1026 // typedef GraphWrapper<Graph> Parent; |
1026 // capacity=&_capacity; |
1027 // protected: |
1027 // } |
1028 // //const CapacityMap* capacity; |
1028 // void setFlowMap(FlowMap& _flow) { |
1029 // //FlowMap* flow; |
1029 // flow=&_flow; |
1030 |
1030 // } |
1031 // BidirGraphWrapper() : GraphWrapper<Graph>()/*, |
1031 |
1032 // capacity(0), flow(0)*/ { } |
1032 public: |
1033 // // void setCapacityMap(const CapacityMap& _capacity) { |
1033 |
1034 // // capacity=&_capacity; |
1034 OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, |
1035 // // } |
1035 FlowMap& _flow*/) : |
1036 // // void setFlowMap(FlowMap& _flow) { |
1036 GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { } |
1037 // // flow=&_flow; |
1037 |
1038 // // } |
1038 class Edge; |
1039 |
1039 class OutEdgeIt; |
1040 // public: |
1040 friend class Edge; |
1041 |
1041 friend class OutEdgeIt; |
1042 // BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, |
1042 |
1043 // FlowMap& _flow*/) : |
1043 //template<typename T> class NodeMap; |
1044 // GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { } |
1044 template<typename T> class EdgeMap; |
1045 |
1045 |
1046 // class Edge; |
1046 typedef typename GraphWrapper<Graph>::Node Node; |
1047 // class OutEdgeIt; |
1047 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
1048 // friend class Edge; |
1048 |
1049 // friend class OutEdgeIt; |
1049 class Edge : public Graph::Edge { |
1050 |
1050 friend class OldBidirGraphWrapper<Graph>; |
1051 // //template<typename T> class NodeMap; |
1051 ///\bug ez nem is kell |
1052 // template<typename T> class EdgeMap; |
1052 //template<typename T> friend class NodeMap; |
1053 |
1053 template<typename T> friend class EdgeMap; |
1054 // typedef typename GraphWrapper<Graph>::Node Node; |
1054 protected: |
1055 // typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
1055 bool backward; //true, iff backward |
1056 |
1056 // typename Graph::Edge e; |
1057 // class Edge : public Graph::Edge { |
1057 public: |
1058 // friend class BidirGraphWrapper<Graph>; |
1058 Edge() { } |
1059 // ///\bug ez nem is kell |
1059 ///\bug =false kell-e? zsoltnak kell az addEdge miatt |
1060 // //template<typename T> friend class NodeMap; |
1060 Edge(const typename Graph::Edge& _e, bool _backward=false) : |
1061 // template<typename T> friend class EdgeMap; |
1061 Graph::Edge(_e), backward(_backward) { } |
1062 // protected: |
1062 Edge(const Invalid& i) : Graph::Edge(i), backward(true) { } |
1063 // bool backward; //true, iff backward |
1063 //the unique invalid iterator |
1064 // // typename Graph::Edge e; |
1064 friend bool operator==(const Edge& u, const Edge& v) { |
1065 // public: |
1065 return (v.backward==u.backward && |
1066 // Edge() { } |
1066 static_cast<typename Graph::Edge>(u)== |
1067 // ///\bug =false kell-e? zsoltnak kell az addEdge miatt |
1067 static_cast<typename Graph::Edge>(v)); |
1068 // Edge(const typename Graph::Edge& _e, bool _backward=false) : |
1068 } |
1069 // Graph::Edge(_e), backward(_backward) { } |
1069 friend bool operator!=(const Edge& u, const Edge& v) { |
1070 // Edge(const Invalid& i) : Graph::Edge(i), backward(true) { } |
1070 return (v.backward!=u.backward || |
1071 // //the unique invalid iterator |
1071 static_cast<typename Graph::Edge>(u)!= |
1072 // friend bool operator==(const Edge& u, const Edge& v) { |
1072 static_cast<typename Graph::Edge>(v)); |
1073 // return (v.backward==u.backward && |
1073 } |
1074 // static_cast<typename Graph::Edge>(u)== |
1074 }; |
1075 // static_cast<typename Graph::Edge>(v)); |
1075 |
1076 // } |
1076 class OutEdgeIt { |
1077 // friend bool operator!=(const Edge& u, const Edge& v) { |
1077 friend class OldBidirGraphWrapper<Graph>; |
1078 // return (v.backward!=u.backward || |
1078 protected: |
1079 // static_cast<typename Graph::Edge>(u)!= |
1079 typename Graph::OutEdgeIt out; |
1080 // static_cast<typename Graph::Edge>(v)); |
1080 typename Graph::InEdgeIt in; |
1081 // } |
1081 bool backward; |
1082 // }; |
1082 public: |
1083 |
1083 OutEdgeIt() { } |
1084 // class OutEdgeIt { |
1084 //FIXME |
1085 // friend class BidirGraphWrapper<Graph>; |
1085 // OutEdgeIt(const Edge& e) : Edge(e) { } |
1086 // protected: |
1086 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } |
1087 // typename Graph::OutEdgeIt out; |
1087 //the unique invalid iterator |
1088 // typename Graph::InEdgeIt in; |
1088 OutEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) { |
1089 // bool backward; |
1089 backward=false; |
1090 // public: |
1090 _G.graph->first(out, v); |
1091 // OutEdgeIt() { } |
1091 while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); } |
1092 // //FIXME |
1092 if (!_G.graph->valid(out)) { |
1093 // // OutEdgeIt(const Edge& e) : Edge(e) { } |
1093 backward=true; |
1094 // OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } |
1094 _G.graph->first(in, v); |
1095 // //the unique invalid iterator |
1095 while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); } |
1096 // OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { |
1096 } |
1097 // backward=false; |
1097 } |
1098 // _G.graph->first(out, v); |
1098 operator Edge() const { |
1099 // while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); } |
1099 // Edge e; |
1100 // if (!_G.graph->valid(out)) { |
1100 // e.forward=this->forward; |
1101 // backward=true; |
1101 // if (this->forward) e=out; else e=in; |
1102 // _G.graph->first(in, v); |
1102 // return e; |
1103 // while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); } |
1103 if (this->backward) |
1104 // } |
1104 return Edge(in, this->backward); |
|
1105 else |
|
1106 return Edge(out, this->backward); |
|
1107 } |
|
1108 }; |
|
1109 |
|
1110 class InEdgeIt { |
|
1111 friend class OldBidirGraphWrapper<Graph>; |
|
1112 protected: |
|
1113 typename Graph::OutEdgeIt out; |
|
1114 typename Graph::InEdgeIt in; |
|
1115 bool backward; |
|
1116 public: |
|
1117 InEdgeIt() { } |
|
1118 //FIXME |
|
1119 // OutEdgeIt(const Edge& e) : Edge(e) { } |
|
1120 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } |
|
1121 //the unique invalid iterator |
|
1122 InEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) { |
|
1123 backward=false; |
|
1124 _G.graph->first(in, v); |
|
1125 while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); } |
|
1126 if (!_G.graph->valid(in)) { |
|
1127 backward=true; |
|
1128 _G.graph->first(out, v); |
|
1129 while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); } |
|
1130 } |
|
1131 } |
|
1132 operator Edge() const { |
|
1133 // Edge e; |
|
1134 // e.forward=this->forward; |
|
1135 // if (this->forward) e=out; else e=in; |
|
1136 // return e; |
|
1137 if (this->backward) |
|
1138 return Edge(out, this->backward); |
|
1139 else |
|
1140 return Edge(in, this->backward); |
|
1141 } |
|
1142 }; |
|
1143 |
|
1144 class EdgeIt { |
|
1145 friend class OldBidirGraphWrapper<Graph>; |
|
1146 protected: |
|
1147 typename Graph::EdgeIt e; |
|
1148 bool backward; |
|
1149 public: |
|
1150 EdgeIt() { } |
|
1151 EdgeIt(const Invalid& i) : e(i), backward(true) { } |
|
1152 EdgeIt(const OldBidirGraphWrapper<Graph>& _G) { |
|
1153 backward=false; |
|
1154 _G.graph->first(e); |
|
1155 while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e); |
|
1156 if (!_G.graph->valid(e)) { |
|
1157 backward=true; |
|
1158 _G.graph->first(e); |
|
1159 while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e); |
|
1160 } |
|
1161 } |
|
1162 operator Edge() const { |
|
1163 return Edge(e, this->backward); |
|
1164 } |
|
1165 }; |
|
1166 |
|
1167 using GraphWrapper<Graph>::first; |
|
1168 // NodeIt& first(NodeIt& i) const { |
|
1169 // i=NodeIt(*this); return i; |
|
1170 // } |
|
1171 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
1172 i=OutEdgeIt(*this, p); return i; |
|
1173 } |
|
1174 // FIXME not tested |
|
1175 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
1176 i=InEdgeIt(*this, p); return i; |
|
1177 } |
|
1178 EdgeIt& first(EdgeIt& i) const { |
|
1179 i=EdgeIt(*this); return i; |
|
1180 } |
|
1181 |
|
1182 using GraphWrapper<Graph>::next; |
|
1183 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; } |
|
1184 OutEdgeIt& next(OutEdgeIt& e) const { |
|
1185 if (!e.backward) { |
|
1186 Node v=this->graph->aNode(e.out); |
|
1187 this->graph->next(e.out); |
|
1188 while(this->graph->valid(e.out) && !enabled(e)) { |
|
1189 this->graph->next(e.out); } |
|
1190 if (!this->graph->valid(e.out)) { |
|
1191 e.backward=true; |
|
1192 this->graph->first(e.in, v); |
|
1193 while(this->graph->valid(e.in) && !enabled(e)) { |
|
1194 this->graph->next(e.in); } |
|
1195 } |
|
1196 } else { |
|
1197 this->graph->next(e.in); |
|
1198 while(this->graph->valid(e.in) && !enabled(e)) { |
|
1199 this->graph->next(e.in); } |
|
1200 } |
|
1201 return e; |
|
1202 } |
|
1203 // FIXME Not tested |
|
1204 InEdgeIt& next(InEdgeIt& e) const { |
|
1205 if (!e.backward) { |
|
1206 Node v=this->graph->aNode(e.in); |
|
1207 this->graph->next(e.in); |
|
1208 while(this->graph->valid(e.in) && !enabled(e)) { |
|
1209 this->graph->next(e.in); } |
|
1210 if (!this->graph->valid(e.in)) { |
|
1211 e.backward=true; |
|
1212 this->graph->first(e.out, v); |
|
1213 while(this->graph->valid(e.out) && !enabled(e)) { |
|
1214 this->graph->next(e.out); } |
|
1215 } |
|
1216 } else { |
|
1217 this->graph->next(e.out); |
|
1218 while(this->graph->valid(e.out) && !enabled(e)) { |
|
1219 this->graph->next(e.out); } |
|
1220 } |
|
1221 return e; |
|
1222 } |
|
1223 EdgeIt& next(EdgeIt& e) const { |
|
1224 if (!e.backward) { |
|
1225 this->graph->next(e.e); |
|
1226 while(this->graph->valid(e.e) && !enabled(e)) { |
|
1227 this->graph->next(e.e); } |
|
1228 if (!this->graph->valid(e.e)) { |
|
1229 e.backward=true; |
|
1230 this->graph->first(e.e); |
|
1231 while(this->graph->valid(e.e) && !enabled(e)) { |
|
1232 this->graph->next(e.e); } |
|
1233 } |
|
1234 } else { |
|
1235 this->graph->next(e.e); |
|
1236 while(this->graph->valid(e.e) && !enabled(e)) { |
|
1237 this->graph->next(e.e); } |
|
1238 } |
|
1239 return e; |
|
1240 } |
|
1241 |
|
1242 Node tail(Edge e) const { |
|
1243 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); } |
|
1244 Node head(Edge e) const { |
|
1245 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); } |
|
1246 |
|
1247 Node aNode(OutEdgeIt e) const { |
|
1248 return ((!e.backward) ? this->graph->aNode(e.out) : |
|
1249 this->graph->aNode(e.in)); } |
|
1250 Node bNode(OutEdgeIt e) const { |
|
1251 return ((!e.backward) ? this->graph->bNode(e.out) : |
|
1252 this->graph->bNode(e.in)); } |
|
1253 |
|
1254 Node aNode(InEdgeIt e) const { |
|
1255 return ((!e.backward) ? this->graph->aNode(e.in) : |
|
1256 this->graph->aNode(e.out)); } |
|
1257 Node bNode(InEdgeIt e) const { |
|
1258 return ((!e.backward) ? this->graph->bNode(e.in) : |
|
1259 this->graph->bNode(e.out)); } |
|
1260 |
|
1261 /// Gives back the opposite edge. |
|
1262 Edge opposite(const Edge& e) const { |
|
1263 Edge f=e; |
|
1264 f.backward=!f.backward; |
|
1265 return f; |
|
1266 } |
|
1267 |
|
1268 // int nodeNum() const { return graph->nodeNum(); } |
|
1269 //FIXME |
|
1270 void edgeNum() const { } |
|
1271 //int edgeNum() const { return graph->edgeNum(); } |
|
1272 |
|
1273 |
|
1274 // int id(Node v) const { return graph->id(v); } |
|
1275 |
|
1276 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); } |
|
1277 bool valid(Edge e) const { |
|
1278 return this->graph->valid(e); |
|
1279 //return e.forward ? graph->valid(e.out) : graph->valid(e.in); |
|
1280 } |
|
1281 |
|
1282 bool forward(const Edge& e) const { return !e.backward; } |
|
1283 bool backward(const Edge& e) const { return e.backward; } |
|
1284 |
|
1285 // void augment(const Edge& e, Number a) const { |
|
1286 // if (!e.backward) |
|
1287 // // flow->set(e.out, flow->get(e.out)+a); |
|
1288 // flow->set(e, (*flow)[e]+a); |
|
1289 // else |
|
1290 // // flow->set(e.in, flow->get(e.in)-a); |
|
1291 // flow->set(e, (*flow)[e]-a); |
|
1292 // } |
|
1293 |
|
1294 bool enabled(const Edge& e) const { |
|
1295 if (!e.backward) |
|
1296 // return (capacity->get(e.out)-flow->get(e.out)); |
|
1297 //return ((*capacity)[e]-(*flow)[e]); |
|
1298 return true; |
|
1299 else |
|
1300 // return (flow->get(e.in)); |
|
1301 //return ((*flow)[e]); |
|
1302 return true; |
|
1303 } |
|
1304 |
|
1305 // Number enabled(typename Graph::OutEdgeIt out) const { |
|
1306 // // return (capacity->get(out)-flow->get(out)); |
|
1307 // return ((*capacity)[out]-(*flow)[out]); |
|
1308 // } |
|
1309 |
|
1310 // Number enabled(typename Graph::InEdgeIt in) const { |
|
1311 // // return (flow->get(in)); |
|
1312 // return ((*flow)[in]); |
|
1313 // } |
|
1314 |
|
1315 template <typename T> |
|
1316 class EdgeMap { |
|
1317 typename Graph::template EdgeMap<T> forward_map, backward_map; |
|
1318 public: |
|
1319 typedef T ValueType; |
|
1320 typedef Edge KeyType; |
|
1321 EdgeMap(const OldBidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } |
|
1322 EdgeMap(const OldBidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } |
|
1323 void set(Edge e, T a) { |
|
1324 if (!e.backward) |
|
1325 forward_map.set(e/*.out*/, a); |
|
1326 else |
|
1327 backward_map.set(e/*.in*/, a); |
|
1328 } |
|
1329 T operator[](Edge e) const { |
|
1330 if (!e.backward) |
|
1331 return forward_map[e/*.out*/]; |
|
1332 else |
|
1333 return backward_map[e/*.in*/]; |
|
1334 } |
|
1335 void update() { |
|
1336 forward_map.update(); |
|
1337 backward_map.update(); |
|
1338 } |
|
1339 // T get(Edge e) const { |
|
1340 // if (e.out_or_in) |
|
1341 // return forward_map.get(e.out); |
|
1342 // else |
|
1343 // return backward_map.get(e.in); |
1105 // } |
1344 // } |
1106 // operator Edge() const { |
1345 }; |
1107 // // Edge e; |
1346 }; |
1108 // // e.forward=this->forward; |
1347 |
1109 // // if (this->forward) e=out; else e=in; |
1348 |
1110 // // return e; |
|
1111 // if (this->backward) |
|
1112 // return Edge(in, this->backward); |
|
1113 // else |
|
1114 // return Edge(out, this->backward); |
|
1115 // } |
|
1116 // }; |
|
1117 |
|
1118 // class InEdgeIt { |
|
1119 // friend class BidirGraphWrapper<Graph>; |
|
1120 // protected: |
|
1121 // typename Graph::OutEdgeIt out; |
|
1122 // typename Graph::InEdgeIt in; |
|
1123 // bool backward; |
|
1124 // public: |
|
1125 // InEdgeIt() { } |
|
1126 // //FIXME |
|
1127 // // OutEdgeIt(const Edge& e) : Edge(e) { } |
|
1128 // InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } |
|
1129 // //the unique invalid iterator |
|
1130 // InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { |
|
1131 // backward=false; |
|
1132 // _G.graph->first(in, v); |
|
1133 // while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); } |
|
1134 // if (!_G.graph->valid(in)) { |
|
1135 // backward=true; |
|
1136 // _G.graph->first(out, v); |
|
1137 // while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); } |
|
1138 // } |
|
1139 // } |
|
1140 // operator Edge() const { |
|
1141 // // Edge e; |
|
1142 // // e.forward=this->forward; |
|
1143 // // if (this->forward) e=out; else e=in; |
|
1144 // // return e; |
|
1145 // if (this->backward) |
|
1146 // return Edge(out, this->backward); |
|
1147 // else |
|
1148 // return Edge(in, this->backward); |
|
1149 // } |
|
1150 // }; |
|
1151 |
|
1152 // class EdgeIt { |
|
1153 // friend class BidirGraphWrapper<Graph>; |
|
1154 // protected: |
|
1155 // typename Graph::EdgeIt e; |
|
1156 // bool backward; |
|
1157 // public: |
|
1158 // EdgeIt() { } |
|
1159 // EdgeIt(const Invalid& i) : e(i), backward(true) { } |
|
1160 // EdgeIt(const BidirGraphWrapper<Graph>& _G) { |
|
1161 // backward=false; |
|
1162 // _G.graph->first(e); |
|
1163 // while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e); |
|
1164 // if (!_G.graph->valid(e)) { |
|
1165 // backward=true; |
|
1166 // _G.graph->first(e); |
|
1167 // while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e); |
|
1168 // } |
|
1169 // } |
|
1170 // operator Edge() const { |
|
1171 // return Edge(e, this->backward); |
|
1172 // } |
|
1173 // }; |
|
1174 |
|
1175 // using GraphWrapper<Graph>::first; |
|
1176 // // NodeIt& first(NodeIt& i) const { |
|
1177 // // i=NodeIt(*this); return i; |
|
1178 // // } |
|
1179 // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
1180 // i=OutEdgeIt(*this, p); return i; |
|
1181 // } |
|
1182 // // FIXME not tested |
|
1183 // InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
1184 // i=InEdgeIt(*this, p); return i; |
|
1185 // } |
|
1186 // EdgeIt& first(EdgeIt& i) const { |
|
1187 // i=EdgeIt(*this); return i; |
|
1188 // } |
|
1189 |
|
1190 // using GraphWrapper<Graph>::next; |
|
1191 // // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; } |
|
1192 // OutEdgeIt& next(OutEdgeIt& e) const { |
|
1193 // if (!e.backward) { |
|
1194 // Node v=this->graph->aNode(e.out); |
|
1195 // this->graph->next(e.out); |
|
1196 // while(this->graph->valid(e.out) && !enabled(e)) { |
|
1197 // this->graph->next(e.out); } |
|
1198 // if (!this->graph->valid(e.out)) { |
|
1199 // e.backward=true; |
|
1200 // this->graph->first(e.in, v); |
|
1201 // while(this->graph->valid(e.in) && !enabled(e)) { |
|
1202 // this->graph->next(e.in); } |
|
1203 // } |
|
1204 // } else { |
|
1205 // this->graph->next(e.in); |
|
1206 // while(this->graph->valid(e.in) && !enabled(e)) { |
|
1207 // this->graph->next(e.in); } |
|
1208 // } |
|
1209 // return e; |
|
1210 // } |
|
1211 // // FIXME Not tested |
|
1212 // InEdgeIt& next(InEdgeIt& e) const { |
|
1213 // if (!e.backward) { |
|
1214 // Node v=this->graph->aNode(e.in); |
|
1215 // this->graph->next(e.in); |
|
1216 // while(this->graph->valid(e.in) && !enabled(e)) { |
|
1217 // this->graph->next(e.in); } |
|
1218 // if (!this->graph->valid(e.in)) { |
|
1219 // e.backward=true; |
|
1220 // this->graph->first(e.out, v); |
|
1221 // while(this->graph->valid(e.out) && !enabled(e)) { |
|
1222 // this->graph->next(e.out); } |
|
1223 // } |
|
1224 // } else { |
|
1225 // this->graph->next(e.out); |
|
1226 // while(this->graph->valid(e.out) && !enabled(e)) { |
|
1227 // this->graph->next(e.out); } |
|
1228 // } |
|
1229 // return e; |
|
1230 // } |
|
1231 // EdgeIt& next(EdgeIt& e) const { |
|
1232 // if (!e.backward) { |
|
1233 // this->graph->next(e.e); |
|
1234 // while(this->graph->valid(e.e) && !enabled(e)) { |
|
1235 // this->graph->next(e.e); } |
|
1236 // if (!this->graph->valid(e.e)) { |
|
1237 // e.backward=true; |
|
1238 // this->graph->first(e.e); |
|
1239 // while(this->graph->valid(e.e) && !enabled(e)) { |
|
1240 // this->graph->next(e.e); } |
|
1241 // } |
|
1242 // } else { |
|
1243 // this->graph->next(e.e); |
|
1244 // while(this->graph->valid(e.e) && !enabled(e)) { |
|
1245 // this->graph->next(e.e); } |
|
1246 // } |
|
1247 // return e; |
|
1248 // } |
|
1249 |
|
1250 // Node tail(Edge e) const { |
|
1251 // return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); } |
|
1252 // Node head(Edge e) const { |
|
1253 // return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); } |
|
1254 |
|
1255 // Node aNode(OutEdgeIt e) const { |
|
1256 // return ((!e.backward) ? this->graph->aNode(e.out) : |
|
1257 // this->graph->aNode(e.in)); } |
|
1258 // Node bNode(OutEdgeIt e) const { |
|
1259 // return ((!e.backward) ? this->graph->bNode(e.out) : |
|
1260 // this->graph->bNode(e.in)); } |
|
1261 |
|
1262 // Node aNode(InEdgeIt e) const { |
|
1263 // return ((!e.backward) ? this->graph->aNode(e.in) : |
|
1264 // this->graph->aNode(e.out)); } |
|
1265 // Node bNode(InEdgeIt e) const { |
|
1266 // return ((!e.backward) ? this->graph->bNode(e.in) : |
|
1267 // this->graph->bNode(e.out)); } |
|
1268 |
|
1269 // /// Gives back the opposite edge. |
|
1270 // Edge opposite(const Edge& e) const { |
|
1271 // Edge f=e; |
|
1272 // f.backward=!f.backward; |
|
1273 // return f; |
|
1274 // } |
|
1275 |
|
1276 // // int nodeNum() const { return graph->nodeNum(); } |
|
1277 // //FIXME |
|
1278 // void edgeNum() const { } |
|
1279 // //int edgeNum() const { return graph->edgeNum(); } |
|
1280 |
|
1281 |
|
1282 // // int id(Node v) const { return graph->id(v); } |
|
1283 |
|
1284 // bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); } |
|
1285 // bool valid(Edge e) const { |
|
1286 // return this->graph->valid(e); |
|
1287 // //return e.forward ? graph->valid(e.out) : graph->valid(e.in); |
|
1288 // } |
|
1289 |
|
1290 // bool forward(const Edge& e) const { return !e.backward; } |
|
1291 // bool backward(const Edge& e) const { return e.backward; } |
|
1292 |
|
1293 // // void augment(const Edge& e, Number a) const { |
|
1294 // // if (!e.backward) |
|
1295 // // // flow->set(e.out, flow->get(e.out)+a); |
|
1296 // // flow->set(e, (*flow)[e]+a); |
|
1297 // // else |
|
1298 // // // flow->set(e.in, flow->get(e.in)-a); |
|
1299 // // flow->set(e, (*flow)[e]-a); |
|
1300 // // } |
|
1301 |
|
1302 // bool enabled(const Edge& e) const { |
|
1303 // if (!e.backward) |
|
1304 // // return (capacity->get(e.out)-flow->get(e.out)); |
|
1305 // //return ((*capacity)[e]-(*flow)[e]); |
|
1306 // return true; |
|
1307 // else |
|
1308 // // return (flow->get(e.in)); |
|
1309 // //return ((*flow)[e]); |
|
1310 // return true; |
|
1311 // } |
|
1312 |
|
1313 // // Number enabled(typename Graph::OutEdgeIt out) const { |
|
1314 // // // return (capacity->get(out)-flow->get(out)); |
|
1315 // // return ((*capacity)[out]-(*flow)[out]); |
|
1316 // // } |
|
1317 |
|
1318 // // Number enabled(typename Graph::InEdgeIt in) const { |
|
1319 // // // return (flow->get(in)); |
|
1320 // // return ((*flow)[in]); |
|
1321 // // } |
|
1322 |
|
1323 // template <typename T> |
|
1324 // class EdgeMap { |
|
1325 // typename Graph::template EdgeMap<T> forward_map, backward_map; |
|
1326 // public: |
|
1327 // typedef T ValueType; |
|
1328 // typedef Edge KeyType; |
|
1329 // EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } |
|
1330 // EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } |
|
1331 // void set(Edge e, T a) { |
|
1332 // if (!e.backward) |
|
1333 // forward_map.set(e/*.out*/, a); |
|
1334 // else |
|
1335 // backward_map.set(e/*.in*/, a); |
|
1336 // } |
|
1337 // T operator[](Edge e) const { |
|
1338 // if (!e.backward) |
|
1339 // return forward_map[e/*.out*/]; |
|
1340 // else |
|
1341 // return backward_map[e/*.in*/]; |
|
1342 // } |
|
1343 // void update() { |
|
1344 // forward_map.update(); |
|
1345 // backward_map.update(); |
|
1346 // } |
|
1347 // // T get(Edge e) const { |
|
1348 // // if (e.out_or_in) |
|
1349 // // return forward_map.get(e.out); |
|
1350 // // else |
|
1351 // // return backward_map.get(e.in); |
|
1352 // // } |
|
1353 // }; |
|
1354 // }; |
|
1355 |
1349 |
1356 /// \brief A bidirected graph template. |
1350 /// \brief A bidirected graph template. |
1357 /// |
1351 /// |
1358 /// A bidirected graph template. |
1352 /// A bidirected graph template. |
1359 /// Such a bidirected graph stores each pair of oppositely directed edges |
1353 /// Such a bidirected graph stores each pair of oppositely directed edges |