src/work/marci/oldies/edmonds_karp.hh
author marci
Sat, 03 Apr 2004 14:41:31 +0000
changeset 280 19f3943521ab
permissions -rw-r--r--
takaritas
marci@280
     1
#ifndef EDMONDS_KARP_HH
marci@280
     2
#define EDMONDS_KARP_HH
marci@280
     3
marci@280
     4
#include <algorithm>
marci@280
     5
#include <list>
marci@280
     6
#include <iterator>
marci@280
     7
marci@280
     8
#include <bfs_iterator.hh>
marci@280
     9
//#include <time_measure.h>
marci@280
    10
marci@280
    11
namespace hugo {
marci@280
    12
marci@280
    13
  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
marci@280
    14
  class ResGraph {
marci@280
    15
  public:
marci@280
    16
    typedef typename Graph::NodeIt NodeIt;
marci@280
    17
    typedef typename Graph::EachNodeIt EachNodeIt;
marci@280
    18
  private:
marci@280
    19
    typedef typename Graph::SymEdgeIt OldSymEdgeIt;
marci@280
    20
    const Graph& G;
marci@280
    21
    FlowMap& flow;
marci@280
    22
    const CapacityMap& capacity;
marci@280
    23
  public:
marci@280
    24
    ResGraph(const Graph& _G, FlowMap& _flow, 
marci@280
    25
	     const CapacityMap& _capacity) : 
marci@280
    26
      G(_G), flow(_flow), capacity(_capacity) { }
marci@280
    27
marci@280
    28
    class EdgeIt; 
marci@280
    29
    class OutEdgeIt; 
marci@280
    30
    friend class EdgeIt; 
marci@280
    31
    friend class OutEdgeIt; 
marci@280
    32
marci@280
    33
    class EdgeIt {
marci@280
    34
      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
marci@280
    35
    protected:
marci@280
    36
      const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
marci@280
    37
      OldSymEdgeIt sym;
marci@280
    38
    public:
marci@280
    39
      EdgeIt() { } 
marci@280
    40
      //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
marci@280
    41
      Number free() const { 
marci@280
    42
	if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
marci@280
    43
	  return (resG->capacity.get(sym)-resG->flow.get(sym)); 
marci@280
    44
	} else { 
marci@280
    45
	  return (resG->flow.get(sym)); 
marci@280
    46
	}
marci@280
    47
      }
marci@280
    48
      bool valid() const { return sym.valid(); }
marci@280
    49
      void augment(Number a) const {
marci@280
    50
	if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
marci@280
    51
	  resG->flow.set(sym, resG->flow.get(sym)+a);
marci@280
    52
	  //resG->flow[sym]+=a;
marci@280
    53
	} else { 
marci@280
    54
	  resG->flow.set(sym, resG->flow.get(sym)-a);
marci@280
    55
	  //resG->flow[sym]-=a;
marci@280
    56
	}
marci@280
    57
      }
marci@280
    58
    };
marci@280
    59
marci@280
    60
    class OutEdgeIt : public EdgeIt {
marci@280
    61
      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
marci@280
    62
    public:
marci@280
    63
      OutEdgeIt() { }
marci@280
    64
      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
marci@280
    65
    private:
marci@280
    66
      OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { 
marci@280
    67
      	resG=&_resG;
marci@280
    68
	sym=resG->G.template first<OldSymEdgeIt>(v);
marci@280
    69
	while( sym.valid() && !(free()>0) ) { ++sym; }
marci@280
    70
      }
marci@280
    71
    public:
marci@280
    72
      OutEdgeIt& operator++() { 
marci@280
    73
	++sym; 
marci@280
    74
	while( sym.valid() && !(free()>0) ) { ++sym; }
marci@280
    75
	return *this; 
marci@280
    76
      }
marci@280
    77
    };
marci@280
    78
marci@280
    79
    void getFirst(OutEdgeIt& e, NodeIt v) const { 
marci@280
    80
      e=OutEdgeIt(*this, v); 
marci@280
    81
    }
marci@280
    82
    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
marci@280
    83
    
