src/work/edmonds_karp.hh
author marci
Fri, 27 Feb 2004 12:39:15 +0000
changeset 133 0631992fe7a1
parent 127 dcace15b1874
child 135 1e5060d1fa1d
permissions -rw-r--r--
Dinits blocking flow added to edmonds_karp_demo.hh.
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@133
     9
//#include <time_measure.h>
marci@43
    10
alpar@107
    11
namespace hugo {
marci@43
    12
marci@75
    13
  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
marci@43
    14
  class ResGraph {
klao@127
    15
  public:
marci@43
    16
    typedef typename Graph::NodeIt NodeIt;
marci@43
    17
    typedef typename Graph::EachNodeIt EachNodeIt;
klao@127
    18
  private:
marci@43
    19
    typedef typename Graph::SymEdgeIt OldSymEdgeIt;
marci@43
    20
    const Graph& G;
marci@59
    21
    FlowMap& flow;
marci@59
    22
    const CapacityMap& capacity;
marci@43
    23
  public:
marci@59
    24
    ResGraph(const Graph& _G, FlowMap& _flow, 
marci@59
    25
	     const CapacityMap& _capacity) : 
marci@43
    26
      G(_G), flow(_flow), capacity(_capacity) { }
marci@43
    27
marci@43
    28
    class EdgeIt; 
marci@43
    29
    class OutEdgeIt; 
marci@43
    30
    friend class EdgeIt; 
marci@43
    31
    friend class OutEdgeIt; 
marci@43
    32
marci@43
    33
    class EdgeIt {
marci@75
    34
      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
marci@43
    35
    protected:
marci@75
    36
      const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
marci@43
    37
      OldSymEdgeIt sym;
marci@43
    38
    public:
marci@43
    39
      EdgeIt() { } 
marci@43
    40
      //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
marci@75
    41
      Number free() const { 
marci@43
    42
	if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
marci@43
    43
	  return (resG->capacity.get(sym)-resG->flow.get(sym)); 
marci@43
    44
	} else { 
marci@43
    45
	  return (resG->flow.get(sym)); 
marci@43
    46
	}
marci@43
    47
      }
marci@43
    48
      bool valid() const { return sym.valid(); }
marci@75
    49
      void augment(Number a) const {
marci@43
    50
	if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
marci@43
    51
	  resG->flow.set(sym, resG->flow.get(sym)+a);
marci@75
    52
	  //resG->flow[sym]+=a;
marci@43
    53
	} else { 
marci@43
    54
	  resG->flow.set(sym, resG->flow.get(sym)-a);
marci@75
    55
	  //resG->flow[sym]-=a;
marci@43
    56
	}
marci@43
    57
      }
marci@43
    58
    };
marci@43
    59
marci@43
    60
    class OutEdgeIt : public EdgeIt {
marci@75
    61
      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
marci@43
    62
    public:
marci@43
    63
      OutEdgeIt() { }
marci@43
    64
      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
marci@43
    65
    private:
marci@75
    66
      OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { 
marci@43
    67
      	resG=&_resG;
marci@43
    68
	sym=resG->G.template first<OldSymEdgeIt>(v);
marci@43
    69
	while( sym.valid() && !(free()>0) ) { ++sym; }
marci@43
    70
      }
marci@43
    71
    public:
marci@43
    72
      OutEdgeIt& operator++() { 
marci@43
    73
	++sym; 
marci@43
    74
	while( sym.valid() && !(free()>0) ) { ++sym; }
marci@43
    75
	return *this; 
marci@43
    76
      }
marci@43
    77
    };
marci@43
    78
marci@64
    79
    void getFirst(OutEdgeIt& e, NodeIt v) const { 
marci@43
    80
      e=OutEdgeIt(*this, v); 
marci@43
    81
    }
marci@43
    82
    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
marci@43
    83
    
marci@43
    84
    template< typename It >
marci@43
    85
    It first() const { 
marci@75
    86
      It e;      
marci@75
    87
      getFirst(e);
marci@75
    88
      return e; 
marci@75
    89
    }
marci@75
    90
marci@75
    91
    template< typename It >
marci@75
    92
    It first(NodeIt v) const { 
marci@75
    93
      It e;
marci@75
    94
      getFirst(e, v);
marci@75
    95
      return e; 
marci@75
    96
    }
marci@75
    97
marci@75
    98
    NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
marci@75
    99
    NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
marci@75
   100
marci@75
   101
    NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
marci@75
   102
    NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
marci@75
   103
marci@75
   104
    int id(NodeIt v) const { return G.id(v); }
marci@75
   105
marci@75
   106
    template <typename S>
marci@75
   107
    class NodeMap {
marci@75
   108
      typename Graph::NodeMap<S> node_map; 
marci@75
   109
    public:
marci@75
   110
      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
marci@75
   111
      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
marci@75
   112
      void set(NodeIt nit, S a) { node_map.set(nit, a); }
marci@75
   113
      S get(NodeIt nit) const { return node_map.get(nit); }
marci@75
   114
      S& operator[](NodeIt nit) { return node_map[nit]; } 
marci@75
   115
      const S& operator[](NodeIt nit) const { return node_map[nit]; } 
marci@75
   116
    };
