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

     1 #ifndef EDMONDS_KARP_HH

     2 #define EDMONDS_KARP_HH

     4 #include <algorithm>

     5 #include <list>

     6 #include <iterator>

     8 #include <bfs_iterator.hh>

    10 namespace marci {

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

    13   class ResGraph {

    14     typedef typename Graph::NodeIt NodeIt;

    15     typedef typename Graph::EachNodeIt EachNodeIt;

    16     typedef typename Graph::SymEdgeIt OldSymEdgeIt;

    17     const Graph& G;

    18     FlowMap& flow;

    19     const CapacityMap& capacity;

    20   public:

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

    22 	     const CapacityMap& _capacity) :

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

    25     class EdgeIt;

    26     class OutEdgeIt;

    27     friend class EdgeIt;

    28     friend class OutEdgeIt;

    30     class EdgeIt {

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

    32     protected:

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

    34       OldSymEdgeIt sym;

    35     public:

    36       EdgeIt() { }

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

    38       Number free() const {

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

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

    41 	} else {

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

    43 	}

    44       }

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

    46       void augment(Number a) const {

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

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

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

    50 	} else {

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

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

    53 	}

    54       }

    55     };

    57     class OutEdgeIt : public EdgeIt {

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

    59     public:

    60       OutEdgeIt() { }

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

    62     private:

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

    64       	resG=&_resG;

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

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

    67       }

    68     public:

    69       OutEdgeIt& operator++() {

    70 	++sym;

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

    72 	return *this;

    73       }

    74     };

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

    77       e=OutEdgeIt(*this, v);

    78     }

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

    81     template< typename It >

    82     It first() const {

    83       It e;

    84       getFirst(e);

    85       return e;

    86     }

    88     template< typename It >

    89     It first(NodeIt v) const {

    90       It e;

    91       getFirst(e, v);

    92       return e;

    93     }

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

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

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

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

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

   103     template <typename S>

   104     class NodeMap {

   105       typename Graph::NodeMap<S> node_map;

   106     public:

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

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

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

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

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

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

   113     };

   115   };

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

   119   class ResGraph2 {

   120     typedef typename Graph::NodeIt NodeIt;

   121     typedef typename Graph::EachNodeIt EachNodeIt;

   122     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;

   123     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   124     typedef typename Graph::InEdgeIt OldInEdgeIt;

   126     const Graph& G;

   127     FlowMap& flow;

   128     const CapacityMap& capacity;

   129   public:

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

   131 	     const CapacityMap& _capacity) :

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

   134     class EdgeIt;

   135     class OutEdgeIt;

   136     friend class EdgeIt;

   137     friend class OutEdgeIt;

   139     class EdgeIt {

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

   141     protected:

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

   143       //OldSymEdgeIt sym;

   144       OldOutEdgeIt out;

   145       OldInEdgeIt in;

   146       bool out_or_in; //1, iff out

   147     public:

   148       EdgeIt() : out_or_in(1) { }

   149       Number free() const {

   150 	if (out_or_in) {

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

   152 	} else {

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

   154 	}

   155       }

   156       bool valid() const {

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

   158       void augment(Number a) const {

   159 	if (out_or_in) {

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

   161 	} else {

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

   163 	}

   164       }

   165     };

   167     class OutEdgeIt : public EdgeIt {

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

   169     public:

   170       OutEdgeIt() { }

   171     private:

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

   173       	resG=&_resG;

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

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

   176 	if (!out.valid()) {

   177 	  out_or_in=0;

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

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

   180 	}

   181       }

   182     public:

   183       OutEdgeIt& operator++() {

   184 	if (out_or_in) {

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

   186 	  ++out;

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

   188 	  if (!out.valid()) {

   189 	    out_or_in=0;

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

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

   192 	  }

   193 	} else {

   194 	  ++in;

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

   196 	}

   197 	return *this;

   198       }

   199     };

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

   202       e=OutEdgeIt(*this, v);

   203     }

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

   206     template< typename It >

   207     It first() const {

   208       It e;

   209       getFirst(e);

   210       return e;

   211     }

   213     template< typename It >

   214     It first(NodeIt v) const {

   215       It e;

   216       getFirst(e, v);

   217       return e;

   218     }

   220     NodeIt tail(EdgeIt e) const {

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

   222     NodeIt head(EdgeIt e) const {

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

   225     NodeIt aNode(OutEdgeIt e) const {

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

   227     NodeIt bNode(OutEdgeIt e) const {

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

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

   232     template <typename S>

   233     class NodeMap {

   234       typename Graph::NodeMap<S> node_map;

   235     public:

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

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

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

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

   240     };

   241   };

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

   244   class ResGraph3 {

   245     typedef typename Graph::NodeIt NodeIt;

   246     typedef typename Graph::EachNodeIt EachNodeIt;

   247     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;

   248     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   249     typedef typename Graph::InEdgeIt OldInEdgeIt;

   251     const Graph& G;

   252     FlowMap& flow;

   253     const CapacityMap& capacity;

   254   public:

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

   256 	     const CapacityMap& _capacity) :

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

   259     class EdgeIt;

   260     class OutEdgeIt;

   261     friend class EdgeIt;

   262     friend class OutEdgeIt;

   264     class EdgeIt {

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

   266     protected:

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

   268       const Graph* G;

   269       FlowMap* flow;

   270       const CapacityMap* capacity;

   271       //OldSymEdgeIt sym;

   272       OldOutEdgeIt out;

   273       OldInEdgeIt in;

   274       bool out_or_in; //1, iff out

   275     public:

   276       EdgeIt() : out_or_in(1) { }

   277       Number free() const {

   278 	if (out_or_in) {

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

   280 	} else {

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

   282 	}

   283       }

   284       bool valid() const {

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

   286       void augment(Number a) const {

   287 	if (out_or_in) {

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

   289 	} else {

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

   291 	}

   292       }

   293     };

   295     class OutEdgeIt : public EdgeIt {

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

   297     public:

   298       OutEdgeIt() { }

   299     private:

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

   301       	G=&_G;

   302 	flow=&_flow;

   303 	capacity=&_capacity;

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

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

   306 	if (!out.valid()) {

   307 	  out_or_in=0;

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

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

   310 	}

   311       }

   312     public:

   313       OutEdgeIt& operator++() {

   314 	if (out_or_in) {

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

   316 	  ++out;

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

   318 	  if (!out.valid()) {

   319 	    out_or_in=0;

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

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

   322 	  }

   323 	} else {

   324 	  ++in;

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

   326 	}

   327 	return *this;

   328       }

   329     };

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

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

   333     }

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

   336     template< typename It >

   337     It first() const {

   338       It e;

   339       getFirst(e);

   340       return e;

   341     }

   343     template< typename It >

   344     It first(NodeIt v) const {

   345       It e;

   346       getFirst(e, v);

   347       return e;

   348     }

   350     NodeIt tail(EdgeIt e) const {

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

   352     NodeIt head(EdgeIt e) const {

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

   355     NodeIt aNode(OutEdgeIt e) const {

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

   357     NodeIt bNode(OutEdgeIt e) const {

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

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

   362     template <typename S>

   363     class NodeMap {

   364       typename Graph::NodeMap<S> node_map;

   365     public:

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

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

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

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

   370     };

   372   };

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

   376   class MaxFlow {

   377     typedef typename Graph::NodeIt NodeIt;

   378     typedef typename Graph::EdgeIt EdgeIt;

   379     typedef typename Graph::EachEdgeIt EachEdgeIt;

   380     typedef typename Graph::OutEdgeIt OutEdgeIt;

   381     typedef typename Graph::InEdgeIt InEdgeIt;

   382     const Graph& G;

   383     NodeIt s;

   384     NodeIt t;

   385     FlowMap& flow;

   386     const CapacityMap& capacity;

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

   388     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   389     typedef typename AugGraph::EdgeIt AugEdgeIt;

   391     //AugGraph res_graph;

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

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

   394     //typename AugGraph::NodeMap<int> free;

   395   public:

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

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

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

   399       { }

   400     bool augment() {

   401       AugGraph res_graph(G, flow, capacity);

   402       bool _augment=false;

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

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

   406       res_bfs.pushAndSetReached(s);

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

   409       //filled up with invalid iterators

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

   412       typename AugGraph::NodeMap<int> free(res_graph);

   414       //searching for augmenting path

   415       while ( !res_bfs.finished() ) {

   416 	AugOutEdgeIt e=AugOutEdgeIt(res_bfs);

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

   418 	  NodeIt v=res_graph.tail(e);

   419 	  NodeIt w=res_graph.head(e);

   420 	  pred.set(w, e);

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

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

   423 	  } else {

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

   425 	  }

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

   427 	}

   429 	++res_bfs;

   430       } //end of searching augmenting path

   432       if (_augment) {

   433 	NodeIt n=t;

   434 	Number augment_value=free.get(t);

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

   436 	  AugEdgeIt e=pred.get(n);

   437 	  e.augment(augment_value);

   438 	  n=res_graph.tail(e);

   439 	}

   440       }

   442       return _augment;

   443     }

   444     void run() {

   445       while (augment()) { }

   446     }

   447     Number flowValue() {

   448       Number a=0;

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

   450 	a+=flow.get(i);

   451       }

   452       return a;

   453     }

   454   };

   457 /*

   458   template <typename Graph>

   459   class IteratorBoolNodeMap {

   460     typedef typename Graph::NodeIt NodeIt;

   461     typedef typename Graph::EachNodeIt EachNodeIt;

   462     class BoolItem {

   463     public:

   464       bool value;

   465       NodeIt prev;

   466       NodeIt next;

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

   468     };

   469     NodeIt first_true;

   470     //NodeIt last_true;

   471     NodeIt first_false;

   472     //NodeIt last_false;

   473     const Graph& G;

   474     typename Graph::NodeMap<BoolItem> container;

   475   public:

   476     typedef bool ValueType;

   477     typedef NodeIt KeyType;

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

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

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

   481       //b.me=e;

   482       //container.set(b);

   483       //}

   484       G.getFirst(first_false);

   485       NodeIt e_prev;

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

   487 	container[e].prev=e_prev;

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

   489 	e_prev=e;

   490       }

   491     }

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

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

   494     //FIXME

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

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

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

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

   499   };

   500 */

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

   504   class MaxFlow2 {

   505     typedef typename Graph::NodeIt NodeIt;

   506     typedef typename Graph::EdgeIt EdgeIt;

   507     typedef typename Graph::EachEdgeIt EachEdgeIt;

   508     typedef typename Graph::OutEdgeIt OutEdgeIt;

   509     typedef typename Graph::InEdgeIt InEdgeIt;

   510     const Graph& G;

   511     std::list<NodeIt>& S;

   512     std::list<NodeIt>& T;

   513     FlowMap& flow;

   514     const CapacityMap& capacity;

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

   516     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   517     typedef typename AugGraph::EdgeIt AugEdgeIt;

   518     typename Graph::NodeMap<bool> SMap;

   519     typename Graph::NodeMap<bool> TMap;

   520   public:

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

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

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

   524 	SMap.set(*i, true);

   525       }

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

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

   528 	TMap.set(*i, true);

   529       }

   530     }

   531     bool augment() {

   532       AugGraph res_graph(G, flow, capacity);

   533       bool _augment=false;

   534       NodeIt reached_t_node;

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

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

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

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

   540 	res_bfs.pushAndSetReached(*i);

   541       }

   542       //res_bfs.pushAndSetReached(s);

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

   545       //filled up with invalid iterators

   547       typename AugGraph::NodeMap<int> free(res_graph);

   549       //searching for augmenting path

   550       while ( !res_bfs.finished() ) {

   551 	AugOutEdgeIt e=AugOutEdgeIt(res_bfs);

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

   553 	  NodeIt v=res_graph.tail(e);

   554 	  NodeIt w=res_graph.head(e);

   555 	  pred.set(w, e);

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

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

   558 	  } else {

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

   560 	  }

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

   562 	    _augment=true;

   563 	    reached_t_node=res_graph.head(e);

   564 	    break;

   565 	  }

   566 	}

   568 	++res_bfs;

   569       } //end of searching augmenting path

   571       if (_augment) {

   572 	NodeIt n=reached_t_node;

   573 	Number augment_value=free.get(reached_t_node);

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

   575 	  AugEdgeIt e=pred.get(n);

   576 	  e.augment(augment_value);

   577 	  n=res_graph.tail(e);

   578 	}

   579       }

   581       return _augment;

   582     }

   583     void run() {

   584       while (augment()) { }

   585     }

   586     Number flowValue() {

   587       Number a=0;

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

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

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

   591 	  a+=flow.get(e);

   592 	}

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

   594 	  a-=flow.get(e);

   595 	}

   596       }

   597       return a;

   598     }

   599   };

   603 } // namespace marci

   605 #endif //EDMONDS_KARP_HH

author	marci
	Mon, 16 Feb 2004 11:38:19 +0000
changeset 76	d9650659a6ee
parent 69	24c2c2989e0f
child 94	90a35f45fa6a
permissions	-rw-r--r--