Changeset 653:c3ad7c661a49 in lemon0.x for src
 Timestamp:
 05/21/04 10:15:45 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@853
 Location:
 src
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/hugo/graph_wrapper.h
r650 r653 1013 1013 1014 1014 1015 // ///\brief A wrapper for composing bidirected graph from a directed one. 1016 // /// experimental, for fezso's sake. 1017 // /// 1018 // /// A wrapper for composing bidirected graph from a directed one. 1019 // /// experimental, for fezso's sake. 1020 // /// A bidirected graph is composed over the directed one without physical 1021 // /// storage. As the oppositely directed edges are logically different ones 1022 // /// the maps are able to attach different values for them. 1023 // template<typename Graph> 1024 // class BidirGraphWrapper : public GraphWrapper<Graph> { 1025 // public: 1026 // typedef GraphWrapper<Graph> Parent; 1027 // protected: 1028 // //const CapacityMap* capacity; 1029 // //FlowMap* flow; 1030 1031 // BidirGraphWrapper() : GraphWrapper<Graph>()/*, 1032 // capacity(0), flow(0)*/ { } 1033 // // void setCapacityMap(const CapacityMap& _capacity) { 1034 // // capacity=&_capacity; 1035 // // } 1036 // // void setFlowMap(FlowMap& _flow) { 1037 // // flow=&_flow; 1038 // // } 1039 1040 // public: 1041 1042 // BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 1043 // FlowMap& _flow*/) : 1044 // GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { } 1045 1046 // class Edge; 1047 // class OutEdgeIt; 1048 // friend class Edge; 1049 // friend class OutEdgeIt; 1050 1051 // //template<typename T> class NodeMap; 1052 // template<typename T> class EdgeMap; 1053 1054 // typedef typename GraphWrapper<Graph>::Node Node; 1055 // typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 1056 1057 // class Edge : public Graph::Edge { 1058 // friend class BidirGraphWrapper<Graph>; 1059 // ///\bug ez nem is kell 1060 // //template<typename T> friend class NodeMap; 1061 // template<typename T> friend class EdgeMap; 1062 // protected: 1063 // bool backward; //true, iff backward 1064 // // typename Graph::Edge e; 1065 // public: 1066 // Edge() { } 1067 // ///\bug =false kelle? zsoltnak kell az addEdge miatt 1068 // Edge(const typename Graph::Edge& _e, bool _backward=false) : 1069 // Graph::Edge(_e), backward(_backward) { } 1070 // Edge(const Invalid& i) : Graph::Edge(i), backward(true) { } 1071 // //the unique invalid iterator 1072 // friend bool operator==(const Edge& u, const Edge& v) { 1073 // return (v.backward==u.backward && 1074 // static_cast<typename Graph::Edge>(u)== 1075 // static_cast<typename Graph::Edge>(v)); 1076 // } 1077 // friend bool operator!=(const Edge& u, const Edge& v) { 1078 // return (v.backward!=u.backward  1079 // static_cast<typename Graph::Edge>(u)!= 1080 // static_cast<typename Graph::Edge>(v)); 1081 // } 1082 // }; 1083 1084 // class OutEdgeIt { 1085 // friend class BidirGraphWrapper<Graph>; 1086 // protected: 1087 // typename Graph::OutEdgeIt out; 1088 // typename Graph::InEdgeIt in; 1089 // bool backward; 1090 // public: 1091 // OutEdgeIt() { } 1092 // //FIXME 1093 // // OutEdgeIt(const Edge& e) : Edge(e) { } 1094 // OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } 1095 // //the unique invalid iterator 1096 // OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 1097 // backward=false; 1098 // _G.graph>first(out, v); 1099 // while(_G.graph>valid(out) && !_G.enabled(*this)) { _G.graph>next(out); } 1100 // if (!_G.graph>valid(out)) { 1101 // backward=true; 1102 // _G.graph>first(in, v); 1103 // while(_G.graph>valid(in) && !_G.enabled(*this)) { _G.graph>next(in); } 1104 // } 1015 template<typename Graph> 1016 class OldBidirGraphWrapper : public GraphWrapper<Graph> { 1017 public: 1018 typedef GraphWrapper<Graph> Parent; 1019 protected: 1020 //const CapacityMap* capacity; 1021 //FlowMap* flow; 1022 1023 OldBidirGraphWrapper() : GraphWrapper<Graph>()/*, 1024 capacity(0), flow(0)*/ { } 1025 // void setCapacityMap(const CapacityMap& _capacity) { 1026 // capacity=&_capacity; 1027 // } 1028 // void setFlowMap(FlowMap& _flow) { 1029 // flow=&_flow; 1030 // } 1031 1032 public: 1033 1034 OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 1035 FlowMap& _flow*/) : 1036 GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { } 1037 1038 class Edge; 1039 class OutEdgeIt; 1040 friend class Edge; 1041 friend class OutEdgeIt; 1042 1043 //template<typename T> class NodeMap; 1044 template<typename T> class EdgeMap; 1045 1046 typedef typename GraphWrapper<Graph>::Node Node; 1047 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 1048 1049 class Edge : public Graph::Edge { 1050 friend class OldBidirGraphWrapper<Graph>; 1051 ///\bug ez nem is kell 1052 //template<typename T> friend class NodeMap; 1053 template<typename T> friend class EdgeMap; 1054 protected: 1055 bool backward; //true, iff backward 1056 // typename Graph::Edge e; 1057 public: 1058 Edge() { } 1059 ///\bug =false kelle? zsoltnak kell az addEdge miatt 1060 Edge(const typename Graph::Edge& _e, bool _backward=false) : 1061 Graph::Edge(_e), backward(_backward) { } 1062 Edge(const Invalid& i) : Graph::Edge(i), backward(true) { } 1063 //the unique invalid iterator 1064 friend bool operator==(const Edge& u, const Edge& v) { 1065 return (v.backward==u.backward && 1066 static_cast<typename Graph::Edge>(u)== 1067 static_cast<typename Graph::Edge>(v)); 1068 } 1069 friend bool operator!=(const Edge& u, const Edge& v) { 1070 return (v.backward!=u.backward  1071 static_cast<typename Graph::Edge>(u)!= 1072 static_cast<typename Graph::Edge>(v)); 1073 } 1074 }; 1075 1076 class OutEdgeIt { 1077 friend class OldBidirGraphWrapper<Graph>; 1078 protected: 1079 typename Graph::OutEdgeIt out; 1080 typename Graph::InEdgeIt in; 1081 bool backward; 1082 public: 1083 OutEdgeIt() { } 1084 //FIXME 1085 // OutEdgeIt(const Edge& e) : Edge(e) { } 1086 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } 1087 //the unique invalid iterator 1088 OutEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) { 1089 backward=false; 1090 _G.graph>first(out, v); 1091 while(_G.graph>valid(out) && !_G.enabled(*this)) { _G.graph>next(out); } 1092 if (!_G.graph>valid(out)) { 1093 backward=true; 1094 _G.graph>first(in, v); 1095 while(_G.graph>valid(in) && !_G.enabled(*this)) { _G.graph>next(in); } 1096 } 1097 } 1098 operator Edge() const { 1099 // Edge e; 1100 // e.forward=this>forward; 1101 // if (this>forward) e=out; else e=in; 1102 // return e; 1103 if (this>backward) 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 { 1107 // // Edge e; 1108 // // e.forward=this>forward; 1109 // // if (this>forward) e=out; else e=in; 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 // }; 1345 }; 1346 }; 1347 1348 1355 1349 1356 1350 /// \brief A bidirected graph template. … … 1377 1371 1378 1372 1379 /// An experiment for ResGraphWrapper.1380 1373 template<typename Graph, typename Number, 1381 1374 typename CapacityMap, typename FlowMap> … … 1393 1386 }; 1394 1387 1395 /// An experiment for ResGraphWrapper.1396 1388 template<typename Graph, typename Number, 1397 1389 typename CapacityMap, typename FlowMap> … … 1409 1401 }; 1410 1402 1411 1412 /// An experiment for ResGraphWrapper. 1403 1404 /// A wrapper for composing the residual graph for directed flow and circulation problems. 1405 1406 /// A wrapper for composing the residual graph for directed flow and circulation problems. 1413 1407 template<typename Graph, typename Number, 1414 1408 typename CapacityMap, typename FlowMap> 1415 class ExpResGraphWrapper :1409 class ResGraphWrapper : 1416 1410 public SubBidirGraphWrapper< 1417 1411 Graph, … … 1429 1423 BackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter; 1430 1424 public: 1431 ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,1425 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 1432 1426 FlowMap& _flow) : 1433 1427 Parent(), capacity(&_capacity), flow(&_flow), … … 1465 1459 1466 1460 1467 // /// An experiment for ResGraphWrapper.1468 // template<typename Graph, typename Number,1469 // typename CapacityMap, typename FlowMap>1470 // class ExpResGraphWrapper :1471 // public SubGraphWrapper< BidirGraphWrapper<Graph>,1472 // ConstMap<typename BidirGraphWrapper<Graph>::Node,1473 // bool>,1474 // EdgeFilter< BidirGraphWrapper<Graph>,1475 // CapacityMap, FlowMap> > {1476 // public:1477 // typedef SubGraphWrapper< BidirGraphWrapper<Graph>,1478 // ConstMap<typename BidirGraphWrapper<Graph>::Node,1479 // bool>,1480 // EdgeFilter< BidirGraphWrapper<Graph>,1481 // CapacityMap, FlowMap> > Parent;1482 // protected:1483 // const CapacityMap* capacity;1484 // FlowMap* flow;1485 // BidirGraphWrapper<Graph> bidir_graph;1486 // ConstMap<typename BidirGraphWrapper<Graph>::Node, bool> node_filter;1487 // EdgeFilter< BidirGraphWrapper<Graph>, CapacityMap, FlowMap> edge_filter;1488 // public:1489 // ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,1490 // FlowMap& _flow) :1491 // Parent(), capacity(&_capacity), flow(&_flow),1492 // bidir_graph(_graph),1493 // node_filter(true),1494 // edge_filter(bidir_graph, *capacity, *flow) {1495 // Parent::setGraph(bidir_graph);1496 // Parent::setNodeFilterMap(node_filter);1497 // Parent::setEdgeFilterMap(edge_filter);1498 // }1499 1500 // // bool forward(const Parent::Edge& e) const { return Parent::forward(e); }1501 // //bool backward(const Edge& e) const { return e.backward; }1502 1503 // void augment(const typename Parent::Edge& e, Number a) const {1504 // if (Parent::forward(e))1505 // // flow>set(e.out, flow>get(e.out)+a);1506 // flow>set(e, (*flow)[e]+a);1507 // else1508 // // flow>set(e.in, flow>get(e.in)a);1509 // flow>set(e, (*flow)[e]a);1510 // }1511 1512 // Number resCap(const typename Parent::Edge& e) const {1513 // if (Parent::forward(e))1514 // // return (capacity>get(e.out)flow>get(e.out));1515 // return ((*capacity)[e](*flow)[e]);1516 // else1517 // // return (flow>get(e.in));1518 // return ((*flow)[e]);1519 // }1520 1521 // };1522 1523 1524 1525 /// A wrapper for composing the residual graph for directed flow and circulation problems.1526 1527 /// A wrapper for composing the residual graph for directed flow and circulation problems.1528 1461 template<typename Graph, typename Number, 1529 1462 typename CapacityMap, typename FlowMap> 1530 class ResGraphWrapper : public GraphWrapper<Graph> {1463 class OldResGraphWrapper : public GraphWrapper<Graph> { 1531 1464 public: 1532 1465 typedef GraphWrapper<Graph> Parent; … … 1535 1468 FlowMap* flow; 1536 1469 1537 ResGraphWrapper() : GraphWrapper<Graph>(0),1470 OldResGraphWrapper() : GraphWrapper<Graph>(0), 1538 1471 capacity(0), flow(0) { } 1539 1472 void setCapacityMap(const CapacityMap& _capacity) { … … 1546 1479 public: 1547 1480 1548 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,1481 OldResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 1549 1482 FlowMap& _flow) : 1550 1483 GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { } … … 1558 1491 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 1559 1492 class Edge : public Graph::Edge { 1560 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;1493 friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; 1561 1494 protected: 1562 1495 bool backward; //true, iff backward … … 1581 1514 1582 1515 class OutEdgeIt { 1583 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;1516 friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; 1584 1517 protected: 1585 1518 typename Graph::OutEdgeIt out; … … 1592 1525 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } 1593 1526 //the unique invalid iterator 1594 OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {1527 OutEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 1595 1528 backward=false; 1596 1529 _G.graph>first(out, v); … … 1615 1548 1616 1549 class InEdgeIt { 1617 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;1550 friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; 1618 1551 protected: 1619 1552 typename Graph::OutEdgeIt out; … … 1626 1559 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } 1627 1560 //the unique invalid iterator 1628 InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {1561 InEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 1629 1562 backward=false; 1630 1563 _G.graph>first(in, v); … … 1649 1582 1650 1583 class EdgeIt { 1651 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;1584 friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; 1652 1585 protected: 1653 1586 typename Graph::EdgeIt e; … … 1656 1589 EdgeIt() { } 1657 1590 EdgeIt(const Invalid& i) : e(i), backward(true) { } 1658 EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {1591 EdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) { 1659 1592 backward=false; 1660 1593 _G.graph>first(e); … … 1816 1749 typedef T ValueType; 1817 1750 typedef Edge KeyType; 1818 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }1819 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }1751 EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } 1752 EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } 1820 1753 void set(Edge e, T a) { 1821 1754 if (!e.backward) 
src/work/jacint/max_flow.h
r650 r653 64 64 FlowMap* flow; 65 65 int n; //the number of nodes of G 66 //typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;67 typedef ExpResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;66 typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW; 67 //typedef ExpResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW; 68 68 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; 69 69 typedef typename ResGW::Edge ResGWEdge;
Note: See TracChangeset
for help on using the changeset viewer.