marci@75
   117
marci@75
   118
  };
marci@75
   119
marci@75
   120
marci@75
   121
  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
marci@75
   122
  class ResGraph2 {
klao@127
   123
  public:
marci@75
   124
    typedef typename Graph::NodeIt NodeIt;
marci@75
   125
    typedef typename Graph::EachNodeIt EachNodeIt;
klao@127
   126
  private:
marci@75
   127
    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
marci@75
   128
    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
marci@75
   129
    typedef typename Graph::InEdgeIt OldInEdgeIt;
marci@75
   130
    
marci@75
   131
    const Graph& G;
marci@75
   132
    FlowMap& flow;
marci@75
   133
    const CapacityMap& capacity;
marci@75
   134
  public:
marci@75
   135
    ResGraph2(const Graph& _G, FlowMap& _flow, 
marci@75
   136
	     const CapacityMap& _capacity) : 
marci@75
   137
      G(_G), flow(_flow), capacity(_capacity) { }
marci@75
   138
marci@75
   139
    class EdgeIt; 
marci@75
   140
    class OutEdgeIt; 
marci@75
   141
    friend class EdgeIt; 
marci@75
   142
    friend class OutEdgeIt; 
marci@75
   143
marci@75
   144
    class EdgeIt {
marci@75
   145
      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
marci@75
   146
    protected:
marci@75
   147
      const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
marci@75
   148
      //OldSymEdgeIt sym;
marci@75
   149
      OldOutEdgeIt out;
marci@75
   150
      OldInEdgeIt in;
marci@75
   151
      bool out_or_in; //1, iff out
marci@75
   152
    public:
marci@75
   153
      EdgeIt() : out_or_in(1) { } 
marci@75
   154
      Number free() const { 
marci@75
   155
	if (out_or_in) { 
marci@75
   156
	  return (resG->capacity.get(out)-resG->flow.get(out)); 
marci@75
   157
	} else { 
marci@75
   158
	  return (resG->flow.get(in)); 
marci@75
   159
	}
marci@75
   160
      }
marci@75
   161
      bool valid() const { 
marci@75
   162
	return out_or_in && out.valid() || in.valid(); }
marci@75
   163
      void augment(Number a) const {
marci@75
   164
	if (out_or_in) { 
marci@75
   165
	  resG->flow.set(out, resG->flow.get(out)+a);
marci@75
   166
	} else { 
marci@75
   167
	  resG->flow.set(in, resG->flow.get(in)-a);
marci@75
   168
	}
marci@75
   169
      }
marci@75
   170
    };
marci@75
   171
marci@75
   172
    class OutEdgeIt : public EdgeIt {
marci@75
   173
      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
marci@75
   174
    public:
marci@75
   175
      OutEdgeIt() { }
marci@75
   176
    private:
marci@75
   177
      OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { 
marci@75
   178
      	resG=&_resG;
marci@75
   179
	out=resG->G.template first<OldOutEdgeIt>(v);
marci@75
   180
	while( out.valid() && !(free()>0) ) { ++out; }
marci@75
   181
	if (!out.valid()) {
marci@75
   182
	  out_or_in=0;
marci@75
   183
	  in=resG->G.template first<OldInEdgeIt>(v);
marci@75
   184
	  while( in.valid() && !(free()>0) ) { ++in; }
marci@75
   185
	}
marci@75
   186
      }
marci@75
   187
    public:
marci@75
   188
      OutEdgeIt& operator++() { 
marci@75
   189
	if (out_or_in) {
marci@75
   190
	  NodeIt v=resG->G.aNode(out);
marci@75
   191
	  ++out;
marci@75
   192
	  while( out.valid() && !(free()>0) ) { ++out; }
marci@75
   193
	  if (!out.valid()) {
marci@75
   194
	    out_or_in=0;
marci@75
   195
	    in=resG->G.template first<OldInEdgeIt>(v);
marci@75
   196
	    while( in.valid() && !(free()>0) ) { ++in; }
marci@75
   197
	  }
marci@75
   198
	} else {
marci@75
   199
	  ++in;
marci@75
   200
	  while( in.valid() && !(free()>0) ) { ++in; } 
marci@75
   201
	}
marci@75
   202
	return *this; 
marci@75
   203
      }
marci@75
   204
    };
marci@75
   205
marci@75
   206
    void getFirst(OutEdgeIt& e, NodeIt v) const { 
marci@75
   207
      e=OutEdgeIt(*this, v); 
marci@75
   208
    }
marci@75
   209
    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
marci@75
   210
    
marci@75
   211
    template< typename It >
marci@75
   212
    It first() const { 
marci@43
   213
      It e;
marci@43
   214
      getFirst(e);
marci@43
   215
      return e; 
marci@43
   216
    }
marci@43
   217
marci@43
   218
    template< typename It >
marci@64
   219
    It first(NodeIt v) const { 
marci@43
   220
      It e;
marci@43
   221
      getFirst(e, v);
marci@43
   222
      return e; 
marci@43
   223
    }
marci@43
   224
marci@75
   225
    NodeIt tail(EdgeIt e) const { 
marci@75
   226
      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
marci@75
   227
    NodeIt head(EdgeIt e) const { 
marci@75
   228
      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
marci@43
   229
marci@75
   230
    NodeIt aNode(OutEdgeIt e) const { 
marci@75
   231
      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
marci@75
   232
    NodeIt bNode(OutEdgeIt e) const { 
marci@75
   233
      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
marci@43
   234
marci@64
   235
    int id(NodeIt v) const { return G.id(v); }
marci@43
   236
marci@69
   237
    template <typename S>
marci@43
   238
    class NodeMap {
marci@69
   239
      typename Graph::NodeMap<S> node_map; 
marci@43
   240
    public:
marci@75
   241
      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
marci@75
   242
      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
marci@75
   243
      void set(NodeIt nit, S a) { node_map.set(nit, a); }
marci@75
   244
      S get(NodeIt nit) const { return node_map.get(nit); }
marci@75
   245
    };
marci@75
   246
  };
marci@75
   247
marci@75
   248
  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
marci@75
   249
  class ResGraph3 {
klao@127
   250
  public:
marci@75
   251
    typedef typename Graph::NodeIt NodeIt;
marci@75
   252
    typedef typename Graph::EachNodeIt EachNodeIt;
klao@127
   253
klao@127
   254
  private:
marci@75
   255
    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
marci@75
   256
    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
marci@75
   257
    typedef typename Graph::InEdgeIt OldInEdgeIt;
marci@75
   258
    const Graph& G;
marci@75
   259
    FlowMap& flow;
marci@75
   260
    const CapacityMap& capacity;
marci@75
   261
  public:
marci@75
   262
    ResGraph3(const Graph& _G, FlowMap& _flow, 
marci@75
   263
	     const CapacityMap& _capacity) : 
marci@75
   264
      G(_G), flow(_flow), capacity(_capacity) { }
marci@75
   265
marci@75
   266
    class EdgeIt; 
marci@75
   267
    class OutEdgeIt; 
marci@75
   268
    friend class EdgeIt; 
marci@75
   269
    friend class OutEdgeIt; 
marci@75
   270
marci@75
   271
    class EdgeIt {
marci@75
   272
      friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
marci@75
   273
    protected:
marci@75
   274
      //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
marci@75
   275
      const Graph* G;
marci@75
   276
      FlowMap* flow;
marci@75
   277
      const CapacityMap* capacity;
marci@75
   278
      //OldSymEdgeIt sym;
marci@75
   279
      OldOutEdgeIt out;
marci@75
   280
      OldInEdgeIt in;
marci@75
   281
      bool out_or_in; //1, iff out
marci@75
   282
    public:
marci@75
   283
      EdgeIt() : out_or_in(1) { } 
marci@133
   284
      //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }
marci@75
   285
      Number free() const { 
marci@75
   286
	if (out_or_in) { 
marci@75
   287
	  return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out)); 
marci@75
   288
	} else { 
marci@75
   289
	  return (/*resG->*/flow->get(in)); 
marci@75
   290
	}
marci@75
   291
      }
marci@75
   292
      bool valid() const { 
marci@75
   293
	return out_or_in && out.valid() || in.valid(); }
marci@75
   294
      void augment(Number a) const {
marci@75
   295
	if (out_or_in) { 
marci@75
   296
	  /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
marci@75
   297
	} else { 
marci@75
   298
	  /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
marci@75
   299
	}
marci@75
   300
      }
marci@133
   301
      void print() { 
marci@133
   302
	if (out_or_in) {
marci@133
   303
	  std::cout << "out "; 
marci@133
   304
	  if (out.valid()) 
marci@133
   305
	    std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out)); 
marci@133
   306
	  else 
marci@133
   307
	    std::cout << "invalid"; 
marci@133
   308
	}
marci@133
   309
	else {
marci@133
   310
	  std::cout << "in "; 
marci@133
   311
	  if (in.valid()) 
marci@133
   312
	    std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in)); 
marci@133
   313
	  else 
marci@133
   314
	    std::cout << "invalid"; 
marci@133
   315
	}
marci@133
   316
	std::cout << std::endl;
marci@133
   317
      }
