lemon-0.x: src/work/edmonds_karp.hh@01d47457aff3

     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; //1, iff out

   152     public:

   153       EdgeIt() : out_or_in(1) { }

   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 ResGraph3 {

   250   public:

   251     typedef typename Graph::NodeIt NodeIt;

   252     typedef typename Graph::EachNodeIt EachNodeIt;

   254   private:

   255     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;

   256     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   257     typedef typename Graph::InEdgeIt OldInEdgeIt;

   258     const Graph& G;

   259     FlowMap& flow;

   260     const CapacityMap& capacity;

   261   public:

   262     ResGraph3(const Graph& _G, FlowMap& _flow,

   263 	     const CapacityMap& _capacity) :

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

   266     class EdgeIt;

   267     class OutEdgeIt;

   268     friend class EdgeIt;

   269     friend class OutEdgeIt;

   271     class EdgeIt {

   272       friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;

   273     protected:

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

   275       const Graph* G;

   276       FlowMap* flow;

   277       const CapacityMap* capacity;

   278       //OldSymEdgeIt sym;

   279       OldOutEdgeIt out;

   280       OldInEdgeIt in;

   281       bool out_or_in; //1, iff out

   282     public:

   283       EdgeIt() : out_or_in(1) { }

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

   285       Number free() const {

   286 	if (out_or_in) {

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

   288 	} else {

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

   290 	}

   291       }

   292       bool valid() const {

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

   294       void augment(Number a) const {

   295 	if (out_or_in) {

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

   297 	} else {

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

   299 	}

   300       }

   301       void print() {

   302 	if (out_or_in) {

   303 	  std::cout << "out ";

   304 	  if (out.valid())

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

   306 	  else

   307 	    std::cout << "invalid";

   308 	}

   309 	else {

   310 	  std::cout << "in ";

   311 	  if (in.valid())

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

   313 	  else

   314 	    std::cout << "invalid";

   315 	}

   316 	std::cout << std::endl;

   317       }

   318     };

   320     class OutEdgeIt : public EdgeIt {

   321       friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;

   322     public:

   323       OutEdgeIt() { }

   324     private:

   325       OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) {

   326       	G=&_G;

   327 	flow=&_flow;

   328 	capacity=&_capacity;

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

   330 	G->getFirst(out, v);

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

   332 	if (!out.valid()) {

   333 	  out_or_in=0;

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

   335 	  G->getFirst(in, v);

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

   337 	}

   338       }

   339     public:

   340       OutEdgeIt& operator++() {

   341 	if (out_or_in) {

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

   343 	  ++out;

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

   345 	  if (!out.valid()) {

   346 	    out_or_in=0;

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

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

   349 	  }

   350 	} else {

   351 	  ++in;

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

   353 	}

   354 	return *this;

   355       }

   356     };

   358     class EachEdgeIt : public EdgeIt {

   359       typename Graph::EachNodeIt v;

   360     public:

   361       EachEdgeIt() { }

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

   363       EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) {

   364 	G=&_G;

   365 	flow=&_flow;

   366 	capacity=&_capacity;

   367 	out_or_in=1;

   368 	G->getFirst(v);

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

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

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

   372 	  ++v;

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

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

   375 	}

   376 	if (!out.valid()) {

   377 	  out_or_in=0;

   378 	  G->getFirst(v);

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

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

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

   382 	    ++v;

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

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

   385 	  }

   386 	}

   387       }

   388       EachEdgeIt& operator++() {

   389 	if (out_or_in) {

   390 	  ++out;

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

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

   393 	    ++v;

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

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

   396 	  }

   397 	  if (!out.valid()) {

   398 	    out_or_in=0;

   399 	    G->getFirst(v);

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

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

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

   403 	      ++v;

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

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

   406 	    }

   407 	  }

   408 	} else {

   409 	  ++in;

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

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

   412 	    ++v;

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

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

   415 	  }

   416 	}

   417 	return *this;

   418       }

   419     };

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

   422       e=OutEdgeIt(G, v, flow, capacity);

   423     }

   424     void getFirst(EachEdgeIt& e) const {

   425       e=EachEdgeIt(G, flow, capacity);

   426     }

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

   429     template< typename It >

   430     It first() const {

   431       It e;

   432       getFirst(e);

   433       return e;

   434     }

   436     template< typename It >

   437     It first(NodeIt v) const {

   438       It e;

   439       getFirst(e, v);

   440       return e;

   441     }

   443     NodeIt tail(EdgeIt e) const {

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

   445     NodeIt head(EdgeIt e) const {

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

   448     NodeIt aNode(OutEdgeIt e) const {

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

   450     NodeIt bNode(OutEdgeIt e) const {

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

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

   455     template <typename T>

   456     class NodeMap {

   457       typename Graph::NodeMap<T> node_map;

   458     public:

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

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

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

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

   463     };

   465     template <typename T>

   466     class EdgeMap {

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

   468     public:

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

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

   471       void set(EdgeIt e, T a) {

   472 	if (e.out_or_in)

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

   474 	else

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

   476       }

   477       T get(EdgeIt e) {

   478 	if (e.out_or_in)

   479 	  return forward_map.get(e.out);

   480 	else

   481 	  return backward_map.get(e.in);

   482       }

   483     };

   485   };

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

   488   class MaxFlow {

   489   public:

   490     typedef typename Graph::NodeIt NodeIt;

   491     typedef typename Graph::EdgeIt EdgeIt;

   492     typedef typename Graph::EachEdgeIt EachEdgeIt;

   493     typedef typename Graph::OutEdgeIt OutEdgeIt;

   494     typedef typename Graph::InEdgeIt InEdgeIt;

   496   private:

   497     const Graph& G;

   498     NodeIt s;

   499     NodeIt t;

   500     FlowMap& flow;

   501     const CapacityMap& capacity;

   502     typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;

   503     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   504     typedef typename AugGraph::EdgeIt AugEdgeIt;

   506     //AugGraph res_graph;

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

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

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

   510   public:

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

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

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

   514       { }

   515     bool augmentOnShortestPath() {

   516       AugGraph res_graph(G, flow, capacity);

   517       bool _augment=false;

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

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

   521       res_bfs.pushAndSetReached(s);

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

   524       //filled up with invalid iterators

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

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

   529       //searching for augmenting path

   530       while ( !res_bfs.finished() ) {

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

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

   533 	  NodeIt v=res_graph.tail(e);

   534 	  NodeIt w=res_graph.head(e);

   535 	  pred.set(w, e);

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

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

   538 	  } else {

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

   540 	  }

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

   542 	}

   544 	++res_bfs;

   545       } //end of searching augmenting path

   547       if (_augment) {

   548 	NodeIt n=t;

   549 	Number augment_value=free.get(t);

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

   551 	  AugEdgeIt e=pred.get(n);

   552 	  e.augment(augment_value);

   553 	  n=res_graph.tail(e);

   554 	}

   555       }

   557       return _augment;

   558     }

   560     template<typename MutableGraph> bool augmentOnBlockingFlow() {

   561       bool _augment=false;

   563       AugGraph res_graph(G, flow, capacity);

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

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

   568       bfs.pushAndSetReached(s);

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

   570       while ( !bfs.finished() ) {

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

   572 	if (e.valid() && bfs.isBNodeNewlyReached()) {

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

   574 	}

   576 	++bfs;

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

   579       MutableGraph F;

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

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

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

   583       }

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

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

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

   589       typename MutableGraph::EdgeMap<Number> free_on_edge(F);

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

   592       //which are in some shortest paths

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

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

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

   596 	  original_edge.update();

   597 	  original_edge.set(f, e);

   598 	  free_on_edge.update();

   599 	  free_on_edge.set(f, e.free());

   600 	}

   601       }

   603       bool __augment=true;

   605       while (__augment) {

   606 	__augment=false;

   607 	//computing blocking flow with dfs

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

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

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

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

   613 	dfs.pushAndSetReached(sF);

   614 	while (!dfs.finished()) {

   615 	  ++dfs;

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

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

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

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

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

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

   623 	    pred.set(w, dfs);

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

   625 	      free.set(w, std::min(free.get(v), free_on_edge.get(dfs)));

   626 	    } else {

   627 	      free.set(w, free_on_edge.get(dfs)/*original_edge.get(dfs).free()*/);

   628 	    }

   629 	    if (w==tF) {

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

   631 	      __augment=true;

   632 	      _augment=true;

   633 	      break;

   634 	    }

   635 	  } else {

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

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

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

   639 	  }

   640 	  if (dfs.isBNodeNewlyReached()) {

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

   642 	  } else {

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

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

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

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

   647 	    }

   648 	  }

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

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

   651 	    //} else {

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

   653 	    //}

   654 	  //std::cout<<std::endl;

   655 	}

   657 	if (__augment) {

   658 	  typename MutableGraph::NodeIt n=tF;

   659 	  Number augment_value=free.get(tF);

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

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

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

   663 	    n=F.tail(e);

   664 	    if (free_on_edge.get(e)==augment_value)

   665 	      F.erase(e);

   666 	    else

   667 	      free_on_edge.set(e, free_on_edge.get(e)-augment_value);

   668 	  }

   669 	}

   671       }

   673       return _augment;

   674     }

   675     void run() {

   676       //int num_of_augmentations=0;

   677       while (augmentOnShortestPath()) {

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

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

   680 	//std::cout<<std::endl;

   681       }

   682     }

   683     template<typename MutableGraph> void run() {

   684       //int num_of_augmentations=0;

   685       //while (augmentOnShortestPath()) {

   686 	while (augmentOnBlockingFlow<MutableGraph>()) {

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

   688 	//std::cout<<std::endl;

   689       }

   690     }

   691     Number flowValue() {

   692       Number a=0;

   693       for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {

   694 	a+=flow.get(i);

   695       }

   696       return a;

   697     }

   698   };

   701 /*

   702   template <typename Graph>

   703   class IteratorBoolNodeMap {

   704     typedef typename Graph::NodeIt NodeIt;

   705     typedef typename Graph::EachNodeIt EachNodeIt;

   706     class BoolItem {

   707     public:

   708       bool value;

   709       NodeIt prev;

   710       NodeIt next;

   711       BoolItem() : value(false), prev(), next() {}

   712     };

   713     NodeIt first_true;

   714     //NodeIt last_true;

   715     NodeIt first_false;

   716     //NodeIt last_false;

   717     const Graph& G;

   718     typename Graph::NodeMap<BoolItem> container;

   719   public:

   720     typedef bool ValueType;

   721     typedef NodeIt KeyType;

   722     IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) {

   723       //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {

   724       //BoolItem b=container.get(e);

   725       //b.me=e;

   726       //container.set(b);

   727       //}

   728       G.getFirst(first_false);

   729       NodeIt e_prev;

   730       for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {

   731 	container[e].prev=e_prev;

   732 	if (e_prev.valid()) container[e_prev].next=e;

   733 	e_prev=e;

   734       }

   735     }

   736     //NodeMap(const Graph& _G, T a) :

   737     //  G(_G), container(G.node_id, a) { }

   738     //FIXME

   739     void set(NodeIt nit, T a) { container[G.id(nit)]=a; }

   740     T get(NodeIt nit) const { return container[G.id(nit)]; }

   741     //void update() { container.resize(G.node_id); }

   742     //void update(T a) { container.resize(G.node_id, a); }

   743   };

   744 */

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

   748   class MaxFlow2 {

   749   public:

   750     typedef typename Graph::NodeIt NodeIt;

   751     typedef typename Graph::EdgeIt EdgeIt;

   752     typedef typename Graph::EachEdgeIt EachEdgeIt;

   753     typedef typename Graph::OutEdgeIt OutEdgeIt;

   754     typedef typename Graph::InEdgeIt InEdgeIt;

   755   private:

   756     const Graph& G;

   757     std::list<NodeIt>& S;

   758     std::list<NodeIt>& T;

   759     FlowMap& flow;

   760     const CapacityMap& capacity;

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

   762     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   763     typedef typename AugGraph::EdgeIt AugEdgeIt;

   764     typename Graph::NodeMap<bool> SMap;

   765     typename Graph::NodeMap<bool> TMap;

   766   public:

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

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

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

   770 	SMap.set(*i, true);

   771       }

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

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

   774 	TMap.set(*i, true);

   775       }

   776     }

   777     bool augment() {

   778       AugGraph res_graph(G, flow, capacity);

   779       bool _augment=false;

   780       NodeIt reached_t_node;

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

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

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

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

   786 	res_bfs.pushAndSetReached(*i);

   787       }

   788       //res_bfs.pushAndSetReached(s);

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

   791       //filled up with invalid iterators

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

   795       //searching for augmenting path

   796       while ( !res_bfs.finished() ) {

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

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

   799 	  NodeIt v=res_graph.tail(e);

   800 	  NodeIt w=res_graph.head(e);

   801 	  pred.set(w, e);

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

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

   804 	  } else {

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

   806 	  }

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

   808 	    _augment=true;

   809 	    reached_t_node=res_graph.head(e);

   810 	    break;

   811 	  }

   812 	}

   814 	++res_bfs;

   815       } //end of searching augmenting path

   817       if (_augment) {

   818 	NodeIt n=reached_t_node;

   819 	Number augment_value=free.get(reached_t_node);

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

   821 	  AugEdgeIt e=pred.get(n);

   822 	  e.augment(augment_value);

   823 	  n=res_graph.tail(e);

   824 	}

   825       }

   827       return _augment;

   828     }

   829     void run() {

   830       while (augment()) { }

   831     }

   832     Number flowValue() {

   833       Number a=0;

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

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

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

   837 	  a+=flow.get(e);

   838 	}

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

   840 	  a-=flow.get(e);

   841 	}

   842       }

   843       return a;

   844     }

   845   };

   849 } // namespace hugo

   851 #endif //EDMONDS_KARP_HH

author	jacint
	Mon, 01 Mar 2004 17:24:34 +0000
changeset 142	01d47457aff3
parent 137	6364b07f8cd4
child 148	004fdf703abb
permissions	-rw-r--r--