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

     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; //1, iff out

   152     public:

   153       EdgeIt() : out_or_in(1) { }

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

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

   249   class ResGraph3 {

   250   public:

   251     typedef typename Graph::NodeIt NodeIt;

   252     typedef typename Graph::EachNodeIt EachNodeIt;

   254   private:

   255     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;

   256     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   257     typedef typename Graph::InEdgeIt OldInEdgeIt;

   258     const Graph& G;

   259     FlowMap& flow;

   260     const CapacityMap& capacity;

   261   public:

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

   263 	     const CapacityMap& _capacity) :

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

   266     class EdgeIt;

   267     class OutEdgeIt;

   268     friend class EdgeIt;

   269     friend class OutEdgeIt;

   271     class EdgeIt {

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

   273     protected:

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

   275       const Graph* G;

   276       FlowMap* flow;

   277       const CapacityMap* capacity;

   278       //OldSymEdgeIt sym;

   279       OldOutEdgeIt out;

   280       OldInEdgeIt in;

   281       bool out_or_in; //1, iff out

   282     public:

   283       EdgeIt() : out_or_in(1) { }

   284       Number free() const {

   285 	if (out_or_in) {

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

   287 	} else {

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

   289 	}

   290       }

   291       bool valid() const {

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

   293       void augment(Number a) const {

   294 	if (out_or_in) {

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

   296 	} else {

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

   298 	}

   299       }

   300     };

   302     class OutEdgeIt : public EdgeIt {

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

   304     public:

   305       OutEdgeIt() { }

   306     private:

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

   308       	G=&_G;

   309 	flow=&_flow;

   310 	capacity=&_capacity;

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

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

   313 	if (!out.valid()) {

   314 	  out_or_in=0;

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

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

   317 	}

   318       }

   319     public:

   320       OutEdgeIt& operator++() {

   321 	if (out_or_in) {

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

   323 	  ++out;

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

   325 	  if (!out.valid()) {

   326 	    out_or_in=0;

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

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

   329 	  }

   330 	} else {

   331 	  ++in;

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

   333 	}

   334 	return *this;

   335       }

   336     };

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

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

   340     }

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

   343     template< typename It >

   344     It first() const {

   345       It e;

   346       getFirst(e);

   347       return e;

   348     }

   350     template< typename It >

   351     It first(NodeIt v) const {

   352       It e;

   353       getFirst(e, v);

   354       return e;

   355     }

   357     NodeIt tail(EdgeIt e) const {

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

   359     NodeIt head(EdgeIt e) const {

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

   362     NodeIt aNode(OutEdgeIt e) const {

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

   364     NodeIt bNode(OutEdgeIt e) const {

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

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

   369     template <typename S>

   370     class NodeMap {

   371       typename Graph::NodeMap<S> node_map;

   372     public:

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

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

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

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

   377     };

   379   };

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

   383   class MaxFlow {

   384   public:

   385     typedef typename Graph::NodeIt NodeIt;

   386     typedef typename Graph::EdgeIt EdgeIt;

   387     typedef typename Graph::EachEdgeIt EachEdgeIt;

   388     typedef typename Graph::OutEdgeIt OutEdgeIt;

   389     typedef typename Graph::InEdgeIt InEdgeIt;

   391   private:

   392     const Graph& G;

   393     NodeIt s;

   394     NodeIt t;

   395     FlowMap& flow;

   396     const CapacityMap& capacity;

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

   398     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   399     typedef typename AugGraph::EdgeIt AugEdgeIt;

   401     //AugGraph res_graph;

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

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

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

   405   public:

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

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

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

   409       { }

   410     bool augment() {

   411       AugGraph res_graph(G, flow, capacity);

   412       bool _augment=false;

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

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

   416       res_bfs.pushAndSetReached(s);

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

   419       //filled up with invalid iterators

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

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

   424       //searching for augmenting path

   425       while ( !res_bfs.finished() ) {

   426 	AugOutEdgeIt e=AugOutEdgeIt(res_bfs);

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

   428 	  NodeIt v=res_graph.tail(e);

   429 	  NodeIt w=res_graph.head(e);

   430 	  pred.set(w, e);

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

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

   433 	  } else {

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

   435 	  }

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

   437 	}

   439 	++res_bfs;

   440       } //end of searching augmenting path

   442       if (_augment) {

   443 	NodeIt n=t;

   444 	Number augment_value=free.get(t);

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

   446 	  AugEdgeIt e=pred.get(n);

   447 	  e.augment(augment_value);

   448 	  n=res_graph.tail(e);

   449 	}

   450       }

   452       return _augment;

   453     }

   454     bool augmentWithBlockingFlow() {

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

   456       bfs.pushAndSetReached(s);

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

   458       while ( !bfs.finished() ) {

   459 	OutEdgeIt e=OutEdgeIt(bfs);

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

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

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

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

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

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

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

   467 	  //} else {

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

   469 	  //}

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

   471 	}

   473 	++bfs;

   474       } //end of searching augmenting path

   476       double pre_time_copy=currTime();

   477       typedef Graph MutableGraph;

   478       MutableGraph F;

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

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

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

   482       }

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

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

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

   486 	}

   487       }

   488       double post_time_copy=currTime();

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

   491       return 0;

   492     }

   493     void run() {

   494       //int num_of_augmentations=0;

   495       while (augment()) {

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

   497 	//std::cout<<std::endl;

   498       }

   499     }

   500     Number flowValue() {

   501       Number a=0;

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

   503 	a+=flow.get(i);

   504       }

   505       return a;

   506     }

   507   };

   510 /*

   511   template <typename Graph>

   512   class IteratorBoolNodeMap {

   513     typedef typename Graph::NodeIt NodeIt;

   514     typedef typename Graph::EachNodeIt EachNodeIt;

   515     class BoolItem {

   516     public:

   517       bool value;

   518       NodeIt prev;

   519       NodeIt next;

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

   521     };

   522     NodeIt first_true;

   523     //NodeIt last_true;

   524     NodeIt first_false;

   525     //NodeIt last_false;

   526     const Graph& G;

   527     typename Graph::NodeMap<BoolItem> container;

   528   public:

   529     typedef bool ValueType;

   530     typedef NodeIt KeyType;

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

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

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

   534       //b.me=e;

   535       //container.set(b);

   536       //}

   537       G.getFirst(first_false);

   538       NodeIt e_prev;

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

   540 	container[e].prev=e_prev;

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

   542 	e_prev=e;

   543       }

   544     }

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

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

   547     //FIXME

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

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

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

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

   552   };

   553 */

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

   557   class MaxFlow2 {

   558   public:

   559     typedef typename Graph::NodeIt NodeIt;

   560     typedef typename Graph::EdgeIt EdgeIt;

   561     typedef typename Graph::EachEdgeIt EachEdgeIt;

   562     typedef typename Graph::OutEdgeIt OutEdgeIt;

   563     typedef typename Graph::InEdgeIt InEdgeIt;

   564   private:

   565     const Graph& G;

   566     std::list<NodeIt>& S;

   567     std::list<NodeIt>& T;

   568     FlowMap& flow;

   569     const CapacityMap& capacity;

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

   571     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   572     typedef typename AugGraph::EdgeIt AugEdgeIt;

   573     typename Graph::NodeMap<bool> SMap;

   574     typename Graph::NodeMap<bool> TMap;

   575   public:

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

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

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

   579 	SMap.set(*i, true);

   580       }

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

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

   583 	TMap.set(*i, true);

   584       }

   585     }

   586     bool augment() {

   587       AugGraph res_graph(G, flow, capacity);

   588       bool _augment=false;

   589       NodeIt reached_t_node;

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

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

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

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

   595 	res_bfs.pushAndSetReached(*i);

   596       }

   597       //res_bfs.pushAndSetReached(s);

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

   600       //filled up with invalid iterators

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

   604       //searching for augmenting path

   605       while ( !res_bfs.finished() ) {

   606 	AugOutEdgeIt e=AugOutEdgeIt(res_bfs);

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

   608 	  NodeIt v=res_graph.tail(e);

   609 	  NodeIt w=res_graph.head(e);

   610 	  pred.set(w, e);

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

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

   613 	  } else {

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

   615 	  }

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

   617 	    _augment=true;

   618 	    reached_t_node=res_graph.head(e);

   619 	    break;

   620 	  }

   621 	}

   623 	++res_bfs;

   624       } //end of searching augmenting path

   626       if (_augment) {

   627 	NodeIt n=reached_t_node;

   628 	Number augment_value=free.get(reached_t_node);

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

   630 	  AugEdgeIt e=pred.get(n);

   631 	  e.augment(augment_value);

   632 	  n=res_graph.tail(e);

   633 	}

   634       }

   636       return _augment;

   637     }

   638     void run() {

   639       while (augment()) { }

   640     }

   641     Number flowValue() {

   642       Number a=0;

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

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

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

   646 	  a+=flow.get(e);

   647 	}

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

   649 	  a-=flow.get(e);

   650 	}

   651       }

   652       return a;

   653     }

   654   };

   658 } // namespace hugo

   660 #endif //EDMONDS_KARP_HH

author	klao
	Thu, 26 Feb 2004 16:07:40 +0000
changeset 132	1ac27e476e25
parent 107	8d62f0072ff0
child 133	0631992fe7a1
permissions	-rw-r--r--