marci@75
   318
    };
marci@75
   319
marci@75
   320
    class OutEdgeIt : public EdgeIt {
marci@75
   321
      friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
marci@75
   322
    public:
marci@75
   323
      OutEdgeIt() { }
marci@75
   324
    private:
marci@75
   325
      OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) { 
marci@75
   326
      	G=&_G;
marci@75
   327
	flow=&_flow;
marci@75
   328
	capacity=&_capacity;
marci@133
   329
	//out=/*resG->*/G->template first<OldOutEdgeIt>(v);
marci@133
   330
	G->getFirst(out, v);
marci@75
   331
	while( out.valid() && !(free()>0) ) { ++out; }
marci@75
   332
	if (!out.valid()) {
marci@75
   333
	  out_or_in=0;
marci@133
   334
	  //in=/*resG->*/G->template first<OldInEdgeIt>(v);
marci@133
   335
	  G->getFirst(in, v);
marci@75
   336
	  while( in.valid() && !(free()>0) ) { ++in; }
marci@75
   337
	}
marci@75
   338
      }
marci@75
   339
    public:
marci@75
   340
      OutEdgeIt& operator++() { 
marci@75
   341
	if (out_or_in) {
marci@75
   342
	  NodeIt v=/*resG->*/G->aNode(out);
marci@75
   343
	  ++out;
marci@75
   344
	  while( out.valid() && !(free()>0) ) { ++out; }
marci@75
   345
	  if (!out.valid()) {
marci@75
   346
	    out_or_in=0;
marci@133
   347
	    G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
marci@75
   348
	    while( in.valid() && !(free()>0) ) { ++in; }
marci@75
   349
	  }
marci@75
   350
	} else {
marci@75
   351
	  ++in;
marci@75
   352
	  while( in.valid() && !(free()>0) ) { ++in; } 
marci@75
   353
	}
marci@75
   354
	return *this; 
marci@75
   355
      }
