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

     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 public:

   246     typedef typename Graph::NodeIt NodeIt;

   247     typedef typename Graph::EachNodeIt EachNodeIt;

   248     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;

   249     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   250     typedef typename Graph::InEdgeIt OldInEdgeIt;

   252 private:

   253     const Graph& G;

   254     FlowMap& flow;

   255     const CapacityMap& capacity;

   256   public:

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

   258 	     const CapacityMap& _capacity) :

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

   261     class EdgeIt;

   262     class OutEdgeIt;

   263     friend class EdgeIt;

   264     friend class OutEdgeIt;

   266     class EdgeIt {

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

   268     protected:

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

   270       const Graph* G;

   271       FlowMap* flow;

   272       const CapacityMap* capacity;

   273       //OldSymEdgeIt sym;

   274       OldOutEdgeIt out;

   275       OldInEdgeIt in;

   276       bool out_or_in; //1, iff out

   277     public:

   278       EdgeIt() : out_or_in(1) { }

   279       Number free() const {

   280 	if (out_or_in) {

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

   282 	} else {

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

   284 	}

   285       }

   286       bool valid() const {

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

   288       void augment(Number a) const {

   289 	if (out_or_in) {

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

   291 	} else {

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

   293 	}

   294       }

   295     };

   297     class OutEdgeIt : public EdgeIt {

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

   299     public:

   300       OutEdgeIt() { }

   301     private:

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

   303       	G=&_G;

   304 	flow=&_flow;

   305 	capacity=&_capacity;

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

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

   308 	if (!out.valid()) {

   309 	  out_or_in=0;

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

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

   312 	}

   313       }

   314     public:

   315       OutEdgeIt& operator++() {

   316 	if (out_or_in) {

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

   318 	  ++out;

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

   320 	  if (!out.valid()) {

   321 	    out_or_in=0;

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

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

   324 	  }

   325 	} else {

   326 	  ++in;

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

   328 	}

   329 	return *this;

   330       }

   331     };

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

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

   335     }

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

   338     template< typename It >

   339     It first() const {

   340       It e;

   341       getFirst(e);

   342       return e;

   343     }

   345     template< typename It >

   346     It first(NodeIt v) const {

   347       It e;

   348       getFirst(e, v);

   349       return e;

   350     }

   352     NodeIt tail(EdgeIt e) const {

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

   354     NodeIt head(EdgeIt e) const {

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

   357     NodeIt aNode(OutEdgeIt e) const {

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

   359     NodeIt bNode(OutEdgeIt e) const {

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

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

   364     template <typename S>

   365     class NodeMap {

   366       typename Graph::NodeMap<S> node_map;

   367     public:

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

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

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

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

   372     };

   374   };

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

   378   class MaxFlow {

   379     typedef typename Graph::NodeIt NodeIt;

   380     typedef typename Graph::EdgeIt EdgeIt;

   381     typedef typename Graph::EachEdgeIt EachEdgeIt;

   382     typedef typename Graph::OutEdgeIt OutEdgeIt;

   383     typedef typename Graph::InEdgeIt InEdgeIt;

   384     const Graph& G;

   385     NodeIt s;

   386     NodeIt t;

   387     FlowMap& flow;

   388     const CapacityMap& capacity;

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

   390     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   391     typedef typename AugGraph::EdgeIt AugEdgeIt;

   393     //AugGraph res_graph;

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

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

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

   397   public:

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

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

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

   401       { }

   402     bool augment() {

   403       AugGraph res_graph(G, flow, capacity);

   404       bool _augment=false;

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

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

   408       res_bfs.pushAndSetReached(s);

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

   411       //filled up with invalid iterators

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

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

   416       //searching for augmenting path

   417       while ( !res_bfs.finished() ) {

   418 	AugOutEdgeIt e=AugOutEdgeIt(res_bfs);

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

   420 	  NodeIt v=res_graph.tail(e);

   421 	  NodeIt w=res_graph.head(e);

   422 	  pred.set(w, e);

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

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

   425 	  } else {

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

   427 	  }

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

   429 	}

   431 	++res_bfs;

   432       } //end of searching augmenting path

   434       if (_augment) {

   435 	NodeIt n=t;

   436 	Number augment_value=free.get(t);

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

   438 	  AugEdgeIt e=pred.get(n);

   439 	  e.augment(augment_value);

   440 	  n=res_graph.tail(e);

   441 	}

   442       }

   444       return _augment;

   445     }

   446     void run() {

   447       while (augment()) { }

   448     }

   449     Number flowValue() {

   450       Number a=0;

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

   452 	a+=flow.get(i);

   453       }

   454       return a;

   455     }

   456   };

   459 /*

   460   template <typename Graph>

   461   class IteratorBoolNodeMap {

   462     typedef typename Graph::NodeIt NodeIt;

   463     typedef typename Graph::EachNodeIt EachNodeIt;

   464     class BoolItem {

   465     public:

   466       bool value;

   467       NodeIt prev;

   468       NodeIt next;

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

   470     };

   471     NodeIt first_true;

   472     //NodeIt last_true;

   473     NodeIt first_false;

   474     //NodeIt last_false;

   475     const Graph& G;

   476     typename Graph::NodeMap<BoolItem> container;

   477   public:

   478     typedef bool ValueType;

   479     typedef NodeIt KeyType;

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

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

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

   483       //b.me=e;

   484       //container.set(b);

   485       //}

   486       G.getFirst(first_false);

   487       NodeIt e_prev;

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

   489 	container[e].prev=e_prev;

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

   491 	e_prev=e;

   492       }

   493     }

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

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

   496     //FIXME

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

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

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

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

   501   };

   502 */

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

   506   class MaxFlow2 {

   507     typedef typename Graph::NodeIt NodeIt;

   508     typedef typename Graph::EdgeIt EdgeIt;

   509     typedef typename Graph::EachEdgeIt EachEdgeIt;

   510     typedef typename Graph::OutEdgeIt OutEdgeIt;

   511     typedef typename Graph::InEdgeIt InEdgeIt;

   512     const Graph& G;

   513     std::list<NodeIt>& S;

   514     std::list<NodeIt>& T;

   515     FlowMap& flow;

   516     const CapacityMap& capacity;

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

   518     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   519     typedef typename AugGraph::EdgeIt AugEdgeIt;

   520     typename Graph::NodeMap<bool> SMap;

   521     typename Graph::NodeMap<bool> TMap;

   522   public:

   523     MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {

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

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

   526 	SMap.set(*i, true);

   527       }

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

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

   530 	TMap.set(*i, true);

   531       }

   532     }

   533     bool augment() {

   534       AugGraph res_graph(G, flow, capacity);

   535       bool _augment=false;

   536       NodeIt reached_t_node;

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

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

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

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

   542 	res_bfs.pushAndSetReached(*i);

   543       }

   544       //res_bfs.pushAndSetReached(s);

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

   547       //filled up with invalid iterators

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

   551       //searching for augmenting path

   552       while ( !res_bfs.finished() ) {

   553 	AugOutEdgeIt e=AugOutEdgeIt(res_bfs);

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

   555 	  NodeIt v=res_graph.tail(e);

   556 	  NodeIt w=res_graph.head(e);

   557 	  pred.set(w, e);

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

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

   560 	  } else {

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

   562 	  }

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

   564 	    _augment=true;

   565 	    reached_t_node=res_graph.head(e);

   566 	    break;

   567 	  }

   568 	}

   570 	++res_bfs;

   571       } //end of searching augmenting path

   573       if (_augment) {

   574 	NodeIt n=reached_t_node;

   575 	Number augment_value=free.get(reached_t_node);

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

   577 	  AugEdgeIt e=pred.get(n);

   578 	  e.augment(augment_value);

   579 	  n=res_graph.tail(e);

   580 	}

   581       }

   583       return _augment;

   584     }

   585     void run() {

   586       while (augment()) { }

   587     }

   588     Number flowValue() {

   589       Number a=0;

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

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

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

   593 	  a+=flow.get(e);

   594 	}

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

   596 	  a-=flow.get(e);

   597 	}

   598       }

   599       return a;

   600     }

   601   };

   605 } // namespace marci

   607 #endif //EDMONDS_KARP_HH

author	marci
	Wed, 18 Feb 2004 13:06:41 +0000
changeset 96	e2e18eb0fd10
parent 75	87623302a68f
child 100	f1de2ab64e1c
permissions	-rw-r--r--