lemon-0.x: src/work/edmonds_karp.h@08735c8704cd

     1 // -*- c++ -*-

     2 #ifndef EDMONDS_KARP_H

     3 #define EDMONDS_KARP_H

     5 #include <algorithm>

     6 #include <list>

     7 #include <iterator>

     9 #include <bfs_iterator.h>

    10 #include <invalid.h>

    12 namespace hugo {

    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) { }

    29     class Edge;

    30     class OutEdgeIt;

    31     friend class Edge;

    32     friend class OutEdgeIt;

    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     };

    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     };

    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); }

    85     template< typename It >

    86     It first() const {

    87       It e;

    88       /*getF*/first(e);

    89       return e;

    90     }

    92     template< typename It >

    93     It first(Node v) const {

    94       It e;

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

    96       return e;

    97     }

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

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

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

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

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

   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     };

   119   };

   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;

   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) { }

   140     class Edge;

   141     class OutEdgeIt;

   142     friend class Edge;

   143     friend class OutEdgeIt;

   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     };

   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     };

   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); }

   212     template< typename It >

   213     It first() const {

   214       It e;

   215       /*getF*/first(e);

   216       return e;

   217     }

   219     template< typename It >

   220     It first(Node v) const {

   221       It e;

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

   223       return e;

   224     }

   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)); }

   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)); }

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

   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   };

   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;

   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;

   269     //AugGraph res_graph;

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

   271     //typename AugGraph::NodeMap<AugEdge> pred;

   272     //typename AugGraph::NodeMap<Number> free;

   273   public:

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

   275       G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //,

   276       //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)

   277       { }

   278     bool augmentOnShortestPath() {

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

   280       bool _augment=false;

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

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

   284       res_bfs.pushAndSetReached(s);

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

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

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

   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 	  Node v=res_graph.tail(e);

   296 	  Node 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 	}

   306 	++res_bfs;

   307       } //end of searching augmenting path

   309       if (_augment) {

   310 	Node n=t;

   311 	Number augment_value=free.get(t);

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

   313 	  AugEdge e=pred.get(n);

   314 	  res_graph.augment(e, augment_value);

   315 	  //e.augment(augment_value);

   316 	  n=res_graph.tail(e);

   317 	}

   318       }

   320       return _augment;

   321     }

   323     template<typename MutableGraph> bool augmentOnBlockingFlow() {

   325 //       std::cout << "number of nodes: " << G->nodeNum() << std::endl;

   326 //       typename Graph::NodeIt n;

   327 //       G->first(n);

   328 //       for( ; G->valid(n); G->next(n)) {

   329 // 	std::cout << G->id(n) << std::endl;

   330 //       }

   331 //       std::cout << "meg elek 1";

   333 //       for(typename Graph::NodeIt n=G->template first<typename Graph::NodeIt>(); G->valid(n); G->next(n)) {

   334 // 	std::cout << G->id(n) << std::endl;

   335 //       }

   336 //       std::cout << "meg elek 2";

   338       bool _augment=false;

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

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

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

   345       bfs.pushAndSetReached(s);

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

   347       while ( !bfs.finished() ) {

   348 	AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);

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

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

   351 	}

   353 	++bfs;

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

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

   357 // 	std::cout << res_graph.id(n) << std::endl;

   358 //       }

   359 //       std::cout << "meg elek";

   361       MutableGraph F;

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

   363 	res_graph_to_F(res_graph);

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

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

   366       }

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

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

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

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

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

   375       //which are in some shortest paths

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

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

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

   379 	  original_edge.update();

   380 	  original_edge.set(f, e);

   381 	  residual_capacity.update();

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

   383 	}

   384       }

   386 //       for(typename MutableGraph::NodeIt n=F.template first<typename MutableGraph::NodeIt>(); F.valid(n); F.next(n)) {

   387 // 	std::cout << F.id(n) << std::endl;

   388 //       }

   390       bool __augment=true;

   392       while (__augment) {

   393 	__augment=false;

   394 	//computing blocking flow with dfs

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

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

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

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

   399 	//invalid iterators for sources

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

   403 	dfs.pushAndSetReached(sF);

   404 	while (!dfs.finished()) {

   405 	  ++dfs;

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

   407 	    if (dfs.isBNodeNewlyReached()) {

   408 // 	      std::cout << "OutEdgeIt: " << dfs;

   409 // 	      std::cout << " aNode: " << F.aNode(dfs);

   410 // 	      std::cout << " bNode: " << F.bNode(dfs) << " ";

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

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

   414 	      pred.set(w, dfs);

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

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

   417 	      } else {

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

   419 	      }

   420 	      if (w==tF) {

   421 		//std::cout << "AUGMENTATION"<<std::endl;

   422 		__augment=true;

   423 		_augment=true;

   424 		break;

   425 	      }

   427 	    } else {

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

   429 	    }

   430 	  }

   431 	}

   433 	if (__augment) {

   434 	  typename MutableGraph::Node n=tF;

   435 	  Number augment_value=free.get(tF);

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

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

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

   439 	    //original_edge.get(e).augment(augment_value);

   440 	    n=F.tail(e);

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

   442 	      F.erase(e);

   443 	    else

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

   445 	  }

   446 	}

   448       }

   450       return _augment;

   451     }

   452     bool augmentOnBlockingFlow2() {

   453       bool _augment=false;

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

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

   457       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;

   458       typedef typename EAugGraph::Edge EAugEdge;

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

   462       //std::cout << "meg jo1" << std::endl;

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

   465       BfsIterator4<

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

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

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

   470       //std::cout << "meg jo2" << std::endl;

   472       bfs.pushAndSetReached(s);

   473       //std::cout << "meg jo2.5" << std::endl;

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

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

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

   478       //std::cout << "meg jo2.6" << std::endl;

   480       while ( !bfs.finished() ) {

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

   482 //	EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);

   483  	//if (res_graph.valid(e)) {

   484  	//    std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;

   485  	//}

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

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

   488 	}

   490 	++bfs;

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

   494       //std::cout << "meg jo3" << std::endl;

   496 //       typedef typename EAugGraph::NodeIt EAugNodeIt;

   497 //       for(EAugNodeIt n=res_graph.template first<EAugNodeIt>(); res_graph.valid(n); res_graph.next(n)) {

   498 // 	std::cout << "dist: " << dist.get(n) << std::endl;

   499 //       }

   501       bool __augment=true;

   503       while (__augment) {

   504 //	std::cout << "new iteration"<< std::endl;

   506 	__augment=false;

   507 	//computing blocking flow with dfs

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

   509 	DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >

   510 	  dfs(res_graph);

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

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

   513 	//invalid iterators for sources

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

   517 	dfs.pushAndSetReached(s);

   518 	while (!dfs.finished()) {

   519 	  ++dfs;

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

   521 	    if (dfs.isBNodeNewlyReached()) {

   522 // 	      std::cout << "OutEdgeIt: " << dfs;

   523 // 	      std::cout << " aNode: " << res_graph.aNode(dfs);

   524 // 	      std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();

   525 // 	      std::cout << " bNode: " << res_graph.bNode(dfs) << " ";

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

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

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

   532 	      //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;

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

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

   535 	      } else {

   536 		free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs)));

   537 	      }

   539 	      if (w==t) {

   540 //		std::cout << "t is reached, AUGMENTATION"<<std::endl;

   541 		__augment=true;

   542 		_augment=true;

   543 		break;

   544 	      }

   545 	    } else {

   546 //	      std::cout << "<<DELETE ";

   547 //	      std::cout << " aNode: " << res_graph.aNode(dfs);

   548 //	      std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();

   549 //	      std::cout << " bNode: " << res_graph.bNode(dfs) << " ";

   550 //	      std::cout << "DELETE>> ";

   552 	      res_graph.erase(dfs);

   553 	    }

   554 	  }

   556 	}

   558 	if (__augment) {

   559 	  typename EAugGraph::Node n=t;

   560 	  Number augment_value=free.get(t);

   561 //	  std::cout << "av:" << augment_value << std::endl;

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

   563 	    EAugEdge e=pred.get(n);

   564 	    res_graph.augment(e, augment_value);

   565 	    //e.augment(augment_value);

   566 	    n=res_graph.tail(e);

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

   568 	      res_graph.erase(e);

   569 	  }

   570 	}

   572       }

   574       return _augment;

   575     }

   576     void run() {

   577       //int num_of_augmentations=0;

   578       while (augmentOnShortestPath()) {

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

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

   581 	//std::cout<<std::endl;

   582       }

   583     }

   584     template<typename MutableGraph> void run() {

   585       //int num_of_augmentations=0;

   586       //while (augmentOnShortestPath()) {

   587 	while (augmentOnBlockingFlow<MutableGraph>()) {

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

   589 	//std::cout<<std::endl;

   590       }

   591     }

   592     Number flowValue() {

   593       Number a=0;

   594       OutEdgeIt e;

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

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

   597       }

   598       return a;

   599     }

   600   };

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

   604 //   class MaxFlow2 {

   605 //   public:

   606 //     typedef typename Graph::Node Node;

   607 //     typedef typename Graph::Edge Edge;

   608 //     typedef typename Graph::EdgeIt EdgeIt;

   609 //     typedef typename Graph::OutEdgeIt OutEdgeIt;

   610 //     typedef typename Graph::InEdgeIt InEdgeIt;

   611 //   private:

   612 //     const Graph& G;

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

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

   615 //     FlowMap& flow;

   616 //     const CapacityMap& capacity;

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

   618 //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   619 //     typedef typename AugGraph::Edge AugEdge;

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

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

   622 //   public:

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

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

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

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

   627 //       }

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

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

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

   631 //       }

   632 //     }

   633 //     bool augment() {

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

   635 //       bool _augment=false;

   636 //       Node reached_t_node;

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

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

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

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

   642 // 	res_bfs.pushAndSetReached(*i);

   643 //       }

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

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

   647 //       //filled up with invalid iterators

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

   651 //       //searching for augmenting path

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

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

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

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

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

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

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

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

   660 // 	  } else {

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

   662 // 	  }

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

   664 // 	    _augment=true;

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

   666 // 	    break;

   667 // 	  }

   668 // 	}

   670 // 	++res_bfs;

   671 //       } //end of searching augmenting path

   673 //       if (_augment) {

   674 // 	Node n=reached_t_node;

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

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

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

   678 // 	  e.augment(augment_value);

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

   680 // 	}

   681 //       }

   683 //       return _augment;

   684 //     }

   685 //     void run() {

   686 //       while (augment()) { }

   687 //     }

   688 //     Number flowValue() {

   689 //       Number a=0;

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

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

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

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

   694 // 	}

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

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

   697 // 	}

   698 //       }

   699 //       return a;

   700 //     }

   701 //   };

   705 } // namespace hugo

   707 #endif //EDMONDS_KARP_H

author	alpar
	Sat, 13 Mar 2004 22:49:54 +0000
changeset 184	08735c8704cd
parent 174	44700ed9ffaa
child 191	efea403c9595
permissions	-rw-r--r--