marci@75
   356
    };
marci@75
   357
marci@133
   358
    class EachEdgeIt : public EdgeIt {
marci@133
   359
      typename Graph::EachNodeIt v;
marci@133
   360
    public:
marci@133
   361
      EachEdgeIt() { }
marci@133
   362
      //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
marci@133
   363
      EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) { 
marci@133
   364
	G=&_G;
marci@133
   365
	flow=&_flow;
marci@133
   366
	capacity=&_capacity;
marci@133
   367
	out_or_in=1;
marci@133
   368
	G->getFirst(v);
marci@133
   369
	if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
marci@133
   370
	while (out.valid() && !(free()>0) ) { ++out; }
marci@133
   371
	while (v.valid() && !out.valid()) { 
marci@133
   372
	  ++v; 
marci@133
   373
	  if (v.valid()) G->getFirst(out, v); 
marci@133
   374
	  while (out.valid() && !(free()>0) ) { ++out; }
marci@133
   375
	}
marci@133
   376
	if (!out.valid()) {
marci@133
   377
	  out_or_in=0;
marci@133
   378
	  G->getFirst(v);
marci@133
   379
	  if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
marci@133
   380
	  while (in.valid() && !(free()>0) ) { ++in; }
marci@133
   381
	  while (v.valid() && !in.valid()) { 
marci@133
   382
	    ++v; 
marci@133
   383
	    if (v.valid()) G->getFirst(in, v); 
marci@133
   384
	    while (in.valid() && !(free()>0) ) { ++in; }
marci@133
   385
	  }
marci@133
   386
	}
marci@133
   387
      }
marci@133
   388
      EachEdgeIt& operator++() { 
marci@133
   389
	if (out_or_in) {
marci@133
   390
	  ++out;
marci@133
   391
	  while (out.valid() && !(free()>0) ) { ++out; }
marci@133
   392
	  while (v.valid() && !out.valid()) { 
marci@133
   393
	    ++v; 
marci@133
   394
	    if (v.valid()) G->getFirst(out, v); 
marci@133
   395
	    while (out.valid() && !(free()>0) ) { ++out; }
marci@133
   396
	  }
marci@133
   397
	  if (!out.valid()) {
marci@133
   398
	    out_or_in=0;
marci@133
   399
	    G->getFirst(v);
marci@133
   400
	    if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
marci@133
   401
	    while (in.valid() && !(free()>0) ) { ++in; }
marci@133
   402
	    while (v.valid() && !in.valid()) { 
marci@133
   403
	      ++v; 
marci@133
   404
	      if (v.valid()) G->getFirst(in, v); 
marci@133
   405
	      while (in.valid() && !(free()>0) ) { ++in; }
marci@133
   406
	    }  
marci@133
   407
	  }
marci@133
   408
	} else {
marci@133
   409
	  ++in;
marci@133
   410
	  while (in.valid() && !(free()>0) ) { ++in; }
marci@133
   411
	  while (v.valid() && !in.valid()) { 
marci@133
   412
	    ++v; 
marci@133
   413
	    if (v.valid()) G->getFirst(in, v); 
marci@133
   414
	    while (in.valid() && !(free()>0) ) { ++in; }
marci@133
   415
	  }
marci@133
   416
	}
marci@133
   417
	return *this;
marci@133
   418
      }
marci@133
   419
    };
marci@133
   420
marci@75
   421
    void getFirst(OutEdgeIt& e, NodeIt v) const { 
marci@75
   422
      e=OutEdgeIt(G, v, flow, capacity); 
marci@75
   423
    }
