1.1 --- a/src/work/edmonds_karp.h Tue Mar 30 13:37:21 2004 +0000
1.2 +++ b/src/work/edmonds_karp.h Tue Mar 30 17:16:53 2004 +0000
1.3 @@ -247,30 +247,32 @@
1.4 };
1.5
1.6
1.7 - template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.8 + template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
1.9 class MaxFlow {
1.10 public:
1.11 - typedef typename Graph::Node Node;
1.12 - typedef typename Graph::Edge Edge;
1.13 - typedef typename Graph::EdgeIt EdgeIt;
1.14 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.15 - typedef typename Graph::InEdgeIt InEdgeIt;
1.16 + typedef typename GraphWrapper::Node Node;
1.17 + typedef typename GraphWrapper::Edge Edge;
1.18 + typedef typename GraphWrapper::EdgeIt EdgeIt;
1.19 + typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.20 + typedef typename GraphWrapper::InEdgeIt InEdgeIt;
1.21
1.22 private:
1.23 - const Graph* G;
1.24 + //const Graph* G;
1.25 + GraphWrapper gw;
1.26 Node s;
1.27 Node t;
1.28 FlowMap* flow;
1.29 const CapacityMap* capacity;
1.30 - typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.31 + typedef ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap >
1.32 + AugGraph;
1.33 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.34 typedef typename AugGraph::Edge AugEdge;
1.35
1.36 public:
1.37 - MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
1.38 - G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
1.39 + MaxFlow(const GraphWrapper& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
1.40 + gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
1.41 bool augmentOnShortestPath() {
1.42 - AugGraph res_graph(*G, *flow, *capacity);
1.43 + AugGraph res_graph(gw, *flow, *capacity);
1.44 bool _augment=false;
1.45
1.46 typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.47 @@ -313,131 +315,24 @@
1.48 return _augment;
1.49 }
1.50
1.51 -// template<typename MutableGraph> bool augmentOnBlockingFlow() {
1.52 -// bool _augment=false;
1.53 -
1.54 -// AugGraph res_graph(*G, *flow, *capacity);
1.55 -
1.56 -// typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.57 -// BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
1.58 -
1.59 -// bfs.pushAndSetReached(s);
1.60 -// typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.61 -// while ( !bfs.finished() ) {
1.62 -// AugOutEdgeIt e=bfs;
1.63 -// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.64 -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.65 -// }
1.66 -
1.67 -// ++bfs;
1.68 -// } //computing distances from s in the residual graph
1.69 -
1.70 -// MutableGraph F;
1.71 -// typename AugGraph::NodeMap<typename MutableGraph::Node>
1.72 -// res_graph_to_F(res_graph);
1.73 -// for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.74 -// res_graph_to_F.set(n, F.addNode());
1.75 -// }
1.76 -
1.77 -// typename MutableGraph::Node sF=res_graph_to_F.get(s);
1.78 -// typename MutableGraph::Node tF=res_graph_to_F.get(t);
1.79 -
1.80 -// typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
1.81 -// typename MutableGraph::EdgeMap<Number> residual_capacity(F);
1.82 -
1.83 -// //Making F to the graph containing the edges of the residual graph
1.84 -// //which are in some shortest paths
1.85 -// for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
1.86 -// if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
1.87 -// typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.88 -// original_edge.update();
1.89 -// original_edge.set(f, e);
1.90 -// residual_capacity.update();
1.91 -// residual_capacity.set(f, res_graph.free(e));
1.92 -// }
1.93 -// }
1.94 -
1.95 -// bool __augment=true;
1.96 -
1.97 -// while (__augment) {
1.98 -// __augment=false;
1.99 -// //computing blocking flow with dfs
1.100 -// typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
1.101 -// DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
1.102 -// typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
1.103 -// pred.set(sF, typename MutableGraph::Edge(INVALID));
1.104 -// //invalid iterators for sources
1.105 -
1.106 -// typename MutableGraph::NodeMap<Number> free(F);
1.107 -
1.108 -// dfs.pushAndSetReached(sF);
1.109 -// while (!dfs.finished()) {
1.110 -// ++dfs;
1.111 -// if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
1.112 -// if (dfs.isBNodeNewlyReached()) {
1.113 -// typename MutableGraph::Node v=F.aNode(dfs);
1.114 -// typename MutableGraph::Node w=F.bNode(dfs);
1.115 -// pred.set(w, dfs);
1.116 -// if (F.valid(pred.get(v))) {
1.117 -// free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
1.118 -// } else {
1.119 -// free.set(w, residual_capacity.get(dfs));
1.120 -// }
1.121 -// if (w==tF) {
1.122 -// __augment=true;
1.123 -// _augment=true;
1.124 -// break;
1.125 -// }
1.126 -
1.127 -// } else {
1.128 -// F.erase(typename MutableGraph::OutEdgeIt(dfs));
1.129 -// }
1.130 -// }
1.131 -// }
1.132 -
1.133 -// if (__augment) {
1.134 -// typename MutableGraph::Node n=tF;
1.135 -// Number augment_value=free.get(tF);
1.136 -// while (F.valid(pred.get(n))) {
1.137 -// typename MutableGraph::Edge e=pred.get(n);
1.138 -// res_graph.augment(original_edge.get(e), augment_value);
1.139 -// n=F.tail(e);
1.140 -// if (residual_capacity.get(e)==augment_value)
1.141 -// F.erase(e);
1.142 -// else
1.143 -// residual_capacity.set(e, residual_capacity.get(e)-augment_value);
1.144 -// }
1.145 -// }
1.146 -
1.147 -// }
1.148 -
1.149 -// return _augment;
1.150 -// }
1.151 -
1.152 - template<typename GraphWrapper>
1.153 + template<typename MapGraphWrapper>
1.154 class DistanceMap {
1.155 protected:
1.156 - GraphWrapper gw;
1.157 - typename GraphWrapper::NodeMap<int> dist;
1.158 + MapGraphWrapper gw;
1.159 + typename MapGraphWrapper::NodeMap<int> dist;
1.160 public:
1.161 - DistanceMap(GraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
1.162 - //NodeMap(const ListGraph& _G, T a) :
1.163 - //G(_G), container(G.node_id, a) { }
1.164 - void set(const typename GraphWrapper::Node& n, int a) { dist[n]=a; }
1.165 - int get(const typename GraphWrapper::Node& n) const { return dist[n]; }
1.166 - bool get(const typename GraphWrapper::Edge& e) const {
1.167 + DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
1.168 + void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
1.169 + int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; }
1.170 + bool get(const typename MapGraphWrapper::Edge& e) const {
1.171 return (dist.get(gw.tail(e))<dist.get(gw.head(e)));
1.172 }
1.173 - //typename std::vector<T>::reference operator[](Node n) {
1.174 - //return container[/*G.id(n)*/n.node->id]; }
1.175 - //typename std::vector<T>::const_reference operator[](Node n) const {
1.176 - //return container[/*G.id(n)*/n.node->id];
1.177 };
1.178
1.179 template<typename MutableGraph> bool augmentOnBlockingFlow() {
1.180 bool _augment=false;
1.181
1.182 - AugGraph res_graph(*G, *flow, *capacity);
1.183 + AugGraph res_graph(gw, *flow, *capacity);
1.184
1.185 typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.186 BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
1.187 @@ -453,34 +348,9 @@
1.188 ++bfs;
1.189 } //computing distances from s in the residual graph
1.190
1.191 -// MutableGraph F;
1.192 -// typename AugGraph::NodeMap<typename MutableGraph::Node>
1.193 -// res_graph_to_F(res_graph);
1.194 -// for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.195 -// res_graph_to_F.set(n, F.addNode());
1.196 -// }
1.197 -
1.198 -// typename MutableGraph::Node sF=res_graph_to_F.get(s);
1.199 -// typename MutableGraph::Node tF=res_graph_to_F.get(t);
1.200 -
1.201 -// typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
1.202 -// typename MutableGraph::EdgeMap<Number> residual_capacity(F);
1.203 -
1.204 -// //Making F to the graph containing the edges of the residual graph
1.205 -// //which are in some shortest paths
1.206 -// for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
1.207 -// if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
1.208 -// typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.209 -// original_edge.update();
1.210 -// original_edge.set(f, e);
1.211 -// residual_capacity.update();
1.212 -// residual_capacity.set(f, res_graph.free(e));
1.213 -// }
1.214 -// }
1.215 -
1.216 MutableGraph F;
1.217 - //typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph;
1.218 - //FilterResGraph filter_res_graph(res_graph, dist);
1.219 + typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph;
1.220 + FilterResGraph filter_res_graph(res_graph, dist);
1.221 typename AugGraph::NodeMap<typename MutableGraph::Node>
1.222 res_graph_to_F(res_graph);
1.223 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.224 @@ -495,16 +365,14 @@
1.225
1.226 //Making F to the graph containing the edges of the residual graph
1.227 //which are in some shortest paths
1.228 - for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>();
1.229 - res_graph.valid(e);
1.230 - res_graph.next(e)) {
1.231 - if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
1.232 + for(typename FilterResGraph::EdgeIt e=filter_res_graph.template first<typename FilterResGraph::EdgeIt>(); filter_res_graph.valid(e); filter_res_graph.next(e)) {
1.233 + //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
1.234 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.235 original_edge.update();
1.236 original_edge.set(f, e);
1.237 residual_capacity.update();
1.238 residual_capacity.set(f, res_graph.free(e));
1.239 - }
1.240 + //}
1.241 }
1.242
1.243 bool __augment=true;
1.244 @@ -564,387 +432,60 @@
1.245 return _augment;
1.246 }
1.247
1.248 - template<typename MutableGraph> bool augmentOnBlockingFlow1() {
1.249 - bool _augment=false;
1.250 -
1.251 - AugGraph res_graph(*G, *flow, *capacity);
1.252 -
1.253 - //bfs for distances on the residual graph
1.254 - typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.255 - BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
1.256 - bfs.pushAndSetReached(s);
1.257 - typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.258 -
1.259 - //F will contain the physical copy of the residual graph
1.260 - //with the set of edges which areon shortest paths
1.261 - MutableGraph F;
1.262 - typename AugGraph::NodeMap<typename MutableGraph::Node>
1.263 - res_graph_to_F(res_graph);
1.264 - for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.265 - res_graph_to_F.set(n, F.addNode());
1.266 - }
1.267 - typename MutableGraph::Node sF=res_graph_to_F.get(s);
1.268 - typename MutableGraph::Node tF=res_graph_to_F.get(t);
1.269 - typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
1.270 - typename MutableGraph::EdgeMap<Number> residual_capacity(F);
1.271 -
1.272 - while ( !bfs.finished() ) {
1.273 - AugOutEdgeIt e=bfs;
1.274 - if (res_graph.valid(e)) {
1.275 - if (bfs.isBNodeNewlyReached()) {
1.276 - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.277 - typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.278 - original_edge.update();
1.279 - original_edge.set(f, e);
1.280 - residual_capacity.update();
1.281 - residual_capacity.set(f, res_graph.free(e));
1.282 - } else {
1.283 - if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
1.284 - typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.285 - original_edge.update();
1.286 - original_edge.set(f, e);
1.287 - residual_capacity.update();
1.288 - residual_capacity.set(f, res_graph.free(e));
1.289 - }
1.290 - }
1.291 - }
1.292 - ++bfs;
1.293 - } //computing distances from s in the residual graph
1.294 -
1.295 - bool __augment=true;
1.296 -
1.297 - while (__augment) {
1.298 - __augment=false;
1.299 - //computing blocking flow with dfs
1.300 - typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
1.301 - DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
1.302 - typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
1.303 - pred.set(sF, typename MutableGraph::Edge(INVALID));
1.304 - //invalid iterators for sources
1.305 -
1.306 - typename MutableGraph::NodeMap<Number> free(F);
1.307 -
1.308 - dfs.pushAndSetReached(sF);
1.309 - while (!dfs.finished()) {
1.310 - ++dfs;
1.311 - if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
1.312 - if (dfs.isBNodeNewlyReached()) {
1.313 - typename MutableGraph::Node v=F.aNode(dfs);
1.314 - typename MutableGraph::Node w=F.bNode(dfs);
1.315 - pred.set(w, dfs);
1.316 - if (F.valid(pred.get(v))) {
1.317 - free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
1.318 - } else {
1.319 - free.set(w, residual_capacity.get(dfs));
1.320 - }
1.321 - if (w==tF) {
1.322 - __augment=true;
1.323 - _augment=true;
1.324 - break;
1.325 - }
1.326 -
1.327 - } else {
1.328 - F.erase(typename MutableGraph::OutEdgeIt(dfs));
1.329 - }
1.330 - }
1.331 - }
1.332 -
1.333 - if (__augment) {
1.334 - typename MutableGraph::Node n=tF;
1.335 - Number augment_value=free.get(tF);
1.336 - while (F.valid(pred.get(n))) {
1.337 - typename MutableGraph::Edge e=pred.get(n);
1.338 - res_graph.augment(original_edge.get(e), augment_value);
1.339 - n=F.tail(e);
1.340 - if (residual_capacity.get(e)==augment_value)
1.341 - F.erase(e);
1.342 - else
1.343 - residual_capacity.set(e, residual_capacity.get(e)-augment_value);
1.344 - }
1.345 - }
1.346 -
1.347 - }
1.348 -
1.349 - return _augment;
1.350 - }
1.351 - bool augmentOnBlockingFlow2() {
1.352 - bool _augment=false;
1.353 -
1.354 - //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
1.355 - typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
1.356 - typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
1.357 - typedef typename EAugGraph::Edge EAugEdge;
1.358 -
1.359 - EAugGraph res_graph(*G, *flow, *capacity);
1.360 -
1.361 - //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
1.362 - BfsIterator5<
1.363 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
1.364 - /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
1.365 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
1.366 -
1.367 - bfs.pushAndSetReached(s);
1.368 -
1.369 - typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
1.370 - NodeMap<int>& dist=res_graph.dist;
1.371 -
1.372 - while ( !bfs.finished() ) {
1.373 - typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1.374 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.375 - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.376 - }
1.377 - ++bfs;
1.378 - } //computing distances from s in the residual graph
1.379 -
1.380 - bool __augment=true;
1.381 -
1.382 - while (__augment) {
1.383 -
1.384 - __augment=false;
1.385 - //computing blocking flow with dfs
1.386 - typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
1.387 - DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
1.388 - dfs(res_graph);
1.389 - typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
1.390 - pred.set(s, EAugEdge(INVALID));
1.391 - //invalid iterators for sources
1.392 -
1.393 - typename EAugGraph::NodeMap<Number> free(res_graph);
1.394 -
1.395 - dfs.pushAndSetReached(s);
1.396 - while (!dfs.finished()) {
1.397 - ++dfs;
1.398 - if (res_graph.valid(EAugOutEdgeIt(dfs))) {
1.399 - if (dfs.isBNodeNewlyReached()) {
1.400 -
1.401 - typename EAugGraph::Node v=res_graph.aNode(dfs);
1.402 - typename EAugGraph::Node w=res_graph.bNode(dfs);
1.403 -
1.404 - pred.set(w, EAugOutEdgeIt(dfs));
1.405 - if (res_graph.valid(pred.get(v))) {
1.406 - free.set(w, std::min(free.get(v), res_graph.free(dfs)));
1.407 - } else {
1.408 - free.set(w, res_graph.free(dfs));
1.409 - }
1.410 -
1.411 - if (w==t) {
1.412 - __augment=true;
1.413 - _augment=true;
1.414 - break;
1.415 - }
1.416 - } else {
1.417 - res_graph.erase(dfs);
1.418 - }
1.419 - }
1.420 -
1.421 - }
1.422 -
1.423 - if (__augment) {
1.424 - typename EAugGraph::Node n=t;
1.425 - Number augment_value=free.get(t);
1.426 - while (res_graph.valid(pred.get(n))) {
1.427 - EAugEdge e=pred.get(n);
1.428 - res_graph.augment(e, augment_value);
1.429 - n=res_graph.tail(e);
1.430 - if (res_graph.free(e)==0)
1.431 - res_graph.erase(e);
1.432 - }
1.433 - }
1.434 -
1.435 - }
1.436 -
1.437 - return _augment;
1.438 - }
1.439 - void run() {
1.440 - //int num_of_augmentations=0;
1.441 - while (augmentOnShortestPath()) {
1.442 - //while (augmentOnBlockingFlow<MutableGraph>()) {
1.443 - //std::cout << ++num_of_augmentations << " ";
1.444 - //std::cout<<std::endl;
1.445 - }
1.446 - }
1.447 - template<typename MutableGraph> void run() {
1.448 - //int num_of_augmentations=0;
1.449 - //while (augmentOnShortestPath()) {
1.450 - while (augmentOnBlockingFlow<MutableGraph>()) {
1.451 - //std::cout << ++num_of_augmentations << " ";
1.452 - //std::cout<<std::endl;
1.453 - }
1.454 - }
1.455 - Number flowValue() {
1.456 - Number a=0;
1.457 - OutEdgeIt e;
1.458 - for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) {
1.459 - a+=flow->get(e);
1.460 - }
1.461 - return a;
1.462 - }
1.463 - };
1.464 -
1.465 -
1.466 - template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.467 - class MaxMatching {
1.468 - public:
1.469 - typedef typename Graph::Node Node;
1.470 - typedef typename Graph::NodeIt NodeIt;
1.471 - typedef typename Graph::Edge Edge;
1.472 - typedef typename Graph::EdgeIt EdgeIt;
1.473 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.474 - typedef typename Graph::InEdgeIt InEdgeIt;
1.475 -
1.476 - typedef typename Graph::NodeMap<bool> SMap;
1.477 - typedef typename Graph::NodeMap<bool> TMap;
1.478 - private:
1.479 - const Graph* G;
1.480 - SMap* S;
1.481 - TMap* T;
1.482 - //Node s;
1.483 - //Node t;
1.484 - FlowMap* flow;
1.485 - const CapacityMap* capacity;
1.486 - typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.487 - typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.488 - typedef typename AugGraph::Edge AugEdge;
1.489 - typename Graph::NodeMap<int> used; //0
1.490 -
1.491 - public:
1.492 - MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
1.493 - G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
1.494 - bool augmentOnShortestPath() {
1.495 - AugGraph res_graph(*G, *flow, *capacity);
1.496 - bool _augment=false;
1.497 -
1.498 - typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.499 - BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
1.500 - typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.501 - for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.502 - if ((S->get(s)) && (used.get(s)<1) ) {
1.503 - //Number u=0;
1.504 - //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.505 - //u+=flow->get(e);
1.506 - //if (u<1) {
1.507 - res_bfs.pushAndSetReached(s);
1.508 - pred.set(s, AugEdge(INVALID));
1.509 - //}
1.510 - }
1.511 - }
1.512 -
1.513 - typename AugGraph::NodeMap<Number> free(res_graph);
1.514 -
1.515 - Node n;
1.516 - //searching for augmenting path
1.517 - while ( !res_bfs.finished() ) {
1.518 - AugOutEdgeIt e=res_bfs;
1.519 - if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
1.520 - Node v=res_graph.tail(e);
1.521 - Node w=res_graph.head(e);
1.522 - pred.set(w, e);
1.523 - if (res_graph.valid(pred.get(v))) {
1.524 - free.set(w, std::min(free.get(v), res_graph.free(e)));
1.525 - } else {
1.526 - free.set(w, res_graph.free(e));
1.527 - }
1.528 - n=res_graph.head(e);
1.529 - if (T->get(n) && (used.get(n)<1) ) {
1.530 - //Number u=0;
1.531 - //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.532 - //u+=flow->get(f);
1.533 - //if (u<1) {
1.534 - _augment=true;
1.535 - break;
1.536 - //}
1.537 - }
1.538 - }
1.539 -
1.540 - ++res_bfs;
1.541 - } //end of searching augmenting path
1.542 -
1.543 - if (_augment) {
1.544 - //Node n=t;
1.545 - used.set(n, 1); //mind2 vegen jav
1.546 - Number augment_value=free.get(n);
1.547 - while (res_graph.valid(pred.get(n))) {
1.548 - AugEdge e=pred.get(n);
1.549 - res_graph.augment(e, augment_value);
1.550 - n=res_graph.tail(e);
1.551 - }
1.552 - used.set(n, 1); //mind2 vegen jav
1.553 - }
1.554 -
1.555 - return _augment;
1.556 - }
1.557 -
1.558 -// template<typename MutableGraph> bool augmentOnBlockingFlow() {
1.559 +// template<typename MutableGraph> bool augmentOnBlockingFlow1() {
1.560 // bool _augment=false;
1.561
1.562 // AugGraph res_graph(*G, *flow, *capacity);
1.563
1.564 +// //bfs for distances on the residual graph
1.565 // typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.566 -// BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
1.567 +// BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
1.568 +// bfs.pushAndSetReached(s);
1.569 +// typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.570
1.571 -
1.572 -
1.573 -
1.574 -
1.575 -// //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.576 -// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.577 -// if (S->get(s)) {
1.578 -// Number u=0;
1.579 -// for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.580 -// u+=flow->get(e);
1.581 -// if (u<1) {
1.582 -// res_bfs.pushAndSetReached(s);
1.583 -// //pred.set(s, AugEdge(INVALID));
1.584 -// }
1.585 -// }
1.586 -// }
1.587 -
1.588 -
1.589 -
1.590 -
1.591 -// //bfs.pushAndSetReached(s);
1.592 -// typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.593 -// while ( !bfs.finished() ) {
1.594 -// AugOutEdgeIt e=bfs;
1.595 -// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.596 -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.597 -// }
1.598 -
1.599 -// ++bfs;
1.600 -// } //computing distances from s in the residual graph
1.601 -
1.602 +// //F will contain the physical copy of the residual graph
1.603 +// //with the set of edges which areon shortest paths
1.604 // MutableGraph F;
1.605 // typename AugGraph::NodeMap<typename MutableGraph::Node>
1.606 // res_graph_to_F(res_graph);
1.607 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.608 // res_graph_to_F.set(n, F.addNode());
1.609 // }
1.610 -
1.611 // typename MutableGraph::Node sF=res_graph_to_F.get(s);
1.612 // typename MutableGraph::Node tF=res_graph_to_F.get(t);
1.613 -
1.614 // typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
1.615 // typename MutableGraph::EdgeMap<Number> residual_capacity(F);
1.616
1.617 -// //Making F to the graph containing the edges of the residual graph
1.618 -// //which are in some shortest paths
1.619 -// for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
1.620 -// if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
1.621 -// typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.622 -// original_edge.update();
1.623 -// original_edge.set(f, e);
1.624 -// residual_capacity.update();
1.625 -// residual_capacity.set(f, res_graph.free(e));
1.626 -// }
1.627 -// }
1.628 +// while ( !bfs.finished() ) {
1.629 +// AugOutEdgeIt e=bfs;
1.630 +// if (res_graph.valid(e)) {
1.631 +// if (bfs.isBNodeNewlyReached()) {
1.632 +// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.633 +// typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.634 +// original_edge.update();
1.635 +// original_edge.set(f, e);
1.636 +// residual_capacity.update();
1.637 +// residual_capacity.set(f, res_graph.free(e));
1.638 +// } else {
1.639 +// if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
1.640 +// typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.641 +// original_edge.update();
1.642 +// original_edge.set(f, e);
1.643 +// residual_capacity.update();
1.644 +// residual_capacity.set(f, res_graph.free(e));
1.645 +// }
1.646 +// }
1.647 +// }
1.648 +// ++bfs;
1.649 +// } //computing distances from s in the residual graph
1.650
1.651 // bool __augment=true;
1.652
1.653 // while (__augment) {
1.654 // __augment=false;
1.655 // //computing blocking flow with dfs
1.656 -// typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
1.657 -// DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
1.658 +// typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
1.659 +// DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
1.660 // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
1.661 // pred.set(sF, typename MutableGraph::Edge(INVALID));
1.662 // //invalid iterators for sources
1.663 @@ -994,140 +535,102 @@
1.664
1.665 // return _augment;
1.666 // }
1.667 - bool augmentOnBlockingFlow2() {
1.668 - bool _augment=false;
1.669 +// bool augmentOnBlockingFlow2() {
1.670 +// bool _augment=false;
1.671
1.672 - //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
1.673 - typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
1.674 - typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
1.675 - typedef typename EAugGraph::Edge EAugEdge;
1.676 +// //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
1.677 +// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
1.678 +// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
1.679 +// typedef typename EAugGraph::Edge EAugEdge;
1.680
1.681 - EAugGraph res_graph(*G, *flow, *capacity);
1.682 +// EAugGraph res_graph(*G, *flow, *capacity);
1.683
1.684 - //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
1.685 - BfsIterator5<
1.686 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
1.687 - /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
1.688 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
1.689 +// //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
1.690 +// BfsIterator5<
1.691 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
1.692 +// /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
1.693 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
1.694 +
1.695 +// bfs.pushAndSetReached(s);
1.696
1.697 +// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
1.698 +// NodeMap<int>& dist=res_graph.dist;
1.699
1.700 - //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.701 - for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.702 - if (S->get(s)) {
1.703 - Number u=0;
1.704 - for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.705 - u+=flow->get(e);
1.706 - if (u<1) {
1.707 - bfs.pushAndSetReached(s);
1.708 - //pred.set(s, AugEdge(INVALID));
1.709 - }
1.710 - }
1.711 - }
1.712 +// while ( !bfs.finished() ) {
1.713 +// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1.714 +// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.715 +// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.716 +// }
1.717 +// ++bfs;
1.718 +// } //computing distances from s in the residual graph
1.719
1.720 +// bool __augment=true;
1.721 +
1.722 +// while (__augment) {
1.723 +
1.724 +// __augment=false;
1.725 +// //computing blocking flow with dfs
1.726 +// typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
1.727 +// DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
1.728 +// dfs(res_graph);
1.729 +// typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
1.730 +// pred.set(s, EAugEdge(INVALID));
1.731 +// //invalid iterators for sources
1.732 +
1.733 +// typename EAugGraph::NodeMap<Number> free(res_graph);
1.734 +
1.735 +// dfs.pushAndSetReached(s);
1.736 +// while (!dfs.finished()) {
1.737 +// ++dfs;
1.738 +// if (res_graph.valid(EAugOutEdgeIt(dfs))) {
1.739 +// if (dfs.isBNodeNewlyReached()) {
1.740 +
1.741 +// typename EAugGraph::Node v=res_graph.aNode(dfs);
1.742 +// typename EAugGraph::Node w=res_graph.bNode(dfs);
1.743 +
1.744 +// pred.set(w, EAugOutEdgeIt(dfs));
1.745 +// if (res_graph.valid(pred.get(v))) {
1.746 +// free.set(w, std::min(free.get(v), res_graph.free(dfs)));
1.747 +// } else {
1.748 +// free.set(w, res_graph.free(dfs));
1.749 +// }
1.750 +
1.751 +// if (w==t) {
1.752 +// __augment=true;
1.753 +// _augment=true;
1.754 +// break;
1.755 +// }
1.756 +// } else {
1.757 +// res_graph.erase(dfs);
1.758 +// }
1.759 +// }
1.760 +
1.761 +// }
1.762 +
1.763 +// if (__augment) {
1.764 +// typename EAugGraph::Node n=t;
1.765 +// Number augment_value=free.get(t);
1.766 +// while (res_graph.valid(pred.get(n))) {
1.767 +// EAugEdge e=pred.get(n);
1.768 +// res_graph.augment(e, augment_value);
1.769 +// n=res_graph.tail(e);
1.770 +// if (res_graph.free(e)==0)
1.771 +// res_graph.erase(e);
1.772 +// }
1.773 +// }
1.774
1.775 - //bfs.pushAndSetReached(s);
1.776 -
1.777 - typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
1.778 - NodeMap<int>& dist=res_graph.dist;
1.779 -
1.780 - while ( !bfs.finished() ) {
1.781 - typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1.782 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.783 - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.784 - }
1.785 - ++bfs;
1.786 - } //computing distances from s in the residual graph
1.787 -
1.788 - bool __augment=true;
1.789 -
1.790 - while (__augment) {
1.791 -
1.792 - __augment=false;
1.793 - //computing blocking flow with dfs
1.794 - typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
1.795 - DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
1.796 - dfs(res_graph);
1.797 - typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
1.798 - //pred.set(s, EAugEdge(INVALID));
1.799 - //invalid iterators for sources
1.800 -
1.801 - typename EAugGraph::NodeMap<Number> free(res_graph);
1.802 -
1.803 -
1.804 - //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.805 - for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.806 - if (S->get(s)) {
1.807 - Number u=0;
1.808 - for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.809 - u+=flow->get(e);
1.810 - if (u<1) {
1.811 - dfs.pushAndSetReached(s);
1.812 - //pred.set(s, AugEdge(INVALID));
1.813 - }
1.814 - }
1.815 - }
1.816 -
1.817 -
1.818 -
1.819 - //dfs.pushAndSetReached(s);
1.820 - typename EAugGraph::Node n;
1.821 - while (!dfs.finished()) {
1.822 - ++dfs;
1.823 - if (res_graph.valid(EAugOutEdgeIt(dfs))) {
1.824 - if (dfs.isBNodeNewlyReached()) {
1.825 -
1.826 - typename EAugGraph::Node v=res_graph.aNode(dfs);
1.827 - typename EAugGraph::Node w=res_graph.bNode(dfs);
1.828 -
1.829 - pred.set(w, EAugOutEdgeIt(dfs));
1.830 - if (res_graph.valid(pred.get(v))) {
1.831 - free.set(w, std::min(free.get(v), res_graph.free(dfs)));
1.832 - } else {
1.833 - free.set(w, res_graph.free(dfs));
1.834 - }
1.835 -
1.836 - n=w;
1.837 - if (T->get(w)) {
1.838 - Number u=0;
1.839 - for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.840 - u+=flow->get(f);
1.841 - if (u<1) {
1.842 - __augment=true;
1.843 - _augment=true;
1.844 - break;
1.845 - }
1.846 - }
1.847 - } else {
1.848 - res_graph.erase(dfs);
1.849 - }
1.850 - }
1.851 -
1.852 - }
1.853 -
1.854 - if (__augment) {
1.855 - // typename EAugGraph::Node n=t;
1.856 - Number augment_value=free.get(n);
1.857 - while (res_graph.valid(pred.get(n))) {
1.858 - EAugEdge e=pred.get(n);
1.859 - res_graph.augment(e, augment_value);
1.860 - n=res_graph.tail(e);
1.861 - if (res_graph.free(e)==0)
1.862 - res_graph.erase(e);
1.863 - }
1.864 - }
1.865 -
1.866 - }
1.867 +// }
1.868
1.869 - return _augment;
1.870 - }
1.871 - void run() {
1.872 - //int num_of_augmentations=0;
1.873 - while (augmentOnShortestPath()) {
1.874 - //while (augmentOnBlockingFlow<MutableGraph>()) {
1.875 - //std::cout << ++num_of_augmentations << " ";
1.876 - //std::cout<<std::endl;
1.877 - }
1.878 - }
1.879 +// return _augment;
1.880 +// }
1.881 +// void run() {
1.882 +// //int num_of_augmentations=0;
1.883 +// while (augmentOnShortestPath()) {
1.884 +// //while (augmentOnBlockingFlow<MutableGraph>()) {
1.885 +// //std::cout << ++num_of_augmentations << " ";
1.886 +// //std::cout<<std::endl;
1.887 +// }
1.888 +// }
1.889 // template<typename MutableGraph> void run() {
1.890 // //int num_of_augmentations=0;
1.891 // //while (augmentOnShortestPath()) {
1.892 @@ -1135,11 +638,11 @@
1.893 // //std::cout << ++num_of_augmentations << " ";
1.894 // //std::cout<<std::endl;
1.895 // }
1.896 -// }
1.897 +// }
1.898 Number flowValue() {
1.899 Number a=0;
1.900 - EdgeIt e;
1.901 - for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
1.902 + OutEdgeIt e;
1.903 + for(gw.first(e, s); gw.valid(e); gw.next(e)) {
1.904 a+=flow->get(e);
1.905 }
1.906 return a;
1.907 @@ -1147,74 +650,77 @@
1.908 };
1.909
1.910
1.911 -
1.912 -
1.913 -
1.914 -
1.915 // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.916 -// class MaxFlow2 {
1.917 +// class MaxMatching {
1.918 // public:
1.919 // typedef typename Graph::Node Node;
1.920 +// typedef typename Graph::NodeIt NodeIt;
1.921 // typedef typename Graph::Edge Edge;
1.922 // typedef typename Graph::EdgeIt EdgeIt;
1.923 // typedef typename Graph::OutEdgeIt OutEdgeIt;
1.924 // typedef typename Graph::InEdgeIt InEdgeIt;
1.925 +
1.926 +// typedef typename Graph::NodeMap<bool> SMap;
1.927 +// typedef typename Graph::NodeMap<bool> TMap;
1.928 // private:
1.929 -// const Graph& G;
1.930 -// std::list<Node>& S;
1.931 -// std::list<Node>& T;
1.932 -// FlowMap& flow;
1.933 -// const CapacityMap& capacity;
1.934 +// const Graph* G;
1.935 +// SMap* S;
1.936 +// TMap* T;
1.937 +// //Node s;
1.938 +// //Node t;
1.939 +// FlowMap* flow;
1.940 +// const CapacityMap* capacity;
1.941 // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.942 // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.943 // typedef typename AugGraph::Edge AugEdge;
1.944 -// typename Graph::NodeMap<bool> SMap;
1.945 -// typename Graph::NodeMap<bool> TMap;
1.946 +// typename Graph::NodeMap<int> used; //0
1.947 +
1.948 // public:
1.949 -// MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
1.950 -// for(typename std::list<Node>::const_iterator i=S.begin();
1.951 -// i!=S.end(); ++i) {
1.952 -// SMap.set(*i, true);
1.953 -// }
1.954 -// for (typename std::list<Node>::const_iterator i=T.begin();
1.955 -// i!=T.end(); ++i) {
1.956 -// TMap.set(*i, true);
1.957 -// }
1.958 -// }
1.959 -// bool augment() {
1.960 -// AugGraph res_graph(G, flow, capacity);
1.961 +// MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
1.962 +// G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
1.963 +// bool augmentOnShortestPath() {
1.964 +// AugGraph res_graph(*G, *flow, *capacity);
1.965 // bool _augment=false;
1.966 -// Node reached_t_node;
1.967
1.968 // typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.969 -// BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1.970 -// for(typename std::list<Node>::const_iterator i=S.begin();
1.971 -// i!=S.end(); ++i) {
1.972 -// res_bfs.pushAndSetReached(*i);
1.973 +// BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
1.974 +// typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.975 +// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.976 +// if ((S->get(s)) && (used.get(s)<1) ) {
1.977 +// //Number u=0;
1.978 +// //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.979 +// //u+=flow->get(e);
1.980 +// //if (u<1) {
1.981 +// res_bfs.pushAndSetReached(s);
1.982 +// pred.set(s, AugEdge(INVALID));
1.983 +// //}
1.984 +// }
1.985 // }
1.986 -// //res_bfs.pushAndSetReached(s);
1.987 -
1.988 -// typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.989 -// //filled up with invalid iterators
1.990
1.991 // typename AugGraph::NodeMap<Number> free(res_graph);
1.992
1.993 +// Node n;
1.994 // //searching for augmenting path
1.995 // while ( !res_bfs.finished() ) {
1.996 -// AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
1.997 -// if (e.valid() && res_bfs.isBNodeNewlyReached()) {
1.998 +// AugOutEdgeIt e=res_bfs;
1.999 +// if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
1.1000 // Node v=res_graph.tail(e);
1.1001 // Node w=res_graph.head(e);
1.1002 // pred.set(w, e);
1.1003 -// if (pred.get(v).valid()) {
1.1004 -// free.set(w, std::min(free.get(v), e.free()));
1.1005 +// if (res_graph.valid(pred.get(v))) {
1.1006 +// free.set(w, std::min(free.get(v), res_graph.free(e)));
1.1007 // } else {
1.1008 -// free.set(w, e.free());
1.1009 +// free.set(w, res_graph.free(e));
1.1010 // }
1.1011 -// if (TMap.get(res_graph.head(e))) {
1.1012 -// _augment=true;
1.1013 -// reached_t_node=res_graph.head(e);
1.1014 -// break;
1.1015 +// n=res_graph.head(e);
1.1016 +// if (T->get(n) && (used.get(n)<1) ) {
1.1017 +// //Number u=0;
1.1018 +// //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.1019 +// //u+=flow->get(f);
1.1020 +// //if (u<1) {
1.1021 +// _augment=true;
1.1022 +// break;
1.1023 +// //}
1.1024 // }
1.1025 // }
1.1026
1.1027 @@ -1222,30 +728,287 @@
1.1028 // } //end of searching augmenting path
1.1029
1.1030 // if (_augment) {
1.1031 -// Node n=reached_t_node;
1.1032 -// Number augment_value=free.get(reached_t_node);
1.1033 -// while (pred.get(n).valid()) {
1.1034 +// //Node n=t;
1.1035 +// used.set(n, 1); //mind2 vegen jav
1.1036 +// Number augment_value=free.get(n);
1.1037 +// while (res_graph.valid(pred.get(n))) {
1.1038 // AugEdge e=pred.get(n);
1.1039 -// e.augment(augment_value);
1.1040 +// res_graph.augment(e, augment_value);
1.1041 // n=res_graph.tail(e);
1.1042 // }
1.1043 +// used.set(n, 1); //mind2 vegen jav
1.1044 // }
1.1045
1.1046 // return _augment;
1.1047 // }
1.1048 +
1.1049 +// // template<typename MutableGraph> bool augmentOnBlockingFlow() {
1.1050 +// // bool _augment=false;
1.1051 +
1.1052 +// // AugGraph res_graph(*G, *flow, *capacity);
1.1053 +
1.1054 +// // typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.1055 +// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
1.1056 +
1.1057 +
1.1058 +
1.1059 +
1.1060 +
1.1061 +// // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.1062 +// // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.1063 +// // if (S->get(s)) {
1.1064 +// // Number u=0;
1.1065 +// // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.1066 +// // u+=flow->get(e);
1.1067 +// // if (u<1) {
1.1068 +// // res_bfs.pushAndSetReached(s);
1.1069 +// // //pred.set(s, AugEdge(INVALID));
1.1070 +// // }
1.1071 +// // }
1.1072 +// // }
1.1073 +
1.1074 +
1.1075 +
1.1076 +
1.1077 +// // //bfs.pushAndSetReached(s);
1.1078 +// // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.1079 +// // while ( !bfs.finished() ) {
1.1080 +// // AugOutEdgeIt e=bfs;
1.1081 +// // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.1082 +// // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.1083 +// // }
1.1084 +
1.1085 +// // ++bfs;
1.1086 +// // } //computing distances from s in the residual graph
1.1087 +
1.1088 +// // MutableGraph F;
1.1089 +// // typename AugGraph::NodeMap<typename MutableGraph::Node>
1.1090 +// // res_graph_to_F(res_graph);
1.1091 +// // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.1092 +// // res_graph_to_F.set(n, F.addNode());
1.1093 +// // }
1.1094 +
1.1095 +// // typename MutableGraph::Node sF=res_graph_to_F.get(s);
1.1096 +// // typename MutableGraph::Node tF=res_graph_to_F.get(t);
1.1097 +
1.1098 +// // typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
1.1099 +// // typename MutableGraph::EdgeMap<Number> residual_capacity(F);
1.1100 +
1.1101 +// // //Making F to the graph containing the edges of the residual graph
1.1102 +// // //which are in some shortest paths
1.1103 +// // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
1.1104 +// // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
1.1105 +// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.1106 +// // original_edge.update();
1.1107 +// // original_edge.set(f, e);
1.1108 +// // residual_capacity.update();
1.1109 +// // residual_capacity.set(f, res_graph.free(e));
1.1110 +// // }
1.1111 +// // }
1.1112 +
1.1113 +// // bool __augment=true;
1.1114 +
1.1115 +// // while (__augment) {
1.1116 +// // __augment=false;
1.1117 +// // //computing blocking flow with dfs
1.1118 +// // typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
1.1119 +// // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
1.1120 +// // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
1.1121 +// // pred.set(sF, typename MutableGraph::Edge(INVALID));
1.1122 +// // //invalid iterators for sources
1.1123 +
1.1124 +// // typename MutableGraph::NodeMap<Number> free(F);
1.1125 +
1.1126 +// // dfs.pushAndSetReached(sF);
1.1127 +// // while (!dfs.finished()) {
1.1128 +// // ++dfs;
1.1129 +// // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
1.1130 +// // if (dfs.isBNodeNewlyReached()) {
1.1131 +// // typename MutableGraph::Node v=F.aNode(dfs);
1.1132 +// // typename MutableGraph::Node w=F.bNode(dfs);
1.1133 +// // pred.set(w, dfs);
1.1134 +// // if (F.valid(pred.get(v))) {
1.1135 +// // free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
1.1136 +// // } else {
1.1137 +// // free.set(w, residual_capacity.get(dfs));
1.1138 +// // }
1.1139 +// // if (w==tF) {
1.1140 +// // __augment=true;
1.1141 +// // _augment=true;
1.1142 +// // break;
1.1143 +// // }
1.1144 +
1.1145 +// // } else {
1.1146 +// // F.erase(typename MutableGraph::OutEdgeIt(dfs));
1.1147 +// // }
1.1148 +// // }
1.1149 +// // }
1.1150 +
1.1151 +// // if (__augment) {
1.1152 +// // typename MutableGraph::Node n=tF;
1.1153 +// // Number augment_value=free.get(tF);
1.1154 +// // while (F.valid(pred.get(n))) {
1.1155 +// // typename MutableGraph::Edge e=pred.get(n);
1.1156 +// // res_graph.augment(original_edge.get(e), augment_value);
1.1157 +// // n=F.tail(e);
1.1158 +// // if (residual_capacity.get(e)==augment_value)
1.1159 +// // F.erase(e);
1.1160 +// // else
1.1161 +// // residual_capacity.set(e, residual_capacity.get(e)-augment_value);
1.1162 +// // }
1.1163 +// // }
1.1164 +
1.1165 +// // }
1.1166 +
1.1167 +// // return _augment;
1.1168 +// // }
1.1169 +// bool augmentOnBlockingFlow2() {
1.1170 +// bool _augment=false;
1.1171 +
1.1172 +// //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
1.1173 +// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
1.1174 +// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
1.1175 +// typedef typename EAugGraph::Edge EAugEdge;
1.1176 +
1.1177 +// EAugGraph res_graph(*G, *flow, *capacity);
1.1178 +
1.1179 +// //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
1.1180 +// BfsIterator5<
1.1181 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
1.1182 +// /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
1.1183 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
1.1184 +
1.1185 +
1.1186 +// //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.1187 +// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.1188 +// if (S->get(s)) {
1.1189 +// Number u=0;
1.1190 +// for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.1191 +// u+=flow->get(e);
1.1192 +// if (u<1) {
1.1193 +// bfs.pushAndSetReached(s);
1.1194 +// //pred.set(s, AugEdge(INVALID));
1.1195 +// }
1.1196 +// }
1.1197 +// }
1.1198 +
1.1199 +
1.1200 +// //bfs.pushAndSetReached(s);
1.1201 +
1.1202 +// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
1.1203 +// NodeMap<int>& dist=res_graph.dist;
1.1204 +
1.1205 +// while ( !bfs.finished() ) {
1.1206 +// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1.1207 +// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.1208 +// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.1209 +// }
1.1210 +// ++bfs;
1.1211 +// } //computing distances from s in the residual graph
1.1212 +
1.1213 +// bool __augment=true;
1.1214 +
1.1215 +// while (__augment) {
1.1216 +
1.1217 +// __augment=false;
1.1218 +// //computing blocking flow with dfs
1.1219 +// typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
1.1220 +// DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
1.1221 +// dfs(res_graph);
1.1222 +// typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
1.1223 +// //pred.set(s, EAugEdge(INVALID));
1.1224 +// //invalid iterators for sources
1.1225 +
1.1226 +// typename EAugGraph::NodeMap<Number> free(res_graph);
1.1227 +
1.1228 +
1.1229 +// //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.1230 +// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.1231 +// if (S->get(s)) {
1.1232 +// Number u=0;
1.1233 +// for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.1234 +// u+=flow->get(e);
1.1235 +// if (u<1) {
1.1236 +// dfs.pushAndSetReached(s);
1.1237 +// //pred.set(s, AugEdge(INVALID));
1.1238 +// }
1.1239 +// }
1.1240 +// }
1.1241 +
1.1242 +
1.1243 +
1.1244 +// //dfs.pushAndSetReached(s);
1.1245 +// typename EAugGraph::Node n;
1.1246 +// while (!dfs.finished()) {
1.1247 +// ++dfs;
1.1248 +// if (res_graph.valid(EAugOutEdgeIt(dfs))) {
1.1249 +// if (dfs.isBNodeNewlyReached()) {
1.1250 +
1.1251 +// typename EAugGraph::Node v=res_graph.aNode(dfs);
1.1252 +// typename EAugGraph::Node w=res_graph.bNode(dfs);
1.1253 +
1.1254 +// pred.set(w, EAugOutEdgeIt(dfs));
1.1255 +// if (res_graph.valid(pred.get(v))) {
1.1256 +// free.set(w, std::min(free.get(v), res_graph.free(dfs)));
1.1257 +// } else {
1.1258 +// free.set(w, res_graph.free(dfs));
1.1259 +// }
1.1260 +
1.1261 +// n=w;
1.1262 +// if (T->get(w)) {
1.1263 +// Number u=0;
1.1264 +// for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.1265 +// u+=flow->get(f);
1.1266 +// if (u<1) {
1.1267 +// __augment=true;
1.1268 +// _augment=true;
1.1269 +// break;
1.1270 +// }
1.1271 +// }
1.1272 +// } else {
1.1273 +// res_graph.erase(dfs);
1.1274 +// }
1.1275 +// }
1.1276 +
1.1277 +// }
1.1278 +
1.1279 +// if (__augment) {
1.1280 +// // typename EAugGraph::Node n=t;
1.1281 +// Number augment_value=free.get(n);
1.1282 +// while (res_graph.valid(pred.get(n))) {
1.1283 +// EAugEdge e=pred.get(n);
1.1284 +// res_graph.augment(e, augment_value);
1.1285 +// n=res_graph.tail(e);
1.1286 +// if (res_graph.free(e)==0)
1.1287 +// res_graph.erase(e);
1.1288 +// }
1.1289 +// }
1.1290 +
1.1291 +// }
1.1292 +
1.1293 +// return _augment;
1.1294 +// }
1.1295 // void run() {
1.1296 -// while (augment()) { }
1.1297 +// //int num_of_augmentations=0;
1.1298 +// while (augmentOnShortestPath()) {
1.1299 +// //while (augmentOnBlockingFlow<MutableGraph>()) {
1.1300 +// //std::cout << ++num_of_augmentations << " ";
1.1301 +// //std::cout<<std::endl;
1.1302 +// }
1.1303 // }
1.1304 +// // template<typename MutableGraph> void run() {
1.1305 +// // //int num_of_augmentations=0;
1.1306 +// // //while (augmentOnShortestPath()) {
1.1307 +// // while (augmentOnBlockingFlow<MutableGraph>()) {
1.1308 +// // //std::cout << ++num_of_augmentations << " ";
1.1309 +// // //std::cout<<std::endl;
1.1310 +// // }
1.1311 +// // }
1.1312 // Number flowValue() {
1.1313 // Number a=0;
1.1314 -// for(typename std::list<Node>::const_iterator i=S.begin();
1.1315 -// i!=S.end(); ++i) {
1.1316 -// for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
1.1317 -// a+=flow.get(e);
1.1318 -// }
1.1319 -// for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
1.1320 -// a-=flow.get(e);
1.1321 -// }
1.1322 +// EdgeIt e;
1.1323 +// for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
1.1324 +// a+=flow->get(e);
1.1325 // }
1.1326 // return a;
1.1327 // }
1.1328 @@ -1253,6 +1016,110 @@
1.1329
1.1330
1.1331
1.1332 +
1.1333 +
1.1334 +
1.1335 +// // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.1336 +// // class MaxFlow2 {
1.1337 +// // public:
1.1338 +// // typedef typename Graph::Node Node;
1.1339 +// // typedef typename Graph::Edge Edge;
1.1340 +// // typedef typename Graph::EdgeIt EdgeIt;
1.1341 +// // typedef typename Graph::OutEdgeIt OutEdgeIt;
1.1342 +// // typedef typename Graph::InEdgeIt InEdgeIt;
1.1343 +// // private:
1.1344 +// // const Graph& G;
1.1345 +// // std::list<Node>& S;
1.1346 +// // std::list<Node>& T;
1.1347 +// // FlowMap& flow;
1.1348 +// // const CapacityMap& capacity;
1.1349 +// // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.1350 +// // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.1351 +// // typedef typename AugGraph::Edge AugEdge;
1.1352 +// // typename Graph::NodeMap<bool> SMap;
1.1353 +// // typename Graph::NodeMap<bool> TMap;
1.1354 +// // public:
1.1355 +// // MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
1.1356 +// // for(typename std::list<Node>::const_iterator i=S.begin();
1.1357 +// // i!=S.end(); ++i) {
1.1358 +// // SMap.set(*i, true);
1.1359 +// // }
1.1360 +// // for (typename std::list<Node>::const_iterator i=T.begin();
1.1361 +// // i!=T.end(); ++i) {
1.1362 +// // TMap.set(*i, true);
1.1363 +// // }
1.1364 +// // }
1.1365 +// // bool augment() {
1.1366 +// // AugGraph res_graph(G, flow, capacity);
1.1367 +// // bool _augment=false;
1.1368 +// // Node reached_t_node;
1.1369 +
1.1370 +// // typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.1371 +// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1.1372 +// // for(typename std::list<Node>::const_iterator i=S.begin();
1.1373 +// // i!=S.end(); ++i) {
1.1374 +// // res_bfs.pushAndSetReached(*i);
1.1375 +// // }
1.1376 +// // //res_bfs.pushAndSetReached(s);
1.1377 +
1.1378 +// // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.1379 +// // //filled up with invalid iterators
1.1380 +
1.1381 +// // typename AugGraph::NodeMap<Number> free(res_graph);
1.1382 +
1.1383 +// // //searching for augmenting path
1.1384 +// // while ( !res_bfs.finished() ) {
1.1385 +// // AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
1.1386 +// // if (e.valid() && res_bfs.isBNodeNewlyReached()) {
1.1387 +// // Node v=res_graph.tail(e);
1.1388 +// // Node w=res_graph.head(e);
1.1389 +// // pred.set(w, e);
1.1390 +// // if (pred.get(v).valid()) {
1.1391 +// // free.set(w, std::min(free.get(v), e.free()));
1.1392 +// // } else {
1.1393 +// // free.set(w, e.free());
1.1394 +// // }
1.1395 +// // if (TMap.get(res_graph.head(e))) {
1.1396 +// // _augment=true;
1.1397 +// // reached_t_node=res_graph.head(e);
1.1398 +// // break;
1.1399 +// // }
1.1400 +// // }
1.1401 +
1.1402 +// // ++res_bfs;
1.1403 +// // } //end of searching augmenting path
1.1404 +
1.1405 +// // if (_augment) {
1.1406 +// // Node n=reached_t_node;
1.1407 +// // Number augment_value=free.get(reached_t_node);
1.1408 +// // while (pred.get(n).valid()) {
1.1409 +// // AugEdge e=pred.get(n);
1.1410 +// // e.augment(augment_value);
1.1411 +// // n=res_graph.tail(e);
1.1412 +// // }
1.1413 +// // }
1.1414 +
1.1415 +// // return _augment;
1.1416 +// // }
1.1417 +// // void run() {
1.1418 +// // while (augment()) { }
1.1419 +// // }
1.1420 +// // Number flowValue() {
1.1421 +// // Number a=0;
1.1422 +// // for(typename std::list<Node>::const_iterator i=S.begin();
1.1423 +// // i!=S.end(); ++i) {
1.1424 +// // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
1.1425 +// // a+=flow.get(e);
1.1426 +// // }
1.1427 +// // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
1.1428 +// // a-=flow.get(e);
1.1429 +// // }
1.1430 +// // }
1.1431 +// // return a;
1.1432 +// // }
1.1433 +// // };
1.1434 +
1.1435 +
1.1436 } // namespace hugo
1.1437
1.1438 #endif //HUGO_EDMONDS_KARP_H
2.1 --- a/src/work/marci/edmonds_karp_demo.cc Tue Mar 30 13:37:21 2004 +0000
2.2 +++ b/src/work/marci/edmonds_karp_demo.cc Tue Mar 30 17:16:53 2004 +0000
2.3 @@ -9,6 +9,11 @@
2.4 #include <time_measure.h>
2.5 #include <graph_wrapper.h>
2.6
2.7 +class CM {
2.8 +public:
2.9 + template<typename T> int get(T) const {return 1;}
2.10 +};
2.11 +
2.12 using namespace hugo;
2.13
2.14 // Use a DIMACS max flow file as stdin.
2.15 @@ -86,14 +91,17 @@
2.16
2.17 {
2.18 //std::cout << "SmartGraph..." << std::endl;
2.19 + typedef TrivGraphWrapper<const Graph> GW;
2.20 + GW gw(G);
2.21 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
2.22 - Graph::EdgeMap<int> flow(G); //0 flow
2.23 + GW::EdgeMap<int> flow(G); //0 flow
2.24
2.25 Timer ts;
2.26 ts.reset();
2.27
2.28 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
2.29 - //max_flow_test.augmentWithBlockingFlow<Graph>();
2.30 + typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
2.31 + EMW cw(cap);
2.32 + MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(G, s, t, flow, cw);
2.33 int i=0;
2.34 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
2.35 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
2.36 @@ -113,72 +121,74 @@
2.37 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.38 }
2.39
2.40 +// {
2.41 +// //std::cout << "SmartGraph..." << std::endl;
2.42 +// std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
2.43 +// Graph::EdgeMap<int> flow(G); //0 flow
2.44 +
2.45 +// Timer ts;
2.46 +// ts.reset();
2.47 +
2.48 +// MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
2.49 +// int i=0;
2.50 +// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
2.51 +// // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
2.52 +// // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
2.53 +// // }
2.54 +// // std::cout<<std::endl;
2.55 +// ++i;
2.56 +// }
2.57 +
2.58 +// // std::cout << "maximum flow: "<< std::endl;
2.59 +// // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
2.60 +// // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
2.61 +// // }
2.62 +// // std::cout<<std::endl;
2.63 +// std::cout << "elapsed time: " << ts << std::endl;
2.64 +// std::cout << "number of augmentation phases: " << i << std::endl;
2.65 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.66 +// }
2.67 +
2.68 +// {
2.69 +// std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
2.70 +// Graph::EdgeMap<int> flow(G); //0 flow
2.71 +
2.72 +// Timer ts;
2.73 +// ts.reset();
2.74 +
2.75 +// MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
2.76 +// int i=0;
2.77 +// while (max_flow_test.augmentOnBlockingFlow2()) {
2.78 +// // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
2.79 +// // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
2.80 +// // }
2.81 +// // std::cout<<std::endl;
2.82 +// ++i;
2.83 +// }
2.84 +
2.85 +// // std::cout << "maximum flow: "<< std::endl;
2.86 +// // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
2.87 +// // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
2.88 +// // }
2.89 +// // std::cout<<std::endl;
2.90 +// std::cout << "elapsed time: " << ts << std::endl;
2.91 +// std::cout << "number of augmentation phases: " << i << std::endl;
2.92 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.93 +// }
2.94 +
2.95 {
2.96 - //std::cout << "SmartGraph..." << std::endl;
2.97 - std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
2.98 - Graph::EdgeMap<int> flow(G); //0 flow
2.99 + typedef TrivGraphWrapper<const Graph> GW;
2.100 + GW gw(G);
2.101 + std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
2.102 + GW::EdgeMap<int> flow(gw); //0 flow
2.103
2.104 Timer ts;
2.105 ts.reset();
2.106
2.107 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
2.108 - //max_flow_test.augmentWithBlockingFlow<Graph>();
2.109 - int i=0;
2.110 - while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
2.111 -// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
2.112 -// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
2.113 -// }
2.114 -// std::cout<<std::endl;
2.115 - ++i;
2.116 - }
2.117 -
2.118 -// std::cout << "maximum flow: "<< std::endl;
2.119 -// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
2.120 -// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
2.121 -// }
2.122 -// std::cout<<std::endl;
2.123 - std::cout << "elapsed time: " << ts << std::endl;
2.124 - std::cout << "number of augmentation phases: " << i << std::endl;
2.125 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.126 - }
2.127 -
2.128 - {
2.129 - std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
2.130 - Graph::EdgeMap<int> flow(G); //0 flow
2.131 -
2.132 - Timer ts;
2.133 - ts.reset();
2.134 -
2.135 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
2.136 - //max_flow_test.augmentWithBlockingFlow<Graph>();
2.137 - int i=0;
2.138 - while (max_flow_test.augmentOnBlockingFlow2()) {
2.139 -// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
2.140 -// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
2.141 -// }
2.142 -// std::cout<<std::endl;
2.143 - ++i;
2.144 - }
2.145 -
2.146 -// std::cout << "maximum flow: "<< std::endl;
2.147 -// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
2.148 -// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
2.149 -// }
2.150 -// std::cout<<std::endl;
2.151 - std::cout << "elapsed time: " << ts << std::endl;
2.152 - std::cout << "number of augmentation phases: " << i << std::endl;
2.153 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.154 - }
2.155 -
2.156 - {
2.157 - std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
2.158 - Graph::EdgeMap<int> flow(G); //0 flow
2.159 -
2.160 - Timer ts;
2.161 - ts.reset();
2.162 -
2.163 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
2.164 - //max_flow_test.augmentWithBlockingFlow<Graph>();
2.165 + //CM cm;
2.166 + typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
2.167 + EMW cw(cap);
2.168 + MaxFlow<GW, int, GW::EdgeMap<int>, EMW> max_flow_test(gw, s, t, flow, cw);
2.169 int i=0;
2.170 while (max_flow_test.augmentOnShortestPath()) {
2.171 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
3.1 --- a/src/work/marci/graph_wrapper.h Tue Mar 30 13:37:21 2004 +0000
3.2 +++ b/src/work/marci/graph_wrapper.h Tue Mar 30 17:16:53 2004 +0000
3.3 @@ -123,7 +123,7 @@
3.4
3.5 template<typename T> class NodeMap : public Graph::NodeMap<T> {
3.6 public:
3.7 - NodeMap(const TrivGraphWrapper<Graph>& _G) :
3.8 + NodeMap(const TrivGraphWrapper<Graph>& _G) :
3.9 Graph::NodeMap<T>(*(_G.graph)) { }
3.10 NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
3.11 Graph::NodeMap<T>(*(_G.graph), a) { }
3.12 @@ -131,11 +131,33 @@
3.13
3.14 template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
3.15 public:
3.16 - EdgeMap(const TrivGraphWrapper<Graph>& _G) :
3.17 + EdgeMap(const TrivGraphWrapper<Graph>& _G) :
3.18 Graph::EdgeMap<T>(*(_G.graph)) { }
3.19 EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
3.20 Graph::EdgeMap<T>(*(_G.graph), a) { }
3.21 };
3.22 +
3.23 + template<typename Map, typename T> class NodeMapWrapper {
3.24 + protected:
3.25 + Map* map;
3.26 + public:
3.27 + NodeMapWrapper(Map& _map) : map(&_map) { }
3.28 + //template<typename T>
3.29 + void set(Node n, T a) { map->set(n, a); }
3.30 + //template<typename T>
3.31 + T get(Node n) const { return map->get(n); }
3.32 + };
3.33 +
3.34 + template<typename Map, typename T> class EdgeMapWrapper {
3.35 + protected:
3.36 + Map* map;
3.37 + public:
3.38 + EdgeMapWrapper(Map& _map) : map(&_map) { }
3.39 + //template<typename T>
3.40 + void set(Edge n, T a) { map->set(n, a); }
3.41 + //template<typename T>
3.42 + T get(Edge n) const { return map->get(n); }
3.43 + };
3.44 };
3.45
3.46 template<typename GraphWrapper>
3.47 @@ -247,7 +269,7 @@
3.48
3.49 template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
3.50 public:
3.51 - NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
3.52 + NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
3.53 GraphWrapper::NodeMap<T>(_G.gw) { }
3.54 NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
3.55 GraphWrapper::NodeMap<T>(_G.gw, a) { }
3.56 @@ -255,7 +277,7 @@
3.57
3.58 template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
3.59 public:
3.60 - EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
3.61 + EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
3.62 GraphWrapper::EdgeMap<T>(_G.gw) { }
3.63 EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
3.64 GraphWrapper::EdgeMap<T>(_G.gw, a) { }
3.65 @@ -759,7 +781,7 @@
3.66
3.67 template<typename I> I& first(I& i) const { gw.first(i); return i; }
3.68 template<typename I, typename P> I& first(I& i, const P& p) const {
3.69 - graph->first(i, p); return i; }
3.70 + gw.first(i, p); return i; }
3.71
3.72 OutEdgeIt& next(OutEdgeIt& e) const {
3.73 if (e.out_or_in) {
3.74 @@ -911,26 +933,27 @@
3.75 // };
3.76
3.77
3.78 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
3.79 - class ResGraphWrapper {
3.80 + template<typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
3.81 + class ResGraphWrapper : public GraphWrapperSkeleton<GraphWrapper>{
3.82 public:
3.83 //typedef Graph BaseGraph;
3.84 - typedef TrivGraphWrapper<const Graph> GraphWrapper;
3.85 - typedef typename GraphWrapper::Node Node;
3.86 - typedef typename GraphWrapper::NodeIt NodeIt;
3.87 + //typedef TrivGraphWrapper<const Graph> GraphWrapper;
3.88 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
3.89 + typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
3.90 private:
3.91 - typedef typename GraphWrapper::OutEdgeIt OldOutEdgeIt;
3.92 - typedef typename GraphWrapper::InEdgeIt OldInEdgeIt;
3.93 + typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OldOutEdgeIt;
3.94 + typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt OldInEdgeIt;
3.95 protected:
3.96 //const Graph* graph;
3.97 - GraphWrapper gw;
3.98 + //GraphWrapper gw;
3.99 FlowMap* flow;
3.100 const CapacityMap* capacity;
3.101 public:
3.102
3.103 - ResGraphWrapper(const Graph& _G, FlowMap& _flow,
3.104 - const CapacityMap& _capacity) :
3.105 - gw(_G), flow(&_flow), capacity(&_capacity) { }
3.106 + ResGraphWrapper(const GraphWrapper& _gw, FlowMap& _flow,
3.107 + const CapacityMap& _capacity) :
3.108 + GraphWrapperSkeleton<GraphWrapper>(_gw),
3.109 + flow(&_flow), capacity(&_capacity) { }
3.110
3.111 //void setGraph(const Graph& _graph) { graph = &_graph; }
3.112 //const Graph& getGraph() const { return (*graph); }
3.113 @@ -941,7 +964,7 @@
3.114 friend class OutEdgeIt;
3.115
3.116 class Edge {
3.117 - friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
3.118 + friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
3.119 protected:
3.120 bool out_or_in; //true, iff out
3.121 OldOutEdgeIt out;
3.122 @@ -967,14 +990,14 @@
3.123
3.124
3.125 class OutEdgeIt : public Edge {
3.126 - friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
3.127 + friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
3.128 public:
3.129 OutEdgeIt() { }
3.130 //FIXME
3.131 OutEdgeIt(const Edge& e) : Edge(e) { }
3.132 OutEdgeIt(const Invalid& i) : Edge(i) { }
3.133 protected:
3.134 - OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
3.135 + OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
3.136 resG.gw.first(out, v);
3.137 while( resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
3.138 if (!resG.gw.valid(out)) {
3.139 @@ -1006,13 +1029,13 @@
3.140 typedef void InEdgeIt;
3.141
3.142 class EdgeIt : public Edge {
3.143 - friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
3.144 + friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
3.145 NodeIt v;
3.146 public:
3.147 EdgeIt() { }
3.148 //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
3.149 EdgeIt(const Invalid& i) : Edge(i) { }
3.150 - EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
3.151 + EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {
3.152 resG.gw.first(v);
3.153 if (resG.gw.valid(v)) resG.gw.first(out, v); else out=/*OldOutEdgeIt*/(INVALID);
3.154 while (resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
3.155 @@ -1066,7 +1089,7 @@
3.156 // }
3.157 };
3.158
3.159 - NodeIt& first(NodeIt& v) const { return gw.first(v); }
3.160 + NodeIt& first(NodeIt& v) const { gw.first(v); return v; }
3.161 OutEdgeIt& first(OutEdgeIt& e, Node v) const {
3.162 e=OutEdgeIt(*this, v);
3.163 return e;
3.164 @@ -1185,13 +1208,13 @@
3.165 return (flow->get(in));
3.166 }
3.167
3.168 - template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
3.169 - public:
3.170 - NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
3.171 - : GraphWrapper::NodeMap<T>(_G.gw) { }
3.172 - NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
3.173 - T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }
3.174 - };
3.175 +// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
3.176 +// public:
3.177 +// NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G)
3.178 +// : GraphWrapper::NodeMap<T>(_G.gw) { }
3.179 +// NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G,
3.180 +// T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }
3.181 +// };
3.182
3.183 // template <typename T>
3.184 // class NodeMap {
3.185 @@ -1207,8 +1230,8 @@
3.186 class EdgeMap {
3.187 typename GraphWrapper::EdgeMap<T> forward_map, backward_map;
3.188 public:
3.189 - EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }
3.190 - EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }
3.191 + EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }
3.192 + EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }
3.193 void set(Edge e, T a) {
3.194 if (e.out_or_in)
3.195 forward_map.set(e.out, a);
3.196 @@ -1224,243 +1247,243 @@
3.197 };
3.198 };
3.199
3.200 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
3.201 - class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
3.202 - protected:
3.203 - ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
3.204 - //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
3.205 - public:
3.206 - ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
3.207 - const CapacityMap& _capacity) :
3.208 - ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
3.209 - first_out_edges(*this) /*, dist(*this)*/ {
3.210 - for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
3.211 - OutEdgeIt e;
3.212 - ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
3.213 - first_out_edges.set(n, e);
3.214 - }
3.215 - }
3.216 +// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
3.217 +// class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
3.218 +// protected:
3.219 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
3.220 +// //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
3.221 +// public:
3.222 +// ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
3.223 +// const CapacityMap& _capacity) :
3.224 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
3.225 +// first_out_edges(*this) /*, dist(*this)*/ {
3.226 +// for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
3.227 +// OutEdgeIt e;
3.228 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
3.229 +// first_out_edges.set(n, e);
3.230 +// }
3.231 +// }
3.232
3.233 - //void setGraph(Graph& _graph) { graph = &_graph; }
3.234 - //Graph& getGraph() const { return (*graph); }
3.235 +// //void setGraph(Graph& _graph) { graph = &_graph; }
3.236 +// //Graph& getGraph() const { return (*graph); }
3.237
3.238 - //TrivGraphWrapper() : graph(0) { }
3.239 - //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
3.240 +// //TrivGraphWrapper() : graph(0) { }
3.241 +// //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
3.242
3.243 - //typedef Graph BaseGraph;
3.244 +// //typedef Graph BaseGraph;
3.245
3.246 - //typedef typename Graph::Node Node;
3.247 - //typedef typename Graph::NodeIt NodeIt;
3.248 +// //typedef typename Graph::Node Node;
3.249 +// //typedef typename Graph::NodeIt NodeIt;
3.250
3.251 - //typedef typename Graph::Edge Edge;
3.252 - //typedef typename Graph::OutEdgeIt OutEdgeIt;
3.253 - //typedef typename Graph::InEdgeIt InEdgeIt;
3.254 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
3.255 - //typedef typename Graph::EdgeIt EdgeIt;
3.256 +// //typedef typename Graph::Edge Edge;
3.257 +// //typedef typename Graph::OutEdgeIt OutEdgeIt;
3.258 +// //typedef typename Graph::InEdgeIt InEdgeIt;
3.259 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
3.260 +// //typedef typename Graph::EdgeIt EdgeIt;
3.261
3.262 - typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
3.263 - typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
3.264 +// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
3.265 +// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
3.266
3.267 - typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
3.268 - typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
3.269 - //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
3.270 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
3.271 - //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
3.272 +// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
3.273 +// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
3.274 +// //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
3.275 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
3.276 +// //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
3.277
3.278 - NodeIt& first(NodeIt& n) const {
3.279 - return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
3.280 - }
3.281 +// NodeIt& first(NodeIt& n) const {
3.282 +// return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
3.283 +// }
3.284
3.285 - OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
3.286 - e=first_out_edges.get(n);
3.287 - return e;
3.288 - }
3.289 +// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
3.290 +// e=first_out_edges.get(n);
3.291 +// return e;
3.292 +// }
3.293
3.294 - //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
3.295 - //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
3.296 - // return first(i, p); }
3.297 +// //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
3.298 +// //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
3.299 +// // return first(i, p); }
3.300
3.301 - //template<typename I> I getNext(const I& i) const {
3.302 - // return gw.getNext(i); }
3.303 - //template<typename I> I& next(I &i) const { return gw.next(i); }
3.304 +// //template<typename I> I getNext(const I& i) const {
3.305 +// // return gw.getNext(i); }
3.306 +// //template<typename I> I& next(I &i) const { return gw.next(i); }
3.307
3.308 - template< typename It > It first() const {
3.309 - It e; first(e); return e; }
3.310 +// template< typename It > It first() const {
3.311 +// It e; first(e); return e; }
3.312
3.313 - template< typename It > It first(const Node& v) const {
3.314 - It e; first(e, v); return e; }
3.315 +// template< typename It > It first(const Node& v) const {
3.316 +// It e; first(e, v); return e; }
3.317
3.318 - //Node head(const Edge& e) const { return gw.head(e); }
3.319 - //Node tail(const Edge& e) const { return gw.tail(e); }
3.320 +// //Node head(const Edge& e) const { return gw.head(e); }
3.321 +// //Node tail(const Edge& e) const { return gw.tail(e); }
3.322
3.323 - //template<typename I> bool valid(const I& i) const
3.324 - // { return gw.valid(i); }
3.325 +// //template<typename I> bool valid(const I& i) const
3.326 +// // { return gw.valid(i); }
3.327
3.328 - //int nodeNum() const { return gw.nodeNum(); }
3.329 - //int edgeNum() const { return gw.edgeNum(); }
3.330 +// //int nodeNum() const { return gw.nodeNum(); }
3.331 +// //int edgeNum() const { return gw.edgeNum(); }
3.332
3.333 - //template<typename I> Node aNode(const I& e) const {
3.334 - // return gw.aNode(e); }
3.335 - //template<typename I> Node bNode(const I& e) const {
3.336 - // return gw.bNode(e); }
3.337 +// //template<typename I> Node aNode(const I& e) const {
3.338 +// // return gw.aNode(e); }
3.339 +// //template<typename I> Node bNode(const I& e) const {
3.340 +// // return gw.bNode(e); }
3.341
3.342 - //Node addNode() const { return gw.addNode(); }
3.343 - //Edge addEdge(const Node& tail, const Node& head) const {
3.344 - // return gw.addEdge(tail, head); }
3.345 +// //Node addNode() const { return gw.addNode(); }
3.346 +// //Edge addEdge(const Node& tail, const Node& head) const {
3.347 +// // return gw.addEdge(tail, head); }
3.348
3.349 - //void erase(const OutEdgeIt& e) {
3.350 - // first_out_edge(this->tail(e))=e;
3.351 - //}
3.352 - void erase(const Edge& e) {
3.353 - OutEdgeIt f(e);
3.354 - next(f);
3.355 - first_out_edges.set(this->tail(e), f);
3.356 - }
3.357 - //template<typename I> void erase(const I& i) const { gw.erase(i); }
3.358 +// //void erase(const OutEdgeIt& e) {
3.359 +// // first_out_edge(this->tail(e))=e;
3.360 +// //}
3.361 +// void erase(const Edge& e) {
3.362 +// OutEdgeIt f(e);
3.363 +// next(f);
3.364 +// first_out_edges.set(this->tail(e), f);
3.365 +// }
3.366 +// //template<typename I> void erase(const I& i) const { gw.erase(i); }
3.367
3.368 - //void clear() const { gw.clear(); }
3.369 +// //void clear() const { gw.clear(); }
3.370
3.371 - template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
3.372 - public:
3.373 - NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
3.374 - ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
3.375 - NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
3.376 - ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
3.377 - };
3.378 +// template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
3.379 +// public:
3.380 +// NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
3.381 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
3.382 +// NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
3.383 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
3.384 +// };
3.385
3.386 - template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
3.387 - public:
3.388 - EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
3.389 - ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
3.390 - EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
3.391 - ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
3.392 - };
3.393 - };
3.394 +// template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
3.395 +// public:
3.396 +// EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
3.397 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
3.398 +// EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
3.399 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
3.400 +// };
3.401 +// };
3.402
3.403 - template<typename GraphWrapper>
3.404 - class FilterGraphWrapper {
3.405 - };
3.406 +// template<typename GraphWrapper>
3.407 +// class FilterGraphWrapper {
3.408 +// };
3.409
3.410 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
3.411 - class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
3.412 +// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
3.413 +// class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
3.414
3.415 - //Graph* graph;
3.416 +// //Graph* graph;
3.417
3.418 - public:
3.419 - //typedef Graph BaseGraph;
3.420 +// public:
3.421 +// //typedef Graph BaseGraph;
3.422
3.423 - typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
3.424 - typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
3.425 +// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
3.426 +// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
3.427
3.428 - typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
3.429 - typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
3.430 - //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
3.431 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
3.432 - typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
3.433 +// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
3.434 +// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
3.435 +// //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
3.436 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
3.437 +// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
3.438
3.439 - //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
3.440 +// //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
3.441
3.442 - public:
3.443 - FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
3.444 - const CapacityMap& _capacity) :
3.445 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {
3.446 - }
3.447 +// public:
3.448 +// FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
3.449 +// const CapacityMap& _capacity) :
3.450 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {
3.451 +// }
3.452
3.453 - OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
3.454 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
3.455 - while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
3.456 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
3.457 - return e;
3.458 - }
3.459 +// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
3.460 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
3.461 +// while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
3.462 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
3.463 +// return e;
3.464 +// }
3.465
3.466 - NodeIt& next(NodeIt& e) const {
3.467 - return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
3.468 - }
3.469 +// NodeIt& next(NodeIt& e) const {
3.470 +// return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
3.471 +// }
3.472
3.473 - OutEdgeIt& next(OutEdgeIt& e) const {
3.474 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
3.475 - while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))
3.476 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
3.477 - return e;
3.478 - }
3.479 +// OutEdgeIt& next(OutEdgeIt& e) const {
3.480 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
3.481 +// while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))
3.482 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
3.483 +// return e;
3.484 +// }
3.485
3.486 - NodeIt& first(NodeIt& n) const {
3.487 - return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
3.488 - }
3.489 +// NodeIt& first(NodeIt& n) const {
3.490 +// return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
3.491 +// }
3.492
3.493 - void erase(const Edge& e) {
3.494 - OutEdgeIt f(e);
3.495 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
3.496 - while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))
3.497 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
3.498 - first_out_edges.set(this->tail(e), f);
3.499 - }
3.500 +// void erase(const Edge& e) {
3.501 +// OutEdgeIt f(e);
3.502 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
3.503 +// while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))
3.504 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
3.505 +// first_out_edges.set(this->tail(e), f);
3.506 +// }
3.507
3.508 - //TrivGraphWrapper() : graph(0) { }
3.509 - //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
3.510 +// //TrivGraphWrapper() : graph(0) { }
3.511 +// //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
3.512
3.513 - //void setGraph(Graph& _graph) { graph = &_graph; }
3.514 - //Graph& getGraph() const { return (*graph); }
3.515 +// //void setGraph(Graph& _graph) { graph = &_graph; }
3.516 +// //Graph& getGraph() const { return (*graph); }
3.517
3.518 - //template<typename I> I& first(I& i) const { return gw.first(i); }
3.519 - //template<typename I, typename P> I& first(I& i, const P& p) const {
3.520 - // return gw.first(i, p); }
3.521 +// //template<typename I> I& first(I& i) const { return gw.first(i); }
3.522 +// //template<typename I, typename P> I& first(I& i, const P& p) const {
3.523 +// // return gw.first(i, p); }
3.524
3.525 - //template<typename I> I getNext(const I& i) const {
3.526 - // return gw.getNext(i); }
3.527 - //template<typename I> I& next(I &i) const { return gw.next(i); }
3.528 +// //template<typename I> I getNext(const I& i) const {
3.529 +// // return gw.getNext(i); }
3.530 +// //template<typename I> I& next(I &i) const { return gw.next(i); }
3.531
3.532 - template< typename It > It first() const {
3.533 - It e; first(e); return e; }
3.534 +// template< typename It > It first() const {
3.535 +// It e; first(e); return e; }
3.536
3.537 - template< typename It > It first(const Node& v) const {
3.538 - It e; first(e, v); return e; }
3.539 +// template< typename It > It first(const Node& v) const {
3.540 +// It e; first(e, v); return e; }
3.541
3.542 - //Node head(const Edge& e) const { return gw.head(e); }
3.543 - //Node tail(const Edge& e) const { return gw.tail(e); }
3.544 +// //Node head(const Edge& e) const { return gw.head(e); }
3.545 +// //Node tail(const Edge& e) const { return gw.tail(e); }
3.546
3.547 - //template<typename I> bool valid(const I& i) const
3.548 - // { return gw.valid(i); }
3.549 +// //template<typename I> bool valid(const I& i) const
3.550 +// // { return gw.valid(i); }
3.551
3.552 - //template<typename I> void setInvalid(const I &i);
3.553 - //{ return gw.setInvalid(i); }
3.554 +// //template<typename I> void setInvalid(const I &i);
3.555 +// //{ return gw.setInvalid(i); }
3.556
3.557 - //int nodeNum() const { return gw.nodeNum(); }
3.558 - //int edgeNum() const { return gw.edgeNum(); }
3.559 +// //int nodeNum() const { return gw.nodeNum(); }
3.560 +// //int edgeNum() const { return gw.edgeNum(); }
3.561
3.562 - //template<typename I> Node aNode(const I& e) const {
3.563 - // return gw.aNode(e); }
3.564 - //template<typename I> Node bNode(const I& e) const {
3.565 - // return gw.bNode(e); }
3.566 +// //template<typename I> Node aNode(const I& e) const {
3.567 +// // return gw.aNode(e); }
3.568 +// //template<typename I> Node bNode(const I& e) const {
3.569 +// // return gw.bNode(e); }
3.570
3.571 - //Node addNode() const { return gw.addNode(); }
3.572 - //Edge addEdge(const Node& tail, const Node& head) const {
3.573 - // return gw.addEdge(tail, head); }
3.574 +// //Node addNode() const { return gw.addNode(); }
3.575 +// //Edge addEdge(const Node& tail, const Node& head) const {
3.576 +// // return gw.addEdge(tail, head); }
3.577
3.578 - //template<typename I> void erase(const I& i) const { gw.erase(i); }
3.579 +// //template<typename I> void erase(const I& i) const { gw.erase(i); }
3.580
3.581 - //void clear() const { gw.clear(); }
3.582 +// //void clear() const { gw.clear(); }
3.583
3.584 - template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
3.585 - public:
3.586 - NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
3.587 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
3.588 - NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
3.589 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
3.590 - };
3.591 +// template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
3.592 +// public:
3.593 +// NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
3.594 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
3.595 +// NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
3.596 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
3.597 +// };
3.598
3.599 - template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
3.600 - public:
3.601 - EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
3.602 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
3.603 - EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
3.604 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
3.605 - };
3.606 +// template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
3.607 +// public:
3.608 +// EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
3.609 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
3.610 +// EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
3.611 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
3.612 +// };
3.613
3.614 - public:
3.615 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
3.616 +// public:
3.617 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
3.618
3.619 - };
3.620 +// };
3.621
3.622
3.623