lemon-0.x: src/work/marci/experiment/edmonds_karp

     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_1.h>

    10 #include <invalid.h>

    11 #include <graph_wrapper_1.h>

    13 namespace hugo {

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

    16   class ResGraph {

    17   public:

    18     typedef typename Graph::Node Node;

    19     typedef typename Graph::NodeIt NodeIt;

    20   private:

    21     typedef typename Graph::SymEdgeIt OldSymEdgeIt;

    22     const Graph& G;

    23     FlowMap& flow;

    24     const CapacityMap& capacity;

    25   public:

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

    27 	     const CapacityMap& _capacity) :

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

    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, typename FlowMap, typename CapacityMap>

   252   class MaxFlow {

   253   protected:

   254     typedef typename Graph::Node Node;

   255     typedef typename Graph::Edge Edge;

   256     typedef typename Graph::EdgeIt EdgeIt;

   257     typedef typename Graph::OutEdgeIt OutEdgeIt;

   258     typedef typename Graph::InEdgeIt InEdgeIt;

   259     const Graph* g;

   260     Node s;

   261     Node t;

   262     FlowMap* flow;

   263     const CapacityMap* capacity;

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

   265     typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;

   266     typedef typename ResGW::Edge ResGWEdge;

   267   public:

   269     MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :

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

   272     bool augmentOnShortestPath() {

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

   274       bool _augment=false;

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

   277       BfsIterator5< ResGW, ReachedMap > bfs(res_graph);

   278       bfs.pushAndSetReached(s);

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

   281       pred.set(s, INVALID);

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

   285       //searching for augmenting path

   286       while ( !bfs.finished() ) {

   287 	ResGWOutEdgeIt e=bfs;

   288 	if (res_graph.valid(e) && 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.resCap(e)));

   294 	  } else {

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

   296 	  }

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

   298 	}

   300 	++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 	  ResGWEdge 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 MapGraphWrapper>

   317     class DistanceMap {

   318     protected:

   319       const MapGraphWrapper* g;

   320       typename MapGraphWrapper::NodeMap<int> dist;

   321     public:

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

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

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

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

   326 	return (dist.get(g->tail(e))<dist.get(g->head(e)));

   327       }

   328     };

   330     template<typename MutableGraph> bool augmentOnBlockingFlow() {

   331       typedef MutableGraph MG;

   332       bool _augment=false;

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

   336       typedef typename ResGW::NodeMap<bool> ReachedMap;

   337       BfsIterator5< ResGW, ReachedMap > bfs(res_graph);

   339       bfs.pushAndSetReached(s);

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

   341       DistanceMap<ResGW> dist(res_graph);

   342       while ( !bfs.finished() ) {

   343 	ResGWOutEdgeIt e=bfs;

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

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

   346 	}

   347 	++bfs;

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

   350       MG F;

   351       typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;

   352       FilterResGW filter_res_graph(res_graph, dist);

   353       typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);

   354       {

   355 	typename ResGW::NodeIt n;

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

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

   358 	}

   359       }

   361       typename MG::Node sF=res_graph_to_F.get(s);

   362       typename MG::Node tF=res_graph_to_F.get(t);

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

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

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

   367       //which are in some shortest paths

   368       {

   369 	typename FilterResGW::EdgeIt e;

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

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

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

   373 	  original_edge.update();

   374 	  original_edge.set(f, e);

   375 	  residual_capacity.update();

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

   377 	  //}

   378 	}

   379       }

   381       bool __augment=true;

   383       while (__augment) {

   384 	__augment=false;

   385 	//computing blocking flow with dfs

   386 	typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap;

   387 	DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F);

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

   389 	pred.set(sF, INVALID);

   390 	//invalid iterators for sources

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

   394 	dfs.pushAndSetReached(sF);

   395 	while (!dfs.finished()) {

   396 	  ++dfs;

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

   398 	    if (dfs.isBNodeNewlyReached()) {

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

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

   401 	      pred.set(w, dfs);

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

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

   404 	      } else {

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

   406 	      }

   407 	      if (w==tF) {

   408 		__augment=true;

   409 		_augment=true;

   410 		break;

   411 	      }

   413 	    } else {

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

   415 	    }

   416 	  }

   417 	}

   419 	if (__augment) {

   420 	  typename MG::Node n=tF;

   421 	  Number augment_value=free.get(tF);

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

   423 	    typename MG::Edge e=pred.get(n);

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

   425 	    n=F.tail(e);

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

   427 	      F.erase(e);

   428 	    else

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

   430 	  }

   431 	}

   433       }

   435       return _augment;

   436     }

   438     template<typename MutableGraph> bool augmentOnBlockingFlow1() {

   439       typedef MutableGraph MG;

   440       bool _augment=false;

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

   444       //bfs for distances on the residual graph

   445       typedef typename ResGW::NodeMap<bool> ReachedMap;

   446       BfsIterator5< ResGW, ReachedMap > bfs(res_graph);

   447       bfs.pushAndSetReached(s);

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

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

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

   452       MG F;

   453       typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);

   454       {

   455 	typename ResGW::NodeIt n;

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

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

   458 	}

   459       }

   461       typename MG::Node sF=res_graph_to_F.get(s);

   462       typename MG::Node tF=res_graph_to_F.get(t);

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

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

   466       while ( !bfs.finished() ) {

   467 	ResGWOutEdgeIt e=bfs;

   468 	if (res_graph.valid(e)) {

   469 	  if (bfs.isBNodeNewlyReached()) {

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

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

   472 	    original_edge.update();

   473 	    original_edge.set(f, e);

   474 	    residual_capacity.update();

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

   476 	  } else {

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

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

   479 	      original_edge.update();

   480 	      original_edge.set(f, e);

   481 	      residual_capacity.update();

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

   483 	    }

   484 	  }

   485 	}

   486 	++bfs;

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

   489       bool __augment=true;

   491       while (__augment) {

   492 	__augment=false;

   493 	//computing blocking flow with dfs

   494 	typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap;

   495 	DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F);

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

   497 	pred.set(sF, INVALID);

   498 	//invalid iterators for sources

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

   502 	dfs.pushAndSetReached(sF);

   503 	while (!dfs.finished()) {

   504 	  ++dfs;

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

   506 	    if (dfs.isBNodeNewlyReached()) {

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

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

   509 	      pred.set(w, dfs);

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

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

   512 	      } else {

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

   514 	      }

   515 	      if (w==tF) {

   516 		__augment=true;

   517 		_augment=true;

   518 		break;

   519 	      }

   521 	    } else {

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

   523 	    }

   524 	  }

   525 	}

   527 	if (__augment) {

   528 	  typename MG::Node n=tF;

   529 	  Number augment_value=free.get(tF);

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

   531 	    typename MG::Edge e=pred.get(n);

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

   533 	    n=F.tail(e);

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

   535 	      F.erase(e);

   536 	    else

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

   538 	  }

   539 	}

   541       }

   543       return _augment;

   544     }

   546     bool augmentOnBlockingFlow2() {

   547       bool _augment=false;

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

   551       typedef typename ResGW::NodeMap<bool> ReachedMap;

   552       BfsIterator5< ResGW, ReachedMap > bfs(res_graph);

   554       bfs.pushAndSetReached(s);

   555       DistanceMap<ResGW> dist(res_graph);

   556       while ( !bfs.finished() ) {

   557  	ResGWOutEdgeIt e=bfs;

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

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

   560  	}

   561 	++bfs;

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

   564       //Subgraph containing the edges on some shortest paths

   565       typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;

   566       FilterResGW filter_res_graph(res_graph, dist);

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

   569       //met by the dfs

   570       typename FilterResGW::NodeMap<typename FilterResGW::OutEdgeIt>

   571  	first_out_edges(filter_res_graph);

   572       typename FilterResGW::NodeIt v;

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

   574  	  filter_res_graph.next(v))

   575       {

   576  	typename FilterResGW::OutEdgeIt e;

   577  	filter_res_graph.first(e, v);

   578  	first_out_edges.set(v, e);

   579       }

   580       typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::

   581 	NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;

   582       ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);

   584       bool __augment=true;

   586       while (__augment) {

   588  	__augment=false;

   589  	//computing blocking flow with dfs

   590 	typedef typename ErasingResGW::NodeMap<bool> BlockingReachedMap;

   591  	DfsIterator5< ErasingResGW, BlockingReachedMap >

   592  	  dfs(erasing_res_graph);

   593  	typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt>

   594  	  pred(erasing_res_graph);

   595  	pred.set(s, INVALID);

   596  	//invalid iterators for sources

   598  	typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);

   600  	dfs.pushAndSetReached(s);

   601  	while (!dfs.finished()) {

   602  	  ++dfs;

   603  	  if (erasing_res_graph.valid(

   604  		/*typename ErasingResGW::OutEdgeIt*/(dfs)))

   605  	  {

   606  	    if (dfs.isBNodeNewlyReached()) {

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

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

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

   612  	      if (erasing_res_graph.valid(pred.get(v))) {

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

   614  	      } else {

   615  		free.set(w, res_graph.resCap(dfs));

   616  	      }

   618  	      if (w==t) {

   619  		__augment=true;

   620  		_augment=true;

   621  		break;

   622  	      }

   623 	    } else {

   624 	      erasing_res_graph.erase(dfs);

   625 	    }

   626 	  }

   627 	}

   629  	if (__augment) {

   630  	  typename ErasingResGW::Node n=t;

   631  	  Number augment_value=free.get(n);

   632  	  while (erasing_res_graph.valid(pred.get(n))) {

   633  	    typename ErasingResGW::OutEdgeIt e=pred.get(n);

   634  	    res_graph.augment(e, augment_value);

   635  	    n=erasing_res_graph.tail(e);

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

   637  	      erasing_res_graph.erase(e);

   638  	  }

   639  	}

   641       } //while (__augment)

   643       return _augment;

   644     }

   646     void run() {

   647       //int num_of_augmentations=0;

   648       while (augmentOnShortestPath()) {

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

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

   651 	//std::cout<<std::endl;

   652       }

   653     }

   655     template<typename MutableGraph> void run() {

   656       //int num_of_augmentations=0;

   657       //while (augmentOnShortestPath()) {

   658 	while (augmentOnBlockingFlow<MutableGraph>()) {

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

   660 	//std::cout<<std::endl;

   661       }

   662     }

   664     Number flowValue() {

   665       Number a=0;

   666       OutEdgeIt e;

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

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

   669       }

   670       return a;

   671     }

   673   };

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

   677 //   class MaxMatching {

   678 //   public:

   679 //     typedef typename Graph::Node Node;

   680 //     typedef typename Graph::NodeIt NodeIt;

   681 //     typedef typename Graph::Edge Edge;

   682 //     typedef typename Graph::EdgeIt EdgeIt;

   683 //     typedef typename Graph::OutEdgeIt OutEdgeIt;

   684 //     typedef typename Graph::InEdgeIt InEdgeIt;

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

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

   688 //   private:

   689 //     const Graph* G;

   690 //     SMap* S;

   691 //     TMap* T;

   692 //     //Node s;

   693 //     //Node t;

   694 //     FlowMap* flow;

   695 //     const CapacityMap* capacity;

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

   697 //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   698 //     typedef typename AugGraph::Edge AugEdge;

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

   701 //   public:

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

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

   704 //     bool augmentOnShortestPath() {

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

   706 //       bool _augment=false;

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

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

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

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

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

   713 // 	  //Number u=0;

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

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

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

   717 // 	    bfs.pushAndSetReached(s);

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

   719 // 	    //}

   720 // 	}

   721 //       }

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

   725 //       Node n;

   726 //       //searching for augmenting path

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

   728 // 	AugOutEdgeIt e=bfs;

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

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

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

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

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

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

   735 // 	  } else {

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

   737 // 	  }

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

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

   740 // 	    //Number u=0;

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

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

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

   744 // 	      _augment=true;

   745 // 	      break;

   746 // 	      //}

   747 // 	  }

   748 // 	}

   750 // 	++bfs;

   751 //       } //end of searching augmenting path

   753 //       if (_augment) {

   754 // 	//Node n=t;

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

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

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

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

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

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

   761 // 	}

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

   763 //       }

   765 //       return _augment;

   766 //     }

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

   769 // //       bool _augment=false;

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

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

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

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

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

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

   783 // // 	  Number u=0;

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

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

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

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

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

   789 // // 	  }

   790 // // 	}

   791 // //       }

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

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

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

   799 // // 	AugOutEdgeIt e=bfs;

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

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

   802 // // 	}

   804 // // 	++bfs;

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

   807 // //       MutableGraph F;

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

   809 // // 	res_graph_to_F(res_graph);

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

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

   812 // //       }

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

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

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

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

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

   821 // //       //which are in some shortest paths

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

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

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

   825 // // 	  original_edge.update();

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

   827 // // 	  residual_capacity.update();

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

   829 // // 	}

   830 // //       }

   832 // //       bool __augment=true;

   834 // //       while (__augment) {

   835 // // 	__augment=false;

   836 // // 	//computing blocking flow with dfs

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

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

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

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

   841 // // 	//invalid iterators for sources

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

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

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

   847 // // 	  ++dfs;

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

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

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

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

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

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

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

   855 // // 	      } else {

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

   857 // // 	      }

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

   859 // // 		__augment=true;

   860 // // 		_augment=true;

   861 // // 		break;

   862 // // 	      }

   864 // // 	    } else {

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

   866 // // 	    }

   867 // // 	  }

   868 // // 	}

   870 // // 	if (__augment) {

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

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

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

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

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

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

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

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

   879 // // 	    else

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

   881 // // 	  }

   882 // // 	}

   884 // //       }

   886 // //       return _augment;

   887 // //     }

   888 //     bool augmentOnBlockingFlow2() {

   889 //       bool _augment=false;

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

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

   893 //       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;

   894 //       typedef typename EAugGraph::Edge EAugEdge;

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

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

   899 //       BfsIterator5<

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

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

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

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

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

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

   908 // 	  Number u=0;

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

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

   911 // 	  if (u<1) {

   912 // 	    bfs.pushAndSetReached(s);

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

   914 // 	  }

   915 // 	}

   916 //       }

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

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

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

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

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

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

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

   928 // 	}

   929 // 	++bfs;

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

   932 //       bool __augment=true;

   934 //       while (__augment) {

   936 // 	__augment=false;

   937 // 	//computing blocking flow with dfs

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

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

   940 // 	  dfs(res_graph);

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

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

   943 // 	//invalid iterators for sources

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

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

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

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

   951 // 	  Number u=0;

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

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

   954 // 	  if (u<1) {

   955 // 	    dfs.pushAndSetReached(s);

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

   957 // 	  }

   958 // 	}

   959 //       }

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

   964 //       typename EAugGraph::Node n;

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

   966 // 	  ++dfs;

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

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

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

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

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

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

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

   976 // 	      } else {

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

   978 // 	      }

   980 // 	      n=w;

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

   982 // 		Number u=0;

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

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

   985 // 		if (u<1) {

   986 // 		  __augment=true;

   987 // 		  _augment=true;

   988 // 		  break;

   989 // 		}

   990 // 	      }

   991 // 	    } else {

   992 // 	      res_graph.erase(dfs);

   993 // 	    }

   994 // 	  }

   996 // 	}

   998 // 	if (__augment) {

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

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

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

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

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

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

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

  1006 // 	      res_graph.erase(e);

  1007 // 	  }

  1008 // 	}

  1010 //       }

  1012 //       return _augment;

  1013 //     }

  1014 //     void run() {

  1015 //       //int num_of_augmentations=0;

  1016 //       while (augmentOnShortestPath()) {

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

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

  1019 // 	//std::cout<<std::endl;

  1020 //       }

  1021 //     }

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

  1023 // //       //int num_of_augmentations=0;

  1024 // //       //while (augmentOnShortestPath()) {

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

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

  1027 // // 	//std::cout<<std::endl;

  1028 // //       }

  1029 // //     }

  1030 //     Number flowValue() {

  1031 //       Number a=0;

  1032 //       EdgeIt e;

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

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

  1035 //       }

  1036 //       return a;

  1037 //     }

  1038 //   };

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

  1046 // //   class MaxFlow2 {

  1047 // //   public:

  1048 // //     typedef typename Graph::Node Node;

  1049 // //     typedef typename Graph::Edge Edge;

  1050 // //     typedef typename Graph::EdgeIt EdgeIt;

  1051 // //     typedef typename Graph::OutEdgeIt OutEdgeIt;

  1052 // //     typedef typename Graph::InEdgeIt InEdgeIt;

  1053 // //   private:

  1054 // //     const Graph& G;

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

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

  1057 // //     FlowMap& flow;

  1058 // //     const CapacityMap& capacity;

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

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

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

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

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

  1064 // //   public:

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

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

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

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

  1069 // //       }

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

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

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

  1073 // //       }

  1074 // //     }

  1075 // //     bool augment() {

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

  1077 // //       bool _augment=false;

  1078 // //       Node reached_t_node;

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

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

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

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

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

  1085 // //       }

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

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

  1089 // //       //filled up with invalid iterators

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

  1093 // //       //searching for augmenting path

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

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

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

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

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

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

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

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

  1102 // // 	  } else {

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

  1104 // // 	  }

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

  1106 // // 	    _augment=true;

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

  1108 // // 	    break;

  1109 // // 	  }

  1110 // // 	}

  1112 // // 	++bfs;

  1113 // //       } //end of searching augmenting path

  1115 // //       if (_augment) {

  1116 // // 	Node n=reached_t_node;

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

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

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

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

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

  1122 // // 	}

  1123 // //       }

  1125 // //       return _augment;

  1126 // //     }

  1127 // //     void run() {

  1128 // //       while (augment()) { }

  1129 // //     }

  1130 // //     Number flowValue() {

  1131 // //       Number a=0;

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

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

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

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

  1136 // // 	}

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

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

  1139 // // 	}

  1140 // //       }

  1141 // //       return a;

  1142 // //     }

  1143 // //   };

  1146 } // namespace hugo

  1148 #endif //HUGO_EDMONDS_KARP_H

author	alpar
	Mon, 06 Sep 2004 08:21:42 +0000
changeset 804	6874a72dbdc5
parent 281	3fefabfd00b7
child 921	818510fa3d99
permissions	-rw-r--r--