marci@280
    84
    template< typename It >
marci@280
    85
    It first() const { 
marci@280
    86
      It e;      
marci@280
    87
      getFirst(e);
marci@280
    88
      return e; 
marci@280
    89
    }
marci@280
    90
marci@280
    91
    template< typename It >
marci@280
    92
    It first(NodeIt v) const { 
marci@280
    93
      It e;
marci@280
    94
      getFirst(e, v);
marci@280
    95
      return e; 
marci@280
    96
    }
marci@280
    97
marci@280
    98
    NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
marci@280
    99
    NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
marci@280
   100
marci@280
   101
    NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
marci@280
   102
    NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
marci@280
   103
marci@280
   104
    int id(NodeIt v) const { return G.id(v); }
marci@280
   105
marci@280
   106
    template <typename S>
marci@280
   107
    class NodeMap {
marci@280
   108
      typename Graph::NodeMap<S> node_map; 
marci@280
   109
    public:
marci@280
   110
      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
marci@280
   111
      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
marci@280
   112
      void set(NodeIt nit, S a) { node_map.set(nit, a); }
marci@280
   113
      S get(NodeIt nit) const { return node_map.get(nit); }
marci@280
   114
      S& operator[](NodeIt nit) { return node_map[nit]; } 
marci@280
   115
      const S& operator[](NodeIt nit) const { return node_map[nit]; } 
marci@280
   116
    };
marci@280
   117
marci@280
   118
  };
marci@280
   119
marci@280
   120
marci@280
   121
  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
