Mercuriallemon-0.x / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/edmonds_karp.h
author marci
Wed, 17 Mar 2004 15:41:00 +0000
changeset 195 19f8bd411014
parent 193 84c19824322a
child 196 8a9b9360463e
permissions -rw-r--r--
. 
     1 // -*- c++ -*-

     2 #ifndef EDMONDS_KARP_H

     3 #define EDMONDS_KARP_H

     4 

     5 #include <algorithm>

     6 #include <list>

     7 #include <iterator>

     8 

     9 #include <bfs_iterator.h>

    10 #include <invalid.h>

    11 

    12 namespace hugo {

    13 

    14   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>

    15   class ResGraph {

    16   public:

    17     typedef typename Graph::Node Node;

    18     typedef typename Graph::NodeIt NodeIt;

    19   private:

    20     typedef typename Graph::SymEdgeIt OldSymEdgeIt;

    21     const Graph& G;

    22     FlowMap& flow;

    23     const CapacityMap& capacity;

    24   public:

    25     ResGraph(const Graph& _G, FlowMap& _flow, 

    26 	     const CapacityMap& _capacity) : 

    27       G(_G), flow(_flow), capacity(_capacity) { }

    28 

    29     class Edge; 

    30     class OutEdgeIt; 

    31     friend class Edge; 

    32     friend class OutEdgeIt; 

    33 

    34     class Edge {

    35       friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;

    36     protected:

    37       const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;

    38       OldSymEdgeIt sym;

    39     public:

    40       Edge() { } 

    41       //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }

    42       Number free() const { 

    43 	if (resG->G.aNode(sym)==resG->G.tail(sym)) { 

    44 	  return (resG->capacity.get(sym)-resG->flow.get(sym)); 

    45 	} else { 

    46 	  return (resG->flow.get(sym)); 

    47 	}

    48       }

    49       bool valid() const { return sym.valid(); }

    50       void augment(Number a) const {

    51 	if (resG->G.aNode(sym)==resG->G.tail(sym)) { 

    52 	  resG->flow.set(sym, resG->flow.get(sym)+a);

    53 	  //resG->flow[sym]+=a;

    54 	} else { 

    55 	  resG->flow.set(sym, resG->flow.get(sym)-a);

    56 	  //resG->flow[sym]-=a;

    57 	}

    58       }

    59     };

    60 

    61     class OutEdgeIt : public Edge {

    62       friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;

    63     public:

    64       OutEdgeIt() { }

    65       //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }

    66     private:

    67       OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) { 

    68       	resG=&_resG;

    69 	sym=resG->G.template first<OldSymEdgeIt>(v);

    70 	while( sym.valid() && !(free()>0) ) { ++sym; }

    71       }

    72     public:

    73       OutEdgeIt& operator++() { 

    74 	++sym; 

    75 	while( sym.valid() && !(free()>0) ) { ++sym; }

    76 	return *this; 

    77       }

    78     };

    79 

    80     void /*getF*/first(OutEdgeIt& e, Node v) const { 

    81       e=OutEdgeIt(*this, v); 

    82     }

    83     void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }

    84     

    85     template< typename It >

    86     It first() const { 

    87       It e;      

    88       /*getF*/first(e);

    89       return e; 

    90     }

    91 

    92     template< typename It >

    93     It first(Node v) const { 

    94       It e;

    95       /*getF*/first(e, v);

    96       return e; 

    97     }

    98 

    99     Node tail(Edge e) const { return G.aNode(e.sym); }

   100     Node head(Edge e) const { return G.bNode(e.sym); }

   101 

   102     Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }

   103     Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }

   104 

   105     int id(Node v) const { return G.id(v); }

   106 

   107     template <typename S>

   108     class NodeMap {

   109       typename Graph::NodeMap<S> node_map; 

   110     public:

   111       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }

   112       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }

   113       void set(Node nit, S a) { node_map.set(nit, a); }

   114       S get(Node nit) const { return node_map.get(nit); }

   115       S& operator[](Node nit) { return node_map[nit]; } 

   116       const S& operator[](Node nit) const { return node_map[nit]; } 

   117     };

   118 

   119   };

   120 

   121 

   122   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>

   123   class ResGraph2 {

   124   public:

   125     typedef typename Graph::Node Node;

   126     typedef typename Graph::NodeIt NodeIt;

   127   private:

   128     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;

   129     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   130     typedef typename Graph::InEdgeIt OldInEdgeIt;

   131     

   132     const Graph& G;

   133     FlowMap& flow;

   134     const CapacityMap& capacity;

   135   public:

   136     ResGraph2(const Graph& _G, FlowMap& _flow, 

   137 	     const CapacityMap& _capacity) : 

   138       G(_G), flow(_flow), capacity(_capacity) { }

   139 

   140     class Edge; 

   141     class OutEdgeIt; 

   142     friend class Edge; 

   143     friend class OutEdgeIt; 

   144 

   145     class Edge {

   146       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;

   147     protected:

   148       const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;

   149       //OldSymEdgeIt sym;

   150       OldOutEdgeIt out;

   151       OldInEdgeIt in;

   152       bool out_or_in; //true, iff out

   153     public:

   154       Edge() : out_or_in(true) { } 

   155       Number free() const { 

   156 	if (out_or_in) { 

   157 	  return (resG->capacity.get(out)-resG->flow.get(out)); 

   158 	} else { 

   159 	  return (resG->flow.get(in)); 

   160 	}

   161       }

   162       bool valid() const { 

   163 	return out_or_in && out.valid() || in.valid(); }

   164       void augment(Number a) const {

   165 	if (out_or_in) { 

   166 	  resG->flow.set(out, resG->flow.get(out)+a);

   167 	} else { 

   168 	  resG->flow.set(in, resG->flow.get(in)-a);

   169 	}

   170       }

   171     };

   172 

   173     class OutEdgeIt : public Edge {

   174       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;

   175     public:

   176       OutEdgeIt() { }

   177     private:

   178       OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) { 

   179       	resG=&_resG;

   180 	out=resG->G.template first<OldOutEdgeIt>(v);

   181 	while( out.valid() && !(free()>0) ) { ++out; }

   182 	if (!out.valid()) {

   183 	  out_or_in=0;

   184 	  in=resG->G.template first<OldInEdgeIt>(v);

   185 	  while( in.valid() && !(free()>0) ) { ++in; }

   186 	}

   187       }

   188     public:

   189       OutEdgeIt& operator++() { 

   190 	if (out_or_in) {

   191 	  Node v=resG->G.aNode(out);

   192 	  ++out;

   193 	  while( out.valid() && !(free()>0) ) { ++out; }

   194 	  if (!out.valid()) {

   195 	    out_or_in=0;

   196 	    in=resG->G.template first<OldInEdgeIt>(v);

   197 	    while( in.valid() && !(free()>0) ) { ++in; }

   198 	  }

   199 	} else {

   200 	  ++in;

   201 	  while( in.valid() && !(free()>0) ) { ++in; } 

   202 	}

   203 	return *this; 

   204       }

   205     };

   206 

   207     void /*getF*/first(OutEdgeIt& e, Node v) const { 

   208       e=OutEdgeIt(*this, v); 

   209     }

   210     void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }

   211     

   212     template< typename It >

   213     It first() const { 

   214       It e;

   215       /*getF*/first(e);

   216       return e; 

   217     }

   218 

   219     template< typename It >

   220     It first(Node v) const { 

   221       It e;

   222       /*getF*/first(e, v);

   223       return e; 

   224     }

   225 

   226     Node tail(Edge e) const { 

   227       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }

   228     Node head(Edge e) const { 

   229       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }

   230 

   231     Node aNode(OutEdgeIt e) const { 

   232       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }

   233     Node bNode(OutEdgeIt e) const { 

   234       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }

   235 

   236     int id(Node v) const { return G.id(v); }

   237 

   238     template <typename S>

   239     class NodeMap {

   240       typename Graph::NodeMap<S> node_map; 

   241     public:

   242       NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }

   243       NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }

   244       void set(Node nit, S a) { node_map.set(nit, a); }

   245       S get(Node nit) const { return node_map.get(nit); }

   246     };

   247   };

   248 

   249 

   250   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>

   251   class MaxFlow {

   252   public:

   253     typedef typename Graph::Node Node;

   254     typedef typename Graph::Edge Edge;

   255     typedef typename Graph::EdgeIt EdgeIt;

   256     typedef typename Graph::OutEdgeIt OutEdgeIt;

   257     typedef typename Graph::InEdgeIt InEdgeIt;

   258 

   259   private:

   260     const Graph* G;

   261     Node s;

   262     Node t;

   263     FlowMap* flow;

   264     const CapacityMap* capacity;

   265     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;

   266     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   267     typedef typename AugGraph::Edge AugEdge;

   268 

   269   public:

   270     MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : 

   271       G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }

   272     bool augmentOnShortestPath() {

   273       AugGraph res_graph(*G, *flow, *capacity);

   274       bool _augment=false;

   275       

   276       typedef typename AugGraph::NodeMap<bool> ReachedMap;

   277       BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);

   278       res_bfs.pushAndSetReached(s);

   279 	

   280       typename AugGraph::NodeMap<AugEdge> pred(res_graph); 

   281       pred.set(s, AugEdge(INVALID));

   282       

   283       typename AugGraph::NodeMap<Number> free(res_graph);

   284 	

   285       //searching for augmenting path

   286       while ( !res_bfs.finished() ) { 

   287 	AugOutEdgeIt e=res_bfs;

   288 	if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {

   289 	  Node v=res_graph.tail(e);

   290 	  Node w=res_graph.head(e);

   291 	  pred.set(w, e);

   292 	  if (res_graph.valid(pred.get(v))) {

   293 	    free.set(w, std::min(free.get(v), res_graph.free(e)));

   294 	  } else {

   295 	    free.set(w, res_graph.free(e)); 

   296 	  }

   297 	  if (res_graph.head(e)==t) { _augment=true; break; }

   298 	}

   299 	

   300 	++res_bfs;

   301       } //end of searching augmenting path

   302 

   303       if (_augment) {

   304 	Node n=t;

   305 	Number augment_value=free.get(t);

   306 	while (res_graph.valid(pred.get(n))) { 

   307 	  AugEdge e=pred.get(n);

   308 	  res_graph.augment(e, augment_value); 

   309 	  n=res_graph.tail(e);

   310 	}

   311       }

   312 

   313       return _augment;

   314     }

   315 

   316     template<typename MutableGraph> bool augmentOnBlockingFlow() {      

   317       bool _augment=false;

   318 

   319       AugGraph res_graph(*G, *flow, *capacity);

   320 

   321       typedef typename AugGraph::NodeMap<bool> ReachedMap;

   322       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);

   323 

   324       bfs.pushAndSetReached(s);

   325       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's

   326       while ( !bfs.finished() ) { 

   327 	AugOutEdgeIt e=bfs;

   328 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {

   329 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);

   330 	}

   331 	

   332 	++bfs;

   333       } //computing distances from s in the residual graph

   334 

   335       MutableGraph F;

   336       typename AugGraph::NodeMap<typename MutableGraph::Node> 

   337 	res_graph_to_F(res_graph);

   338       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {

   339 	res_graph_to_F.set(n, F.addNode());

   340       }

   341       

   342       typename MutableGraph::Node sF=res_graph_to_F.get(s);

   343       typename MutableGraph::Node tF=res_graph_to_F.get(t);

   344 

   345       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);

   346       typename MutableGraph::EdgeMap<Number> residual_capacity(F);

   347 

   348       //Making F to the graph containing the edges of the residual graph 

   349       //which are in some shortest paths

   350       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {

   351 	if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {

   352 	  typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));

   353 	  original_edge.update();

   354 	  original_edge.set(f, e);

   355 	  residual_capacity.update();

   356 	  residual_capacity.set(f, res_graph.free(e));

   357 	} 

   358       }

   359 

   360       bool __augment=true;

   361 

   362       while (__augment) {

   363 	__augment=false;

   364 	//computing blocking flow with dfs

   365 	typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;

   366 	DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);

   367 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);

   368 	pred.set(sF, typename MutableGraph::Edge(INVALID));

   369 	//invalid iterators for sources

   370 

   371 	typename MutableGraph::NodeMap<Number> free(F);

   372 

   373 	dfs.pushAndSetReached(sF);      

   374 	while (!dfs.finished()) {

   375 	  ++dfs;

   376 	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {

   377 	    if (dfs.isBNodeNewlyReached()) {

   378 	      typename MutableGraph::Node v=F.aNode(dfs);

   379 	      typename MutableGraph::Node w=F.bNode(dfs);

   380 	      pred.set(w, dfs);

   381 	      if (F.valid(pred.get(v))) {

   382 		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));

   383 	      } else {

   384 		free.set(w, residual_capacity.get(dfs)); 

   385 	      }

   386 	      if (w==tF) { 

   387 		__augment=true; 

   388 		_augment=true;

   389 		break; 

   390 	      }

   391 	      

   392 	    } else {

   393 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));

   394 	    }

   395 	  } 

   396 	}

   397 

   398 	if (__augment) {

   399 	  typename MutableGraph::Node n=tF;

   400 	  Number augment_value=free.get(tF);

   401 	  while (F.valid(pred.get(n))) { 

   402 	    typename MutableGraph::Edge e=pred.get(n);

   403 	    res_graph.augment(original_edge.get(e), augment_value); 

   404 	    n=F.tail(e);

   405 	    if (residual_capacity.get(e)==augment_value) 

   406 	      F.erase(e); 

   407 	    else 

   408 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);

   409 	  }

   410 	}

   411 	

   412       }

   413             

   414       return _augment;

   415     }

   416     bool augmentOnBlockingFlow2() {

   417       bool _augment=false;

   418 

   419       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;

   420       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;

   421       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;

   422       typedef typename EAugGraph::Edge EAugEdge;

   423 

   424       EAugGraph res_graph(*G, *flow, *capacity);

   425 

   426       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;

   427       BfsIterator4< 

   428 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 

   429 	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 

   430 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);

   431       

   432       bfs.pushAndSetReached(s);

   433 

   434       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::

   435 	NodeMap<int>& dist=res_graph.dist;

   436 

   437       while ( !bfs.finished() ) {

   438 	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;

   439 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {

   440 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);

   441 	}

   442 	++bfs;	

   443       } //computing distances from s in the residual graph

   444 

   445       bool __augment=true;

   446 

   447       while (__augment) {

   448 

   449 	__augment=false;

   450 	//computing blocking flow with dfs

   451 	typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;

   452 	DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > 

   453 	  dfs(res_graph);

   454 	typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); 

   455 	pred.set(s, EAugEdge(INVALID));

   456 	//invalid iterators for sources

   457 

   458 	typename EAugGraph::NodeMap<Number> free(res_graph);

   459 

   460 	dfs.pushAndSetReached(s);

   461 	while (!dfs.finished()) {

   462 	  ++dfs;

   463 	  if (res_graph.valid(EAugOutEdgeIt(dfs))) { 

   464 	    if (dfs.isBNodeNewlyReached()) {

   465 	  

   466 	      typename EAugGraph::Node v=res_graph.aNode(dfs);

   467 	      typename EAugGraph::Node w=res_graph.bNode(dfs);

   468 

   469 	      pred.set(w, EAugOutEdgeIt(dfs));

   470 	      if (res_graph.valid(pred.get(v))) {

   471 		free.set(w, std::min(free.get(v), res_graph.free(dfs)));

   472 	      } else {

   473 		free.set(w, res_graph.free(dfs)); 

   474 	      }

   475 	      

   476 	      if (w==t) { 

   477 		__augment=true; 

   478 		_augment=true;

   479 		break; 

   480 	      }

   481 	    } else {

   482 	      res_graph.erase(dfs);

   483 	    }

   484 	  } 

   485 

   486 	}

   487 

   488 	if (__augment) {

   489 	  typename EAugGraph::Node n=t;

   490 	  Number augment_value=free.get(t);

   491 	  while (res_graph.valid(pred.get(n))) { 

   492 	    EAugEdge e=pred.get(n);

   493 	    res_graph.augment(e, augment_value);

   494 	    n=res_graph.tail(e);

   495 	    if (res_graph.free(e)==0)

   496 	      res_graph.erase(e);

   497 	  }

   498 	}

   499       

   500       }

   501             

   502       return _augment;

   503     }

   504     void run() {

   505       //int num_of_augmentations=0;

   506       while (augmentOnShortestPath()) { 

   507 	//while (augmentOnBlockingFlow<MutableGraph>()) { 

   508 	//std::cout << ++num_of_augmentations << " ";

   509 	//std::cout<<std::endl;

   510       } 

   511     }

   512     template<typename MutableGraph> void run() {

   513       //int num_of_augmentations=0;

   514       //while (augmentOnShortestPath()) { 

   515 	while (augmentOnBlockingFlow<MutableGraph>()) { 

   516 	//std::cout << ++num_of_augmentations << " ";

   517 	//std::cout<<std::endl;

   518       } 

   519     }

   520     Number flowValue() { 

   521       Number a=0;

   522       OutEdgeIt e;

   523       for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) {

   524 	a+=flow->get(e);

   525       }

   526       return a;

   527     }

   528   };

   529 

   530 

   531   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>

   532   class MaxMatching {

   533   public:

   534     typedef typename Graph::Node Node;

   535     typedef typename Graph::NodeIt NodeIt;

   536     typedef typename Graph::Edge Edge;

   537     typedef typename Graph::EdgeIt EdgeIt;

   538     typedef typename Graph::OutEdgeIt OutEdgeIt;

   539     typedef typename Graph::InEdgeIt InEdgeIt;

   540 

   541     typedef typename Graph::NodeMap<bool> SMap;

   542     typedef typename Graph::NodeMap<bool> TMap;

   543   private:

   544     const Graph* G;

   545     SMap* S;

   546     TMap* T;

   547     //Node s;

   548     //Node t;

   549     FlowMap* flow;

   550     const CapacityMap* capacity;

   551     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;

   552     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   553     typedef typename AugGraph::Edge AugEdge;

   554 

   555   public:

   556     MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : 

   557       G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity) { }

   558     bool augmentOnShortestPath() {

   559       AugGraph res_graph(*G, *flow, *capacity);

   560       bool _augment=false;

   561       

   562       typedef typename AugGraph::NodeMap<bool> ReachedMap;

   563       BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);

   564       typename AugGraph::NodeMap<AugEdge> pred(res_graph); 

   565       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {

   566 	Number f=0;

   567 	for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))

   568 	  f+=flow->get(e);

   569 	if (f<1) {

   570 	  res_bfs.pushAndSetReached(s);

   571 	  pred.set(s, AugEdge(INVALID));

   572 	}

   573       }

   574       

   575       typename AugGraph::NodeMap<Number> free(res_graph);

   576 	

   577       Node n;

   578       //searching for augmenting path

   579       while ( !res_bfs.finished() ) { 

   580 	AugOutEdgeIt e=res_bfs;

   581 	if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {

   582 	  Node v=res_graph.tail(e);

   583 	  Node w=res_graph.head(e);

   584 	  pred.set(w, e);

   585 	  if (res_graph.valid(pred.get(v))) {

   586 	    free.set(w, std::min(free.get(v), res_graph.free(e)));

   587 	  } else {

   588 	    free.set(w, res_graph.free(e)); 

   589 	  }

   590 	  if (T->get(res_graph.head(e))) { 

   591 	    n=res_graph.head(e);

   592 	    _augment=true; 

   593 	    break; 

   594 	  }

   595 	}

   596 	

   597 	++res_bfs;

   598       } //end of searching augmenting path

   599 

   600       if (_augment) {

   601 	//Node n=t;

   602 	Number augment_value=free.get(n);

   603 	while (res_graph.valid(pred.get(n))) { 

   604 	  AugEdge e=pred.get(n);

   605 	  res_graph.augment(e, augment_value); 

   606 	  n=res_graph.tail(e);

   607 	}

   608       }

   609 

   610       return _augment;

   611     }

   612 

   613 //     template<typename MutableGraph> bool augmentOnBlockingFlow() {      

   614 //       bool _augment=false;

   615 

   616 //       AugGraph res_graph(*G, *flow, *capacity);

   617 

   618 //       typedef typename AugGraph::NodeMap<bool> ReachedMap;

   619 //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);

   620 

   621 //       bfs.pushAndSetReached(s);

   622 //       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's

   623 //       while ( !bfs.finished() ) { 

   624 // 	AugOutEdgeIt e=bfs;

   625 // 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {

   626 // 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);

   627 // 	}

   628 	

   629 // 	++bfs;

   630 //       } //computing distances from s in the residual graph

   631 

   632 //       MutableGraph F;

   633 //       typename AugGraph::NodeMap<typename MutableGraph::Node> 

   634 // 	res_graph_to_F(res_graph);

   635 //       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {

   636 // 	res_graph_to_F.set(n, F.addNode());

   637 //       }

   638       

   639 //       typename MutableGraph::Node sF=res_graph_to_F.get(s);

   640 //       typename MutableGraph::Node tF=res_graph_to_F.get(t);

   641 

   642 //       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);

   643 //       typename MutableGraph::EdgeMap<Number> residual_capacity(F);

   644 

   645 //       //Making F to the graph containing the edges of the residual graph 

   646 //       //which are in some shortest paths

   647 //       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {

   648 // 	if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {

   649 // 	  typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));

   650 // 	  original_edge.update();

   651 // 	  original_edge.set(f, e);

   652 // 	  residual_capacity.update();

   653 // 	  residual_capacity.set(f, res_graph.free(e));

   654 // 	} 

   655 //       }

   656 

   657 //       bool __augment=true;

   658 

   659 //       while (__augment) {

   660 // 	__augment=false;

   661 // 	//computing blocking flow with dfs

   662 // 	typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;

   663 // 	DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);

   664 // 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);

   665 // 	pred.set(sF, typename MutableGraph::Edge(INVALID));

   666 // 	//invalid iterators for sources

   667 

   668 // 	typename MutableGraph::NodeMap<Number> free(F);

   669 

   670 // 	dfs.pushAndSetReached(sF);      

   671 // 	while (!dfs.finished()) {

   672 // 	  ++dfs;

   673 // 	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {

   674 // 	    if (dfs.isBNodeNewlyReached()) {

   675 // 	      typename MutableGraph::Node v=F.aNode(dfs);

   676 // 	      typename MutableGraph::Node w=F.bNode(dfs);

   677 // 	      pred.set(w, dfs);

   678 // 	      if (F.valid(pred.get(v))) {

   679 // 		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));

   680 // 	      } else {

   681 // 		free.set(w, residual_capacity.get(dfs)); 

   682 // 	      }

   683 // 	      if (w==tF) { 

   684 // 		__augment=true; 

   685 // 		_augment=true;

   686 // 		break; 

   687 // 	      }

   688 	      

   689 // 	    } else {

   690 // 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));

   691 // 	    }

   692 // 	  } 

   693 // 	}

   694 

   695 // 	if (__augment) {

   696 // 	  typename MutableGraph::Node n=tF;

   697 // 	  Number augment_value=free.get(tF);

   698 // 	  while (F.valid(pred.get(n))) { 

   699 // 	    typename MutableGraph::Edge e=pred.get(n);

   700 // 	    res_graph.augment(original_edge.get(e), augment_value); 

   701 // 	    n=F.tail(e);

   702 // 	    if (residual_capacity.get(e)==augment_value) 

   703 // 	      F.erase(e); 

   704 // 	    else 

   705 // 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);

   706 // 	  }

   707 // 	}

   708 	

   709 //       }

   710             

   711 //       return _augment;

   712 //     }

   713 //     bool augmentOnBlockingFlow2() {

   714 //       bool _augment=false;

   715 

   716 //       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;

   717 //       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;

   718 //       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;

   719 //       typedef typename EAugGraph::Edge EAugEdge;

   720 

   721 //       EAugGraph res_graph(*G, *flow, *capacity);

   722 

   723 //       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;

   724 //       BfsIterator4< 

   725 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 

   726 // 	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 

   727 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);

   728       

   729 //       bfs.pushAndSetReached(s);

   730 

   731 //       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::

   732 // 	NodeMap<int>& dist=res_graph.dist;

   733 

   734 //       while ( !bfs.finished() ) {

   735 // 	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;

   736 // 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {

   737 // 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);

   738 // 	}

   739 // 	++bfs;	

   740 //       } //computing distances from s in the residual graph

   741 

   742 //       bool __augment=true;

   743 

   744 //       while (__augment) {

   745 

   746 // 	__augment=false;

   747 // 	//computing blocking flow with dfs

   748 // 	typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;

   749 // 	DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > 

   750 // 	  dfs(res_graph);

   751 // 	typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); 

   752 // 	pred.set(s, EAugEdge(INVALID));

   753 // 	//invalid iterators for sources

   754 

   755 // 	typename EAugGraph::NodeMap<Number> free(res_graph);

   756 

   757 // 	dfs.pushAndSetReached(s);

   758 // 	while (!dfs.finished()) {

   759 // 	  ++dfs;

   760 // 	  if (res_graph.valid(EAugOutEdgeIt(dfs))) { 

   761 // 	    if (dfs.isBNodeNewlyReached()) {

   762 	  

   763 // 	      typename EAugGraph::Node v=res_graph.aNode(dfs);

   764 // 	      typename EAugGraph::Node w=res_graph.bNode(dfs);

   765 

   766 // 	      pred.set(w, EAugOutEdgeIt(dfs));

   767 // 	      if (res_graph.valid(pred.get(v))) {

   768 // 		free.set(w, std::min(free.get(v), res_graph.free(dfs)));

   769 // 	      } else {

   770 // 		free.set(w, res_graph.free(dfs)); 

   771 // 	      }

   772 	      

   773 // 	      if (w==t) { 

   774 // 		__augment=true; 

   775 // 		_augment=true;

   776 // 		break; 

   777 // 	      }

   778 // 	    } else {

   779 // 	      res_graph.erase(dfs);

   780 // 	    }

   781 // 	  } 

   782 

   783 // 	}

   784 

   785 // 	if (__augment) {

   786 // 	  typename EAugGraph::Node n=t;

   787 // 	  Number augment_value=free.get(t);

   788 // 	  while (res_graph.valid(pred.get(n))) { 

   789 // 	    EAugEdge e=pred.get(n);

   790 // 	    res_graph.augment(e, augment_value);

   791 // 	    n=res_graph.tail(e);

   792 // 	    if (res_graph.free(e)==0)

   793 // 	      res_graph.erase(e);

   794 // 	  }

   795 // 	}

   796       

   797 //       }

   798             

   799 //       return _augment;

   800 //     }

   801     void run() {

   802       //int num_of_augmentations=0;

   803       while (augmentOnShortestPath()) { 

   804 	//while (augmentOnBlockingFlow<MutableGraph>()) { 

   805 	//std::cout << ++num_of_augmentations << " ";

   806 	//std::cout<<std::endl;

   807       } 

   808     }

   809 //     template<typename MutableGraph> void run() {

   810 //       //int num_of_augmentations=0;

   811 //       //while (augmentOnShortestPath()) { 

   812 // 	while (augmentOnBlockingFlow<MutableGraph>()) { 

   813 // 	//std::cout << ++num_of_augmentations << " ";

   814 // 	//std::cout<<std::endl;

   815 //       } 

   816 //     } 

   817     Number flowValue() { 

   818       Number a=0;

   819       EdgeIt e;

   820       for(G->/*getF*/first(e); G->valid(e); G->next(e)) {

   821 	a+=flow->get(e);

   822       }

   823       return a;

   824     }

   825   };

   826 

   827 

   828 

   829 

   830 

   831   

   832 //   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>

   833 //   class MaxFlow2 {

   834 //   public:

   835 //     typedef typename Graph::Node Node;

   836 //     typedef typename Graph::Edge Edge;

   837 //     typedef typename Graph::EdgeIt EdgeIt;

   838 //     typedef typename Graph::OutEdgeIt OutEdgeIt;

   839 //     typedef typename Graph::InEdgeIt InEdgeIt;

   840 //   private:

   841 //     const Graph& G;

   842 //     std::list<Node>& S;

   843 //     std::list<Node>& T;

   844 //     FlowMap& flow;

   845 //     const CapacityMap& capacity;

   846 //     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;

   847 //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   848 //     typedef typename AugGraph::Edge AugEdge;

   849 //     typename Graph::NodeMap<bool> SMap;

   850 //     typename Graph::NodeMap<bool> TMap;

   851 //   public:

   852 //     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) { 

   853 //       for(typename std::list<Node>::const_iterator i=S.begin(); 

   854 // 	  i!=S.end(); ++i) { 

   855 // 	SMap.set(*i, true); 

   856 //       }

   857 //       for (typename std::list<Node>::const_iterator i=T.begin(); 

   858 // 	   i!=T.end(); ++i) { 

   859 // 	TMap.set(*i, true); 

   860 //       }

   861 //     }

   862 //     bool augment() {

   863 //       AugGraph res_graph(G, flow, capacity);

   864 //       bool _augment=false;

   865 //       Node reached_t_node;

   866       

   867 //       typedef typename AugGraph::NodeMap<bool> ReachedMap;

   868 //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);

   869 //       for(typename std::list<Node>::const_iterator i=S.begin(); 

   870 // 	  i!=S.end(); ++i) {

   871 // 	res_bfs.pushAndSetReached(*i);

   872 //       }

   873 //       //res_bfs.pushAndSetReached(s);

   874 	

   875 //       typename AugGraph::NodeMap<AugEdge> pred(res_graph); 

   876 //       //filled up with invalid iterators

   877       

   878 //       typename AugGraph::NodeMap<Number> free(res_graph);

   879 	

   880 //       //searching for augmenting path

   881 //       while ( !res_bfs.finished() ) { 

   882 // 	AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);

   883 // 	if (e.valid() && res_bfs.isBNodeNewlyReached()) {

   884 // 	  Node v=res_graph.tail(e);

   885 // 	  Node w=res_graph.head(e);

   886 // 	  pred.set(w, e);

   887 // 	  if (pred.get(v).valid()) {

   888 // 	    free.set(w, std::min(free.get(v), e.free()));

   889 // 	  } else {

   890 // 	    free.set(w, e.free()); 

   891 // 	  }

   892 // 	  if (TMap.get(res_graph.head(e))) { 

   893 // 	    _augment=true; 

   894 // 	    reached_t_node=res_graph.head(e);

   895 // 	    break; 

   896 // 	  }

   897 // 	}

   898 	

   899 // 	++res_bfs;

   900 //       } //end of searching augmenting path

   901 

   902 //       if (_augment) {

   903 // 	Node n=reached_t_node;

   904 // 	Number augment_value=free.get(reached_t_node);

   905 // 	while (pred.get(n).valid()) { 

   906 // 	  AugEdge e=pred.get(n);

   907 // 	  e.augment(augment_value); 

   908 // 	  n=res_graph.tail(e);

   909 // 	}

   910 //       }

   911 

   912 //       return _augment;

   913 //     }

   914 //     void run() {

   915 //       while (augment()) { } 

   916 //     }

   917 //     Number flowValue() { 

   918 //       Number a=0;

   919 //       for(typename std::list<Node>::const_iterator i=S.begin(); 

   920 // 	  i!=S.end(); ++i) { 

   921 // 	for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {

   922 // 	  a+=flow.get(e);

   923 // 	}

   924 // 	for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {

   925 // 	  a-=flow.get(e);

   926 // 	}

   927 //       }

   928 //       return a;

   929 //     }

   930 //   };

   931 

   932 

   933 

   934 } // namespace hugo

   935 

   936 #endif //EDMONDS_KARP_H
lemon-0.x