lemon-0.x: src/work/edmonds_karp.hh@824c0438020c

     1 #ifndef EDMONDS_KARP_HH

     2 #define EDMONDS_KARP_HH

     4 #include <algorithm>

     5 #include <list>

     6 #include <iterator>

     8 #include <bfs_iterator.hh>

     9 //#include <time_measure.h>

    11 namespace hugo {

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

    14   class ResGraph {

    15   public:

    16     typedef typename Graph::NodeIt NodeIt;

    17     typedef typename Graph::EachNodeIt EachNodeIt;

    18   private:

    19     typedef typename Graph::SymEdgeIt OldSymEdgeIt;

    20     const Graph& G;

    21     FlowMap& flow;

    22     const CapacityMap& capacity;

    23   public:

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

    25 	     const CapacityMap& _capacity) :

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

    28     class EdgeIt;

    29     class OutEdgeIt;

    30     friend class EdgeIt;

    31     friend class OutEdgeIt;

    33     class EdgeIt {

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

    35     protected:

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

    37       OldSymEdgeIt sym;

    38     public:

    39       EdgeIt() { }

    40       //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }

    41       Number free() const {

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

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

    44 	} else {

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

    46 	}

    47       }

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

    49       void augment(Number a) const {

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

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

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

    53 	} else {

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

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

    56 	}

    57       }

    58     };

    60     class OutEdgeIt : public EdgeIt {

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

    62     public:

    63       OutEdgeIt() { }

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

    65     private:

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

    67       	resG=&_resG;

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

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

    70       }

    71     public:

    72       OutEdgeIt& operator++() {

    73 	++sym;

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

    75 	return *this;

    76       }

    77     };

    79     void getFirst(OutEdgeIt& e, NodeIt v) const {

    80       e=OutEdgeIt(*this, v);

    81     }

    82     void getFirst(EachNodeIt& v) const { G.getFirst(v); }

    84     template< typename It >

    85     It first() const {

    86       It e;

    87       getFirst(e);

    88       return e;

    89     }

    91     template< typename It >

    92     It first(NodeIt v) const {

    93       It e;

    94       getFirst(e, v);

    95       return e;

    96     }

    98     NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }

    99     NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }

   101     NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }

   102     NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }

   104     int id(NodeIt v) const { return G.id(v); }

   106     template <typename S>

   107     class NodeMap {

   108       typename Graph::NodeMap<S> node_map;

   109     public:

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

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

   112       void set(NodeIt nit, S a) { node_map.set(nit, a); }

   113       S get(NodeIt nit) const { return node_map.get(nit); }

   114       S& operator[](NodeIt nit) { return node_map[nit]; }

   115       const S& operator[](NodeIt nit) const { return node_map[nit]; }

   116     };

   118   };

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

   122   class ResGraph2 {

   123   public:

   124     typedef typename Graph::NodeIt NodeIt;

   125     typedef typename Graph::EachNodeIt EachNodeIt;

   126   private:

   127     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;

   128     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   129     typedef typename Graph::InEdgeIt OldInEdgeIt;

   131     const Graph& G;

   132     FlowMap& flow;

   133     const CapacityMap& capacity;

   134   public:

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

   136 	     const CapacityMap& _capacity) :

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

   139     class EdgeIt;

   140     class OutEdgeIt;

   141     friend class EdgeIt;

   142     friend class OutEdgeIt;

   144     class EdgeIt {

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

   146     protected:

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

   148       //OldSymEdgeIt sym;

   149       OldOutEdgeIt out;

   150       OldInEdgeIt in;

   151       bool out_or_in; //true, iff out

   152     public:

   153       EdgeIt() : out_or_in(true) { }

   154       Number free() const {

   155 	if (out_or_in) {

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

   157 	} else {

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

   159 	}

   160       }

   161       bool valid() const {

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

   163       void augment(Number a) const {

   164 	if (out_or_in) {

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

   166 	} else {

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

   168 	}

   169       }

   170     };

   172     class OutEdgeIt : public EdgeIt {

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

   174     public:

   175       OutEdgeIt() { }

   176     private:

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

   178       	resG=&_resG;

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

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

   181 	if (!out.valid()) {

   182 	  out_or_in=0;

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

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

   185 	}

   186       }

   187     public:

   188       OutEdgeIt& operator++() {

   189 	if (out_or_in) {

   190 	  NodeIt v=resG->G.aNode(out);

   191 	  ++out;

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

   193 	  if (!out.valid()) {

   194 	    out_or_in=0;

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

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

   197 	  }

   198 	} else {

   199 	  ++in;

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

   201 	}

   202 	return *this;

   203       }

   204     };

   206     void getFirst(OutEdgeIt& e, NodeIt v) const {

   207       e=OutEdgeIt(*this, v);

   208     }

   209     void getFirst(EachNodeIt& v) const { G.getFirst(v); }

   211     template< typename It >

   212     It first() const {

   213       It e;

   214       getFirst(e);

   215       return e;

   216     }

   218     template< typename It >

   219     It first(NodeIt v) const {

   220       It e;

   221       getFirst(e, v);

   222       return e;

   223     }

   225     NodeIt tail(EdgeIt e) const {

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

   227     NodeIt head(EdgeIt e) const {

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

   230     NodeIt aNode(OutEdgeIt e) const {

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

   232     NodeIt bNode(OutEdgeIt e) const {

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

   235     int id(NodeIt v) const { return G.id(v); }

   237     template <typename S>

   238     class NodeMap {

   239       typename Graph::NodeMap<S> node_map;

   240     public:

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

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

   243       void set(NodeIt nit, S a) { node_map.set(nit, a); }

   244       S get(NodeIt nit) const { return node_map.get(nit); }

   245     };

   246   };

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

   249   class ResGraphWrapper {

   250   public:

   251     typedef typename Graph::NodeIt NodeIt;

   252     typedef typename Graph::EachNodeIt EachNodeIt;

   253   private:

   254     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   255     typedef typename Graph::InEdgeIt OldInEdgeIt;

   256     const Graph* G;

   257     FlowMap* flow;

   258     const CapacityMap* capacity;

   259   public:

   260     ResGraphWrapper(const Graph& _G, FlowMap& _flow,

   261 	     const CapacityMap& _capacity) :

   262       G(&_G), flow(&_flow), capacity(&_capacity) { }

   263 //     ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :

   264 //       G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }

   265     class EdgeIt;

   266     class OutEdgeIt;

   267     friend class EdgeIt;

   268     friend class OutEdgeIt;

   270     class EdgeIt {

   271       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

   272     protected:

   273       //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;

   274       const Graph* G;

   275       FlowMap* flow;

   276       const CapacityMap* capacity;

   277       //OldSymEdgeIt sym;

   278       OldOutEdgeIt out;

   279       OldInEdgeIt in;

   280       bool out_or_in; //true, iff out

   281     public:

   282       EdgeIt() : out_or_in(true) { }

   283       EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :

   284 	G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }

   285       //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) { }

   286       Number free() const {

   287 	if (out_or_in) {

   288 	  return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));

   289 	} else {

   290 	  return (/*resG->*/flow->get(in));

   291 	}

   292       }

   293       bool valid() const {

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

   295       void augment(Number a) const {

   296 	if (out_or_in) {

   297 	  /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);

   298 	} else {

   299 	  /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);

   300 	}

   301       }

   302       void print() {

   303 	if (out_or_in) {

   304 	  std::cout << "out ";

   305 	  if (out.valid())

   306 	    std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));

   307 	  else

   308 	    std::cout << "invalid";

   309 	}

   310 	else {

   311 	  std::cout << "in ";

   312 	  if (in.valid())

   313 	    std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));

   314 	  else

   315 	    std::cout << "invalid";

   316 	}

   317 	std::cout << std::endl;

   318       }

   319     };

   321     Number free(OldOutEdgeIt out) const {

   322       return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));

   323     }

   324     Number free(OldInEdgeIt in) const {

   325       return (/*resG->*/flow->get(in));

   326     }

   328     class OutEdgeIt : public EdgeIt {

   329       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

   330     public:

   331       OutEdgeIt() { }

   332     private:

   333       OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {

   334 	//out=/*resG->*/G->template first<OldOutEdgeIt>(v);

   335 	G->getFirst(out, v);

   336 	while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }

   337 	if (!out.valid()) {

   338 	  out_or_in=0;

   339 	  //in=/*resG->*/G->template first<OldInEdgeIt>(v);

   340 	  G->getFirst(in, v);

   341 	  while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }

   342 	}

   343       }

   344     public:

   345       OutEdgeIt& operator++() {

   346 	if (out_or_in) {

   347 	  NodeIt v=/*resG->*/G->aNode(out);

   348 	  ++out;

   349 	  while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }

   350 	  if (!out.valid()) {

   351 	    out_or_in=0;

   352 	    G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);

   353 	    while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }

   354 	  }

   355 	} else {

   356 	  ++in;

   357 	  while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }

   358 	}

   359 	return *this;

   360       }

   361     };

   363     class EachEdgeIt : public EdgeIt {

   364       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

   365       typename Graph::EachNodeIt v;

   366     public:

   367       EachEdgeIt() { }

   368       //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }

   369       EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {

   370 	out_or_in=true;

   371 	G->getFirst(v);

   372 	if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();

   373 	while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }

   374 	while (v.valid() && !out.valid()) {

   375 	  ++v;

   376 	  if (v.valid()) G->getFirst(out, v);

   377 	  while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }

   378 	}

   379 	if (!out.valid()) {

   380 	  out_or_in=0;

   381 	  G->getFirst(v);

   382 	  if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();

   383 	  while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }

   384 	  while (v.valid() && !in.valid()) {

   385 	    ++v;

   386 	    if (v.valid()) G->getFirst(in, v);

   387 	    while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }

   388 	  }

   389 	}

   390       }

   391       EachEdgeIt& operator++() {

   392 	if (out_or_in) {

   393 	  ++out;

   394 	  while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }

   395 	  while (v.valid() && !out.valid()) {

   396 	    ++v;

   397 	    if (v.valid()) G->getFirst(out, v);

   398 	    while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }

   399 	  }

   400 	  if (!out.valid()) {

   401 	    out_or_in=0;

   402 	    G->getFirst(v);

   403 	    if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();

   404 	    while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }

   405 	    while (v.valid() && !in.valid()) {

   406 	      ++v;

   407 	      if (v.valid()) G->getFirst(in, v);

   408 	      while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }

   409 	    }

   410 	  }

   411 	} else {

   412 	  ++in;

   413 	  while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }

   414 	  while (v.valid() && !in.valid()) {

   415 	    ++v;

   416 	    if (v.valid()) G->getFirst(in, v);

   417 	    while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }

   418 	  }

   419 	}

   420 	return *this;

   421       }

   422     };

   424     void getFirst(EachNodeIt& v) const { G->getFirst(v); }

   425     void getFirst(OutEdgeIt& e, NodeIt v) const {

   426       e=OutEdgeIt(*G, v, *flow, *capacity);

   427     }

   428     void getFirst(EachEdgeIt& e) const {

   429       e=EachEdgeIt(*G, *flow, *capacity);

   430     }

   432     EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }

   434     OutEdgeIt& next(OutEdgeIt& e) const {

   435       if (e.out_or_in) {

   436 	NodeIt v=G->aNode(e.out);

   437 	++(e.out);

   438 	while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }

   439 	if (!G->valid(e.out)) {

   440 	  e.out_or_in=0;

   441 	  G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);

   442 	  while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }

   443 	}

   444       } else {

   445 	++(e.in);

   446 	while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }

   447       }

   448       return e;

   449     }

   451     EachEdgeIt& next(EachEdgeIt& e) const {

   452       if (e.out_or_in) {

   453 	++(e.out);

   454 	while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }

   455 	  while (G->valid(e.v) && !G->valid(e.out)) {

   456 	    ++(e.v);

   457 	    if (G->valid(e.v)) G->getFirst(e.out, e.v);

   458 	    while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }

   459 	  }

   460 	  if (!G->valid(e.out)) {

   461 	    e.out_or_in=0;

   462 	    G->getFirst(e.v);

   463 	    if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();

   464 	    while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }

   465 	    while (G->valid(e.v) && !G->valid(e.in)) {

   466 	      ++(e.v);

   467 	      if (G->valid(e.v)) G->getFirst(e.in, e.v);

   468 	      while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }

   469 	    }

   470 	  }

   471 	} else {

   472 	  ++(e.in);

   473 	  while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }

   474 	  while (G->valid(e.v) && !G->valid(e.in)) {

   475 	    ++(e.v);

   476 	    if (G->valid(e.v)) G->getFirst(e.in, e.v);

   477 	    while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }

   478 	  }

   479 	}

   480 	return e;

   481       }

   484     template< typename It >

   485     It first() const {

   486       It e;

   487       getFirst(e);

   488       return e;

   489     }

   491     template< typename It >

   492     It first(NodeIt v) const {

   493       It e;

   494       getFirst(e, v);

   495       return e;

   496     }

   498     NodeIt tail(EdgeIt e) const {

   499       return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }

   500     NodeIt head(EdgeIt e) const {

   501       return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }

   503     NodeIt aNode(OutEdgeIt e) const {

   504       return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }

   505     NodeIt bNode(OutEdgeIt e) const {

   506       return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }

   508     int id(NodeIt v) const { return G->id(v); }

   510     bool valid(NodeIt n) const { return G->valid(n); }

   511     bool valid(EdgeIt e) const {

   512       return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }

   514     template <typename T>

   515     class NodeMap {

   516       typename Graph::NodeMap<T> node_map;

   517     public:

   518       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }

   519       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }

   520       void set(NodeIt nit, T a) { node_map.set(nit, a); }

   521       T get(NodeIt nit) const { return node_map.get(nit); }

   522     };

   524     template <typename T>

   525     class EdgeMap {

   526       typename Graph::EdgeMap<T> forward_map, backward_map;

   527     public:

   528       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { }

   529       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { }

   530       void set(EdgeIt e, T a) {

   531 	if (e.out_or_in)

   532 	  forward_map.set(e.out, a);

   533 	else

   534 	  backward_map.set(e.in, a);

   535       }

   536       T get(EdgeIt e) {

   537 	if (e.out_or_in)

   538 	  return forward_map.get(e.out);

   539 	else

   540 	  return backward_map.get(e.in);

   541       }

   542     };

   544   };

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

   547   class MaxFlow {

   548   public:

   549     typedef typename Graph::NodeIt NodeIt;

   550     typedef typename Graph::EdgeIt EdgeIt;

   551     typedef typename Graph::EachEdgeIt EachEdgeIt;

   552     typedef typename Graph::OutEdgeIt OutEdgeIt;

   553     typedef typename Graph::InEdgeIt InEdgeIt;

   555   private:

   556     const Graph* G;

   557     NodeIt s;

   558     NodeIt t;

   559     FlowMap* flow;

   560     const CapacityMap* capacity;

   561     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;

   562     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   563     typedef typename AugGraph::EdgeIt AugEdgeIt;

   565     //AugGraph res_graph;

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

   567     //typename AugGraph::NodeMap<AugEdgeIt> pred;

   568     //typename AugGraph::NodeMap<Number> free;

   569   public:

   570     MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :

   571       G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //,

   572       //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)

   573       { }

   574     bool augmentOnShortestPath() {

   575       AugGraph res_graph(*G, *flow, *capacity);

   576       bool _augment=false;

   578       typedef typename AugGraph::NodeMap<bool> ReachedMap;

   579       BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);

   580       res_bfs.pushAndSetReached(s);

   582       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);

   583       //filled up with invalid iterators

   584       //pred.set(s, AugEdgeIt());

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

   588       //searching for augmenting path

   589       while ( !res_bfs.finished() ) {

   590 	AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);

   591 	if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {

   592 	  NodeIt v=res_graph.tail(e);

   593 	  NodeIt w=res_graph.head(e);

   594 	  pred.set(w, e);

   595 	  if (res_graph.valid(pred.get(v))) {

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

   597 	  } else {

   598 	    free.set(w, e.free());

   599 	  }

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

   601 	}

   603 	++res_bfs;

   604       } //end of searching augmenting path

   606       if (_augment) {

   607 	NodeIt n=t;

   608 	Number augment_value=free.get(t);

   609 	while (res_graph.valid(pred.get(n))) {

   610 	  AugEdgeIt e=pred.get(n);

   611 	  e.augment(augment_value);

   612 	  n=res_graph.tail(e);

   613 	}

   614       }

   616       return _augment;

   617     }

   619     template<typename MutableGraph> bool augmentOnBlockingFlow() {

   620       bool _augment=false;

   622       AugGraph res_graph(*G, *flow, *capacity);

   624       typedef typename AugGraph::NodeMap<bool> ReachedMap;

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

   627       bfs.pushAndSetReached(s);

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

   629       while ( !bfs.finished() ) {

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

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

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

   633 	}

   635 	++bfs;

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

   638       MutableGraph F;

   639       typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);

   640       for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {

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

   642       }

   644       typename MutableGraph::NodeIt sF=res_graph_to_F.get(s);

   645       typename MutableGraph::NodeIt tF=res_graph_to_F.get(t);

   647       typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);

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

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

   651       //which are in some shortest paths

   652       for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); res_graph.valid(e); res_graph.next(e)) {

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

   654 	  typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));

   655 	  original_edge.update();

   656 	  original_edge.set(f, e);

   657 	  residual_capacity.update();

   658 	  residual_capacity.set(f, e.free());

   659 	}

   660       }

   662       bool __augment=true;

   664       while (__augment) {

   665 	__augment=false;

   666 	//computing blocking flow with dfs

   667 	typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;

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

   669 	typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators

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

   672 	dfs.pushAndSetReached(sF);

   673 	while (!dfs.finished()) {

   674 	  ++dfs;

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

   676 	    //std::cout << "OutEdgeIt: " << dfs;

   677 	    //std::cout << " aNode: " << F.aNode(dfs);

   678 	    //std::cout << " bNode: " << F.bNode(dfs) << " ";

   680 	    typename MutableGraph::NodeIt v=F.aNode(dfs);

   681 	    typename MutableGraph::NodeIt w=F.bNode(dfs);

   682 	    pred.set(w, dfs);

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

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

   685 	    } else {

   686 	      free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/);

   687 	    }

   688 	    if (w==tF) {

   689 	      //std::cout << "AUGMENTATION"<<std::endl;

   690 	      __augment=true;

   691 	      _augment=true;

   692 	      break;

   693 	    }

   694 	  } else {

   695 	    //std::cout << "OutEdgeIt: " << "invalid";

   696 	    //std::cout << " aNode: " << dfs.aNode();

   697 	    //std::cout << " bNode: " << "invalid" << " ";

   698 	  }

   699 	  if (dfs.isBNodeNewlyReached()) {

   700 	    //std::cout << "bNodeIsNewlyReached ";

   701 	  } else {

   702 	    //std::cout << "bNodeIsNotNewlyReached ";

   703 	    if (typename MutableGraph::OutEdgeIt(dfs).valid()) {

   704 	      //std::cout << "DELETE ";

   705 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));

   706 	    }

   707 	  }

   708 	  //if (dfs.isANodeExamined()) {

   709 	    //std::cout << "aNodeIsExamined ";

   710 	    //} else {

   711 	    //std::cout << "aNodeIsNotExamined ";

   712 	    //}

   713 	  //std::cout<<std::endl;

   714 	}

   716 	if (__augment) {

   717 	  typename MutableGraph::NodeIt n=tF;

   718 	  Number augment_value=free.get(tF);

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

   720 	    typename MutableGraph::EdgeIt e=pred.get(n);

   721 	    original_edge.get(e).augment(augment_value);

   722 	    n=F.tail(e);

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

   724 	      F.erase(e);

   725 	    else

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

   727 	  }

   728 	}

   730       }

   732       return _augment;

   733     }

   734     void run() {

   735       //int num_of_augmentations=0;

   736       while (augmentOnShortestPath()) {

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

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

   739 	//std::cout<<std::endl;

   740       }

   741     }

   742     template<typename MutableGraph> void run() {

   743       //int num_of_augmentations=0;

   744       //while (augmentOnShortestPath()) {

   745 	while (augmentOnBlockingFlow<MutableGraph>()) {

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

   747 	//std::cout<<std::endl;

   748       }

   749     }

   750     Number flowValue() {

   751       Number a=0;

   752       OutEdgeIt e;

   753       for(G->getFirst(e, s); G->valid(e); G->next(e)) {

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

   755       }

   756       return a;

   757     }

   758   };

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

   762   class MaxFlow2 {

   763   public:

   764     typedef typename Graph::NodeIt NodeIt;

   765     typedef typename Graph::EdgeIt EdgeIt;

   766     typedef typename Graph::EachEdgeIt EachEdgeIt;

   767     typedef typename Graph::OutEdgeIt OutEdgeIt;

   768     typedef typename Graph::InEdgeIt InEdgeIt;

   769   private:

   770     const Graph& G;

   771     std::list<NodeIt>& S;

   772     std::list<NodeIt>& T;

   773     FlowMap& flow;

   774     const CapacityMap& capacity;

   775     typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;

   776     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   777     typedef typename AugGraph::EdgeIt AugEdgeIt;

   778     typename Graph::NodeMap<bool> SMap;

   779     typename Graph::NodeMap<bool> TMap;

   780   public:

   781     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) {

   782       for(typename std::list<NodeIt>::const_iterator i=S.begin();

   783 	  i!=S.end(); ++i) {

   784 	SMap.set(*i, true);

   785       }

   786       for (typename std::list<NodeIt>::const_iterator i=T.begin();

   787 	   i!=T.end(); ++i) {

   788 	TMap.set(*i, true);

   789       }

   790     }

   791     bool augment() {

   792       AugGraph res_graph(G, flow, capacity);

   793       bool _augment=false;

   794       NodeIt reached_t_node;

   796       typedef typename AugGraph::NodeMap<bool> ReachedMap;

   797       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);

   798       for(typename std::list<NodeIt>::const_iterator i=S.begin();

   799 	  i!=S.end(); ++i) {

   800 	res_bfs.pushAndSetReached(*i);

   801       }

   802       //res_bfs.pushAndSetReached(s);

   804       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);

   805       //filled up with invalid iterators

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

   809       //searching for augmenting path

   810       while ( !res_bfs.finished() ) {

   811 	AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);

   812 	if (e.valid() && res_bfs.isBNodeNewlyReached()) {

   813 	  NodeIt v=res_graph.tail(e);

   814 	  NodeIt w=res_graph.head(e);

   815 	  pred.set(w, e);

   816 	  if (pred.get(v).valid()) {

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

   818 	  } else {

   819 	    free.set(w, e.free());

   820 	  }

   821 	  if (TMap.get(res_graph.head(e))) {

   822 	    _augment=true;

   823 	    reached_t_node=res_graph.head(e);

   824 	    break;

   825 	  }

   826 	}

   828 	++res_bfs;

   829       } //end of searching augmenting path

   831       if (_augment) {

   832 	NodeIt n=reached_t_node;

   833 	Number augment_value=free.get(reached_t_node);

   834 	while (pred.get(n).valid()) {

   835 	  AugEdgeIt e=pred.get(n);

   836 	  e.augment(augment_value);

   837 	  n=res_graph.tail(e);

   838 	}

   839       }

   841       return _augment;

   842     }

   843     void run() {

   844       while (augment()) { }

   845     }

   846     Number flowValue() {

   847       Number a=0;

   848       for(typename std::list<NodeIt>::const_iterator i=S.begin();

   849 	  i!=S.end(); ++i) {

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

   851 	  a+=flow.get(e);

   852 	}

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

   854 	  a-=flow.get(e);

   855 	}

   856       }

   857       return a;

   858     }

   859   };

   863 } // namespace hugo

   865 #endif //EDMONDS_KARP_HH

author	beckerjc
	Wed, 03 Mar 2004 19:14:27 +0000
changeset 149	824c0438020c
parent 141	a17d2a6462ee
child 155	8c6292ec54c6
permissions	-rw-r--r--