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.hh
author marci
Wed, 18 Feb 2004 17:27:13 +0000
changeset 100 f1de2ab64e1c
parent 94 90a35f45fa6a
child 107 8d62f0072ff0
permissions -rw-r--r--
. 
     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 marci {

    12 

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

    14   class ResGraph {

    15     typedef typename Graph::NodeIt NodeIt;

    16     typedef typename Graph::EachNodeIt EachNodeIt;

    17     typedef typename Graph::SymEdgeIt OldSymEdgeIt;

    18     const Graph& G;

    19     FlowMap& flow;

    20     const CapacityMap& capacity;

    21   public:

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

    23 	     const CapacityMap& _capacity) : 

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

    25 

    26     class EdgeIt; 

    27     class OutEdgeIt; 

    28     friend class EdgeIt; 

    29     friend class OutEdgeIt; 

    30 

    31     class EdgeIt {

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

    33     protected:

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

    35       OldSymEdgeIt sym;

    36     public:

    37       EdgeIt() { } 

    38       //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }

    39       Number free() const { 

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

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

    42 	} else { 

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

    44 	}

    45       }

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

    47       void augment(Number a) const {

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

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

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

    51 	} else { 

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

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

    54 	}

    55       }

    56     };

    57 

    58     class OutEdgeIt : public EdgeIt {

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

    60     public:

    61       OutEdgeIt() { }

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

    63     private:

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

    65       	resG=&_resG;

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

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

    68       }

    69     public:

    70       OutEdgeIt& operator++() { 

    71 	++sym; 

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

    73 	return *this; 

    74       }

    75     };

    76 

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

    78       e=OutEdgeIt(*this, v); 

    79     }

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

    81     

    82     template< typename It >

    83     It first() const { 

    84       It e;      

    85       getFirst(e);

    86       return e; 

    87     }

    88 

    89     template< typename It >

    90     It first(NodeIt v) const { 

    91       It e;

    92       getFirst(e, v);

    93       return e; 

    94     }

    95 

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

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

    98 

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

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

   101 

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

   103 

   104     template <typename S>

   105     class NodeMap {

   106       typename Graph::NodeMap<S> node_map; 

   107     public:

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

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

   110       void set(NodeIt nit, S a) { node_map.set(nit, a); }

   111       S get(NodeIt nit) const { return node_map.get(nit); }

   112       S& operator[](NodeIt nit) { return node_map[nit]; } 

   113       const S& operator[](NodeIt nit) const { return node_map[nit]; } 

   114     };

   115 

   116   };

   117 

   118 

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

   120   class ResGraph2 {

   121     typedef typename Graph::NodeIt NodeIt;

   122     typedef typename Graph::EachNodeIt EachNodeIt;

   123     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;

   124     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   125     typedef typename Graph::InEdgeIt OldInEdgeIt;

   126     

   127     const Graph& G;

   128     FlowMap& flow;

   129     const CapacityMap& capacity;

   130   public:

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

   132 	     const CapacityMap& _capacity) : 

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

   134 

   135     class EdgeIt; 

   136     class OutEdgeIt; 

   137     friend class EdgeIt; 

   138     friend class OutEdgeIt; 

   139 

   140     class EdgeIt {

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

   142     protected:

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

   144       //OldSymEdgeIt sym;

   145       OldOutEdgeIt out;

   146       OldInEdgeIt in;

   147       bool out_or_in; //1, iff out

   148     public:

   149       EdgeIt() : out_or_in(1) { } 

   150       Number free() const { 

   151 	if (out_or_in) { 

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

   153 	} else { 

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

   155 	}

   156       }

   157       bool valid() const { 

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

   159       void augment(Number a) const {

   160 	if (out_or_in) { 

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

   162 	} else { 

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

   164 	}

   165       }

   166     };

   167 

   168     class OutEdgeIt : public EdgeIt {

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

   170     public:

   171       OutEdgeIt() { }

   172     private:

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

   174       	resG=&_resG;

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

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

   177 	if (!out.valid()) {

   178 	  out_or_in=0;

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

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

   181 	}

   182       }

   183     public:

   184       OutEdgeIt& operator++() { 

   185 	if (out_or_in) {

   186 	  NodeIt v=resG->G.aNode(out);

   187 	  ++out;

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

   189 	  if (!out.valid()) {

   190 	    out_or_in=0;

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

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

   193 	  }

   194 	} else {

   195 	  ++in;

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

   197 	}

   198 	return *this; 

   199       }

   200     };

   201 

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

   203       e=OutEdgeIt(*this, v); 

   204     }

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

   206     

   207     template< typename It >

   208     It first() const { 

   209       It e;

   210       getFirst(e);

   211       return e; 

   212     }

   213 

   214     template< typename It >

   215     It first(NodeIt v) const { 

   216       It e;

   217       getFirst(e, v);

   218       return e; 

   219     }

   220 

   221     NodeIt tail(EdgeIt e) const { 

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

   223     NodeIt head(EdgeIt e) const { 

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

   225 

   226     NodeIt aNode(OutEdgeIt e) const { 

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

   228     NodeIt bNode(OutEdgeIt e) const { 

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

   230 

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

   232 

   233     template <typename S>

   234     class NodeMap {

   235       typename Graph::NodeMap<S> node_map; 

   236     public:

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

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

   239       void set(NodeIt nit, S a) { node_map.set(nit, a); }

   240       S get(NodeIt nit) const { return node_map.get(nit); }

   241     };

   242   };

   243 

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

   245   class ResGraph3 {

   246 public:

   247     typedef typename Graph::NodeIt NodeIt;

   248     typedef typename Graph::EachNodeIt EachNodeIt;

   249     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;

   250     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   251     typedef typename Graph::InEdgeIt OldInEdgeIt;

   252     

   253 private:

   254     const Graph& G;

   255     FlowMap& flow;

   256     const CapacityMap& capacity;

   257   public:

   258     ResGraph3(const Graph& _G, FlowMap& _flow, 

   259 	     const CapacityMap& _capacity) : 

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

   261 

   262     class EdgeIt; 

   263     class OutEdgeIt; 

   264     friend class EdgeIt; 

   265     friend class OutEdgeIt; 

   266 

   267     class EdgeIt {

   268       friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;

   269     protected:

   270       //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;

   271       const Graph* G;

   272       FlowMap* flow;

   273       const CapacityMap* capacity;

   274       //OldSymEdgeIt sym;

   275       OldOutEdgeIt out;

   276       OldInEdgeIt in;

   277       bool out_or_in; //1, iff out

   278     public:

   279       EdgeIt() : out_or_in(1) { } 

   280       Number free() const { 

   281 	if (out_or_in) { 

   282 	  return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out)); 

   283 	} else { 

   284 	  return (/*resG->*/flow->get(in)); 

   285 	}

   286       }

   287       bool valid() const { 

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

   289       void augment(Number a) const {

   290 	if (out_or_in) { 

   291 	  /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);

   292 	} else { 

   293 	  /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);

   294 	}

   295       }

   296     };

   297 

   298     class OutEdgeIt : public EdgeIt {

   299       friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;

   300     public:

   301       OutEdgeIt() { }

   302     private:

   303       OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) { 

   304       	G=&_G;

   305 	flow=&_flow;

   306 	capacity=&_capacity;

   307 	out=/*resG->*/G->template first<OldOutEdgeIt>(v);

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

   309 	if (!out.valid()) {

   310 	  out_or_in=0;

   311 	  in=/*resG->*/G->template first<OldInEdgeIt>(v);

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

   313 	}

   314       }

   315     public:

   316       OutEdgeIt& operator++() { 

   317 	if (out_or_in) {

   318 	  NodeIt v=/*resG->*/G->aNode(out);

   319 	  ++out;

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

   321 	  if (!out.valid()) {

   322 	    out_or_in=0;

   323 	    in=/*resG->*/G->template first<OldInEdgeIt>(v);

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

   325 	  }

   326 	} else {

   327 	  ++in;

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

   329 	}

   330 	return *this; 

   331       }

   332     };

   333 

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

   335       e=OutEdgeIt(G, v, flow, capacity); 

   336     }

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

   338     

   339     template< typename It >

   340     It first() const { 

   341       It e;

   342       getFirst(e);

   343       return e; 

   344     }

   345 

   346     template< typename It >

   347     It first(NodeIt v) const { 

   348       It e;

   349       getFirst(e, v);

   350       return e; 

   351     }

   352 

   353     NodeIt tail(EdgeIt e) const { 

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

   355     NodeIt head(EdgeIt e) const { 

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

   357 

   358     NodeIt aNode(OutEdgeIt e) const { 

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

   360     NodeIt bNode(OutEdgeIt e) const { 

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

   362 

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

   364 

   365     template <typename S>

   366     class NodeMap {

   367       typename Graph::NodeMap<S> node_map; 

   368     public:

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

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

   371       void set(NodeIt nit, S a) { node_map.set(nit, a); }

   372       S get(NodeIt nit) const { return node_map.get(nit); }

   373     };

   374 

   375   };

   376 

   377 

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

   379   class MaxFlow {

   380     typedef typename Graph::NodeIt NodeIt;

   381     typedef typename Graph::EdgeIt EdgeIt;

   382     typedef typename Graph::EachEdgeIt EachEdgeIt;

   383     typedef typename Graph::OutEdgeIt OutEdgeIt;

   384     typedef typename Graph::InEdgeIt InEdgeIt;

   385     const Graph& G;

   386     NodeIt s;

   387     NodeIt t;

   388     FlowMap& flow;

   389     const CapacityMap& capacity;

   390     typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;

   391     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   392     typedef typename AugGraph::EdgeIt AugEdgeIt;

   393 

   394     //AugGraph res_graph;    

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

   396     //typename AugGraph::NodeMap<AugEdgeIt> pred; 

   397     //typename AugGraph::NodeMap<int> free;

   398   public:

   399     MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : 

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

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

   402       { }

   403     bool augment() {

   404       AugGraph res_graph(G, flow, capacity);

   405       bool _augment=false;

   406       

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

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

   409       res_bfs.pushAndSetReached(s);

   410 	

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

   412       //filled up with invalid iterators

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

   414       

   415       typename AugGraph::NodeMap<int> free(res_graph);

   416 	

   417       //searching for augmenting path

   418       while ( !res_bfs.finished() ) { 

   419 	AugOutEdgeIt e=AugOutEdgeIt(res_bfs);

   420 	if (e.valid() && res_bfs.isBNodeNewlyReached()) {

   421 	  NodeIt v=res_graph.tail(e);

   422 	  NodeIt w=res_graph.head(e);

   423 	  pred.set(w, e);

   424 	  if (pred.get(v).valid()) {

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

   426 	  } else {

   427 	    free.set(w, e.free()); 

   428 	  }

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

   430 	}

   431 	

   432 	++res_bfs;

   433       } //end of searching augmenting path

   434 

   435       if (_augment) {

   436 	NodeIt n=t;

   437 	Number augment_value=free.get(t);

   438 	while (pred.get(n).valid()) { 

   439 	  AugEdgeIt e=pred.get(n);

   440 	  e.augment(augment_value); 

   441 	  n=res_graph.tail(e);

   442 	}

   443       }

   444 

   445       return _augment;

   446     }

   447     bool augmentWithBlockingFlow() {

   448       BfsIterator4< Graph, OutEdgeIt, typename Graph::NodeMap<bool> > bfs(G);

   449       bfs.pushAndSetReached(s);

   450       typename Graph::NodeMap<int> dist(G); //filled up with 0's

   451       while ( !bfs.finished() ) { 

   452 	OutEdgeIt e=OutEdgeIt(bfs);

   453 	if (e.valid() && bfs.isBNodeNewlyReached()) {

   454 	  dist.set(G.head(e), dist.get(G.tail(e))+1);

   455 	  //NodeIt v=res_graph.tail(e);

   456 	  //NodeIt w=res_graph.head(e);

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

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

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

   460 	  //} else {

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

   462 	  //}

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

   464 	}

   465 	

   466 	++bfs;

   467       } //end of searching augmenting path

   468 

   469       double pre_time_copy=currTime();

   470       typedef Graph MutableGraph;

   471       MutableGraph F;

   472       typename Graph::NodeMap<NodeIt> G_to_F(G);

   473       for(typename Graph::EachNodeIt n=G.template first<typename Graph::EachNodeIt>(); n.valid(); ++n) {

   474 	G_to_F.set(n, F.addNode());

   475       }

   476       for(typename Graph::EachEdgeIt e=G.template first<typename Graph::EachEdgeIt>(); e.valid(); ++e) {

   477 	if (dist.get(G.head(e))==dist.get(G.tail(e))+1) {

   478 	  F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e)));

   479 	}

   480       }

   481       double post_time_copy=currTime();

   482       std::cout << "copy time: " << post_time_copy-pre_time_copy << " sec"<< std::endl; 

   483 

   484       return 0;

   485     }

   486     void run() {

   487       //int num_of_augmentations=0;

   488       while (augment()) { 

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

   490 	//std::cout<<std::endl;

   491       } 

   492     }

   493     Number flowValue() { 

   494       Number a=0;

   495       for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {

   496 	a+=flow.get(i);

   497       }

   498       return a;

   499     }

   500   };

   501 

   502 

   503 /*

   504   template <typename Graph>

   505   class IteratorBoolNodeMap {

   506     typedef typename Graph::NodeIt NodeIt;

   507     typedef typename Graph::EachNodeIt EachNodeIt;

   508     class BoolItem {

   509     public:

   510       bool value;

   511       NodeIt prev;

   512       NodeIt next;

   513       BoolItem() : value(false), prev(), next() {}

   514     };

   515     NodeIt first_true;

   516     //NodeIt last_true;

   517     NodeIt first_false;

   518     //NodeIt last_false;

   519     const Graph& G; 

   520     typename Graph::NodeMap<BoolItem> container;

   521   public:

   522     typedef bool ValueType;

   523     typedef NodeIt KeyType;

   524     IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) { 

   525       //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {

   526       //BoolItem b=container.get(e);

   527       //b.me=e;

   528       //container.set(b);

   529       //} 

   530       G.getFirst(first_false);

   531       NodeIt e_prev;

   532       for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {

   533 	container[e].prev=e_prev;

   534 	if (e_prev.valid()) container[e_prev].next=e;

   535 	e_prev=e;

   536       }

   537     }

   538     //NodeMap(const Graph& _G, T a) : 

   539     //  G(_G), container(G.node_id, a) { }

   540     //FIXME

   541     void set(NodeIt nit, T a) { container[G.id(nit)]=a; }

   542     T get(NodeIt nit) const { return container[G.id(nit)]; }

   543     //void resize() { container.resize(G.node_id); }

   544     //void resize(T a) { container.resize(G.node_id, a); }

   545   };

   546 */

   547 

   548   

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

   550   class MaxFlow2 {

   551     typedef typename Graph::NodeIt NodeIt;

   552     typedef typename Graph::EdgeIt EdgeIt;

   553     typedef typename Graph::EachEdgeIt EachEdgeIt;

   554     typedef typename Graph::OutEdgeIt OutEdgeIt;

   555     typedef typename Graph::InEdgeIt InEdgeIt;

   556     const Graph& G;

   557     std::list<NodeIt>& S;

   558     std::list<NodeIt>& T;

   559     FlowMap& flow;

   560     const CapacityMap& capacity;

   561     typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;

   562     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   563     typedef typename AugGraph::EdgeIt AugEdgeIt;

   564     typename Graph::NodeMap<bool> SMap;

   565     typename Graph::NodeMap<bool> TMap;

   566   public:

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

   568       for(typename std::list<NodeIt>::const_iterator i=S.begin(); 

   569 	  i!=S.end(); ++i) { 

   570 	SMap.set(*i, true); 

   571       }

   572       for (typename std::list<NodeIt>::const_iterator i=T.begin(); 

   573 	   i!=T.end(); ++i) { 

   574 	TMap.set(*i, true); 

   575       }

   576     }

   577     bool augment() {

   578       AugGraph res_graph(G, flow, capacity);

   579       bool _augment=false;

   580       NodeIt reached_t_node;

   581       

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

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

   584       for(typename std::list<NodeIt>::const_iterator i=S.begin(); 

   585 	  i!=S.end(); ++i) {

   586 	res_bfs.pushAndSetReached(*i);

   587       }

   588       //res_bfs.pushAndSetReached(s);

   589 	

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

   591       //filled up with invalid iterators

   592       

   593       typename AugGraph::NodeMap<int> free(res_graph);

   594 	

   595       //searching for augmenting path

   596       while ( !res_bfs.finished() ) { 

   597 	AugOutEdgeIt e=AugOutEdgeIt(res_bfs);

   598 	if (e.valid() && res_bfs.isBNodeNewlyReached()) {

   599 	  NodeIt v=res_graph.tail(e);

   600 	  NodeIt w=res_graph.head(e);

   601 	  pred.set(w, e);

   602 	  if (pred.get(v).valid()) {

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

   604 	  } else {

   605 	    free.set(w, e.free()); 

   606 	  }

   607 	  if (TMap.get(res_graph.head(e))) { 

   608 	    _augment=true; 

   609 	    reached_t_node=res_graph.head(e);

   610 	    break; 

   611 	  }

   612 	}

   613 	

   614 	++res_bfs;

   615       } //end of searching augmenting path

   616 

   617       if (_augment) {

   618 	NodeIt n=reached_t_node;

   619 	Number augment_value=free.get(reached_t_node);

   620 	while (pred.get(n).valid()) { 

   621 	  AugEdgeIt e=pred.get(n);

   622 	  e.augment(augment_value); 

   623 	  n=res_graph.tail(e);

   624 	}

   625       }

   626 

   627       return _augment;

   628     }

   629     void run() {

   630       while (augment()) { } 

   631     }

   632     Number flowValue() { 

   633       Number a=0;

   634       for(typename std::list<NodeIt>::const_iterator i=S.begin(); 

   635 	  i!=S.end(); ++i) { 

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

   637 	  a+=flow.get(e);

   638 	}

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

   640 	  a-=flow.get(e);

   641 	}

   642       }

   643       return a;

   644     }

   645   };

   646 

   647 

   648 

   649 } // namespace marci

   650 

   651 #endif //EDMONDS_KARP_HH
lemon-0.x