marci@280
   122
  class ResGraph2 {
marci@280
   123
  public:
marci@280
   124
    typedef typename Graph::NodeIt NodeIt;
marci@280
   125
    typedef typename Graph::EachNodeIt EachNodeIt;
marci@280
   126
  private:
marci@280
   127
    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
marci@280
   128
    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
marci@280
   129
    typedef typename Graph::InEdgeIt OldInEdgeIt;
marci@280
   130
    
marci@280
   131
    const Graph& G;
marci@280
   132
    FlowMap& flow;
marci@280
   133
    const CapacityMap& capacity;
marci@280
   134
  public:
marci@280
   135
    ResGraph2(const Graph& _G, FlowMap& _flow, 
marci@280
   136
	     const CapacityMap& _capacity) : 
marci@280
   137
      G(_G), flow(_flow), capacity(_capacity) { }
marci@280
   138
marci@280
   139
    class EdgeIt; 
marci@280
   140
    class OutEdgeIt; 
marci@280
   141
    friend class EdgeIt; 
marci@280
   142
    friend class OutEdgeIt; 
marci@280
   143
marci@280
   144
    class EdgeIt {
marci@280
   145
      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
marci@280
   146
    protected:
marci@280
   147
      const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
marci@280
   148
      //OldSymEdgeIt sym;
marci@280
   149
      OldOutEdgeIt out;
marci@280
   150
      OldInEdgeIt in;
marci@280
   151
      bool out_or_in; //true, iff out
marci@280
   152
    public:
marci@280
   153
      EdgeIt() : out_or_in(true) { } 
marci@280
   154
      Number free() const { 
marci@280
   155
	if (out_or_in) { 
marci@280
   156
	  return (resG->capacity.get(out)-resG->flow.get(out)); 
marci@280
   157
	} else { 
marci@280
   158
	  return (resG->flow.get(in)); 
marci@280
   159
	}
marci@280
   160
      }
marci@280
   161
      bool valid() const { 
marci@280
   162
	return out_or_in && out.valid() || in.valid(); }
marci@280
   163
      void augment(Number a) const {
marci@280
   164
	if (out_or_in) { 
marci@280
   165
	  resG->flow.set(out, resG->flow.get(out)+a);
marci@280
   166
	} else { 
marci@280
   167
	  resG->flow.set(in, resG->flow.get(in)-a);
marci@280
   168
	}
marci@280
   169
      }
marci@280
   170
    };
marci@280
   171
marci@280
   172
    class OutEdgeIt : public EdgeIt {
marci@280
   173
      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
marci@280
   174
    public:
marci@280
   175
      OutEdgeIt() { }
marci@280
   176
    private:
marci@280
   177
      OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { 
marci@280
   178
      	resG=&_resG;
marci@280
   179
	out=resG->G.template first<OldOutEdgeIt>(v);
marci@280
   180
	while( out.valid() && !(free()>0) ) { ++out; }
marci@280
   181
	if (!out.valid()) {
marci@280
   182
	  out_or_in=0;
marci@280
   183
	  in=resG->G.template first<OldInEdgeIt>(v);
marci@280
   184
	  while( in.valid() && !(free()>0) ) { ++in; }
marci@280
   185
	}
marci@280
   186
      }
marci@280
   187
    public:
marci@280
   188
      OutEdgeIt& operator++() { 
marci@280
   189
	if (out_or_in) {
marci@280
   190
	  NodeIt v=resG->G.aNode(out);
marci@280
   191
	  ++out;
marci@280
   192
	  while( out.valid() && !(free()>0) ) { ++out; }
marci@280
   193
	  if (!out.valid()) {
marci@280
   194
	    out_or_in=0;
marci@280
   195
	    in=resG->G.template first<OldInEdgeIt>(v);
marci@280
   196
	    while( in.valid() && !(free()>0) ) { ++in; }
marci@280
   197
	  }
marci@280
   198
	} else {
marci@280
   199
	  ++in;
marci@280
   200
	  while( in.valid() && !(free()>0) ) { ++in; } 
marci@280
   201
	}
marci@280
   202
	return *this; 
marci@280
   203
      }
marci@280
   204
    };
marci@280
   205
marci@280
   206
    void getFirst(OutEdgeIt& e, NodeIt v) const { 
marci@280
   207
      e=OutEdgeIt(*this, v); 
marci@280
   208
    }
marci@280
   209
    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
marci@280
   210
    
marci@280
   211
    template< typename It >
marci@280
   212
    It first() const { 
marci@280
   213
      It e;
marci@280
   214
      getFirst(e);
marci@280
   215
      return e; 
marci@280
   216
    }
marci@280
   217
marci@280
   218
    template< typename It >
marci@280
   219
    It first(NodeIt v) const { 
marci@280
   220
      It e;
marci@280
   221
      getFirst(e, v);
marci@280
   222
      return e; 
marci@280
   223
    }
marci@280
   224
marci@280
   225
    NodeIt tail(EdgeIt e) const { 
marci@280
   226
      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
marci@280
   227
    NodeIt head(EdgeIt e) const { 
marci@280
   228
      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
marci@280
   229
marci@280
   230
    NodeIt aNode(OutEdgeIt e) const { 
marci@280
   231
      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
marci@280
   232
    NodeIt bNode(OutEdgeIt e) const { 
marci@280
   233
      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
marci@280
   234
marci@280
   235
    int id(NodeIt v) const { return G.id(v); }
marci@280
   236
marci@280
   237
    template <typename S>
marci@280
   238
    class NodeMap {
marci@280
   239
      typename Graph::NodeMap<S> node_map; 
marci@280
   240
    public:
marci@280
   241
      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
marci@280
   242
      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
marci@280
   243
      void set(NodeIt nit, S a) { node_map.set(nit, a); }
marci@280
   244
      S get(NodeIt nit) const { return node_map.get(nit); }
marci@280
   245
    };
marci@280
   246
  };
marci@280
   247
marci@280
   248
marci@280
   249
  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
marci@280
   250
  class MaxFlow {
marci@280
   251
  public:
marci@280
   252
    typedef typename Graph::NodeIt NodeIt;
marci@280
   253
    typedef typename Graph::EdgeIt EdgeIt;
marci@280
   254
    typedef typename Graph::EachEdgeIt EachEdgeIt;
marci@280
   255
    typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@280
   256
    typedef typename Graph::InEdgeIt InEdgeIt;
marci@280
   257
marci@280
   258
  private:
marci@280
   259
    const Graph* G;
marci@280
   260
    NodeIt s;
marci@280
   261
    NodeIt t;
marci@280
   262
    FlowMap* flow;
marci@280
   263
    const CapacityMap* capacity;
marci@280
   264
    typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
marci@280
   265
    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
marci@280
   266
    typedef typename AugGraph::EdgeIt AugEdgeIt;
marci@280
   267
marci@280
   268
    //AugGraph res_graph;    
marci@280
   269
    //typedef typename AugGraph::NodeMap<bool> ReachedMap;
marci@280
   270
    //typename AugGraph::NodeMap<AugEdgeIt> pred; 
marci@280
   271
    //typename AugGraph::NodeMap<Number> free;
marci@280
   272
  public:
marci@280
   273
    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : 
marci@280
   274
      G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //,  
marci@280
   275
      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) 
marci@280
   276
      { }
marci@280
   277
    bool augmentOnShortestPath() {
marci@280
   278
      AugGraph res_graph(*G, *flow, *capacity);
marci@280
   279
      bool _augment=false;
marci@280
   280
      
marci@280
   281
      typedef typename AugGraph::NodeMap<bool> ReachedMap;
marci@280
   282
      BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
marci@280
   283
      res_bfs.pushAndSetReached(s);
marci@280
   284
	
marci@280
   285
      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 
marci@280
   286
      //filled up with invalid iterators
marci@280
   287
      //pred.set(s, AugEdgeIt());
marci@280
   288
      
marci@280
   289
      typename AugGraph::NodeMap<Number> free(res_graph);
marci@280
   290
	
marci@280
   291
      //searching for augmenting path
marci@280
   292
      while ( !res_bfs.finished() ) { 
marci@280
   293
	AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
marci@280
   294
	if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
marci@280
   295
	  NodeIt v=res_graph.tail(e);
marci@280
   296
	  NodeIt w=res_graph.head(e);
marci@280
   297
	  pred.set(w, e);
marci@280
   298
	  if (res_graph.valid(pred.get(v))) {
marci@280
   299
	    free.set(w, std::min(free.get(v), res_graph.free(e)));
marci@280
   300
	  } else {
marci@280
   301
	    free.set(w, res_graph.free(e)); 
marci@280
   302
	  }
marci@280
   303
	  if (res_graph.head(e)==t) { _augment=true; break; }
marci@280
   304
	}
marci@280
   305
	
marci@280
   306
	++res_bfs;
marci@280
   307
      } //end of searching augmenting path
marci@280
   308
marci@280
   309
      if (_augment) {
marci@280
   310
	NodeIt n=t;
marci@280
   311
	Number augment_value=free.get(t);
marci@280
   312
	while (res_graph.valid(pred.get(n))) { 
marci@280
   313
	  AugEdgeIt e=pred.get(n);
marci@280
   314
	  res_graph.augment(e, augment_value); 
marci@280
   315
	  //e.augment(augment_value); 
marci@280
   316
	  n=res_graph.tail(e);
marci@280
   317
	}
marci@280
   318
      }
marci@280
   319
marci@280
   320
      return _augment;
marci@280
   321
    }
marci@280
   322
marci@280
   323
    template<typename MutableGraph> bool augmentOnBlockingFlow() {
marci@280
   324
      bool _augment=false;
marci@280
   325
marci@280
   326
      AugGraph res_graph(*G, *flow, *capacity);
marci@280
   327
marci@280
   328
      typedef typename AugGraph::NodeMap<bool> ReachedMap;
marci@280
   329
      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
marci@280
   330
marci@280
   331
      bfs.pushAndSetReached(s);
marci@280
   332
      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
marci@280
   333
      while ( !bfs.finished() ) { 
marci@280
   334
	AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
marci@280
   335
	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
marci@280
   336
	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
marci@280
   337
	}
marci@280
   338
	
marci@280
   339
	++bfs;
marci@280
   340
      } //computing distances from s in the residual graph
marci@280
   341
marci@280
   342
      MutableGraph F;
marci@280
   343
      typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
marci@280
   344
      for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
marci@280
   345
	res_graph_to_F.set(n, F.addNode());
marci@280
   346
      }
marci@280
   347
      
marci@280
   348
      typename MutableGraph::NodeIt sF=res_graph_to_F.get(s);
marci@280
   349
      typename MutableGraph::NodeIt tF=res_graph_to_F.get(t);
marci@280
   350
marci@280
   351
      typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);
marci@280
   352
      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
marci@280
   353
marci@280
   354
      //Making F to the graph containing the edges of the residual graph 
marci@280
   355
      //which are in some shortest paths
marci@280
   356
      for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
marci@280
   357
	if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
marci@280
   358
	  typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
marci@280
   359
	  original_edge.update();
marci@280
   360
	  original_edge.set(f, e);
marci@280
   361
	  residual_capacity.update();
marci@280
   362
	  residual_capacity.set(f, res_graph.free(e));
marci@280
   363
	} 