marci@133
   424
    void getFirst(EachEdgeIt& e) const { 
marci@133
   425
      e=EachEdgeIt(G, flow, capacity); 
marci@133
   426
    }
marci@75
   427
    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
marci@75
   428
    
marci@75
   429
    template< typename It >
marci@75
   430
    It first() const { 
marci@75
   431
      It e;
marci@75
   432
      getFirst(e);
marci@75
   433
      return e; 
marci@75
   434
    }
marci@75
   435
marci@75
   436
    template< typename It >
marci@75
   437
    It first(NodeIt v) const { 
marci@75
   438
      It e;
marci@75
   439
      getFirst(e, v);
marci@75
   440
      return e; 
marci@75
   441
    }
marci@75
   442
marci@75
   443
    NodeIt tail(EdgeIt e) const { 
marci@75
   444
      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
marci@75
   445
    NodeIt head(EdgeIt e) const { 
marci@75
   446
      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
marci@75
   447
marci@75
   448
    NodeIt aNode(OutEdgeIt e) const { 
marci@75
   449
      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
marci@75
   450
    NodeIt bNode(OutEdgeIt e) const { 
marci@75
   451
      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
marci@75
   452
marci@75
   453
    int id(NodeIt v) const { return G.id(v); }
marci@75
   454
marci@75
   455
    template <typename S>
marci@75
   456
    class NodeMap {
marci@75
   457
      typename Graph::NodeMap<S> node_map; 
marci@75
   458
    public:
marci@75
   459
      NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
marci@75
   460
      NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
marci@69
   461
      void set(NodeIt nit, S a) { node_map.set(nit, a); }
marci@69
   462
      S get(NodeIt nit) const { return node_map.get(nit); }
marci@43
   463
    };
marci@43
   464
marci@43
   465
  };
marci@43
   466
marci@75
   467
marci@75
   468
  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
marci@59
   469
  class MaxFlow {
klao@127
   470
  public:
marci@43
   471
    typedef typename Graph::NodeIt NodeIt;
marci@43
   472
    typedef typename Graph::EdgeIt EdgeIt;
marci@43
   473
    typedef typename Graph::EachEdgeIt EachEdgeIt;
marci@43
   474
    typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@43
   475
    typedef typename Graph::InEdgeIt InEdgeIt;
klao@127
   476
klao@127
   477
  private:
marci@43
   478
    const Graph& G;
marci@64
   479
    NodeIt s;
marci@64
   480
    NodeIt t;
marci@59
   481
    FlowMap& flow;
marci@59
   482
    const CapacityMap& capacity;
marci@75
   483
    typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;
marci@59
   484
    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
marci@59
   485
    typedef typename AugGraph::EdgeIt AugEdgeIt;
marci@75
   486
marci@75
   487
    //AugGraph res_graph;    
marci@75
   488
    //typedef typename AugGraph::NodeMap<bool> ReachedMap;
marci@75
   489
    //typename AugGraph::NodeMap<AugEdgeIt> pred; 
marci@133
   490
    //typename AugGraph::NodeMap<Number> free;
marci@59
   491
  public:
marci@75
   492
    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : 
marci@75
   493
      G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //,  
marci@75
   494
      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) 
marci@75
   495
      { }
marci@133
   496
    bool augmentOnShortestPath() {
marci@59
   497
      AugGraph res_graph(G, flow, capacity);
marci@59
   498
      bool _augment=false;
marci@59
   499
      
marci@59
   500
      typedef typename AugGraph::NodeMap<bool> ReachedMap;
marci@75
   501
      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
marci@59
   502
      res_bfs.pushAndSetReached(s);
marci@59
   503
	
marci@59
   504
      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 
marci@75
   505
      //filled up with invalid iterators
marci@75
   506
      //pred.set(s, AugEdgeIt());
marci@59
   507
      
marci@133
   508
      typename AugGraph::NodeMap<Number> free(res_graph);
marci@59
   509
	
marci@59
   510
      //searching for augmenting path
marci@59
   511
      while ( !res_bfs.finished() ) { 
marci@59
   512
	AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
marci@59
   513
	if (e.valid() && res_bfs.isBNodeNewlyReached()) {
marci@59
   514
	  NodeIt v=res_graph.tail(e);
marci@59
   515
	  NodeIt w=res_graph.head(e);
marci@59
   516
	  pred.set(w, e);
marci@59
   517
	  if (pred.get(v).valid()) {
marci@59
   518
	    free.set(w, std::min(free.get(v), e.free()));
marci@59
   519
	  } else {
marci@59
   520
	    free.set(w, e.free()); 
marci@59
   521
	  }
marci@59
   522
	  if (res_graph.head(e)==t) { _augment=true; break; }
marci@59
   523
	}
marci@59
   524
	
marci@59
   525
	++res_bfs;
marci@59
   526
      } //end of searching augmenting path
marci@43
   527
marci@59
   528
      if (_augment) {
marci@59
   529
	NodeIt n=t;
marci@75
   530
	Number augment_value=free.get(t);
marci@59
   531
	while (pred.get(n).valid()) { 
marci@59
   532
	  AugEdgeIt e=pred.get(n);
marci@59
   533
	  e.augment(augment_value); 
marci@59
   534
	  n=res_graph.tail(e);
marci@59
   535
	}
marci@59
   536
      }
marci@59
   537
marci@59
   538
      return _augment;
marci@59
   539
    }
marci@133
   540
    template<typename MutableGraph> bool augmentOnBlockingFlow() {
marci@133
   541
      bool _augment=false;
marci@133
   542
marci@133
   543
      AugGraph res_graph(G, flow, capacity);
marci@133
   544
marci@133
   545
      typedef typename AugGraph::NodeMap<bool> ReachedMap;
marci@133
   546
      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
marci@133
   547
marci@100
   548
      bfs.pushAndSetReached(s);
marci@133
   549
      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
marci@100
   550
      while ( !bfs.finished() ) { 
marci@133
   551
	AugOutEdgeIt e=AugOutEdgeIt(bfs);
marci@100
   552
	if (e.valid() && bfs.isBNodeNewlyReached()) {
marci@133
   553
	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
marci@100
   554
	}
marci@100
   555
	
marci@100
   556
	++bfs;
marci@133
   557
      } //computing distances from s in the residual graph
marci@100
   558
marci@100
   559
      MutableGraph F;
marci@133
   560
      typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
marci@133
   561
      for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); n.valid(); ++n) {
marci@133
   562
	res_graph_to_F.set(n, F.addNode());
marci@100
   563
      }
marci@133
   564
      
marci@133
   565
      typename MutableGraph::NodeIt sF=res_graph_to_F.get(s);
marci@133
   566
      typename MutableGraph::NodeIt tF=res_graph_to_F.get(t);
marci@133
   567
marci@133
   568
      typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);
marci@133
   569
      typename MutableGraph::EdgeMap<Number> free_on_edge(F);
marci@133
   570
marci@133
   571
      //Making F to the graph containing the edges of the residual graph 
marci@133
   572
      //which are in some shortest paths
marci@133
   573
      for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); e.valid(); ++e) {
marci@133
   574
	if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
marci@133
   575
	  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@133
   576
	  original_edge.update();
marci@133
   577
	  original_edge.set(f, e);
marci@133
   578
	  free_on_edge.update();
marci@133
   579
	  free_on_edge.set(f, e.free());
marci@133
   580
	} 
