src/hugo/graph_wrapper.h
changeset 653 c3ad7c661a49
parent 650 588ff2ca55bd
child 655 a9878222d5c8
equal deleted inserted replaced
17:bf5717581e8a 18:79cbefbc5599
  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 
  1374     }
  1368     }
  1375   };
  1369   };
  1376 
  1370 
  1377 
  1371 
  1378 
  1372 
  1379   /// An experiment for ResGraphWrapper.
       
  1380   template<typename Graph, typename Number,
  1373   template<typename Graph, typename Number,
  1381 	   typename CapacityMap, typename FlowMap>
  1374 	   typename CapacityMap, typename FlowMap>
  1382   class ForwardFilter {
  1375   class ForwardFilter {
  1383     const Graph* graph;
  1376     const Graph* graph;
  1384     const CapacityMap* capacity;
  1377     const CapacityMap* capacity;
  1390     bool operator[](const typename Graph::Edge& e) const {
  1383     bool operator[](const typename Graph::Edge& e) const {
  1391       return ((*flow)[e] < (*capacity)[e]);
  1384       return ((*flow)[e] < (*capacity)[e]);
  1392     }
  1385     }
  1393   };
  1386   };
  1394 
  1387 
  1395   /// An experiment for ResGraphWrapper.
       
  1396   template<typename Graph, typename Number,
  1388   template<typename Graph, typename Number,
  1397 	   typename CapacityMap, typename FlowMap>
  1389 	   typename CapacityMap, typename FlowMap>
  1398   class BackwardFilter {
  1390   class BackwardFilter {
  1399     const Graph* graph;
  1391     const Graph* graph;
  1400     const CapacityMap* capacity;
  1392     const CapacityMap* capacity;
  1406     bool operator[](const typename Graph::Edge& e) const {
  1398     bool operator[](const typename Graph::Edge& e) const {
  1407       return (0 < (*flow)[e]);
  1399       return (0 < (*flow)[e]);
  1408     }
  1400     }
  1409   };
  1401   };
  1410 
  1402 
  1411 
  1403   
  1412   /// An experiment for ResGraphWrapper.
  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   template<typename Graph, typename Number, 
  1407   template<typename Graph, typename Number, 
  1414 	   typename CapacityMap, typename FlowMap>
  1408 	   typename CapacityMap, typename FlowMap>
  1415   class ExpResGraphWrapper : 
  1409   class ResGraphWrapper : 
  1416     public SubBidirGraphWrapper< 
  1410     public SubBidirGraphWrapper< 
  1417     Graph, 
  1411     Graph, 
  1418     ForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
  1412     ForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
  1419     BackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
  1413     BackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
  1420   public:
  1414   public:
  1426     const CapacityMap* capacity;
  1420     const CapacityMap* capacity;
  1427     FlowMap* flow;
  1421     FlowMap* flow;
  1428     ForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
  1422     ForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
  1429     BackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
  1423     BackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
  1430   public:
  1424   public:
  1431     ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
  1425     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
  1432 		       FlowMap& _flow) : 
  1426 		       FlowMap& _flow) : 
  1433       Parent(), capacity(&_capacity), flow(&_flow), 
  1427       Parent(), capacity(&_capacity), flow(&_flow), 
  1434       forward_filter(_graph, _capacity, _flow), 
  1428       forward_filter(_graph, _capacity, _flow), 
  1435       backward_filter(_graph, _capacity, _flow) {
  1429       backward_filter(_graph, _capacity, _flow) {
  1436       Parent::setGraph(_graph);
  1430       Parent::setGraph(_graph);
  1462   };
  1456   };
  1463 
  1457 
  1464 
  1458 
  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 //       else  
       
  1508 // // 	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 //       else 
       
  1517 // //	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   template<typename Graph, typename Number, 
  1461   template<typename Graph, typename Number, 
  1529 	   typename CapacityMap, typename FlowMap>
  1462 	   typename CapacityMap, typename FlowMap>
  1530   class ResGraphWrapper : public GraphWrapper<Graph> {
  1463   class OldResGraphWrapper : public GraphWrapper<Graph> {
  1531   public:
  1464   public:
  1532     typedef GraphWrapper<Graph> Parent; 
  1465     typedef GraphWrapper<Graph> Parent; 
  1533   protected:
  1466   protected:
  1534     const CapacityMap* capacity;
  1467     const CapacityMap* capacity;
  1535     FlowMap* flow;
  1468     FlowMap* flow;
  1536 
  1469 
  1537     ResGraphWrapper() : GraphWrapper<Graph>(0), 
  1470     OldResGraphWrapper() : GraphWrapper<Graph>(0), 
  1538 			capacity(0), flow(0) { }
  1471 			capacity(0), flow(0) { }
  1539     void setCapacityMap(const CapacityMap& _capacity) {
  1472     void setCapacityMap(const CapacityMap& _capacity) {
  1540       capacity=&_capacity;
  1473       capacity=&_capacity;
  1541     }
  1474     }
  1542     void setFlowMap(FlowMap& _flow) {
  1475     void setFlowMap(FlowMap& _flow) {
  1543       flow=&_flow;
  1476       flow=&_flow;
  1544     }
  1477     }
  1545 
  1478 
  1546   public:
  1479   public:
  1547 
  1480 
  1548     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
  1481     OldResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
  1549 		    FlowMap& _flow) : 
  1482 		    FlowMap& _flow) : 
  1550       GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
  1483       GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
  1551 
  1484 
  1552     class Edge; 
  1485     class Edge; 
  1553     class OutEdgeIt; 
  1486     class OutEdgeIt; 
  1555     friend class OutEdgeIt; 
  1488     friend class OutEdgeIt; 
  1556 
  1489 
  1557     typedef typename GraphWrapper<Graph>::Node Node;
  1490     typedef typename GraphWrapper<Graph>::Node Node;
  1558     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
  1491     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
  1559     class Edge : public Graph::Edge {
  1492     class Edge : public Graph::Edge {
  1560       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
  1493       friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
  1561     protected:
  1494     protected:
  1562       bool backward; //true, iff backward
  1495       bool backward; //true, iff backward
  1563 //      typename Graph::Edge e;
  1496 //      typename Graph::Edge e;
  1564     public:
  1497     public:
  1565       Edge() { }
  1498       Edge() { }
  1578 		static_cast<typename Graph::Edge>(v));
  1511 		static_cast<typename Graph::Edge>(v));
  1579       } 
  1512       } 
  1580     };
  1513     };
  1581 
  1514 
  1582     class OutEdgeIt {
  1515     class OutEdgeIt {
  1583       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
  1516       friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
  1584     protected:
  1517     protected:
  1585       typename Graph::OutEdgeIt out;
  1518       typename Graph::OutEdgeIt out;
  1586       typename Graph::InEdgeIt in;
  1519       typename Graph::InEdgeIt in;
  1587       bool backward;
  1520       bool backward;
  1588     public:
  1521     public:
  1589       OutEdgeIt() { }
  1522       OutEdgeIt() { }
  1590       //FIXME
  1523       //FIXME
  1591 //      OutEdgeIt(const Edge& e) : Edge(e) { }
  1524 //      OutEdgeIt(const Edge& e) : Edge(e) { }
  1592       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
  1525       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
  1593 //the unique invalid iterator
  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 	backward=false;
  1528 	backward=false;
  1596 	_G.graph->first(out, v);
  1529 	_G.graph->first(out, v);
  1597 	while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
  1530 	while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
  1598 	if (!_G.graph->valid(out)) {
  1531 	if (!_G.graph->valid(out)) {
  1599 	  backward=true;
  1532 	  backward=true;
  1612 	  return Edge(out, this->backward);
  1545 	  return Edge(out, this->backward);
  1613       }
  1546       }
  1614     };
  1547     };
  1615 
  1548 
  1616     class InEdgeIt {
  1549     class InEdgeIt {
  1617       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
  1550       friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
  1618     protected:
  1551     protected:
  1619       typename Graph::OutEdgeIt out;
  1552       typename Graph::OutEdgeIt out;
  1620       typename Graph::InEdgeIt in;
  1553       typename Graph::InEdgeIt in;
  1621       bool backward;
  1554       bool backward;
  1622     public:
  1555     public:
  1623       InEdgeIt() { }
  1556       InEdgeIt() { }
  1624       //FIXME
  1557       //FIXME
  1625 //      OutEdgeIt(const Edge& e) : Edge(e) { }
  1558 //      OutEdgeIt(const Edge& e) : Edge(e) { }
  1626       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
  1559       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
  1627 //the unique invalid iterator
  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 	backward=false;
  1562 	backward=false;
  1630 	_G.graph->first(in, v);
  1563 	_G.graph->first(in, v);
  1631 	while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
  1564 	while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
  1632 	if (!_G.graph->valid(in)) {
  1565 	if (!_G.graph->valid(in)) {
  1633 	  backward=true;
  1566 	  backward=true;
  1646 	  return Edge(in, this->backward);
  1579 	  return Edge(in, this->backward);
  1647       }
  1580       }
  1648     };
  1581     };
  1649 
  1582 
  1650     class EdgeIt {
  1583     class EdgeIt {
  1651       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
  1584       friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
  1652     protected:
  1585     protected:
  1653       typename Graph::EdgeIt e;
  1586       typename Graph::EdgeIt e;
  1654       bool backward;
  1587       bool backward;
  1655     public:
  1588     public:
  1656       EdgeIt() { }
  1589       EdgeIt() { }
  1657       EdgeIt(const Invalid& i) : e(i), backward(true) { }
  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 	backward=false;
  1592 	backward=false;
  1660 	_G.graph->first(e);
  1593 	_G.graph->first(e);
  1661 	while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
  1594 	while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
  1662 	if (!_G.graph->valid(e)) {
  1595 	if (!_G.graph->valid(e)) {
  1663 	  backward=true;
  1596 	  backward=true;
  1813     class EdgeMap {
  1746     class EdgeMap {
  1814       typename Graph::template EdgeMap<T> forward_map, backward_map; 
  1747       typename Graph::template EdgeMap<T> forward_map, backward_map; 
  1815     public:
  1748     public:
  1816       typedef T ValueType;
  1749       typedef T ValueType;
  1817       typedef Edge KeyType;
  1750       typedef Edge KeyType;
  1818       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
  1751       EdgeMap(const OldResGraphWrapper<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) { }
  1752       EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
  1820       void set(Edge e, T a) { 
  1753       void set(Edge e, T a) { 
  1821 	if (!e.backward) 
  1754 	if (!e.backward) 
  1822 	  forward_map.set(e/*.out*/, a); 
  1755 	  forward_map.set(e/*.out*/, a); 
  1823 	else 
  1756 	else 
  1824 	  backward_map.set(e/*.in*/, a); 
  1757 	  backward_map.set(e/*.in*/, a);