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

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

    26     class EdgeIt;

    27     class OutEdgeIt;

    28     friend class EdgeIt;

    29     friend class OutEdgeIt;

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

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

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

    78       e=OutEdgeIt(*this, v);

    79     }

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

    82     template< typename It >

    83     It first() const {

    84       It e;

    85       getFirst(e);

    86       return e;

    87     }

    89     template< typename It >

    90     It first(NodeIt v) const {

    91       It e;

    92       getFirst(e, v);

    93       return e;

    94     }

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

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

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

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

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

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

   116   };

   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;

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

   135     class EdgeIt;

   136     class OutEdgeIt;

   137     friend class EdgeIt;

   138     friend class OutEdgeIt;

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

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

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

   203       e=OutEdgeIt(*this, v);

   204     }

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

   207     template< typename It >

   208     It first() const {

   209       It e;

   210       getFirst(e);

   211       return e;

   212     }

   214     template< typename It >

   215     It first(NodeIt v) const {

   216       It e;

   217       getFirst(e, v);

   218       return e;

   219     }

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

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

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

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

   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;

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

   262     class EdgeIt;

   263     class OutEdgeIt;

   264     friend class EdgeIt;

   265     friend class OutEdgeIt;

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

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

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

   339     template< typename It >

   340     It first() const {

   341       It e;

   342       getFirst(e);

   343       return e;

   344     }

   346     template< typename It >

   347     It first(NodeIt v) const {

   348       It e;

   349       getFirst(e, v);

   350       return e;

   351     }

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

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

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

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

   375   };

   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;

   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;

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

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

   409       res_bfs.pushAndSetReached(s);

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

   412       //filled up with invalid iterators

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

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

   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 	}

   432 	++res_bfs;

   433       } //end of searching augmenting path

   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       }

   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 	}

   466 	++bfs;

   467       } //end of searching augmenting path

   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;

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

   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 update() { container.resize(G.node_id); }

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

   545   };

   546 */

   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;

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

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

   591       //filled up with invalid iterators

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

   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 	}

   614 	++res_bfs;

   615       } //end of searching augmenting path

   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       }

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

   649 } // namespace hugo

   651 #endif //EDMONDS_KARP_HH

author	alpar
	Mon, 23 Feb 2004 07:05:27 +0000
changeset 118	38e16c594a4f
parent 100	f1de2ab64e1c
child 127	dcace15b1874
permissions	-rw-r--r--