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