src/work/marci/oldies/edmonds_karp.hh
author alpar
Mon, 21 Mar 2005 07:47:00 +0000
changeset 1229 aa65e46aebc3
permissions -rw-r--r--
Bugfix, thanks to Janos.
     1 #ifndef EDMONDS_KARP_HH
     2 #define EDMONDS_KARP_HH
     3 
     4 #include <algorithm>
     5 #include <list>
     6 #include <iterator>
     7 
     8 #include <bfs_iterator.hh>
     9 //#include <time_measure.h>
    10 
    11 namespace hugo {
    12 
    13   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    14   class ResGraph {
    15   public:
    16     typedef typename Graph::NodeIt NodeIt;
    17     typedef typename Graph::EachNodeIt EachNodeIt;
    18   private:
    19     typedef typename Graph::SymEdgeIt OldSymEdgeIt;
    20     const Graph& G;
    21     FlowMap& flow;
    22     const CapacityMap& capacity;
    23   public:
    24     ResGraph(const Graph& _G, FlowMap& _flow, 
    25 	     const CapacityMap& _capacity) : 
    26       G(_G), flow(_flow), capacity(_capacity) { }
    27 
    28     class EdgeIt; 
    29     class OutEdgeIt; 
    30     friend class EdgeIt; 
    31     friend class OutEdgeIt; 
    32 
    33     class EdgeIt {
    34       friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
    35     protected:
    36       const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
    37       OldSymEdgeIt sym;
    38     public:
    39       EdgeIt() { } 
    40       //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
    41       Number free() const { 
    42 	if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
    43 	  return (resG->capacity.get(sym)-resG->flow.get(sym)); 
    44 	} else { 
    45 	  return (resG->flow.get(sym)); 
    46 	}
    47       }
    48       bool valid() const { return sym.valid(); }
    49       void augment(Number a) const {
    50 	if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
    51 	  resG->flow.set(sym, resG->flow.get(sym)+a);
    52 	  //resG->flow[sym]+=a;
    53 	} else { 
    54 	  resG->flow.set(sym, resG->flow.get(sym)-a);
    55 	  //resG->flow[sym]-=a;
    56 	}
    57       }
    58     };
    59 
    60     class OutEdgeIt : public EdgeIt {
    61       friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
    62     public:
    63       OutEdgeIt() { }
    64       //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
    65     private:
    66       OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { 
    67       	resG=&_resG;
    68 	sym=resG->G.template first<OldSymEdgeIt>(v);
    69 	while( sym.valid() && !(free()>0) ) { ++sym; }
    70       }
    71     public:
    72       OutEdgeIt& operator++() { 
    73 	++sym; 
    74 	while( sym.valid() && !(free()>0) ) { ++sym; }
    75 	return *this; 
    76       }
    77     };
    78 
    79     void getFirst(OutEdgeIt& e, NodeIt v) const { 
    80       e=OutEdgeIt(*this, v); 
    81     }
    82     void getFirst(EachNodeIt& v) const { G.getFirst(v); }
    83     
    84     template< typename It >
    85     It first() const { 
    86       It e;      
    87       getFirst(e);
    88       return e; 
    89     }
    90 
    91     template< typename It >
    92     It first(NodeIt v) const { 
    93       It e;
    94       getFirst(e, v);
    95       return e; 
    96     }
    97 
    98     NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
    99     NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
   100 
   101     NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
   102     NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
   103 
   104     int id(NodeIt v) const { return G.id(v); }
   105 
   106     template <typename S>
   107     class NodeMap {
   108       typename Graph::NodeMap<S> node_map; 
   109     public:
   110       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
   111       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
   112       void set(NodeIt nit, S a) { node_map.set(nit, a); }
   113       S get(NodeIt nit) const { return node_map.get(nit); }
   114       S& operator[](NodeIt nit) { return node_map[nit]; } 
   115       const S& operator[](NodeIt nit) const { return node_map[nit]; } 
   116     };
   117 
   118   };
   119 
   120 
   121   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
   122   class ResGraph2 {
   123   public:
   124     typedef typename Graph::NodeIt NodeIt;
   125     typedef typename Graph::EachNodeIt EachNodeIt;
   126   private:
   127     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
   128     typedef typename Graph::OutEdgeIt OldOutEdgeIt;
   129     typedef typename Graph::InEdgeIt OldInEdgeIt;
   130     
   131     const Graph& G;
   132     FlowMap& flow;
   133     const CapacityMap& capacity;
   134   public:
   135     ResGraph2(const Graph& _G, FlowMap& _flow, 
   136 	     const CapacityMap& _capacity) : 
   137       G(_G), flow(_flow), capacity(_capacity) { }
   138 
   139     class EdgeIt; 
   140     class OutEdgeIt; 
   141     friend class EdgeIt; 
   142     friend class OutEdgeIt; 
   143 
   144     class EdgeIt {
   145       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
   146     protected:
   147       const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
   148       //OldSymEdgeIt sym;
   149       OldOutEdgeIt out;
   150       OldInEdgeIt in;
   151       bool out_or_in; //true, iff out
   152     public:
   153       EdgeIt() : out_or_in(true) { } 
   154       Number free() const { 
   155 	if (out_or_in) { 
   156 	  return (resG->capacity.get(out)-resG->flow.get(out)); 
   157 	} else { 
   158 	  return (resG->flow.get(in)); 
   159 	}
   160       }
   161       bool valid() const { 
   162 	return out_or_in && out.valid() || in.valid(); }
   163       void augment(Number a) const {
   164 	if (out_or_in) { 
   165 	  resG->flow.set(out, resG->flow.get(out)+a);
   166 	} else { 
   167 	  resG->flow.set(in, resG->flow.get(in)-a);
   168 	}
   169       }
   170     };
   171 
   172     class OutEdgeIt : public EdgeIt {
   173       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
   174     public:
   175       OutEdgeIt() { }
   176     private:
   177       OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { 
   178       	resG=&_resG;
   179 	out=resG->G.template first<OldOutEdgeIt>(v);
   180 	while( out.valid() && !(free()>0) ) { ++out; }
   181 	if (!out.valid()) {
   182 	  out_or_in=0;
   183 	  in=resG->G.template first<OldInEdgeIt>(v);
   184 	  while( in.valid() && !(free()>0) ) { ++in; }
   185 	}
   186       }
   187     public:
   188       OutEdgeIt& operator++() { 
   189 	if (out_or_in) {
   190 	  NodeIt v=resG->G.aNode(out);
   191 	  ++out;
   192 	  while( out.valid() && !(free()>0) ) { ++out; }
   193 	  if (!out.valid()) {
   194 	    out_or_in=0;
   195 	    in=resG->G.template first<OldInEdgeIt>(v);
   196 	    while( in.valid() && !(free()>0) ) { ++in; }
   197 	  }
   198 	} else {
   199 	  ++in;
   200 	  while( in.valid() && !(free()>0) ) { ++in; } 
   201 	}
   202 	return *this; 
   203       }
   204     };
   205 
   206     void getFirst(OutEdgeIt& e, NodeIt v) const { 
   207       e=OutEdgeIt(*this, v); 
   208     }
   209     void getFirst(EachNodeIt& v) const { G.getFirst(v); }
   210     
   211     template< typename It >
   212     It first() const { 
   213       It e;
   214       getFirst(e);
   215       return e; 
   216     }
   217 
   218     template< typename It >
   219     It first(NodeIt v) const { 
   220       It e;
   221       getFirst(e, v);
   222       return e; 
   223     }
   224 
   225     NodeIt tail(EdgeIt e) const { 
   226       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
   227     NodeIt head(EdgeIt e) const { 
   228       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
   229 
   230     NodeIt aNode(OutEdgeIt e) const { 
   231       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
   232     NodeIt bNode(OutEdgeIt e) const { 
   233       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
   234 
   235     int id(NodeIt v) const { return G.id(v); }
   236 
   237     template <typename S>
   238     class NodeMap {
   239       typename Graph::NodeMap<S> node_map; 
   240     public:
   241       NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
   242       NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
   243       void set(NodeIt nit, S a) { node_map.set(nit, a); }
   244       S get(NodeIt nit) const { return node_map.get(nit); }
   245     };
   246   };
   247 
   248 
   249   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
   250   class MaxFlow {
   251   public:
   252     typedef typename Graph::NodeIt NodeIt;
   253     typedef typename Graph::EdgeIt EdgeIt;
   254     typedef typename Graph::EachEdgeIt EachEdgeIt;
   255     typedef typename Graph::OutEdgeIt OutEdgeIt;
   256     typedef typename Graph::InEdgeIt InEdgeIt;
   257 
   258   private:
   259     const Graph* G;
   260     NodeIt s;
   261     NodeIt t;
   262     FlowMap* flow;
   263     const CapacityMap* capacity;
   264     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
   265     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
   266     typedef typename AugGraph::EdgeIt AugEdgeIt;
   267 
   268     //AugGraph res_graph;    
   269     //typedef typename AugGraph::NodeMap<bool> ReachedMap;
   270     //typename AugGraph::NodeMap<AugEdgeIt> pred; 
   271     //typename AugGraph::NodeMap<Number> free;
   272   public:
   273     MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : 
   274       G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //,  
   275       //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) 
   276       { }
   277     bool augmentOnShortestPath() {
   278       AugGraph res_graph(*G, *flow, *capacity);
   279       bool _augment=false;
   280       
   281       typedef typename AugGraph::NodeMap<bool> ReachedMap;
   282       BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
   283       res_bfs.pushAndSetReached(s);
   284 	
   285       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 
   286       //filled up with invalid iterators
   287       //pred.set(s, AugEdgeIt());
   288       
   289       typename AugGraph::NodeMap<Number> free(res_graph);
   290 	
   291       //searching for augmenting path
   292       while ( !res_bfs.finished() ) { 
   293 	AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
   294 	if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
   295 	  NodeIt v=res_graph.tail(e);
   296 	  NodeIt w=res_graph.head(e);
   297 	  pred.set(w, e);
   298 	  if (res_graph.valid(pred.get(v))) {
   299 	    free.set(w, std::min(free.get(v), res_graph.free(e)));
   300 	  } else {
   301 	    free.set(w, res_graph.free(e)); 
   302 	  }
   303 	  if (res_graph.head(e)==t) { _augment=true; break; }
   304 	}
   305 	
   306 	++res_bfs;
   307       } //end of searching augmenting path
   308 
   309       if (_augment) {
   310 	NodeIt n=t;
   311 	Number augment_value=free.get(t);
   312 	while (res_graph.valid(pred.get(n))) { 
   313 	  AugEdgeIt e=pred.get(n);
   314 	  res_graph.augment(e, augment_value); 
   315 	  //e.augment(augment_value); 
   316 	  n=res_graph.tail(e);
   317 	}
   318       }
   319 
   320       return _augment;
   321     }
   322 
   323     template<typename MutableGraph> bool augmentOnBlockingFlow() {
   324       bool _augment=false;
   325 
   326       AugGraph res_graph(*G, *flow, *capacity);
   327 
   328       typedef typename AugGraph::NodeMap<bool> ReachedMap;
   329       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
   330 
   331       bfs.pushAndSetReached(s);
   332       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
   333       while ( !bfs.finished() ) { 
   334 	AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
   335 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
   336 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
   337 	}
   338 	
   339 	++bfs;
   340       } //computing distances from s in the residual graph
   341 
   342       MutableGraph F;
   343       typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
   344       for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
   345 	res_graph_to_F.set(n, F.addNode());
   346       }
   347       
   348       typename MutableGraph::NodeIt sF=res_graph_to_F.get(s);
   349       typename MutableGraph::NodeIt tF=res_graph_to_F.get(t);
   350 
   351       typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);
   352       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
   353 
   354       //Making F to the graph containing the edges of the residual graph 
   355       //which are in some shortest paths
   356       for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
   357 	if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
   358 	  typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
   359 	  original_edge.update();
   360 	  original_edge.set(f, e);
   361 	  residual_capacity.update();
   362 	  residual_capacity.set(f, res_graph.free(e));
   363 	} 
   364       }
   365 
   366       bool __augment=true;
   367 
   368       while (__augment) {
   369 	__augment=false;
   370 	//computing blocking flow with dfs
   371 	typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
   372 	DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
   373 	typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators
   374 	typename MutableGraph::NodeMap<Number> free(F);
   375 
   376 	dfs.pushAndSetReached(sF);      
   377 	while (!dfs.finished()) {
   378 	  ++dfs;
   379 	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
   380 	    if (dfs.isBNodeNewlyReached()) {
   381 // 	      std::cout << "OutEdgeIt: " << dfs; 
   382 // 	      std::cout << " aNode: " << F.aNode(dfs); 
   383 // 	      std::cout << " bNode: " << F.bNode(dfs) << " ";
   384 	  
   385 	      typename MutableGraph::NodeIt v=F.aNode(dfs);
   386 	      typename MutableGraph::NodeIt w=F.bNode(dfs);
   387 	      pred.set(w, dfs);
   388 	      if (F.valid(pred.get(v))) {
   389 		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
   390 	      } else {
   391 		free.set(w, residual_capacity.get(dfs)); 
   392 	      }
   393 	      if (w==tF) { 
   394 		//std::cout << "AUGMENTATION"<<std::endl;
   395 		__augment=true; 
   396 		_augment=true;
   397 		break; 
   398 	      }
   399 	      
   400 	    } else {
   401 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));
   402 	    }
   403 	  } 
   404 	}
   405 
   406 	if (__augment) {
   407 	  typename MutableGraph::NodeIt n=tF;
   408 	  Number augment_value=free.get(tF);
   409 	  while (F.valid(pred.get(n))) { 
   410 	    typename MutableGraph::EdgeIt e=pred.get(n);
   411 	    res_graph.augment(original_edge.get(e), augment_value); 
   412 	    //original_edge.get(e).augment(augment_value); 
   413 	    n=F.tail(e);
   414 	    if (residual_capacity.get(e)==augment_value) 
   415 	      F.erase(e); 
   416 	    else 
   417 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);
   418 	  }
   419 	}
   420 	
   421       }
   422             
   423       return _augment;
   424     }
   425     bool augmentOnBlockingFlow2() {
   426       bool _augment=false;
   427 
   428       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
   429       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
   430       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
   431       typedef typename EAugGraph::EdgeIt EAugEdgeIt;
   432 
   433       EAugGraph res_graph(*G, *flow, *capacity);
   434 
   435       //std::cout << "meg jo1" << std::endl;
   436 
   437       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
   438       BfsIterator4< 
   439 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 
   440 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 
   441 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
   442       
   443       //std::cout << "meg jo2" << std::endl;
   444 
   445       bfs.pushAndSetReached(s);
   446       //std::cout << "meg jo2.5" << std::endl;
   447 
   448       //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
   449       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
   450 	NodeMap<int>& dist=res_graph.dist;
   451       //std::cout << "meg jo2.6" << std::endl;
   452 
   453       while ( !bfs.finished() ) {
   454 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
   455 //	EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
   456  	//if (res_graph.valid(e)) {
   457  	//    std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;
   458  	//}
   459 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
   460 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
   461 	}
   462 	
   463 	++bfs;	
   464       } //computing distances from s in the residual graph
   465 
   466 
   467       //std::cout << "meg jo3" << std::endl;
   468 
   469 //       typedef typename EAugGraph::EachNodeIt EAugEachNodeIt;
   470 //       for(EAugEachNodeIt n=res_graph.template first<EAugEachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
   471 // 	std::cout << "dist: " << dist.get(n) << std::endl;
   472 //       }
   473 
   474       bool __augment=true;
   475 
   476       while (__augment) {
   477 //	std::cout << "new iteration"<< std::endl;
   478 
   479 	__augment=false;
   480 	//computing blocking flow with dfs
   481 	typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
   482 	DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > 
   483 	  dfs(res_graph);
   484 	typename EAugGraph::NodeMap<EAugEdgeIt> pred(res_graph); //invalid iterators
   485 	typename EAugGraph::NodeMap<Number> free(res_graph);
   486 
   487 	dfs.pushAndSetReached(s);
   488 	while (!dfs.finished()) {
   489 	  ++dfs;
   490 	  if (res_graph.valid(EAugOutEdgeIt(dfs))) { 
   491 	    if (dfs.isBNodeNewlyReached()) {
   492 // 	      std::cout << "OutEdgeIt: " << dfs; 
   493 // 	      std::cout << " aNode: " << res_graph.aNode(dfs); 
   494 // 	      std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); 
   495 // 	      std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
   496 	  
   497 	      typename EAugGraph::NodeIt v=res_graph.aNode(dfs);
   498 	      typename EAugGraph::NodeIt w=res_graph.bNode(dfs);
   499 
   500 	      pred.set(w, EAugOutEdgeIt(dfs));
   501 
   502 	      //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;
   503 	      if (res_graph.valid(pred.get(v))) {
   504 		free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs))));
   505 	      } else {
   506 		free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs))); 
   507 	      }
   508 	      
   509 	      if (w==t) { 
   510 //		std::cout << "t is reached, AUGMENTATION"<<std::endl;
   511 		__augment=true; 
   512 		_augment=true;
   513 		break; 
   514 	      }
   515 	    } else {
   516 //	      std::cout << "<<DELETE ";
   517 //	      std::cout << " aNode: " << res_graph.aNode(dfs); 
   518 //	      std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); 
   519 //	      std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
   520 //	      std::cout << "DELETE>> ";
   521 
   522 	      res_graph.erase(dfs);
   523 	    }
   524 	  } 
   525 
   526 	}
   527 
   528 	if (__augment) {
   529 	  typename EAugGraph::NodeIt n=t;
   530 	  Number augment_value=free.get(t);
   531 //	  std::cout << "av:" << augment_value << std::endl;
   532 	  while (res_graph.valid(pred.get(n))) { 
   533 	    EAugEdgeIt e=pred.get(n);
   534 	    res_graph.augment(e, augment_value);
   535 	    //e.augment(augment_value); 
   536 	    n=res_graph.tail(e);
   537 	    if (res_graph.free(e)==0)
   538 	      res_graph.erase(e);
   539 	  }
   540 	}
   541       
   542       }
   543             
   544       return _augment;
   545     }
   546     void run() {
   547       //int num_of_augmentations=0;
   548       while (augmentOnShortestPath()) { 
   549 	//while (augmentOnBlockingFlow<MutableGraph>()) { 
   550 	//std::cout << ++num_of_augmentations << " ";
   551 	//std::cout<<std::endl;
   552       } 
   553     }
   554     template<typename MutableGraph> void run() {
   555       //int num_of_augmentations=0;
   556       //while (augmentOnShortestPath()) { 
   557 	while (augmentOnBlockingFlow<MutableGraph>()) { 
   558 	//std::cout << ++num_of_augmentations << " ";
   559 	//std::cout<<std::endl;
   560       } 
   561     }
   562     Number flowValue() { 
   563       Number a=0;
   564       OutEdgeIt e;
   565       for(G->getFirst(e, s); G->valid(e); G->next(e)) {
   566 	a+=flow->get(e);
   567       }
   568       return a;
   569     }
   570   };
   571 
   572   
   573 //   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
   574 //   class MaxFlow2 {
   575 //   public:
   576 //     typedef typename Graph::NodeIt NodeIt;
   577 //     typedef typename Graph::EdgeIt EdgeIt;
   578 //     typedef typename Graph::EachEdgeIt EachEdgeIt;
   579 //     typedef typename Graph::OutEdgeIt OutEdgeIt;
   580 //     typedef typename Graph::InEdgeIt InEdgeIt;
   581 //   private:
   582 //     const Graph& G;
   583 //     std::list<NodeIt>& S;
   584 //     std::list<NodeIt>& T;
   585 //     FlowMap& flow;
   586 //     const CapacityMap& capacity;
   587 //     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
   588 //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
   589 //     typedef typename AugGraph::EdgeIt AugEdgeIt;
   590 //     typename Graph::NodeMap<bool> SMap;
   591 //     typename Graph::NodeMap<bool> TMap;
   592 //   public:
   593 //     MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { 
   594 //       for(typename std::list<NodeIt>::const_iterator i=S.begin(); 
   595 // 	  i!=S.end(); ++i) { 
   596 // 	SMap.set(*i, true); 
   597 //       }
   598 //       for (typename std::list<NodeIt>::const_iterator i=T.begin(); 
   599 // 	   i!=T.end(); ++i) { 
   600 // 	TMap.set(*i, true); 
   601 //       }
   602 //     }
   603 //     bool augment() {
   604 //       AugGraph res_graph(G, flow, capacity);
   605 //       bool _augment=false;
   606 //       NodeIt reached_t_node;
   607       
   608 //       typedef typename AugGraph::NodeMap<bool> ReachedMap;
   609 //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
   610 //       for(typename std::list<NodeIt>::const_iterator i=S.begin(); 
   611 // 	  i!=S.end(); ++i) {
   612 // 	res_bfs.pushAndSetReached(*i);
   613 //       }
   614 //       //res_bfs.pushAndSetReached(s);
   615 	
   616 //       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 
   617 //       //filled up with invalid iterators
   618       
   619 //       typename AugGraph::NodeMap<Number> free(res_graph);
   620 	
   621 //       //searching for augmenting path
   622 //       while ( !res_bfs.finished() ) { 
   623 // 	AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
   624 // 	if (e.valid() && res_bfs.isBNodeNewlyReached()) {
   625 // 	  NodeIt v=res_graph.tail(e);
   626 // 	  NodeIt w=res_graph.head(e);
   627 // 	  pred.set(w, e);
   628 // 	  if (pred.get(v).valid()) {
   629 // 	    free.set(w, std::min(free.get(v), e.free()));
   630 // 	  } else {
   631 // 	    free.set(w, e.free()); 
   632 // 	  }
   633 // 	  if (TMap.get(res_graph.head(e))) { 
   634 // 	    _augment=true; 
   635 // 	    reached_t_node=res_graph.head(e);
   636 // 	    break; 
   637 // 	  }
   638 // 	}
   639 	
   640 // 	++res_bfs;
   641 //       } //end of searching augmenting path
   642 
   643 //       if (_augment) {
   644 // 	NodeIt n=reached_t_node;
   645 // 	Number augment_value=free.get(reached_t_node);
   646 // 	while (pred.get(n).valid()) { 
   647 // 	  AugEdgeIt e=pred.get(n);
   648 // 	  e.augment(augment_value); 
   649 // 	  n=res_graph.tail(e);
   650 // 	}
   651 //       }
   652 
   653 //       return _augment;
   654 //     }
   655 //     void run() {
   656 //       while (augment()) { } 
   657 //     }
   658 //     Number flowValue() { 
   659 //       Number a=0;
   660 //       for(typename std::list<NodeIt>::const_iterator i=S.begin(); 
   661 // 	  i!=S.end(); ++i) { 
   662 // 	for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
   663 // 	  a+=flow.get(e);
   664 // 	}
   665 // 	for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
   666 // 	  a-=flow.get(e);
   667 // 	}
   668 //       }
   669 //       return a;
   670 //     }
   671 //   };
   672 
   673 
   674 
   675 } // namespace hugo
   676 
   677 #endif //EDMONDS_KARP_HH