marci@133
   581
      }
marci@133
   582
marci@133
   583
      bool __augment=true;
marci@133
   584
marci@133
   585
      while (__augment) {
marci@133
   586
	__augment=false;
marci@133
   587
	//computing blocking flow with dfs
marci@133
   588
	typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
marci@133
   589
	DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
marci@133
   590
	typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators
marci@133
   591
	typename MutableGraph::NodeMap<Number> free(F);
marci@133
   592
marci@133
   593
	dfs.pushAndSetReached(sF);      
marci@133
   594
	while (!dfs.finished()) {
marci@133
   595
	  ++dfs;
marci@133
   596
	  if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
marci@133
   597
	    //std::cout << "OutEdgeIt: " << dfs; 
marci@133
   598
	    //std::cout << " aNode: " << F.aNode(dfs); 
marci@133
   599
	    //std::cout << " bNode: " << F.bNode(dfs) << " ";
marci@133
   600
	  
marci@133
   601
	    typename MutableGraph::NodeIt v=F.aNode(dfs);
marci@133
   602
	    typename MutableGraph::NodeIt w=F.bNode(dfs);
marci@133
   603
	    pred.set(w, dfs);
marci@133
   604
	    if (pred.get(v).valid()) {
marci@133
   605
	      free.set(w, std::min(free.get(v), free_on_edge.get(dfs)));
marci@133
   606
	    } else {
marci@133
   607
	      free.set(w, free_on_edge.get(dfs)/*original_edge.get(dfs).free()*/); 
marci@133
   608
	    }
marci@133
   609
	    if (w==tF) { 
marci@133
   610
	      //std::cout << "AUGMENTATION"<<std::endl;
marci@133
   611
	      __augment=true; 
marci@133
   612
	      _augment=true;
marci@133
   613
	      break; 
marci@133
   614
	    }
marci@133
   615
	  } else { 
marci@133
   616
	    //std::cout << "OutEdgeIt: " << "invalid"; 
marci@133
   617
	    //std::cout << " aNode: " << dfs.aNode(); 
marci@133
   618
	    //std::cout << " bNode: " << "invalid" << " ";
marci@133
   619
	  }
marci@133
   620
	  if (dfs.isBNodeNewlyReached()) { 
marci@133
   621
	    //std::cout << "bNodeIsNewlyReached ";
marci@133
   622
	  } else { 
marci@133
   623
	    //std::cout << "bNodeIsNotNewlyReached ";
marci@133
   624
	    if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
marci@133
   625
	      //std::cout << "DELETE ";
marci@133
   626
	      F.erase(typename MutableGraph::OutEdgeIt(dfs));
marci@133
   627
	    }
marci@133
   628
	  } 