marci@280
   364
      }
marci@280
   365
marci@280
   366
      bool __augment=true;
marci@280
   367
marci@280
   368
      while (__augment) {
marci@280
   369
	__augment=false;
marci@280
   370
	//computing blocking flow with dfs
marci@280
   371
	typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
marci@280
   372
	DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
marci@280
   373
	typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators
marci@280
   374
	typename MutableGraph::NodeMap<Number> free(F);
marci@280
   375
marci@280
   376
	dfs.pushAndSetReached(sF);      
marci@280
   377
	while (!dfs.finished()) {
marci@280
   378
	  ++dfs;
marci@280
   379
	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
marci@280
   380
	    if (dfs.isBNodeNewlyReached()) {
marci@280
   381
// 	      std::cout << "OutEdgeIt: " << dfs; 
marci@280
   382
// 	      std::cout << " aNode: " << F.aNode(dfs); 
marci@280
   383
// 	      std::cout << " bNode: " << F.bNode(dfs) << " ";
marci@280
   384
	  
marci@280
   385
	      typename MutableGraph::NodeIt v=F.aNode(dfs);
marci@280
   386
	      typename MutableGraph::NodeIt w=F.bNode(dfs);
marci@280
   387
	      pred.set(w, dfs);
marci@280
   388
	      if (F.valid(pred.get(v))) {
marci@280
   389
		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
marci@280
   390
	      } else {
marci@280
   391
		free.set(w, residual_capacity.get(dfs)); 
marci@280
   392
	      }
marci@280
   393
	      if (w==tF) { 
marci@280
   394
		//std::cout << "AUGMENTATION"<<std::endl;
marci@280
   395
		__augment=true; 
marci@280
   396
		_augment=true;
marci@280
   397
		break; 
marci@280
   398
	      }
marci@280
   399
	      
marci@280
   400
	    } else {
marci@280
   401
	      F.erase(typename MutableGraph::OutEdgeIt(dfs));
marci@280
   402
	    }
marci@280
   403
	  } 
marci@280
   404
	}
