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

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

     2 #ifndef HUGO_EDMONDS_KARP_H

     3 #define HUGO_EDMONDS_KARP_H

     5 #include <algorithm>

     6 #include <list>

     7 #include <iterator>

     9 #include <bfs_iterator.h>

    10 #include <invalid.h>

    11 #include <graph_wrapper.h>

    12 #include <maps.h>

    14 namespace hugo {

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

    17   class ResGraph {

    18   public:

    19     typedef typename Graph::Node Node;

    20     typedef typename Graph::NodeIt NodeIt;

    21   private:

    22     typedef typename Graph::SymEdgeIt OldSymEdgeIt;

    23     const Graph& G;

    24     FlowMap& flow;

    25     const CapacityMap& capacity;

    26   public:

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

    28 	     const CapacityMap& _capacity) :

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

    31     class Edge;

    32     class OutEdgeIt;

    33     friend class Edge;

    34     friend class OutEdgeIt;

    36     class Edge {

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

    38     protected:

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

    40       OldSymEdgeIt sym;

    41     public:

    42       Edge() { }

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

    44       Number free() const {

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

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

    47 	} else {

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

    49 	}

    50       }

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

    52       void augment(Number a) const {

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

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

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

    56 	} else {

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

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

    59 	}

    60       }

    61     };

    63     class OutEdgeIt : public Edge {

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

    65     public:

    66       OutEdgeIt() { }

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

    68     private:

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

    70       	resG=&_resG;

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

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

    73       }

    74     public:

    75       OutEdgeIt& operator++() {

    76 	++sym;

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

    78 	return *this;

    79       }

    80     };

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

    83       e=OutEdgeIt(*this, v);

    84     }

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

    87     template< typename It >

    88     It first() const {

    89       It e;

    90       /*getF*/first(e);

    91       return e;

    92     }

    94     template< typename It >

    95     It first(Node v) const {

    96       It e;

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

    98       return e;

    99     }

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

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

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

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

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

   109     template <typename S>

   110     class NodeMap {

   111       typename Graph::NodeMap<S> node_map;

   112     public:

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

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

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

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

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

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

   119     };

   121   };

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

   125   class ResGraph2 {

   126   public:

   127     typedef typename Graph::Node Node;

   128     typedef typename Graph::NodeIt NodeIt;

   129   private:

   130     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;

   131     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   132     typedef typename Graph::InEdgeIt OldInEdgeIt;

   134     const Graph& G;

   135     FlowMap& flow;

   136     const CapacityMap& capacity;

   137   public:

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

   139 	     const CapacityMap& _capacity) :

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

   142     class Edge;

   143     class OutEdgeIt;

   144     friend class Edge;

   145     friend class OutEdgeIt;

   147     class Edge {

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

   149     protected:

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

   151       //OldSymEdgeIt sym;

   152       OldOutEdgeIt out;

   153       OldInEdgeIt in;

   154       bool out_or_in; //true, iff out

   155     public:

   156       Edge() : out_or_in(true) { }

   157       Number free() const {

   158 	if (out_or_in) {

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

   160 	} else {

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

   162 	}

   163       }

   164       bool valid() const {

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

   166       void augment(Number a) const {

   167 	if (out_or_in) {

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

   169 	} else {

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

   171 	}

   172       }

   173     };

   175     class OutEdgeIt : public Edge {

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

   177     public:

   178       OutEdgeIt() { }

   179     private:

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

   181       	resG=&_resG;

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

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

   184 	if (!out.valid()) {

   185 	  out_or_in=0;

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

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

   188 	}

   189       }

   190     public:

   191       OutEdgeIt& operator++() {

   192 	if (out_or_in) {

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

   194 	  ++out;

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

   196 	  if (!out.valid()) {

   197 	    out_or_in=0;

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

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

   200 	  }

   201 	} else {

   202 	  ++in;

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

   204 	}

   205 	return *this;

   206       }

   207     };

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

   210       e=OutEdgeIt(*this, v);

   211     }

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

   214     template< typename It >

   215     It first() const {

   216       It e;

   217       /*getF*/first(e);

   218       return e;

   219     }

   221     template< typename It >

   222     It first(Node v) const {

   223       It e;

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

   225       return e;

   226     }

   228     Node tail(Edge e) const {

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

   230     Node head(Edge e) const {

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

   233     Node aNode(OutEdgeIt e) const {

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

   235     Node bNode(OutEdgeIt e) const {

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

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

   240     template <typename S>

   241     class NodeMap {

   242       typename Graph::NodeMap<S> node_map;

   243     public:

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

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

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

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

   248     };

   249   };

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

   253   class MaxFlow {

   254   protected:

   255     typedef typename Graph::Node Node;

   256     typedef typename Graph::Edge Edge;

   257     typedef typename Graph::EdgeIt EdgeIt;

   258     typedef typename Graph::OutEdgeIt OutEdgeIt;

   259     typedef typename Graph::InEdgeIt InEdgeIt;

   260     const Graph* g;

   261     Node s;

   262     Node t;

   263     FlowMap* flow;

   264     const CapacityMap* capacity;

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

   266     typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;

   267     typedef typename ResGW::Edge ResGWEdge;

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

   273     bool augmentOnShortestPath() {

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

   275       bool _augment=false;

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

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

   279       bfs.pushAndSetReached(s);

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

   282       pred.set(s, INVALID);

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

   286       //searching for augmenting path

   287       while ( !bfs.finished() ) {

   288 	ResGWOutEdgeIt e=bfs;

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

   290 	  Node v=res_graph.tail(e);

   291 	  Node w=res_graph.head(e);

   292 	  pred.set(w, e);

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

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

   295 	  } else {

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

   297 	  }

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

   299 	}

   301 	++bfs;

   302       } //end of searching augmenting path

   304       if (_augment) {

   305 	Node n=t;

   306 	Number augment_value=free[t];

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

   308 	  ResGWEdge e=pred[n];

   309 	  res_graph.augment(e, augment_value);

   310 	  n=res_graph.tail(e);

   311 	}

   312       }

   314       return _augment;

   315     }

   317     template<typename MapGraphWrapper>

   318     class DistanceMap {

   319     protected:

   320       const MapGraphWrapper* g;

   321       typename MapGraphWrapper::NodeMap<int> dist;

   322     public:

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

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

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

   326 	{ return dist[n]; }

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

   328 // 	return dist[n]; }

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

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

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

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

   333       }

   334     };

   336     template<typename MutableGraph> bool augmentOnBlockingFlow() {

   337       typedef MutableGraph MG;

   338       bool _augment=false;

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

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

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

   345       bfs.pushAndSetReached(s);

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

   347       DistanceMap<ResGW> dist(res_graph);

   348       while ( !bfs.finished() ) {

   349 	ResGWOutEdgeIt e=bfs;

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

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

   352 	}

   353 	++bfs;

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

   356       MG F;

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

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

   359 	DistanceMap<ResGW> > FilterResGW;

   360       FilterResGW filter_res_graph(res_graph, true_map, dist);

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

   362       {

   363 	typename ResGW::NodeIt n;

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

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

   366 	}

   367       }

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

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

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

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

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

   375       //which are in some shortest paths

   376       {

   377 	typename FilterResGW::EdgeIt e;

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

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

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

   381 	  original_edge.update();

   382 	  original_edge.set(f, e);

   383 	  residual_capacity.update();

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

   385 	  //}

   386 	}

   387       }

   389       bool __augment=true;

   391       while (__augment) {

   392 	__augment=false;

   393 	//computing blocking flow with dfs

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

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

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

   397 	pred.set(sF, INVALID);

   398 	//invalid iterators for sources

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

   402 	dfs.pushAndSetReached(sF);

   403 	while (!dfs.finished()) {

   404 	  ++dfs;

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

   406 	    if (dfs.isBNodeNewlyReached()) {

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

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

   409 	      pred.set(w, dfs);

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

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

   412 	      } else {

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

   414 	      }

   415 	      if (w==tF) {

   416 		__augment=true;

   417 		_augment=true;

   418 		break;

   419 	      }

   421 	    } else {

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

   423 	    }

   424 	  }

   425 	}

   427 	if (__augment) {

   428 	  typename MG::Node n=tF;

   429 	  Number augment_value=free[tF];

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

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

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

   433 	    n=F.tail(e);

   434 	    if (residual_capacity[e]==augment_value)

   435 	      F.erase(e);

   436 	    else

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

   438 	  }

   439 	}

   441       }

   443       return _augment;

   444     }

   446     template<typename MutableGraph> bool augmentOnBlockingFlow1() {

   447       typedef MutableGraph MG;

   448       bool _augment=false;

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

   452       //bfs for distances on the residual graph

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

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

   455       bfs.pushAndSetReached(s);

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

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

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

   460       MG F;

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

   462       {

   463 	typename ResGW::NodeIt n;

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

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

   466 	}

   467       }

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

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

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

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

   474       while ( !bfs.finished() ) {

   475 	ResGWOutEdgeIt e=bfs;

   476 	if (res_graph.valid(e)) {

   477 	  if (bfs.isBNodeNewlyReached()) {

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

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

   480 	    original_edge.update();

   481 	    original_edge.set(f, e);

   482 	    residual_capacity.update();

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

   484 	  } else {

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

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

   487 	      original_edge.update();

   488 	      original_edge.set(f, e);

   489 	      residual_capacity.update();

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

   491 	    }

   492 	  }

   493 	}

   494 	++bfs;

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

   497       bool __augment=true;

   499       while (__augment) {

   500 	__augment=false;

   501 	//computing blocking flow with dfs

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

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

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

   505 	pred.set(sF, INVALID);

   506 	//invalid iterators for sources

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

   510 	dfs.pushAndSetReached(sF);

   511 	while (!dfs.finished()) {

   512 	  ++dfs;

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

   514 	    if (dfs.isBNodeNewlyReached()) {

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

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

   517 	      pred.set(w, dfs);

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

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

   520 	      } else {

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

   522 	      }

   523 	      if (w==tF) {

   524 		__augment=true;

   525 		_augment=true;

   526 		break;

   527 	      }

   529 	    } else {

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

   531 	    }

   532 	  }

   533 	}

   535 	if (__augment) {

   536 	  typename MG::Node n=tF;

   537 	  Number augment_value=free[tF];

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

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

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

   541 	    n=F.tail(e);

   542 	    if (residual_capacity[e]==augment_value)

   543 	      F.erase(e);

   544 	    else

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

   546 	  }

   547 	}

   549       }

   551       return _augment;

   552     }

   554     bool augmentOnBlockingFlow2() {

   555       bool _augment=false;

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

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

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

   562       bfs.pushAndSetReached(s);

   563       DistanceMap<ResGW> dist(res_graph);

   564       while ( !bfs.finished() ) {

   565  	ResGWOutEdgeIt e=bfs;

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

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

   568  	}

   569 	++bfs;

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

   572       //Subgraph containing the edges on some shortest paths

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

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

   575 	DistanceMap<ResGW> > FilterResGW;

   576       FilterResGW filter_res_graph(res_graph, true_map, dist);

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

   579       //met by the dfs

   580       typename FilterResGW::NodeMap<typename FilterResGW::OutEdgeIt>

   581  	first_out_edges(filter_res_graph);

   582       typename FilterResGW::NodeIt v;

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

   584  	  filter_res_graph.next(v))

   585       {

   586  	typename FilterResGW::OutEdgeIt e;

   587  	filter_res_graph.first(e, v);

   588  	first_out_edges.set(v, e);

   589       }

   590       typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::

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

   592       ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);

   594       bool __augment=true;

   596       while (__augment) {

   598  	__augment=false;

   599   	//computing blocking flow with dfs

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

   601   	DfsIterator5< ErasingResGW, BlockingReachedMap >

   602   	  dfs(erasing_res_graph);

   603  	typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt>

   604  	  pred(erasing_res_graph);

   605  	pred.set(s, INVALID);

   606   	//invalid iterators for sources

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

   610  	dfs.pushAndSetReached(s);

   611  	while (!dfs.finished()) {

   612  	  ++dfs;

   613  	  if (erasing_res_graph.valid(

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

   615  	  {

   616   	    if (dfs.isBNodeNewlyReached()) {

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

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

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

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

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

   624  	      } else {

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

   626  	      }

   628  	      if (w==t) {

   629  		__augment=true;

   630  		_augment=true;

   631  		break;

   632  	      }

   633  	    } else {

   634  	      erasing_res_graph.erase(dfs);

   635 	    }

   636 	  }

   637 	}

   639   	if (__augment) {

   640   	  typename ErasingResGW::Node n=t;

   641  	  Number augment_value=free[n];

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

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

   644  	    res_graph.augment(e, augment_value);

   645  	    n=erasing_res_graph.tail(e);

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

   647  	      erasing_res_graph.erase(e);

   648 	}

   649       }

   651       } //while (__augment)

   653       return _augment;

   654     }

   656     void run() {

   657       //int num_of_augmentations=0;

   658       while (augmentOnShortestPath()) {

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

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

   661 	//std::cout<<std::endl;

   662       }

   663     }

   665     template<typename MutableGraph> void run() {

   666       //int num_of_augmentations=0;

   667       //while (augmentOnShortestPath()) {

   668 	while (augmentOnBlockingFlow<MutableGraph>()) {

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

   670 	//std::cout<<std::endl;

   671       }

   672     }

   674     Number flowValue() {

   675       Number a=0;

   676       OutEdgeIt e;

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

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

   679       }

   680       return a;

   681     }

   683   };

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

   687 //   class MaxMatching {

   688 //   public:

   689 //     typedef typename Graph::Node Node;

   690 //     typedef typename Graph::NodeIt NodeIt;

   691 //     typedef typename Graph::Edge Edge;

   692 //     typedef typename Graph::EdgeIt EdgeIt;

   693 //     typedef typename Graph::OutEdgeIt OutEdgeIt;

   694 //     typedef typename Graph::InEdgeIt InEdgeIt;

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

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

   698 //   private:

   699 //     const Graph* G;

   700 //     SMap* S;

   701 //     TMap* T;

   702 //     //Node s;

   703 //     //Node t;

   704 //     FlowMap* flow;

   705 //     const CapacityMap* capacity;

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

   707 //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   708 //     typedef typename AugGraph::Edge AugEdge;

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

   711 //   public:

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

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

   714 //     bool augmentOnShortestPath() {

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

   716 //       bool _augment=false;

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

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

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

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

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

   723 // 	  //Number u=0;

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

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

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

   727 // 	    bfs.pushAndSetReached(s);

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

   729 // 	    //}

   730 // 	}

   731 //       }

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

   735 //       Node n;

   736 //       //searching for augmenting path

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

   738 // 	AugOutEdgeIt e=bfs;

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

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

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

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

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

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

   745 // 	  } else {

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

   747 // 	  }

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

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

   750 // 	    //Number u=0;

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

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

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

   754 // 	      _augment=true;

   755 // 	      break;

   756 // 	      //}

   757 // 	  }

   758 // 	}

   760 // 	++bfs;

   761 //       } //end of searching augmenting path

   763 //       if (_augment) {

   764 // 	//Node n=t;

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

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

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

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

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

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

   771 // 	}

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

   773 //       }

   775 //       return _augment;

   776 //     }

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

   779 // //       bool _augment=false;

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

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

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

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

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

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

   793 // // 	  Number u=0;

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

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

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

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

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

   799 // // 	  }

   800 // // 	}

   801 // //       }

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

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

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

   809 // // 	AugOutEdgeIt e=bfs;

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

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

   812 // // 	}

   814 // // 	++bfs;

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

   817 // //       MutableGraph F;

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

   819 // // 	res_graph_to_F(res_graph);

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

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

   822 // //       }

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

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

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

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

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

   831 // //       //which are in some shortest paths

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

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

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

   835 // // 	  original_edge.update();

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

   837 // // 	  residual_capacity.update();

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

   839 // // 	}

   840 // //       }

   842 // //       bool __augment=true;

   844 // //       while (__augment) {

   845 // // 	__augment=false;

   846 // // 	//computing blocking flow with dfs

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

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

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

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

   851 // // 	//invalid iterators for sources

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

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

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

   857 // // 	  ++dfs;

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

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

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

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

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

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

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

   865 // // 	      } else {

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

   867 // // 	      }

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

   869 // // 		__augment=true;

   870 // // 		_augment=true;

   871 // // 		break;

   872 // // 	      }

   874 // // 	    } else {

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

   876 // // 	    }

   877 // // 	  }

   878 // // 	}

   880 // // 	if (__augment) {

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

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

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

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

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

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

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

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

   889 // // 	    else

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

   891 // // 	  }

   892 // // 	}

   894 // //       }

   896 // //       return _augment;

   897 // //     }

   898 //     bool augmentOnBlockingFlow2() {

   899 //       bool _augment=false;

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

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

   903 //       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;

   904 //       typedef typename EAugGraph::Edge EAugEdge;

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

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

   909 //       BfsIterator5<

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

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

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

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

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

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

   918 // 	  Number u=0;

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

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

   921 // 	  if (u<1) {

   922 // 	    bfs.pushAndSetReached(s);

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

   924 // 	  }

   925 // 	}

   926 //       }

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

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

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

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

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

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

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

   938 // 	}

   939 // 	++bfs;

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

   942 //       bool __augment=true;

   944 //       while (__augment) {

   946 // 	__augment=false;

   947 // 	//computing blocking flow with dfs

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

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

   950 // 	  dfs(res_graph);

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

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

   953 // 	//invalid iterators for sources

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

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

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

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

   961 // 	  Number u=0;

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

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

   964 // 	  if (u<1) {

   965 // 	    dfs.pushAndSetReached(s);

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

   967 // 	  }

   968 // 	}

   969 //       }

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

   974 //       typename EAugGraph::Node n;

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

   976 // 	  ++dfs;

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

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

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

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

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

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

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

   986 // 	      } else {

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

   988 // 	      }

   990 // 	      n=w;

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

   992 // 		Number u=0;

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

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

   995 // 		if (u<1) {

   996 // 		  __augment=true;

   997 // 		  _augment=true;

   998 // 		  break;

   999 // 		}

  1000 // 	      }

  1001 // 	    } else {

  1002 // 	      res_graph.erase(dfs);

  1003 // 	    }

  1004 // 	  }

  1006 // 	}

  1008 // 	if (__augment) {

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

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

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

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

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

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

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

  1016 // 	      res_graph.erase(e);

  1017 // 	  }

  1018 // 	}

  1020 //       }

  1022 //       return _augment;

  1023 //     }

  1024 //     void run() {

  1025 //       //int num_of_augmentations=0;

  1026 //       while (augmentOnShortestPath()) {

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

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

  1029 // 	//std::cout<<std::endl;

  1030 //       }

  1031 //     }

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

  1033 // //       //int num_of_augmentations=0;

  1034 // //       //while (augmentOnShortestPath()) {

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

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

  1037 // // 	//std::cout<<std::endl;

  1038 // //       }

  1039 // //     }

  1040 //     Number flowValue() {

  1041 //       Number a=0;

  1042 //       EdgeIt e;

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

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

  1045 //       }

  1046 //       return a;

  1047 //     }

  1048 //   };

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

  1056 // //   class MaxFlow2 {

  1057 // //   public:

  1058 // //     typedef typename Graph::Node Node;

  1059 // //     typedef typename Graph::Edge Edge;

  1060 // //     typedef typename Graph::EdgeIt EdgeIt;

  1061 // //     typedef typename Graph::OutEdgeIt OutEdgeIt;

  1062 // //     typedef typename Graph::InEdgeIt InEdgeIt;

  1063 // //   private:

  1064 // //     const Graph& G;

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

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

  1067 // //     FlowMap& flow;

  1068 // //     const CapacityMap& capacity;

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

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

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

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

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

  1074 // //   public:

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

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

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

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

  1079 // //       }

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

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

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

  1083 // //       }

  1084 // //     }

  1085 // //     bool augment() {

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

  1087 // //       bool _augment=false;

  1088 // //       Node reached_t_node;

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

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

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

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

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

  1095 // //       }

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

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

  1099 // //       //filled up with invalid iterators

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

  1103 // //       //searching for augmenting path

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

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

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

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

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

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

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

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

  1112 // // 	  } else {

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

  1114 // // 	  }

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

  1116 // // 	    _augment=true;

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

  1118 // // 	    break;

  1119 // // 	  }

  1120 // // 	}

  1122 // // 	++bfs;

  1123 // //       } //end of searching augmenting path

  1125 // //       if (_augment) {

  1126 // // 	Node n=reached_t_node;

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

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

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

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

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

  1132 // // 	}

  1133 // //       }

  1135 // //       return _augment;

  1136 // //     }

  1137 // //     void run() {

  1138 // //       while (augment()) { }

  1139 // //     }

  1140 // //     Number flowValue() {

  1141 // //       Number a=0;

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

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

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

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

  1146 // // 	}

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

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

  1149 // // 	}

  1150 // //       }

  1151 // //       return a;

  1152 // //     }

  1153 // //   };

  1156 } // namespace hugo

  1158 #endif //HUGO_EDMONDS_KARP_H

author	marci
	Tue, 06 Apr 2004 12:00:34 +0000
changeset 311	6635b11938fe
parent 303	1b377a730d02
child 312	54e07057eb47
permissions	-rw-r--r--