marci@133
   629
	  //if (dfs.isANodeExamined()) { 
marci@133
   630
	    //std::cout << "aNodeIsExamined ";
marci@133
   631
	    //} else { 
marci@133
   632
	    //std::cout << "aNodeIsNotExamined ";
marci@133
   633
	    //} 
marci@133
   634
	  //std::cout<<std::endl;
marci@100
   635
	}
marci@133
   636
marci@133
   637
	if (__augment) {
marci@133
   638
	  typename MutableGraph::NodeIt n=tF;
marci@133
   639
	  Number augment_value=free.get(tF);
marci@133
   640
	  while (pred.get(n).valid()) { 
marci@133
   641
	    typename MutableGraph::EdgeIt e=pred.get(n);
marci@133
   642
	    original_edge.get(e).augment(augment_value); 
marci@133
   643
	    n=F.tail(e);
marci@133
   644
	    F.erase(e);
marci@133
   645
	  }
marci@133
   646
	}
marci@133
   647
marci@100
   648
      }
marci@133
   649
            
marci@133
   650
      return _augment;
marci@100
   651
    }
marci@43
   652
    void run() {
marci@100
   653
      //int num_of_augmentations=0;
marci@133
   654
      while (augmentOnShortestPath()) { 
marci@133
   655
	//while (augmentOnBlockingFlow<MutableGraph>()) { 
marci@133
   656
	//std::cout << ++num_of_augmentations << " ";
marci@133
   657
	//std::cout<<std::endl;
marci@133
   658
      } 
marci@133
   659
    }
marci@133
   660
    template<typename MutableGraph> void run() {
marci@133
   661
      //int num_of_augmentations=0;
marci@133
   662
      //while (augmentOnShortestPath()) { 
marci@133
   663
	while (augmentOnBlockingFlow<MutableGraph>()) { 
marci@100
   664
	//std::cout << ++num_of_augmentations << " ";
marci@100
   665
	//std::cout<<std::endl;
marci@100
   666
      } 
marci@43
   667
    }
marci@75
   668
    Number flowValue() { 
marci@75
   669
      Number a=0;
marci@69
   670
      for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
marci@69
   671
	a+=flow.get(i);
marci@69
   672
      }
marci@69
   673
      return a;
marci@69
   674
    }
marci@43
   675
  };
marci@43
   676
marci@75
   677
marci@75
   678
/*
marci@75
   679
  template <typename Graph>
marci@75
   680
  class IteratorBoolNodeMap {
marci@75
   681
    typedef typename Graph::NodeIt NodeIt;
marci@75
   682
    typedef typename Graph::EachNodeIt EachNodeIt;
marci@75
   683
    class BoolItem {
marci@75
   684
    public:
marci@75
   685
      bool value;
marci@75
   686
      NodeIt prev;
marci@75
   687
      NodeIt next;
marci@75
   688
      BoolItem() : value(false), prev(), next() {}
marci@75
   689
    };
marci@75
   690
    NodeIt first_true;
marci@75
   691
    //NodeIt last_true;
marci@75
   692
    NodeIt first_false;
marci@75
   693
    //NodeIt last_false;
marci@75
   694
    const Graph& G; 
marci@75
   695
    typename Graph::NodeMap<BoolItem> container;
marci@75
   696
  public:
marci@75
   697
    typedef bool ValueType;
marci@75
   698
    typedef NodeIt KeyType;
marci@75
   699
    IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) { 
marci@75
   700
      //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
marci@75
   701
      //BoolItem b=container.get(e);
marci@75
   702
      //b.me=e;
marci@75
   703
      //container.set(b);
marci@75
   704
      //} 
marci@75
   705
      G.getFirst(first_false);
marci@75
   706
      NodeIt e_prev;
marci@75
   707
      for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
marci@75
   708
	container[e].prev=e_prev;
marci@75
   709
	if (e_prev.valid()) container[e_prev].next=e;
marci@75
   710
	e_prev=e;
marci@75
   711
      }
marci@75
   712
    }
marci@75
   713
    //NodeMap(const Graph& _G, T a) : 
marci@75
   714
    //  G(_G), container(G.node_id, a) { }
marci@75
   715
    //FIXME
marci@75
   716
    void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
marci@75
   717
    T get(NodeIt nit) const { return container[G.id(nit)]; }
alpar@107
   718
    //void update() { container.resize(G.node_id); }
alpar@107
   719
    //void update(T a) { container.resize(G.node_id, a); }
marci@75
   720
  };
marci@75
   721
*/
marci@75
   722
marci@75
   723
  
marci@75
   724
  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