marci@280
   405
marci@280
   406
	if (__augment) {
marci@280
   407
	  typename MutableGraph::NodeIt n=tF;
marci@280
   408
	  Number augment_value=free.get(tF);
marci@280
   409
	  while (F.valid(pred.get(n))) { 
marci@280
   410
	    typename MutableGraph::EdgeIt e=pred.get(n);
marci@280
   411
	    res_graph.augment(original_edge.get(e), augment_value); 
marci@280
   412
	    //original_edge.get(e).augment(augment_value); 
marci@280
   413
	    n=F.tail(e);
marci@280
   414
	    if (residual_capacity.get(e)==augment_value) 
marci@280
   415
	      F.erase(e); 
marci@280
   416
	    else 
marci@280
   417
	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);
marci@280
   418
	  }
marci@280
   419
	}
marci@280
   420
	
marci@280
   421
      }
marci@280
   422
            
marci@280
   423
      return _augment;
marci@280
   424
    }
marci@280
   425
    bool augmentOnBlockingFlow2() {
marci@280
   426
      bool _augment=false;
marci@280
   427
marci@280
   428
      //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
marci@280
   429
      typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
marci@280
   430
      typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
marci@280
   431
      typedef typename EAugGraph::EdgeIt EAugEdgeIt;
marci@280
   432
marci@280
   433
      EAugGraph res_graph(*G, *flow, *capacity);
marci@280
   434
marci@280
   435
      //std::cout << "meg jo1" << std::endl;
marci@280
   436
marci@280
   437
      //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
marci@280
   438
      BfsIterator4< 
marci@280
   439
	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 
marci@280
   440
	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 
marci@280
   441
	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
marci@280
   442
      
marci@280
   443
      //std::cout << "meg jo2" << std::endl;
marci@280
   444
marci@280
   445
      bfs.pushAndSetReached(s);
marci@280
   446
      //std::cout << "meg jo2.5" << std::endl;
marci@280
   447
marci@280
   448
      //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
marci@280
   449
      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
marci@280
   450
	NodeMap<int>& dist=res_graph.dist;
marci@280
   451
      //std::cout << "meg jo2.6" << std::endl;
marci@280
   452
marci@280
   453
      while ( !bfs.finished() ) {
marci@280
   454
	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
marci@280
   455
//	EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
marci@280
   456
 	//if (res_graph.valid(e)) {
marci@280
   457
 	//    std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;
marci@280
   458
 	//}
marci@280
   459
	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
marci@280
   460
	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
marci@280
   461
	}
marci@280
   462
	
marci@280
   463
	++bfs;	
marci@280
   464
      } //computing distances from s in the residual graph
