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

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

     2 #ifndef EDMONDS_KARP_H

     3 #define 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       BfsIterator4< 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 MutableGraph::NodeMap<bool> BlockingReachedMap;

   366 	DfsIterator4< 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     }

   416     template<typename MutableGraph> bool augmentOnBlockingFlow1() {

   417       bool _augment=false;

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

   421       //bfs for distances on the residual graph

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

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

   424       bfs.pushAndSetReached(s);

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

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

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

   429       MutableGraph F;

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

   431 	res_graph_to_F(res_graph);

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

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

   434       }

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

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

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

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

   440       while ( !bfs.finished() ) {

   441 	AugOutEdgeIt e=bfs;

   442 	if (res_graph.valid(e)) {

   443 	  if (bfs.isBNodeNewlyReached()) {

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

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

   446 	    original_edge.update();

   447 	    original_edge.set(f, e);

   448 	    residual_capacity.update();

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

   450 	  } else {

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

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

   453 	      original_edge.update();

   454 	      original_edge.set(f, e);

   455 	      residual_capacity.update();

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

   457 	    }

   458 	  }

   459 	}

   460 	++bfs;

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

   463       bool __augment=true;

   465       while (__augment) {

   466 	__augment=false;

   467 	//computing blocking flow with dfs

   468 	typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;

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

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

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

   472 	//invalid iterators for sources

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

   476 	dfs.pushAndSetReached(sF);

   477 	while (!dfs.finished()) {

   478 	  ++dfs;

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

   480 	    if (dfs.isBNodeNewlyReached()) {

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

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

   483 	      pred.set(w, dfs);

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

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

   486 	      } else {

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

   488 	      }

   489 	      if (w==tF) {

   490 		__augment=true;

   491 		_augment=true;

   492 		break;

   493 	      }

   495 	    } else {

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

   497 	    }

   498 	  }

   499 	}

   501 	if (__augment) {

   502 	  typename MutableGraph::Node n=tF;

   503 	  Number augment_value=free.get(tF);

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

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

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

   507 	    n=F.tail(e);

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

   509 	      F.erase(e);

   510 	    else

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

   512 	  }

   513 	}

   515       }

   517       return _augment;

   518     }

   519     bool augmentOnBlockingFlow2() {

   520       bool _augment=false;

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

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

   524       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;

   525       typedef typename EAugGraph::Edge EAugEdge;

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

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

   530       BfsIterator4<

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

   532 	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,

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

   535       bfs.pushAndSetReached(s);

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

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

   540       while ( !bfs.finished() ) {

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

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

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

   544 	}

   545 	++bfs;

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

   548       bool __augment=true;

   550       while (__augment) {

   552 	__augment=false;

   553 	//computing blocking flow with dfs

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

   555 	DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >

   556 	  dfs(res_graph);

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

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

   559 	//invalid iterators for sources

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

   563 	dfs.pushAndSetReached(s);

   564 	while (!dfs.finished()) {

   565 	  ++dfs;

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

   567 	    if (dfs.isBNodeNewlyReached()) {

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

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

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

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

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

   575 	      } else {

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

   577 	      }

   579 	      if (w==t) {

   580 		__augment=true;

   581 		_augment=true;

   582 		break;

   583 	      }

   584 	    } else {

   585 	      res_graph.erase(dfs);

   586 	    }

   587 	  }

   589 	}

   591 	if (__augment) {

   592 	  typename EAugGraph::Node n=t;

   593 	  Number augment_value=free.get(t);

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

   595 	    EAugEdge e=pred.get(n);

   596 	    res_graph.augment(e, augment_value);

   597 	    n=res_graph.tail(e);

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

   599 	      res_graph.erase(e);

   600 	  }

   601 	}

   603       }

   605       return _augment;

   606     }

   607     void run() {

   608       //int num_of_augmentations=0;

   609       while (augmentOnShortestPath()) {

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

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

   612 	//std::cout<<std::endl;

   613       }

   614     }

   615     template<typename MutableGraph> void run() {

   616       //int num_of_augmentations=0;

   617       //while (augmentOnShortestPath()) {

   618 	while (augmentOnBlockingFlow<MutableGraph>()) {

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

   620 	//std::cout<<std::endl;

   621       }

   622     }

   623     Number flowValue() {

   624       Number a=0;

   625       OutEdgeIt e;

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

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

   628       }

   629       return a;

   630     }

   631   };

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

   635   class MaxMatching {

   636   public:

   637     typedef typename Graph::Node Node;

   638     typedef typename Graph::NodeIt NodeIt;

   639     typedef typename Graph::Edge Edge;

   640     typedef typename Graph::EdgeIt EdgeIt;

   641     typedef typename Graph::OutEdgeIt OutEdgeIt;

   642     typedef typename Graph::InEdgeIt InEdgeIt;

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

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

   646   private:

   647     const Graph* G;

   648     SMap* S;

   649     TMap* T;

   650     //Node s;

   651     //Node t;

   652     FlowMap* flow;

   653     const CapacityMap* capacity;

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

   655     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   656     typedef typename AugGraph::Edge AugEdge;

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

   659   public:

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

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

   662     bool augmentOnShortestPath() {

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

   664       bool _augment=false;

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

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

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

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

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

   671 	  //Number u=0;

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

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

   674 	  //if (u<1) {

   675 	    res_bfs.pushAndSetReached(s);

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

   677 	    //}

   678 	}

   679       }

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

   683       Node n;

   684       //searching for augmenting path

   685       while ( !res_bfs.finished() ) {

   686 	AugOutEdgeIt e=res_bfs;

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

   688 	  Node v=res_graph.tail(e);

   689 	  Node w=res_graph.head(e);

   690 	  pred.set(w, e);

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

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

   693 	  } else {

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

   695 	  }

   696 	  n=res_graph.head(e);

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

   698 	    //Number u=0;

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

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

   701 	    //if (u<1) {

   702 	      _augment=true;

   703 	      break;

   704 	      //}

   705 	  }

   706 	}

   708 	++res_bfs;

   709       } //end of searching augmenting path

   711       if (_augment) {

   712 	//Node n=t;

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

   714 	Number augment_value=free.get(n);

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

   716 	  AugEdge e=pred.get(n);

   717 	  res_graph.augment(e, augment_value);

   718 	  n=res_graph.tail(e);

   719 	}

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

   721       }

   723       return _augment;

   724     }

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

   727 //       bool _augment=false;

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

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

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

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

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

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

   741 // 	  Number u=0;

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

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

   744 // 	  if (u<1) {

   745 // 	    res_bfs.pushAndSetReached(s);

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

   747 // 	  }

   748 // 	}

   749 //       }

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

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

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

   757 // 	AugOutEdgeIt e=bfs;

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

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

   760 // 	}

   762 // 	++bfs;

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

   765 //       MutableGraph F;

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

   767 // 	res_graph_to_F(res_graph);

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

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

   770 //       }

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

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

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

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

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

   779 //       //which are in some shortest paths

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

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

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

   783 // 	  original_edge.update();

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

   785 // 	  residual_capacity.update();

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

   787 // 	}

   788 //       }

   790 //       bool __augment=true;

   792 //       while (__augment) {

   793 // 	__augment=false;

   794 // 	//computing blocking flow with dfs

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

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

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

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

   799 // 	//invalid iterators for sources

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

   803 // 	dfs.pushAndSetReached(sF);

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

   805 // 	  ++dfs;

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

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

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

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

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

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

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

   813 // 	      } else {

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

   815 // 	      }

   816 // 	      if (w==tF) {

   817 // 		__augment=true;

   818 // 		_augment=true;

   819 // 		break;

   820 // 	      }

   822 // 	    } else {

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

   824 // 	    }

   825 // 	  }

   826 // 	}

   828 // 	if (__augment) {

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

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

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

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

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

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

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

   836 // 	      F.erase(e);

   837 // 	    else

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

   839 // 	  }

   840 // 	}

   842 //       }

   844 //       return _augment;

   845 //     }

   846     bool augmentOnBlockingFlow2() {

   847       bool _augment=false;

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

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

   851       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;

   852       typedef typename EAugGraph::Edge EAugEdge;

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

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

   857       BfsIterator4<

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

   859 	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,

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

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

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

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

   866 	  Number u=0;

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

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

   869 	  if (u<1) {

   870 	    bfs.pushAndSetReached(s);

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

   872 	  }

   873 	}

   874       }

   877       //bfs.pushAndSetReached(s);

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

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

   882       while ( !bfs.finished() ) {

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

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

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

   886 	}

   887 	++bfs;

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

   890       bool __augment=true;

   892       while (__augment) {

   894 	__augment=false;

   895 	//computing blocking flow with dfs

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

   897 	DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >

   898 	  dfs(res_graph);

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

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

   901 	//invalid iterators for sources

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

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

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

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

   909 	  Number u=0;

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

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

   912 	  if (u<1) {

   913 	    dfs.pushAndSetReached(s);

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

   915 	  }

   916 	}

   917       }

   921       //dfs.pushAndSetReached(s);

   922       typename EAugGraph::Node n;

   923 	while (!dfs.finished()) {

   924 	  ++dfs;

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

   926 	    if (dfs.isBNodeNewlyReached()) {

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

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

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

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

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

   934 	      } else {

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

   936 	      }

   938 	      n=w;

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

   940 		Number u=0;

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

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

   943 		if (u<1) {

   944 		  __augment=true;

   945 		  _augment=true;

   946 		  break;

   947 		}

   948 	      }

   949 	    } else {

   950 	      res_graph.erase(dfs);

   951 	    }

   952 	  }

   954 	}

   956 	if (__augment) {

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

   958 	  Number augment_value=free.get(n);

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

   960 	    EAugEdge e=pred.get(n);

   961 	    res_graph.augment(e, augment_value);

   962 	    n=res_graph.tail(e);

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

   964 	      res_graph.erase(e);

   965 	  }

   966 	}

   968       }

   970       return _augment;

   971     }

   972     void run() {

   973       //int num_of_augmentations=0;

   974       while (augmentOnShortestPath()) {

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

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

   977 	//std::cout<<std::endl;

   978       }

   979     }

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

   981 //       //int num_of_augmentations=0;

   982 //       //while (augmentOnShortestPath()) {

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

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

   985 // 	//std::cout<<std::endl;

   986 //       }

   987 //     }

   988     Number flowValue() {

   989       Number a=0;

   990       EdgeIt e;

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

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

   993       }

   994       return a;

   995     }

   996   };

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

  1004 //   class MaxFlow2 {

  1005 //   public:

  1006 //     typedef typename Graph::Node Node;

  1007 //     typedef typename Graph::Edge Edge;

  1008 //     typedef typename Graph::EdgeIt EdgeIt;

  1009 //     typedef typename Graph::OutEdgeIt OutEdgeIt;

  1010 //     typedef typename Graph::InEdgeIt InEdgeIt;

  1011 //   private:

  1012 //     const Graph& G;

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

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

  1015 //     FlowMap& flow;

  1016 //     const CapacityMap& capacity;

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

  1018 //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

  1019 //     typedef typename AugGraph::Edge AugEdge;

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

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

  1022 //   public:

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

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

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

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

  1027 //       }

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

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

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

  1031 //       }

  1032 //     }

  1033 //     bool augment() {

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

  1035 //       bool _augment=false;

  1036 //       Node reached_t_node;

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

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

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

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

  1042 // 	res_bfs.pushAndSetReached(*i);

  1043 //       }

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

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

  1047 //       //filled up with invalid iterators

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

  1051 //       //searching for augmenting path

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

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

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

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

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

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

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

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

  1060 // 	  } else {

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

  1062 // 	  }

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

  1064 // 	    _augment=true;

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

  1066 // 	    break;

  1067 // 	  }

  1068 // 	}

  1070 // 	++res_bfs;

  1071 //       } //end of searching augmenting path

  1073 //       if (_augment) {

  1074 // 	Node n=reached_t_node;

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

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

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

  1078 // 	  e.augment(augment_value);

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

  1080 // 	}

  1081 //       }

  1083 //       return _augment;

  1084 //     }

  1085 //     void run() {

  1086 //       while (augment()) { }

  1087 //     }

  1088 //     Number flowValue() {

  1089 //       Number a=0;

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

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

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

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

  1094 // 	}

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

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

  1097 // 	}

  1098 //       }

  1099 //       return a;

  1100 //     }

  1101 //   };

  1105 } // namespace hugo

  1107 #endif //EDMONDS_KARP_H

author	athos
	Fri, 19 Mar 2004 14:47:36 +0000
changeset 207	9910d5a5be7f
parent 198	5cec393baade
child 243	a85fd87460e3
permissions	-rw-r--r--