lemon-0.x: src/work/edmonds_karp.hh@aa50acc936dc

     1 #ifndef EDMONDS_KARP_HH

     2 #define EDMONDS_KARP_HH

     4 #include <algorithm>

     5 #include <list>

     6 #include <iterator>

     8 #include <bfs_iterator.hh>

     9 //#include <time_measure.h>

    11 namespace hugo {

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

    28     class EdgeIt;

    29     class OutEdgeIt;

    30     friend class EdgeIt;

    31     friend class OutEdgeIt;

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

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

    79     void getFirst(OutEdgeIt& e, NodeIt v) const {

    80       e=OutEdgeIt(*this, v);

    81     }

    82     void getFirst(EachNodeIt& v) const { G.getFirst(v); }

    84     template< typename It >

    85     It first() const {

    86       It e;

    87       getFirst(e);

    88       return e;

    89     }

    91     template< typename It >

    92     It first(NodeIt v) const {

    93       It e;

    94       getFirst(e, v);

    95       return e;

    96     }

    98     NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }

    99     NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }

   101     NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }

   102     NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }

   104     int id(NodeIt v) const { return G.id(v); }

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

   118   };

   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;

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

   139     class EdgeIt;

   140     class OutEdgeIt;

   141     friend class EdgeIt;

   142     friend class OutEdgeIt;

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

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

   206     void getFirst(OutEdgeIt& e, NodeIt v) const {

   207       e=OutEdgeIt(*this, v);

   208     }

   209     void getFirst(EachNodeIt& v) const { G.getFirst(v); }

   211     template< typename It >

   212     It first() const {

   213       It e;

   214       getFirst(e);

   215       return e;

   216     }

   218     template< typename It >

   219     It first(NodeIt v) const {

   220       It e;

   221       getFirst(e, v);

   222       return e;

   223     }

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

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

   235     int id(NodeIt v) const { return G.id(v); }

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

   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;

   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;

   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;

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

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

   283       res_bfs.pushAndSetReached(s);

   285       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);

   286       //filled up with invalid iterators

   287       //pred.set(s, AugEdgeIt());

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

   306 	++res_bfs;

   307       } //end of searching augmenting path

   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       }

   320       return _augment;

   321     }

   323     template<typename MutableGraph> bool augmentOnBlockingFlow() {

   324       bool _augment=false;

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

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

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

   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 	}

   339 	++bfs;

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

   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       }

   348       typename MutableGraph::NodeIt sF=res_graph_to_F.get(s);

   349       typename MutableGraph::NodeIt tF=res_graph_to_F.get(t);

   351       typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);

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

   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       }

   366       bool __augment=true;

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

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

   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 	      }

   400 	    } else {

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

   402 	    }

   403 	  }

   404 	}

   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 	}

   421       }

   423       return _augment;

   424     }

   425     bool augmentOnBlockingFlow2() {

   426       bool _augment=false;

   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;

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

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

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

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

   445       bfs.pushAndSetReached(s);

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

   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;

   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 	}

   463 	++bfs;

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

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

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

   474       bool __augment=true;

   476       while (__augment) {

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

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

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

   497 	      typename EAugGraph::NodeIt v=res_graph.aNode(dfs);

   498 	      typename EAugGraph::NodeIt w=res_graph.bNode(dfs);

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

   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 	      }

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

   522 	      res_graph.erase(dfs);

   523 	    }

   524 	  }

   526 	}

   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 	}

   542       }

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

   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;

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

   616 //       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);

   617 //       //filled up with invalid iterators

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

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

   640 // 	++res_bfs;

   641 //       } //end of searching augmenting path

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

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

   675 } // namespace hugo

   677 #endif //EDMONDS_KARP_HH

author	marci
	Mon, 22 Mar 2004 17:05:08 +0000
changeset 235	aa50acc936dc
parent 155	8c6292ec54c6
permissions	-rw-r--r--