marci@280
   465
marci@280
   466
marci@280
   467
      //std::cout << "meg jo3" << std::endl;
marci@280
   468
marci@280
   469
//       typedef typename EAugGraph::EachNodeIt EAugEachNodeIt;
marci@280
   470
//       for(EAugEachNodeIt n=res_graph.template first<EAugEachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
marci@280
   471
// 	std::cout << "dist: " << dist.get(n) << std::endl;
marci@280
   472
//       }
marci@280
   473
marci@280
   474
      bool __augment=true;
marci@280
   475
marci@280
   476
      while (__augment) {
marci@280
   477
//	std::cout << "new iteration"<< std::endl;
marci@280
   478
marci@280
   479
	__augment=false;
marci@280
   480
	//computing blocking flow with dfs
marci@280
   481
	typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
marci@280
   482
	DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > 
marci@280
   483
	  dfs(res_graph);
marci@280
   484
	typename EAugGraph::NodeMap<EAugEdgeIt> pred(res_graph); //invalid iterators
marci@280
   485
	typename EAugGraph::NodeMap<Number> free(res_graph);
marci@280
   486
marci@280
   487
	dfs.pushAndSetReached(s);
marci@280
   488
	while (!dfs.finished()) {
marci@280
   489
	  ++dfs;
marci@280
   490
	  if (res_graph.valid(EAugOutEdgeIt(dfs))) { 
marci@280
   491
	    if (dfs.isBNodeNewlyReached()) {
marci@280
   492
// 	      std::cout << "OutEdgeIt: " << dfs; 
marci@280
   493
// 	      std::cout << " aNode: " << res_graph.aNode(dfs); 
marci@280
   494
// 	      std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); 
marci@280
   495
// 	      std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
marci@280
   496
	  
marci@280
   497
	      typename EAugGraph::NodeIt v=res_graph.aNode(dfs);
marci@280
   498
	      typename EAugGraph::NodeIt w=res_graph.bNode(dfs);
marci@280
   499
marci@280
   500
	      pred.set(w, EAugOutEdgeIt(dfs));
marci@280
   501
marci@280
   502
	      //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;
marci@280
   503
	      if (res_graph.valid(pred.get(v))) {
marci@280
   504
		free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs))));
marci@280
   505
	      } else {
marci@280
   506
		free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs))); 
marci@280
   507
	      }
marci@280
   508
	      
marci@280
   509
	      if (w==t) { 
marci@280
   510
//		std::cout << "t is reached, AUGMENTATION"<<std::endl;
marci@280
   511
		__augment=true; 
marci@280
   512
		_augment=true;
marci@280
   513
		break; 
marci@280
   514
	      }
