lemon-0.x: src/work/marci/edmonds

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

     2 #ifndef HUGO_EDMONDS_KARP_H

     3 #define HUGO_EDMONDS_KARP_H

     5 #include <algorithm>

     6 #include <list>

     7 #include <iterator>

     9 #include <bfs_iterator.h>

    10 #include <invalid.h>

    11 #include <graph_wrapper.h>

    12 #include <maps.h>

    14 namespace hugo {

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

    17 //   class ResGraph {

    18 //   public:

    19 //     typedef typename Graph::Node Node;

    20 //     typedef typename Graph::NodeIt NodeIt;

    21 //   private:

    22 //     typedef typename Graph::SymEdgeIt OldSymEdgeIt;

    23 //     const Graph& G;

    24 //     const CapacityMap& capacity;

    25 //     FlowMap& flow;

    26 //   public:

    27 //     ResGraph(const Graph& _G, const CapacityMap& _capacity, FlowMap& _flow) :

    28 //       G(_G), capacity(_capacity), flow(_flow) { }

    30 //     class Edge;

    31 //     class OutEdgeIt;

    32 //     friend class Edge;

    33 //     friend class OutEdgeIt;

    35 //     class Edge {

    36 //       friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;

    37 //     protected:

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

    39 //       OldSymEdgeIt sym;

    40 //     public:

    41 //       Edge() { }

    42 //       //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }

    43 //       Number free() const {

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

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

    46 // 	} else {

    47 // 	  return (resG->flow.get(sym));

    48 // 	}

    49 //       }

    50 //       bool valid() const { return sym.valid(); }

    51 //       void augment(Number a) const {

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

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

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

    55 // 	} else {

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

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

    58 // 	}

    59 //       }

    60 //     };

    62 //     class OutEdgeIt : public Edge {

    63 //       friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;

    64 //     public:

    65 //       OutEdgeIt() { }

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

    67 //     private:

    68 //       OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {

    69 //       	resG=&_resG;

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

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

    72 //       }

    73 //     public:

    74 //       OutEdgeIt& operator++() {

    75 // 	++sym;

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

    77 // 	return *this;

    78 //       }

    79 //     };

    81 //     void /*getF*/first(OutEdgeIt& e, Node v) const {

    82 //       e=OutEdgeIt(*this, v);

    83 //     }

    84 //     void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }

    86 //     template< typename It >

    87 //     It first() const {

    88 //       It e;

    89 //       /*getF*/first(e);

    90 //       return e;

    91 //     }

    93 //     template< typename It >

    94 //     It first(Node v) const {

    95 //       It e;

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

    97 //       return e;

    98 //     }

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

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

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

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

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

   108 //     template <typename S>

   109 //     class NodeMap {

   110 //       typename Graph::NodeMap<S> node_map;

   111 //     public:

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

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

   114 //       void set(Node nit, S a) { node_map.set(nit, a); }

   115 //       S get(Node nit) const { return node_map.get(nit); }

   116 //       S& operator[](Node nit) { return node_map[nit]; }

   117 //       const S& operator[](Node nit) const { return node_map[nit]; }

   118 //     };

   120 //   };

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

   124 //   class ResGraph2 {

   125 //   public:

   126 //     typedef typename Graph::Node Node;

   127 //     typedef typename Graph::NodeIt NodeIt;

   128 //   private:

   129 //     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;

   130 //     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   131 //     typedef typename Graph::InEdgeIt OldInEdgeIt;

   133 //     const Graph& G;

   134 //     FlowMap& flow;

   135 //     const CapacityMap& capacity;

   136 //   public:

   137 //     ResGraph2(const Graph& _G, FlowMap& _flow,

   138 // 	     const CapacityMap& _capacity) :

   139 //       G(_G), flow(_flow), capacity(_capacity) { }

   141 //     class Edge;

   142 //     class OutEdgeIt;

   143 //     friend class Edge;

   144 //     friend class OutEdgeIt;

   146 //     class Edge {

   147 //       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;

   148 //     protected:

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

   150 //       //OldSymEdgeIt sym;

   151 //       OldOutEdgeIt out;

   152 //       OldInEdgeIt in;

   153 //       bool out_or_in; //true, iff out

   154 //     public:

   155 //       Edge() : out_or_in(true) { }

   156 //       Number free() const {

   157 // 	if (out_or_in) {

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

   159 // 	} else {

   160 // 	  return (resG->flow.get(in));

   161 // 	}

   162 //       }

   163 //       bool valid() const {

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

   165 //       void augment(Number a) const {

   166 // 	if (out_or_in) {

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

   168 // 	} else {

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

   170 // 	}

   171 //       }

   172 //     };

   174 //     class OutEdgeIt : public Edge {

   175 //       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;

   176 //     public:

   177 //       OutEdgeIt() { }

   178 //     private:

   179 //       OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {

   180 //       	resG=&_resG;

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

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

   183 // 	if (!out.valid()) {

   184 // 	  out_or_in=0;

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

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

   187 // 	}

   188 //       }

   189 //     public:

   190 //       OutEdgeIt& operator++() {

   191 // 	if (out_or_in) {

   192 // 	  Node v=resG->G.aNode(out);

   193 // 	  ++out;

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

   195 // 	  if (!out.valid()) {

   196 // 	    out_or_in=0;

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

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

   199 // 	  }

   200 // 	} else {

   201 // 	  ++in;

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

   203 // 	}

   204 // 	return *this;

   205 //       }

   206 //     };

   208 //     void /*getF*/first(OutEdgeIt& e, Node v) const {

   209 //       e=OutEdgeIt(*this, v);

   210 //     }

   211 //     void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }

   213 //     template< typename It >

   214 //     It first() const {

   215 //       It e;

   216 //       /*getF*/first(e);

   217 //       return e;

   218 //     }

   220 //     template< typename It >

   221 //     It first(Node v) const {

   222 //       It e;

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

   224 //       return e;

   225 //     }

   227 //     Node tail(Edge e) const {

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

   229 //     Node head(Edge e) const {

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

   232 //     Node aNode(OutEdgeIt e) const {

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

   234 //     Node bNode(OutEdgeIt e) const {

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

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

   239 //     template <typename S>

   240 //     class NodeMap {

   241 //       typename Graph::NodeMap<S> node_map;

   242 //     public:

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

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

   245 //       void set(Node nit, S a) { node_map.set(nit, a); }

   246 //       S get(Node nit) const { return node_map.get(nit); }

   247 //     };

   248 //   };

   251   template <typename Graph, typename Number,

   252 	    typename CapacityMap, typename FlowMap>

   253   class MaxFlow {

   254   protected:

   255     typedef typename Graph::Node Node;

   256     typedef typename Graph::Edge Edge;

   257     typedef typename Graph::EdgeIt EdgeIt;

   258     typedef typename Graph::OutEdgeIt OutEdgeIt;

   259     typedef typename Graph::InEdgeIt InEdgeIt;

   260     const Graph* g;

   261     Node s;

   262     Node t;

   263     const CapacityMap* capacity;

   264     FlowMap* flow;

   265     typedef ResGraphWrapper<const Graph, Number, CapacityMap, FlowMap> ResGW;

   266     typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;

   267     typedef typename ResGW::Edge ResGWEdge;

   268   public:

   270     MaxFlow(const Graph& _g, Node _s, Node _t, const CapacityMap& _capacity,

   271 	    FlowMap& _flow) :

   272       g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow) { }

   274     bool augmentOnShortestPath() {

   275       ResGW res_graph(*g, *capacity, *flow);

   276       bool _augment=false;

   278       BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >

   279 	bfs(res_graph);

   280       bfs.pushAndSetReached(s);

   282       typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);

   283       pred.set(s, INVALID);

   285       typename ResGW::template NodeMap<Number> free(res_graph);

   287       //searching for augmenting path

   288       while ( !bfs.finished() ) {

   289 	ResGWOutEdgeIt e=bfs;

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

   291 	  Node v=res_graph.tail(e);

   292 	  Node w=res_graph.head(e);

   293 	  pred.set(w, e);

   294 	  if (res_graph.valid(pred[v])) {

   295 	    free.set(w, std::min(free[v], res_graph.resCap(e)));

   296 	  } else {

   297 	    free.set(w, res_graph.resCap(e));

   298 	  }

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

   300 	}

   302 	++bfs;

   303       } //end of searching augmenting path

   305       if (_augment) {

   306 	Node n=t;

   307 	Number augment_value=free[t];

   308 	while (res_graph.valid(pred[n])) {

   309 	  ResGWEdge e=pred[n];

   310 	  res_graph.augment(e, augment_value);

   311 	  n=res_graph.tail(e);

   312 	}

   313       }

   315       return _augment;

   316     }

   318     template<typename MapGraphWrapper>

   319     class DistanceMap {

   320     protected:

   321       const MapGraphWrapper* g;

   322       typename MapGraphWrapper::template NodeMap<int> dist;

   323     public:

   324       DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }

   325       void set(const typename MapGraphWrapper::Node& n, int a) {

   326 	dist.set(n, a);

   327       }

   328       int operator[](const typename MapGraphWrapper::Node& n)

   329 	{ return dist[n]; }

   330 //       int get(const typename MapGraphWrapper::Node& n) const {

   331 // 	return dist[n]; }

   332 //       bool get(const typename MapGraphWrapper::Edge& e) const {

   333 // 	return (dist.get(g->tail(e))<dist.get(g->head(e))); }

   334       bool operator[](const typename MapGraphWrapper::Edge& e) const {

   335 	return (dist[g->tail(e)]<dist[g->head(e)]);

   336       }

   337     };

   339     template<typename MutableGraph> bool augmentOnBlockingFlow() {

   340       typedef MutableGraph MG;

   341       bool _augment=false;

   343       ResGW res_graph(*g, *capacity, *flow);

   345       BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >

   346 	bfs(res_graph);

   348       bfs.pushAndSetReached(s);

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

   350       DistanceMap<ResGW> dist(res_graph);

   351       while ( !bfs.finished() ) {

   352 	ResGWOutEdgeIt e=bfs;

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

   354 	  dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);

   355 	}

   356 	++bfs;

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

   359       MG F;

   360       ConstMap<typename ResGW::Node, bool> true_map(true);

   361       typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,

   362 	DistanceMap<ResGW> > FilterResGW;

   363       FilterResGW filter_res_graph(res_graph, true_map, dist);

   364       typename ResGW::template NodeMap<typename MG::Node>

   365 	res_graph_to_F(res_graph);

   366       {

   367 	typename ResGW::NodeIt n;

   368 	for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {

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

   370 	}

   371       }

   373       typename MG::Node sF=res_graph_to_F[s];

   374       typename MG::Node tF=res_graph_to_F[t];

   375       typename MG::template EdgeMap<ResGWEdge> original_edge(F);

   376       typename MG::template EdgeMap<Number> residual_capacity(F);

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

   379       //which are in some shortest paths

   380       {

   381 	typename FilterResGW::EdgeIt e;

   382 	for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {

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

   384 	  typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);

   385 	  original_edge.update();

   386 	  original_edge.set(f, e);

   387 	  residual_capacity.update();

   388 	  residual_capacity.set(f, res_graph.resCap(e));

   389 	  //}

   390 	}

   391       }

   393       bool __augment=true;

   395       while (__augment) {

   396 	__augment=false;

   397 	//computing blocking flow with dfs

   399 	DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F);

   400 	typename MG::template NodeMap<typename MG::Edge> pred(F);

   401 	pred.set(sF, INVALID);

   402 	//invalid iterators for sources

   404 	typename MG::template NodeMap<Number> free(F);

   406 	dfs.pushAndSetReached(sF);

   407 	while (!dfs.finished()) {

   408 	  ++dfs;

   409 	  if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {

   410 	    if (dfs.isBNodeNewlyReached()) {

   411 	      typename MG::Node v=F.aNode(dfs);

   412 	      typename MG::Node w=F.bNode(dfs);

   413 	      pred.set(w, dfs);

   414 	      if (F.valid(pred[v])) {

   415 		free.set(w, std::min(free[v], residual_capacity[dfs]));

   416 	      } else {

   417 		free.set(w, residual_capacity[dfs]);

   418 	      }

   419 	      if (w==tF) {

   420 		__augment=true;

   421 		_augment=true;

   422 		break;

   423 	      }

   425 	    } else {

   426 	      F.erase(/*typename MG::OutEdgeIt*/(dfs));

   427 	    }

   428 	  }

   429 	}

   431 	if (__augment) {

   432 	  typename MG::Node n=tF;

   433 	  Number augment_value=free[tF];

   434 	  while (F.valid(pred[n])) {

   435 	    typename MG::Edge e=pred[n];

   436 	    res_graph.augment(original_edge[e], augment_value);

   437 	    n=F.tail(e);

   438 	    if (residual_capacity[e]==augment_value)

   439 	      F.erase(e);

   440 	    else

   441 	      residual_capacity.set(e, residual_capacity[e]-augment_value);

   442 	  }

   443 	}

   445       }

   447       return _augment;

   448     }

   450     template<typename MutableGraph> bool augmentOnBlockingFlow1() {

   451       typedef MutableGraph MG;

   452       bool _augment=false;

   454       ResGW res_graph(*g, *capacity, *flow);

   456       //bfs for distances on the residual graph

   457       BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >

   458 	bfs(res_graph);

   459       bfs.pushAndSetReached(s);

   460       typename ResGW::template NodeMap<int>

   461 	dist(res_graph); //filled up with 0's

   463       //F will contain the physical copy of the residual graph

   464       //with the set of edges which are on shortest paths

   465       MG F;

   466       typename ResGW::template NodeMap<typename MG::Node>

   467 	res_graph_to_F(res_graph);

   468       {

   469 	typename ResGW::NodeIt n;

   470 	for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {

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

   472 	}

   473       }

   475       typename MG::Node sF=res_graph_to_F[s];

   476       typename MG::Node tF=res_graph_to_F[t];

   477       typename MG::template EdgeMap<ResGWEdge> original_edge(F);

   478       typename MG::template EdgeMap<Number> residual_capacity(F);

   480       while ( !bfs.finished() ) {

   481 	ResGWOutEdgeIt e=bfs;

   482 	if (res_graph.valid(e)) {

   483 	  if (bfs.isBNodeNewlyReached()) {

   484 	    dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);

   485 	    typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);

   486 	    original_edge.update();

   487 	    original_edge.set(f, e);

   488 	    residual_capacity.update();

   489 	    residual_capacity.set(f, res_graph.resCap(e));

   490 	  } else {

   491 	    if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {

   492 	      typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);

   493 	      original_edge.update();

   494 	      original_edge.set(f, e);

   495 	      residual_capacity.update();

   496 	      residual_capacity.set(f, res_graph.resCap(e));

   497 	    }

   498 	  }

   499 	}

   500 	++bfs;

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

   503       bool __augment=true;

   505       while (__augment) {

   506 	__augment=false;

   507 	//computing blocking flow with dfs

   508 	DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F);

   509 	typename MG::template NodeMap<typename MG::Edge> pred(F);

   510 	pred.set(sF, INVALID);

   511 	//invalid iterators for sources

   513 	typename MG::template NodeMap<Number> free(F);

   515 	dfs.pushAndSetReached(sF);

   516 	while (!dfs.finished()) {

   517 	  ++dfs;

   518 	  if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {

   519 	    if (dfs.isBNodeNewlyReached()) {

   520 	      typename MG::Node v=F.aNode(dfs);

   521 	      typename MG::Node w=F.bNode(dfs);

   522 	      pred.set(w, dfs);

   523 	      if (F.valid(pred[v])) {

   524 		free.set(w, std::min(free[v], residual_capacity[dfs]));

   525 	      } else {

   526 		free.set(w, residual_capacity[dfs]);

   527 	      }

   528 	      if (w==tF) {

   529 		__augment=true;

   530 		_augment=true;

   531 		break;

   532 	      }

   534 	    } else {

   535 	      F.erase(/*typename MG::OutEdgeIt*/(dfs));

   536 	    }

   537 	  }

   538 	}

   540 	if (__augment) {

   541 	  typename MG::Node n=tF;

   542 	  Number augment_value=free[tF];

   543 	  while (F.valid(pred[n])) {

   544 	    typename MG::Edge e=pred[n];

   545 	    res_graph.augment(original_edge[e], augment_value);

   546 	    n=F.tail(e);

   547 	    if (residual_capacity[e]==augment_value)

   548 	      F.erase(e);

   549 	    else

   550 	      residual_capacity.set(e, residual_capacity[e]-augment_value);

   551 	  }

   552 	}

   554       }

   556       return _augment;

   557     }

   559     bool augmentOnBlockingFlow2() {

   560       bool _augment=false;

   562       ResGW res_graph(*g, *capacity, *flow);

   564       BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >

   565 	bfs(res_graph);

   567       bfs.pushAndSetReached(s);

   568       DistanceMap<ResGW> dist(res_graph);

   569       while ( !bfs.finished() ) {

   570  	ResGWOutEdgeIt e=bfs;

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

   572  	  dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);

   573  	}

   574 	++bfs;

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

   577       //Subgraph containing the edges on some shortest paths

   578       ConstMap<typename ResGW::Node, bool> true_map(true);

   579       typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,

   580 	DistanceMap<ResGW> > FilterResGW;

   581       FilterResGW filter_res_graph(res_graph, true_map, dist);

   583       //Subgraph, which is able to delete edges which are already

   584       //met by the dfs

   585       typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>

   586  	first_out_edges(filter_res_graph);

   587       typename FilterResGW::NodeIt v;

   588       for(filter_res_graph.first(v); filter_res_graph.valid(v);

   589  	  filter_res_graph.next(v))

   590       {

   591  	typename FilterResGW::OutEdgeIt e;

   592  	filter_res_graph.first(e, v);

   593  	first_out_edges.set(v, e);

   594       }

   595       typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::

   596 	template NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;

   597       ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);

   599       bool __augment=true;

   601       while (__augment) {

   603  	__augment=false;

   604   	//computing blocking flow with dfs

   605   	DfsIterator< ErasingResGW,

   606 	  typename ErasingResGW::template NodeMap<bool> >

   607   	  dfs(erasing_res_graph);

   608  	typename ErasingResGW::

   609 	  template NodeMap<typename ErasingResGW::OutEdgeIt>

   610 	  pred(erasing_res_graph);

   611  	pred.set(s, INVALID);

   612   	//invalid iterators for sources

   614   	typename ErasingResGW::template NodeMap<Number>

   615 	  free1(erasing_res_graph);

   617  	dfs.pushAndSetReached(

   618 	  typename ErasingResGW::Node(

   619 	    typename FilterResGW::Node(

   620 	      typename ResGW::Node(s)

   621 	      )

   622 	    )

   623 	  );

   624  	while (!dfs.finished()) {

   625  	  ++dfs;

   626  	  if (erasing_res_graph.valid(

   627  		typename ErasingResGW::OutEdgeIt(dfs)))

   628  	  {

   629   	    if (dfs.isBNodeNewlyReached()) {

   631  	      typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);

   632  	      typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);

   634  	      pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));

   635  	      if (erasing_res_graph.valid(pred[v])) {

   636  		free1.set(w, std::min(free1[v], res_graph.resCap(

   637 				       typename ErasingResGW::OutEdgeIt(dfs))));

   638  	      } else {

   639  		free1.set(w, res_graph.resCap(

   640 			   typename ErasingResGW::OutEdgeIt(dfs)));

   641  	      }

   643  	      if (w==t) {

   644  		__augment=true;

   645  		_augment=true;

   646  		break;

   647  	      }

   648  	    } else {

   649  	      erasing_res_graph.erase(dfs);

   650 	    }

   651 	  }

   652 	}

   654   	if (__augment) {

   655    	  typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));

   656 // 	  typename ResGW::NodeMap<Number> a(res_graph);

   657 // 	  typename ResGW::Node b;

   658 // 	  Number j=a[b];

   659 // 	  typename FilterResGW::NodeMap<Number> a1(filter_res_graph);

   660 // 	  typename FilterResGW::Node b1;

   661 // 	  Number j1=a1[b1];

   662 // 	  typename ErasingResGW::NodeMap<Number> a2(erasing_res_graph);

   663 // 	  typename ErasingResGW::Node b2;

   664 // 	  Number j2=a2[b2];

   665  	  Number augment_value=free1[n];

   666  	  while (erasing_res_graph.valid(pred[n])) {

   667  	    typename ErasingResGW::OutEdgeIt e=pred[n];

   668  	    res_graph.augment(e, augment_value);

   669  	    n=erasing_res_graph.tail(e);

   670  	    if (res_graph.resCap(e)==0)

   671  	      erasing_res_graph.erase(e);

   672 	}

   673       }

   675       } //while (__augment)

   677       return _augment;

   678     }

   680     void run() {

   681       //int num_of_augmentations=0;

   682       while (augmentOnShortestPath()) {

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

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

   685 	//std::cout<<std::endl;

   686       }

   687     }

   689     template<typename MutableGraph> void run() {

   690       //int num_of_augmentations=0;

   691       //while (augmentOnShortestPath()) {

   692 	while (augmentOnBlockingFlow<MutableGraph>()) {

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

   694 	//std::cout<<std::endl;

   695       }

   696     }

   698     Number flowValue() {

   699       Number a=0;

   700       OutEdgeIt e;

   701       for(g->first(e, s); g->valid(e); g->next(e)) {

   702 	a+=(*flow)[e];

   703       }

   704       return a;

   705     }

   707   };

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

   711 //   class MaxMatching {

   712 //   public:

   713 //     typedef typename Graph::Node Node;

   714 //     typedef typename Graph::NodeIt NodeIt;

   715 //     typedef typename Graph::Edge Edge;

   716 //     typedef typename Graph::EdgeIt EdgeIt;

   717 //     typedef typename Graph::OutEdgeIt OutEdgeIt;

   718 //     typedef typename Graph::InEdgeIt InEdgeIt;

   720 //     typedef typename Graph::NodeMap<bool> SMap;

   721 //     typedef typename Graph::NodeMap<bool> TMap;

   722 //   private:

   723 //     const Graph* G;

   724 //     SMap* S;

   725 //     TMap* T;

   726 //     //Node s;

   727 //     //Node t;

   728 //     FlowMap* flow;

   729 //     const CapacityMap* capacity;

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

   731 //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   732 //     typedef typename AugGraph::Edge AugEdge;

   733 //     typename Graph::NodeMap<int> used; //0

   735 //   public:

   736 //     MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :

   737 //       G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }

   738 //     bool augmentOnShortestPath() {

   739 //       AugGraph res_graph(*G, *flow, *capacity);

   740 //       bool _augment=false;

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

   743 //       BfsIterator< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph);

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

   745 //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {

   746 // 	if ((S->get(s)) && (used.get(s)<1) ) {

   747 // 	  //Number u=0;

   748 // 	  //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))

   749 // 	  //u+=flow->get(e);

   750 // 	  //if (u<1) {

   751 // 	    bfs.pushAndSetReached(s);

   752 // 	    pred.set(s, AugEdge(INVALID));

   753 // 	    //}

   754 // 	}

   755 //       }

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

   759 //       Node n;

   760 //       //searching for augmenting path

   761 //       while ( !bfs.finished() ) {

   762 // 	AugOutEdgeIt e=bfs;

   763 // 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {

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

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

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

   767 // 	  if (res_graph.valid(pred.get(v))) {

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

   769 // 	  } else {

   770 // 	    free.set(w, res_graph.free(e));

   771 // 	  }

   772 // 	  n=res_graph.head(e);

   773 // 	  if (T->get(n) && (used.get(n)<1) ) {

   774 // 	    //Number u=0;

   775 // 	    //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))

   776 // 	    //u+=flow->get(f);

   777 // 	    //if (u<1) {

   778 // 	      _augment=true;

   779 // 	      break;

   780 // 	      //}

   781 // 	  }

   782 // 	}

   784 // 	++bfs;

   785 //       } //end of searching augmenting path

   787 //       if (_augment) {

   788 // 	//Node n=t;

   789 // 	used.set(n, 1); //mind2 vegen jav

   790 // 	Number augment_value=free.get(n);

   791 // 	while (res_graph.valid(pred.get(n))) {

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

   793 // 	  res_graph.augment(e, augment_value);

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

   795 // 	}

   796 // 	used.set(n, 1); //mind2 vegen jav

   797 //       }

   799 //       return _augment;

   800 //     }

   802 // //     template<typename MutableGraph> bool augmentOnBlockingFlow() {

   803 // //       bool _augment=false;

   805 // //       AugGraph res_graph(*G, *flow, *capacity);

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

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

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

   815 // //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {

   816 // // 	if (S->get(s)) {

   817 // // 	  Number u=0;

   818 // // 	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))

   819 // // 	    u+=flow->get(e);

   820 // // 	  if (u<1) {

   821 // // 	    bfs.pushAndSetReached(s);

   822 // // 	    //pred.set(s, AugEdge(INVALID));

   823 // // 	  }

   824 // // 	}

   825 // //       }

   830 // //       //bfs.pushAndSetReached(s);

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

   832 // //       while ( !bfs.finished() ) {

   833 // // 	AugOutEdgeIt e=bfs;

   834 // // 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {

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

   836 // // 	}

   838 // // 	++bfs;

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

   841 // //       MutableGraph F;

   842 // //       typename AugGraph::NodeMap<typename MutableGraph::Node>

   843 // // 	res_graph_to_F(res_graph);

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

   845 // // 	res_graph_to_F.set(n, F.addNode());

   846 // //       }

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

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

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

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

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

   855 // //       //which are in some shortest paths

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

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

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

   859 // // 	  original_edge.update();

   860 // // 	  original_edge.set(f, e);

   861 // // 	  residual_capacity.update();

   862 // // 	  residual_capacity.set(f, res_graph.free(e));

   863 // // 	}

   864 // //       }

   866 // //       bool __augment=true;

   868 // //       while (__augment) {

   869 // // 	__augment=false;

   870 // // 	//computing blocking flow with dfs

   871 // // 	typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;

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

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

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

   875 // // 	//invalid iterators for sources

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

   879 // // 	dfs.pushAndSetReached(sF);

   880 // // 	while (!dfs.finished()) {

   881 // // 	  ++dfs;

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

   883 // // 	    if (dfs.isBNodeNewlyReached()) {

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

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

   886 // // 	      pred.set(w, dfs);

   887 // // 	      if (F.valid(pred.get(v))) {

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

   889 // // 	      } else {

   890 // // 		free.set(w, residual_capacity.get(dfs));

   891 // // 	      }

   892 // // 	      if (w==tF) {

   893 // // 		__augment=true;

   894 // // 		_augment=true;

   895 // // 		break;

   896 // // 	      }

   898 // // 	    } else {

   899 // // 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));

   900 // // 	    }

   901 // // 	  }

   902 // // 	}

   904 // // 	if (__augment) {

   905 // // 	  typename MutableGraph::Node n=tF;

   906 // // 	  Number augment_value=free.get(tF);

   907 // // 	  while (F.valid(pred.get(n))) {

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

   909 // // 	    res_graph.augment(original_edge.get(e), augment_value);

   910 // // 	    n=F.tail(e);

   911 // // 	    if (residual_capacity.get(e)==augment_value)

   912 // // 	      F.erase(e);

   913 // // 	    else

   914 // // 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);

   915 // // 	  }

   916 // // 	}

   918 // //       }

   920 // //       return _augment;

   921 // //     }

   922 //     bool augmentOnBlockingFlow2() {

   923 //       bool _augment=false;

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

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

   927 //       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;

   928 //       typedef typename EAugGraph::Edge EAugEdge;

   930 //       EAugGraph res_graph(*G, *flow, *capacity);

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

   933 //       BfsIterator<

   934 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,

   935 // 	/*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/

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

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

   940 //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {

   941 // 	if (S->get(s)) {

   942 // 	  Number u=0;

   943 // 	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))

   944 // 	    u+=flow->get(e);

   945 // 	  if (u<1) {

   946 // 	    bfs.pushAndSetReached(s);

   947 // 	    //pred.set(s, AugEdge(INVALID));

   948 // 	  }

   949 // 	}

   950 //       }

   953 //       //bfs.pushAndSetReached(s);

   955 //       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::

   956 // 	NodeMap<int>& dist=res_graph.dist;

   958 //       while ( !bfs.finished() ) {

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

   960 // 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {

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

   962 // 	}

   963 // 	++bfs;

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

   966 //       bool __augment=true;

   968 //       while (__augment) {

   970 // 	__augment=false;

   971 // 	//computing blocking flow with dfs

   972 // 	typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;

   973 // 	DfsIterator< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >

   974 // 	  dfs(res_graph);

   975 // 	typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);

   976 // 	//pred.set(s, EAugEdge(INVALID));

   977 // 	//invalid iterators for sources

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

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

   983 //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {

   984 // 	if (S->get(s)) {

   985 // 	  Number u=0;

   986 // 	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))

   987 // 	    u+=flow->get(e);

   988 // 	  if (u<1) {

   989 // 	    dfs.pushAndSetReached(s);

   990 // 	    //pred.set(s, AugEdge(INVALID));

   991 // 	  }

   992 // 	}

   993 //       }

   997 //       //dfs.pushAndSetReached(s);

   998 //       typename EAugGraph::Node n;

   999 // 	while (!dfs.finished()) {

  1000 // 	  ++dfs;

  1001 // 	  if (res_graph.valid(EAugOutEdgeIt(dfs))) {

  1002 // 	    if (dfs.isBNodeNewlyReached()) {

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

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

  1007 // 	      pred.set(w, EAugOutEdgeIt(dfs));

  1008 // 	      if (res_graph.valid(pred.get(v))) {

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

  1010 // 	      } else {

  1011 // 		free.set(w, res_graph.free(dfs));

  1012 // 	      }

  1014 // 	      n=w;

  1015 // 	      if (T->get(w)) {

  1016 // 		Number u=0;

  1017 // 		for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))

  1018 // 		  u+=flow->get(f);

  1019 // 		if (u<1) {

  1020 // 		  __augment=true;

  1021 // 		  _augment=true;

  1022 // 		  break;

  1023 // 		}

  1024 // 	      }

  1025 // 	    } else {

  1026 // 	      res_graph.erase(dfs);

  1027 // 	    }

  1028 // 	  }

  1030 // 	}

  1032 // 	if (__augment) {

  1033 // 	  // typename EAugGraph::Node n=t;

  1034 // 	  Number augment_value=free.get(n);

  1035 // 	  while (res_graph.valid(pred.get(n))) {

  1036 // 	    EAugEdge e=pred.get(n);

  1037 // 	    res_graph.augment(e, augment_value);

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

  1039 // 	    if (res_graph.free(e)==0)

  1040 // 	      res_graph.erase(e);

  1041 // 	  }

  1042 // 	}

  1044 //       }

  1046 //       return _augment;

  1047 //     }

  1048 //     void run() {

  1049 //       //int num_of_augmentations=0;

  1050 //       while (augmentOnShortestPath()) {

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

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

  1053 // 	//std::cout<<std::endl;

  1054 //       }

  1055 //     }

  1056 // //     template<typename MutableGraph> void run() {

  1057 // //       //int num_of_augmentations=0;

  1058 // //       //while (augmentOnShortestPath()) {

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

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

  1061 // // 	//std::cout<<std::endl;

  1062 // //       }

  1063 // //     }

  1064 //     Number flowValue() {

  1065 //       Number a=0;

  1066 //       EdgeIt e;

  1067 //       for(G->/*getF*/first(e); G->valid(e); G->next(e)) {

  1068 // 	a+=flow->get(e);

  1069 //       }

  1070 //       return a;

  1071 //     }

  1072 //   };

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

  1080 // //   class MaxFlow2 {

  1081 // //   public:

  1082 // //     typedef typename Graph::Node Node;

  1083 // //     typedef typename Graph::Edge Edge;

  1084 // //     typedef typename Graph::EdgeIt EdgeIt;

  1085 // //     typedef typename Graph::OutEdgeIt OutEdgeIt;

  1086 // //     typedef typename Graph::InEdgeIt InEdgeIt;

  1087 // //   private:

  1088 // //     const Graph& G;

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

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

  1091 // //     FlowMap& flow;

  1092 // //     const CapacityMap& capacity;

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

  1094 // //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

  1095 // //     typedef typename AugGraph::Edge AugEdge;

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

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

  1098 // //   public:

  1099 // //     MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {

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

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

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

  1103 // //       }

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

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

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

  1107 // //       }

  1108 // //     }

  1109 // //     bool augment() {

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

  1111 // //       bool _augment=false;

  1112 // //       Node reached_t_node;

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

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

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

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

  1118 // // 	bfs.pushAndSetReached(*i);

  1119 // //       }

  1120 // //       //bfs.pushAndSetReached(s);

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

  1123 // //       //filled up with invalid iterators

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

  1127 // //       //searching for augmenting path

  1128 // //       while ( !bfs.finished() ) {

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

  1130 // // 	if (e.valid() && bfs.isBNodeNewlyReached()) {

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

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

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

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

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

  1136 // // 	  } else {

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

  1138 // // 	  }

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

  1140 // // 	    _augment=true;

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

  1142 // // 	    break;

  1143 // // 	  }

  1144 // // 	}

  1146 // // 	++bfs;

  1147 // //       } //end of searching augmenting path

  1149 // //       if (_augment) {

  1150 // // 	Node n=reached_t_node;

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

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

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

  1154 // // 	  e.augment(augment_value);

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

  1156 // // 	}

  1157 // //       }

  1159 // //       return _augment;

  1160 // //     }

  1161 // //     void run() {

  1162 // //       while (augment()) { }

  1163 // //     }

  1164 // //     Number flowValue() {

  1165 // //       Number a=0;

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

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

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

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

  1170 // // 	}

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

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

  1173 // // 	}

  1174 // //       }

  1175 // //       return a;

  1176 // //     }

  1177 // //   };

  1180 } // namespace hugo

  1182 #endif //HUGO_EDMONDS_KARP_H

author	jacint
	Mon, 26 Apr 2004 17:05:22 +0000
changeset 422	ede61a3d229b
parent 389	770cc1f4861f
child 466	cd40ecf4d2a9
permissions	-rw-r--r--