lemon-0.x: src/work/edmonds_karp.h@fe81c4b117f4

     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>

    12 namespace hugo {

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

    15   class ResGraph {

    16   public:

    17     typedef typename Graph::Node Node;

    18     typedef typename Graph::NodeIt NodeIt;

    19   private:

    20     typedef typename Graph::SymEdgeIt OldSymEdgeIt;

    21     const Graph& G;

    22     FlowMap& flow;

    23     const CapacityMap& capacity;

    24   public:

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

    26 	     const CapacityMap& _capacity) :

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

    29     class Edge;

    30     class OutEdgeIt;

    31     friend class Edge;

    32     friend class OutEdgeIt;

    34     class Edge {

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

    36     protected:

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

    38       OldSymEdgeIt sym;

    39     public:

    40       Edge() { }

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

    42       Number free() const {

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

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

    45 	} else {

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

    47 	}

    48       }

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

    50       void augment(Number a) const {

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

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

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

    54 	} else {

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

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

    57 	}

    58       }

    59     };

    61     class OutEdgeIt : public Edge {

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

    63     public:

    64       OutEdgeIt() { }

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

    66     private:

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

    68       	resG=&_resG;

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

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

    71       }

    72     public:

    73       OutEdgeIt& operator++() {

    74 	++sym;

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

    76 	return *this;

    77       }

    78     };

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

    81       e=OutEdgeIt(*this, v);

    82     }

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

    85     template< typename It >

    86     It first() const {

    87       It e;

    88       /*getF*/first(e);

    89       return e;

    90     }

    92     template< typename It >

    93     It first(Node v) const {

    94       It e;

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

    96       return e;

    97     }

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

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

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

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

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

   107     template <typename S>

   108     class NodeMap {

   109       typename Graph::NodeMap<S> node_map;

   110     public:

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

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

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

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

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

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

   117     };

   119   };

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

   123   class ResGraph2 {

   124   public:

   125     typedef typename Graph::Node Node;

   126     typedef typename Graph::NodeIt NodeIt;

   127   private:

   128     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;

   129     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   130     typedef typename Graph::InEdgeIt OldInEdgeIt;

   132     const Graph& G;

   133     FlowMap& flow;

   134     const CapacityMap& capacity;

   135   public:

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

   137 	     const CapacityMap& _capacity) :

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

   140     class Edge;

   141     class OutEdgeIt;

   142     friend class Edge;

   143     friend class OutEdgeIt;

   145     class Edge {

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

   147     protected:

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

   149       //OldSymEdgeIt sym;

   150       OldOutEdgeIt out;

   151       OldInEdgeIt in;

   152       bool out_or_in; //true, iff out

   153     public:

   154       Edge() : out_or_in(true) { }

   155       Number free() const {

   156 	if (out_or_in) {

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

   158 	} else {

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

   160 	}

   161       }

   162       bool valid() const {

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

   164       void augment(Number a) const {

   165 	if (out_or_in) {

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

   167 	} else {

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

   169 	}

   170       }

   171     };

   173     class OutEdgeIt : public Edge {

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

   175     public:

   176       OutEdgeIt() { }

   177     private:

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

   179       	resG=&_resG;

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

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

   182 	if (!out.valid()) {

   183 	  out_or_in=0;

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

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

   186 	}

   187       }

   188     public:

   189       OutEdgeIt& operator++() {

   190 	if (out_or_in) {

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

   192 	  ++out;

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

   194 	  if (!out.valid()) {

   195 	    out_or_in=0;

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

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

   198 	  }

   199 	} else {

   200 	  ++in;

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

   202 	}

   203 	return *this;

   204       }

   205     };

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

   208       e=OutEdgeIt(*this, v);

   209     }

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

   212     template< typename It >

   213     It first() const {

   214       It e;

   215       /*getF*/first(e);

   216       return e;

   217     }

   219     template< typename It >

   220     It first(Node v) const {

   221       It e;

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

   223       return e;

   224     }

   226     Node tail(Edge e) const {

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

   228     Node head(Edge e) const {

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

   231     Node aNode(OutEdgeIt e) const {

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

   233     Node bNode(OutEdgeIt e) const {

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

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

   238     template <typename S>

   239     class NodeMap {

   240       typename Graph::NodeMap<S> node_map;

   241     public:

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

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

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

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

   246     };

   247   };

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

   251   class MaxFlow {

   252   public:

   253     typedef typename Graph::Node Node;

   254     typedef typename Graph::Edge Edge;

   255     typedef typename Graph::EdgeIt EdgeIt;

   256     typedef typename Graph::OutEdgeIt OutEdgeIt;

   257     typedef typename Graph::InEdgeIt InEdgeIt;

   259   private:

   260     const Graph* G;

   261     Node s;

   262     Node t;

   263     FlowMap* flow;

   264     const CapacityMap* capacity;

   265     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;

   266     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   267     typedef typename AugGraph::Edge AugEdge;

   269   public:

   270     MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :

   271       G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }

   272     bool augmentOnShortestPath() {

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

   274       bool _augment=false;

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

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

   278       res_bfs.pushAndSetReached(s);

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

   281       pred.set(s, AugEdge(INVALID));

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

   285       //searching for augmenting path

   286       while ( !res_bfs.finished() ) {

   287 	AugOutEdgeIt e=res_bfs;

   288 	if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {

   289 	  Node v=res_graph.tail(e);

   290 	  Node w=res_graph.head(e);

   291 	  pred.set(w, e);

   292 	  if (res_graph.valid(pred.get(v))) {

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

   294 	  } else {

   295 	    free.set(w, res_graph.free(e));

   296 	  }

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

   298 	}

   300 	++res_bfs;

   301       } //end of searching augmenting path

   303       if (_augment) {

   304 	Node n=t;

   305 	Number augment_value=free.get(t);

   306 	while (res_graph.valid(pred.get(n))) {

   307 	  AugEdge e=pred.get(n);

   308 	  res_graph.augment(e, augment_value);

   309 	  n=res_graph.tail(e);

   310 	}

   311       }

   313       return _augment;

   314     }

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

   317 //       bool _augment=false;

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

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

   322 //       BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);

   324 //       bfs.pushAndSetReached(s);

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

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

   327 // 	AugOutEdgeIt e=bfs;

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

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

   330 // 	}

   332 // 	++bfs;

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

   335 //       MutableGraph F;

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

   337 // 	res_graph_to_F(res_graph);

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

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

   340 //       }

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

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

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

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

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

   349 //       //which are in some shortest paths

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

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

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

   353 // 	  original_edge.update();

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

   355 // 	  residual_capacity.update();

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

   357 // 	}

   358 //       }

   360 //       bool __augment=true;

   362 //       while (__augment) {

   363 // 	__augment=false;

   364 // 	//computing blocking flow with dfs

   365 // 	typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;

   366 // 	DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);

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

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

   369 // 	//invalid iterators for sources

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

   373 // 	dfs.pushAndSetReached(sF);

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

   375 // 	  ++dfs;

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

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

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

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

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

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

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

   383 // 	      } else {

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

   385 // 	      }

   386 // 	      if (w==tF) {

   387 // 		__augment=true;

   388 // 		_augment=true;

   389 // 		break;

   390 // 	      }

   392 // 	    } else {

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

   394 // 	    }

   395 // 	  }

   396 // 	}

   398 // 	if (__augment) {

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

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

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

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

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

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

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

   406 // 	      F.erase(e);

   407 // 	    else

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

   409 // 	  }

   410 // 	}

   412 //       }

   414 //       return _augment;

   415 //     }

   417     template<typename GraphWrapper>

   418     class DistanceMap {

   419     protected:

   420       GraphWrapper gw;

   421       typename GraphWrapper::NodeMap<int> dist;

   422     public:

   423       DistanceMap(GraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }

   424       //NodeMap(const ListGraph& _G, T a) :

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

   426       void set(const typename GraphWrapper::Node& n, int a) { dist[n]=a; }

   427       int get(const typename GraphWrapper::Node& n) const { return dist[n]; }

   428       bool get(const typename GraphWrapper::Edge& e) const {

   429 	return (dist.get(gw.tail(e))<dist.get(gw.head(e)));

   430       }

   431       //typename std::vector<T>::reference operator[](Node n) {

   432       //return container[/*G.id(n)*/n.node->id]; }

   433       //typename std::vector<T>::const_reference operator[](Node n) const {

   434       //return container[/*G.id(n)*/n.node->id];

   435     };

   437     template<typename MutableGraph> bool augmentOnBlockingFlow() {

   438       bool _augment=false;

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

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

   443       BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);

   445       bfs.pushAndSetReached(s);

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

   447       DistanceMap<AugGraph> dist(res_graph);

   448       while ( !bfs.finished() ) {

   449 	AugOutEdgeIt e=bfs;

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

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

   452 	}

   453 	++bfs;

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

   456 //       MutableGraph F;

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

   458 // 	res_graph_to_F(res_graph);

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

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

   461 //       }

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

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

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

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

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

   470 //       //which are in some shortest paths

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

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

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

   474 // 	  original_edge.update();

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

   476 // 	  residual_capacity.update();

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

   478 // 	}

   479 //       }

   481       MutableGraph F;

   482       typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph;

   483       FilterResGraph filter_res_graph(res_graph, dist);

   484       typename AugGraph::NodeMap<typename MutableGraph::Node>

   485 	res_graph_to_F(res_graph);

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

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

   488       }

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

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

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

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

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

   497       //which are in some shortest paths

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

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

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

   501 	  original_edge.update();

   502 	  original_edge.set(f, e);

   503 	  residual_capacity.update();

   504 	  residual_capacity.set(f, res_graph.free(e));

   505 	}

   506       }

   508       bool __augment=true;

   510       while (__augment) {

   511 	__augment=false;

   512 	//computing blocking flow with dfs

   513 	typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;

   514 	DfsIterator5< TrivGraphWrapper<MutableGraph>, BlockingReachedMap > dfs(F);

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

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

   517 	//invalid iterators for sources

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

   521 	dfs.pushAndSetReached(sF);

   522 	while (!dfs.finished()) {

   523 	  ++dfs;

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

   525 	    if (dfs.isBNodeNewlyReached()) {

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

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

   528 	      pred.set(w, dfs);

   529 	      if (F.valid(pred.get(v))) {

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

   531 	      } else {

   532 		free.set(w, residual_capacity.get(dfs));

   533 	      }

   534 	      if (w==tF) {

   535 		__augment=true;

   536 		_augment=true;

   537 		break;

   538 	      }

   540 	    } else {

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

   542 	    }

   543 	  }

   544 	}

   546 	if (__augment) {

   547 	  typename MutableGraph::Node n=tF;

   548 	  Number augment_value=free.get(tF);

   549 	  while (F.valid(pred.get(n))) {

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

   551 	    res_graph.augment(original_edge.get(e), augment_value);

   552 	    n=F.tail(e);

   553 	    if (residual_capacity.get(e)==augment_value)

   554 	      F.erase(e);

   555 	    else

   556 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);

   557 	  }

   558 	}

   560       }

   562       return _augment;

   563     }

   565     template<typename MutableGraph> bool augmentOnBlockingFlow1() {

   566       bool _augment=false;

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

   570       //bfs for distances on the residual graph

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

   572       BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);

   573       bfs.pushAndSetReached(s);

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

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

   577       //with the set of edges which areon shortest paths

   578       MutableGraph F;

   579       typename AugGraph::NodeMap<typename MutableGraph::Node>

   580 	res_graph_to_F(res_graph);

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

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

   583       }

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

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

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

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

   589       while ( !bfs.finished() ) {

   590 	AugOutEdgeIt e=bfs;

   591 	if (res_graph.valid(e)) {

   592 	  if (bfs.isBNodeNewlyReached()) {

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

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

   595 	    original_edge.update();

   596 	    original_edge.set(f, e);

   597 	    residual_capacity.update();

   598 	    residual_capacity.set(f, res_graph.free(e));

   599 	  } else {

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

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

   602 	      original_edge.update();

   603 	      original_edge.set(f, e);

   604 	      residual_capacity.update();

   605 	      residual_capacity.set(f, res_graph.free(e));

   606 	    }

   607 	  }

   608 	}

   609 	++bfs;

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

   612       bool __augment=true;

   614       while (__augment) {

   615 	__augment=false;

   616 	//computing blocking flow with dfs

   617 	typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;

   618 	DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);

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

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

   621 	//invalid iterators for sources

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

   625 	dfs.pushAndSetReached(sF);

   626 	while (!dfs.finished()) {

   627 	  ++dfs;

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

   629 	    if (dfs.isBNodeNewlyReached()) {

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

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

   632 	      pred.set(w, dfs);

   633 	      if (F.valid(pred.get(v))) {

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

   635 	      } else {

   636 		free.set(w, residual_capacity.get(dfs));

   637 	      }

   638 	      if (w==tF) {

   639 		__augment=true;

   640 		_augment=true;

   641 		break;

   642 	      }

   644 	    } else {

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

   646 	    }

   647 	  }

   648 	}

   650 	if (__augment) {

   651 	  typename MutableGraph::Node n=tF;

   652 	  Number augment_value=free.get(tF);

   653 	  while (F.valid(pred.get(n))) {

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

   655 	    res_graph.augment(original_edge.get(e), augment_value);

   656 	    n=F.tail(e);

   657 	    if (residual_capacity.get(e)==augment_value)

   658 	      F.erase(e);

   659 	    else

   660 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);

   661 	  }

   662 	}

   664       }

   666       return _augment;

   667     }

   668     bool augmentOnBlockingFlow2() {

   669       bool _augment=false;

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

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

   673       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;

   674       typedef typename EAugGraph::Edge EAugEdge;

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

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

   679       BfsIterator5<

   680 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,

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

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

   684       bfs.pushAndSetReached(s);

   686       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::

   687 	NodeMap<int>& dist=res_graph.dist;

   689       while ( !bfs.finished() ) {

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

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

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

   693 	}

   694 	++bfs;

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

   697       bool __augment=true;

   699       while (__augment) {

   701 	__augment=false;

   702 	//computing blocking flow with dfs

   703 	typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;

   704 	DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >

   705 	  dfs(res_graph);

   706 	typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);

   707 	pred.set(s, EAugEdge(INVALID));

   708 	//invalid iterators for sources

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

   712 	dfs.pushAndSetReached(s);

   713 	while (!dfs.finished()) {

   714 	  ++dfs;

   715 	  if (res_graph.valid(EAugOutEdgeIt(dfs))) {

   716 	    if (dfs.isBNodeNewlyReached()) {

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

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

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

   722 	      if (res_graph.valid(pred.get(v))) {

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

   724 	      } else {

   725 		free.set(w, res_graph.free(dfs));

   726 	      }

   728 	      if (w==t) {

   729 		__augment=true;

   730 		_augment=true;

   731 		break;

   732 	      }

   733 	    } else {

   734 	      res_graph.erase(dfs);

   735 	    }

   736 	  }

   738 	}

   740 	if (__augment) {

   741 	  typename EAugGraph::Node n=t;

   742 	  Number augment_value=free.get(t);

   743 	  while (res_graph.valid(pred.get(n))) {

   744 	    EAugEdge e=pred.get(n);

   745 	    res_graph.augment(e, augment_value);

   746 	    n=res_graph.tail(e);

   747 	    if (res_graph.free(e)==0)

   748 	      res_graph.erase(e);

   749 	  }

   750 	}

   752       }

   754       return _augment;

   755     }

   756     void run() {

   757       //int num_of_augmentations=0;

   758       while (augmentOnShortestPath()) {

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

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

   761 	//std::cout<<std::endl;

   762       }

   763     }

   764     template<typename MutableGraph> void run() {

   765       //int num_of_augmentations=0;

   766       //while (augmentOnShortestPath()) {

   767 	while (augmentOnBlockingFlow<MutableGraph>()) {

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

   769 	//std::cout<<std::endl;

   770       }

   771     }

   772     Number flowValue() {

   773       Number a=0;

   774       OutEdgeIt e;

   775       for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) {

   776 	a+=flow->get(e);

   777       }

   778       return a;

   779     }

   780   };

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

   784   class MaxMatching {

   785   public:

   786     typedef typename Graph::Node Node;

   787     typedef typename Graph::NodeIt NodeIt;

   788     typedef typename Graph::Edge Edge;

   789     typedef typename Graph::EdgeIt EdgeIt;

   790     typedef typename Graph::OutEdgeIt OutEdgeIt;

   791     typedef typename Graph::InEdgeIt InEdgeIt;

   793     typedef typename Graph::NodeMap<bool> SMap;

   794     typedef typename Graph::NodeMap<bool> TMap;

   795   private:

   796     const Graph* G;

   797     SMap* S;

   798     TMap* T;

   799     //Node s;

   800     //Node t;

   801     FlowMap* flow;

   802     const CapacityMap* capacity;

   803     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;

   804     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   805     typedef typename AugGraph::Edge AugEdge;

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

   808   public:

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

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

   811     bool augmentOnShortestPath() {

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

   813       bool _augment=false;

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

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

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

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

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

   820 	  //Number u=0;

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

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

   823 	  //if (u<1) {

   824 	    res_bfs.pushAndSetReached(s);

   825 	    pred.set(s, AugEdge(INVALID));

   826 	    //}

   827 	}

   828       }

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

   832       Node n;

   833       //searching for augmenting path

   834       while ( !res_bfs.finished() ) {

   835 	AugOutEdgeIt e=res_bfs;

   836 	if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {

   837 	  Node v=res_graph.tail(e);

   838 	  Node w=res_graph.head(e);

   839 	  pred.set(w, e);

   840 	  if (res_graph.valid(pred.get(v))) {

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

   842 	  } else {

   843 	    free.set(w, res_graph.free(e));

   844 	  }

   845 	  n=res_graph.head(e);

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

   847 	    //Number u=0;

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

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

   850 	    //if (u<1) {

   851 	      _augment=true;

   852 	      break;

   853 	      //}

   854 	  }

   855 	}

   857 	++res_bfs;

   858       } //end of searching augmenting path

   860       if (_augment) {

   861 	//Node n=t;

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

   863 	Number augment_value=free.get(n);

   864 	while (res_graph.valid(pred.get(n))) {

   865 	  AugEdge e=pred.get(n);

   866 	  res_graph.augment(e, augment_value);

   867 	  n=res_graph.tail(e);

   868 	}

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

   870       }

   872       return _augment;

   873     }

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

   876 //       bool _augment=false;

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

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

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

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

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

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

   890 // 	  Number u=0;

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

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

   893 // 	  if (u<1) {

   894 // 	    res_bfs.pushAndSetReached(s);

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

   896 // 	  }

   897 // 	}

   898 //       }

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

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

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

   906 // 	AugOutEdgeIt e=bfs;

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

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

   909 // 	}

   911 // 	++bfs;

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

   914 //       MutableGraph F;

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

   916 // 	res_graph_to_F(res_graph);

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

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

   919 //       }

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

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

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

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

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

   928 //       //which are in some shortest paths

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

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

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

   932 // 	  original_edge.update();

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

   934 // 	  residual_capacity.update();

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

   936 // 	}

   937 //       }

   939 //       bool __augment=true;

   941 //       while (__augment) {

   942 // 	__augment=false;

   943 // 	//computing blocking flow with dfs

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

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

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

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

   948 // 	//invalid iterators for sources

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

   952 // 	dfs.pushAndSetReached(sF);

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

   954 // 	  ++dfs;

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

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

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

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

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

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

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

   962 // 	      } else {

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

   964 // 	      }

   965 // 	      if (w==tF) {

   966 // 		__augment=true;

   967 // 		_augment=true;

   968 // 		break;

   969 // 	      }

   971 // 	    } else {

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

   973 // 	    }

   974 // 	  }

   975 // 	}

   977 // 	if (__augment) {

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

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

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

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

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

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

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

   985 // 	      F.erase(e);

   986 // 	    else

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

   988 // 	  }

   989 // 	}

   991 //       }

   993 //       return _augment;

   994 //     }

   995     bool augmentOnBlockingFlow2() {

   996       bool _augment=false;

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

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

  1000       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;

  1001       typedef typename EAugGraph::Edge EAugEdge;

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

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

  1006       BfsIterator5<

  1007 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,

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

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

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

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

  1014 	if (S->get(s)) {

  1015 	  Number u=0;

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

  1017 	    u+=flow->get(e);

  1018 	  if (u<1) {

  1019 	    bfs.pushAndSetReached(s);

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

  1021 	  }

  1022 	}

  1023       }

  1026       //bfs.pushAndSetReached(s);

  1028       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::

  1029 	NodeMap<int>& dist=res_graph.dist;

  1031       while ( !bfs.finished() ) {

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

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

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

  1035 	}

  1036 	++bfs;

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

  1039       bool __augment=true;

  1041       while (__augment) {

  1043 	__augment=false;

  1044 	//computing blocking flow with dfs

  1045 	typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;

  1046 	DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >

  1047 	  dfs(res_graph);

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

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

  1050 	//invalid iterators for sources

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

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

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

  1057 	if (S->get(s)) {

  1058 	  Number u=0;

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

  1060 	    u+=flow->get(e);

  1061 	  if (u<1) {

  1062 	    dfs.pushAndSetReached(s);

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

  1064 	  }

  1065 	}

  1066       }

  1070       //dfs.pushAndSetReached(s);

  1071       typename EAugGraph::Node n;

  1072 	while (!dfs.finished()) {

  1073 	  ++dfs;

  1074 	  if (res_graph.valid(EAugOutEdgeIt(dfs))) {

  1075 	    if (dfs.isBNodeNewlyReached()) {

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

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

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

  1081 	      if (res_graph.valid(pred.get(v))) {

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

  1083 	      } else {

  1084 		free.set(w, res_graph.free(dfs));

  1085 	      }

  1087 	      n=w;

  1088 	      if (T->get(w)) {

  1089 		Number u=0;

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

  1091 		  u+=flow->get(f);

  1092 		if (u<1) {

  1093 		  __augment=true;

  1094 		  _augment=true;

  1095 		  break;

  1096 		}

  1097 	      }

  1098 	    } else {

  1099 	      res_graph.erase(dfs);

  1100 	    }

  1101 	  }

  1103 	}

  1105 	if (__augment) {

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

  1107 	  Number augment_value=free.get(n);

  1108 	  while (res_graph.valid(pred.get(n))) {

  1109 	    EAugEdge e=pred.get(n);

  1110 	    res_graph.augment(e, augment_value);

  1111 	    n=res_graph.tail(e);

  1112 	    if (res_graph.free(e)==0)

  1113 	      res_graph.erase(e);

  1114 	  }

  1115 	}

  1117       }

  1119       return _augment;

  1120     }

  1121     void run() {

  1122       //int num_of_augmentations=0;

  1123       while (augmentOnShortestPath()) {

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

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

  1126 	//std::cout<<std::endl;

  1127       }

  1128     }

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

  1130 //       //int num_of_augmentations=0;

  1131 //       //while (augmentOnShortestPath()) {

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

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

  1134 // 	//std::cout<<std::endl;

  1135 //       }

  1136 //     }

  1137     Number flowValue() {

  1138       Number a=0;

  1139       EdgeIt e;

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

  1141 	a+=flow->get(e);

  1142       }

  1143       return a;

  1144     }

  1145   };

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

  1153 //   class MaxFlow2 {

  1154 //   public:

  1155 //     typedef typename Graph::Node Node;

  1156 //     typedef typename Graph::Edge Edge;

  1157 //     typedef typename Graph::EdgeIt EdgeIt;

  1158 //     typedef typename Graph::OutEdgeIt OutEdgeIt;

  1159 //     typedef typename Graph::InEdgeIt InEdgeIt;

  1160 //   private:

  1161 //     const Graph& G;

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

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

  1164 //     FlowMap& flow;

  1165 //     const CapacityMap& capacity;

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

  1167 //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

  1168 //     typedef typename AugGraph::Edge AugEdge;

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

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

  1171 //   public:

  1172 //     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) {

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

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

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

  1176 //       }

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

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

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

  1180 //       }

  1181 //     }

  1182 //     bool augment() {

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

  1184 //       bool _augment=false;

  1185 //       Node reached_t_node;

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

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

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

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

  1191 // 	res_bfs.pushAndSetReached(*i);

  1192 //       }

  1193 //       //res_bfs.pushAndSetReached(s);

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

  1196 //       //filled up with invalid iterators

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

  1200 //       //searching for augmenting path

  1201 //       while ( !res_bfs.finished() ) {

  1202 // 	AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);

  1203 // 	if (e.valid() && res_bfs.isBNodeNewlyReached()) {

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

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

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

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

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

  1209 // 	  } else {

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

  1211 // 	  }

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

  1213 // 	    _augment=true;

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

  1215 // 	    break;

  1216 // 	  }

  1217 // 	}

  1219 // 	++res_bfs;

  1220 //       } //end of searching augmenting path

  1222 //       if (_augment) {

  1223 // 	Node n=reached_t_node;

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

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

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

  1227 // 	  e.augment(augment_value);

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

  1229 // 	}

  1230 //       }

  1232 //       return _augment;

  1233 //     }

  1234 //     void run() {

  1235 //       while (augment()) { }

  1236 //     }

  1237 //     Number flowValue() {

  1238 //       Number a=0;

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

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

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

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

  1243 // 	}

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

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

  1246 // 	}

  1247 //       }

  1248 //       return a;

  1249 //     }

  1250 //   };

  1254 } // namespace hugo

  1256 #endif //HUGO_EDMONDS_KARP_H

author	alpar
	Tue, 30 Mar 2004 13:18:10 +0000
changeset 264	fe81c4b117f4
parent 259	509ba9f136d2
child 265	bf7aea53635a
permissions	-rw-r--r--