marci@280
   515
	    } else {
marci@280
   516
//	      std::cout << "<<DELETE ";
marci@280
   517
//	      std::cout << " aNode: " << res_graph.aNode(dfs); 
marci@280
   518
//	      std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); 
marci@280
   519
//	      std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
marci@280
   520
//	      std::cout << "DELETE>> ";
marci@280
   521
marci@280
   522
	      res_graph.erase(dfs);
marci@280
   523
	    }
marci@280
   524
	  } 
marci@280
   525
marci@280
   526
	}
marci@280
   527
marci@280
   528
	if (__augment) {
marci@280
   529
	  typename EAugGraph::NodeIt n=t;
marci@280
   530
	  Number augment_value=free.get(t);
marci@280
   531
//	  std::cout << "av:" << augment_value << std::endl;
marci@280
   532
	  while (res_graph.valid(pred.get(n))) { 
marci@280
   533
	    EAugEdgeIt e=pred.get(n);
marci@280
   534
	    res_graph.augment(e, augment_value);
marci@280
   535
	    //e.augment(augment_value); 
marci@280
   536
	    n=res_graph.tail(e);
marci@280
   537
	    if (res_graph.free(e)==0)
marci@280
   538
	      res_graph.erase(e);
marci@280
   539
	  }
marci@280
   540
	}
marci@280
   541
      
marci@280
   542
      }
marci@280
   543
            
marci@280
   544
      return _augment;
marci@280
   545
    }
marci@280
   546
    void run() {
marci@280
   547
      //int num_of_augmentations=0;
marci@280
   548
      while (augmentOnShortestPath()) { 
marci@280
   549
	//while (augmentOnBlockingFlow<MutableGraph>()) { 
marci@280
   550
	//std::cout << ++num_of_augmentations << " ";
marci@280
   551
	//std::cout<<std::endl;
marci@280
   552
      } 
marci@280
   553
    }
marci@280
   554
    template<typename MutableGraph> void run() {
marci@280
   555
      //int num_of_augmentations=0;
marci@280
   556
      //while (augmentOnShortestPath()) { 
marci@280
   557
	while (augmentOnBlockingFlow<MutableGraph>()) { 
marci@280
   558
	//std::cout << ++num_of_augmentations << " ";
marci@280
   559
	//std::cout<<std::endl;
marci@280
   560
      } 
marci@280
   561
    }
marci@280
   562
    Number flowValue() { 
marci@280
   563
      Number a=0;
marci@280
   564
      OutEdgeIt e;
marci@280
   565
      for(G->getFirst(e, s); G->valid(e); G->next(e)) {
marci@280
   566
	a+=flow->get(e);
marci@280
   567
      }
marci@280
   568
      return a;
marci@280
   569
    }
marci@280
   570
  };
marci@280
   571
marci@280
   572
  
marci@280
   573
//   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
marci@280
   574
//   class MaxFlow2 {
marci@280
   575
//   public:
marci@280
   576
//     typedef typename Graph::NodeIt NodeIt;
marci@280
   577
//     typedef typename Graph::EdgeIt EdgeIt;
marci@280
   578
//     typedef typename Graph::EachEdgeIt EachEdgeIt;
marci@280
   579
//     typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@280
   580
//     typedef typename Graph::InEdgeIt InEdgeIt;
marci@280
   581
//   private:
marci@280
   582
//     const Graph& G;
marci@280
   583
//     std::list<NodeIt>& S;
marci@280
   584
//     std::list<NodeIt>& T;
marci@280
   585
//     FlowMap& flow;
marci@280
   586
//     const CapacityMap& capacity;
marci@280
   587
//     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
marci@280
   588
//     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
marci@280
   589
//     typedef typename AugGraph::EdgeIt AugEdgeIt;
marci@280
   590
//     typename Graph::NodeMap<bool> SMap;
marci@280
   591
//     typename Graph::NodeMap<bool> TMap;
marci@280
   592
//   public:
marci@280
   593
//     MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { 
marci@280
   594
//       for(typename std::list<NodeIt>::const_iterator i=S.begin(); 
marci@280
   595