marci@75
   725
  class MaxFlow2 {
klao@127
   726
  public:
marci@75
   727
    typedef typename Graph::NodeIt NodeIt;
marci@75
   728
    typedef typename Graph::EdgeIt EdgeIt;
marci@75
   729
    typedef typename Graph::EachEdgeIt EachEdgeIt;
marci@75
   730
    typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@75
   731
    typedef typename Graph::InEdgeIt InEdgeIt;
klao@127
   732
  private:
marci@75
   733
    const Graph& G;
marci@75
   734
    std::list<NodeIt>& S;
marci@75
   735
    std::list<NodeIt>& T;
marci@75
   736
    FlowMap& flow;
marci@75
   737
    const CapacityMap& capacity;
marci@75
   738
    typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;
marci@75
   739
    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
marci@75
   740
    typedef typename AugGraph::EdgeIt AugEdgeIt;
marci@75
   741
    typename Graph::NodeMap<bool> SMap;
marci@75
   742
    typename Graph::NodeMap<bool> TMap;
marci@75
   743
  public:
marci@75
   744
    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
   745
      for(typename std::list<NodeIt>::const_iterator i=S.begin(); 
marci@75
   746
	  i!=S.end(); ++i) { 
marci@75
   747
	SMap.set(*i, true); 
marci@75
   748
      }
marci@75
   749
      for (typename std::list<NodeIt>::const_iterator i=T.begin(); 
marci@75
   750
	   i!=T.end(); ++i) { 
marci@75
   751
	TMap.set(*i, true); 
marci@75
   752
      }
marci@75
   753
    }
marci@75
   754
    bool augment() {
marci@75
   755
      AugGraph res_graph(G, flow, capacity);
marci@75
   756
      bool _augment=false;
marci@75
   757
      NodeIt reached_t_node;
marci@75
   758
      
marci@75
   759
      typedef typename AugGraph::NodeMap<bool> ReachedMap;
marci@75
   760
      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
marci@75
   761
      for(typename std::list<NodeIt>::const_iterator i=S.begin(); 
marci@75
   762
	  i!=S.end(); ++i) {
marci@75
   763
	res_bfs.pushAndSetReached(*i);
marci@75
   764
      }
marci@75
   765
      //res_bfs.pushAndSetReached(s);
marci@75
   766
	
marci@75
   767
      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 
marci@75
   768
      //filled up with invalid iterators
marci@75
   769
      
marci@133
   770
      typename AugGraph::NodeMap<Number> free(res_graph);
marci@75
   771
	
marci@75
   772
      //searching for augmenting path
marci@75
   773
      while ( !res_bfs.finished() ) { 
marci@75
   774
	AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
marci@75
   775
	if (e.valid() && res_bfs.isBNodeNewlyReached()) {
marci@75
   776
	  NodeIt v=res_graph.tail(e);
marci@75
   777
	  NodeIt w=res_graph.head(e);
marci@75
   778
	  pred.set(w, e);
marci@75
   779
	  if (pred.get(v).valid()) {
marci@75
   780
	    free.set(w, std::min(free.get(v), e.free()));
marci@75
   781
	  } else {
marci@75
   782
	    free.set(w, e.free()); 
marci@75
   783
	  }
marci@75
   784
	  if (TMap.get(res_graph.head(e))) { 
marci@75
   785
	    _augment=true; 
marci@75
   786
	    reached_t_node=res_graph.head(e);
marci@75
   787
	    break; 
marci@75
   788
	  }
marci@75
   789
	}
marci@75
   790
	
marci@75
   791
	++res_bfs;
marci@75
   792
      } //end of searching augmenting path
marci@75
   793
marci@75
   794
      if (_augment) {
marci@75
   795
	NodeIt n=reached_t_node;
marci@75
   796
	Number augment_value=free.get(reached_t_node);
marci@75
   797
	while (pred.get(n).valid()) { 
marci@75
   798
	  AugEdgeIt e=pred.get(n);
marci@75
   799
	  e.augment(augment_value); 
marci@75
   800
	  n=res_graph.tail(e);
marci@75
   801
	}
marci@75
   802
      }
marci@75
   803
marci@75
   804
      return _augment;
marci@75
   805
    }
marci@75
   806
    void run() {
marci@75
   807
      while (augment()) { } 
marci@75
   808
    }
marci@75
   809
    Number flowValue() { 
marci@75
   810
      Number a=0;
marci@75
   811
      for(typename std::list<NodeIt>::const_iterator i=S.begin(); 
marci@75
   812
	  i!=S.end(); ++i) { 
marci@75
   813
	for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
marci@75
   814
	  a+=flow.get(e);
marci@75
   815
	}
marci@75
   816
	for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
marci@75
   817
	  a-=flow.get(e);
marci@75
   818
	}
marci@75
   819
      }
marci@75
   820
      return a;
marci@75
   821
    }
marci@75
   822
  };
marci@75
   823
marci@75
   824
marci@75
   825
alpar@107
   826
} // namespace hugo
marci@43
   827
marci@59
   828
#endif //EDMONDS_KARP_HH