// 	  i!=S.end(); ++i) { 
marci@280
   596
// 	SMap.set(*i, true); 
marci@280
   597
//       }
marci@280
   598
//       for (typename std::list<NodeIt>::const_iterator i=T.begin(); 
marci@280
   599
// 	   i!=T.end(); ++i) { 
marci@280
   600
// 	TMap.set(*i, true); 
marci@280
   601
//       }
marci@280
   602
//     }
marci@280
   603
//     bool augment() {
marci@280
   604
//       AugGraph res_graph(G, flow, capacity);
marci@280
   605
//       bool _augment=false;
marci@280
   606
//       NodeIt reached_t_node;
marci@280
   607
      
marci@280
   608
//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
marci@280
   609
//       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
marci@280
   610
//       for(typename std::list<NodeIt>::const_iterator i=S.begin(); 
marci@280
   611
// 	  i!=S.end(); ++i) {
marci@280
   612
// 	res_bfs.pushAndSetReached(*i);
marci@280
   613
//       }
marci@280
   614
//       //res_bfs.pushAndSetReached(s);
marci@280
   615
	
marci@280
   616
//       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 
marci@280
   617
//       //filled up with invalid iterators
marci@280
   618
      
marci@280
   619
//       typename AugGraph::NodeMap<Number> free(res_graph);
marci@280
   620
	
marci@280
   621
//       //searching for augmenting path
marci@280
   622
//       while ( !res_bfs.finished() ) { 
marci@280
   623
// 	AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
marci@280
   624
// 	if (e.valid() && res_bfs.isBNodeNewlyReached()) {
marci@280
   625
// 	  NodeIt v=res_graph.tail(e);
marci@280
   626
// 	  NodeIt w=res_graph.head(e);
marci@280
   627
// 	  pred.set(w, e);
marci@280
   628
// 	  if (pred.get(v).valid()) {
marci@280
   629
// 	    free.set(w, std::min(free.get(v), e.free()));
marci@280
   630
// 	  } else {
marci@280
   631
// 	    free.set(w, e.free()); 
marci@280
   632
// 	  }
marci@280
   633
// 	  if (TMap.get(res_graph.head(e))) { 
marci@280
   634
// 	    _augment=true; 
marci@280
   635
// 	    reached_t_node=res_graph.head(e);
marci@280
   636
// 	    break; 
marci@280
   637
// 	  }
marci@280
   638
// 	}
marci@280
   639
	
marci@280
   640
// 	++res_bfs;
marci@280
   641
//       } //end of searching augmenting path
marci@280
   642
marci@280
   643
//       if (_augment) {
marci@280
   644
// 	NodeIt n=reached_t_node;
marci@280
   645
// 	Number augment_value=free.get(reached_t_node);
marci@280
   646
// 	while (pred.get(n).valid()) { 
marci@280
   647
// 	  AugEdgeIt e=pred.get(n);
marci@280
   648
// 	  e.augment(augment_value); 
marci@280
   649
// 	  n=res_graph.tail(e);
marci@280
   650
// 	}
marci@280
   651
//       }
marci@280
   652
marci@280
   653
//       return _augment;
marci@280
   654
//     }
marci@280
   655
//     void run() {
marci@280
   656
//       while (augment()) { } 
marci@280
   657
//     }
marci@280
   658
//     Number flowValue() { 
marci@280
   659
//       Number a=0;
marci@280
   660
//       for(typename std::list<NodeIt>::const_iterator i=S.begin(); 
marci@280
   661
// 	  i!=S.end(); ++i) { 
marci@280
   662
// 	for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
marci@280
   663
// 	  a+=flow.get(e);
marci@280
   664
// 	}
marci@280
   665
// 	for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
marci@280
   666
// 	  a-=flow.get(e);
marci@280
   667
// 	}
marci@280
   668
//       }
marci@280
   669
//       return a;
marci@280
   670
//     }
marci@280
   671
//   };
marci@280
   672
marci@280
   673
marci@280
   674
marci@280
   675
} // namespace hugo
marci@280
   676
marci@280
   677
#endif //EDMONDS_KARP_HH