COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.hh @ 80:629b9ca9184b

Last change on this file since 80:629b9ca9184b was 75:87623302a68f, checked in by marci, 20 years ago

.

File size: 17.1 KB
Line 
1#ifndef EDMONDS_KARP_HH
2#define EDMONDS_KARP_HH
3
4#include <algorithm>
5#include <list>
6#include <iterator>
7
8#include <bfs_iterator.hh>
9
10namespace marci {
11
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) { }
24
25    class EdgeIt;
26    class OutEdgeIt;
27    friend class EdgeIt;
28    friend class OutEdgeIt;
29
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    };
56
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    };
75
76    void getFirst(OutEdgeIt& e, NodeIt v) const {
77      e=OutEdgeIt(*this, v);
78    }
79    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
80   
81    template< typename It >
82    It first() const {
83      It e;     
84      getFirst(e);
85      return e;
86    }
87
88    template< typename It >
89    It first(NodeIt v) const {
90      It e;
91      getFirst(e, v);
92      return e;
93    }
94
95    NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
96    NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
97
98    NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
99    NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
100
101    int id(NodeIt v) const { return G.id(v); }
102
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    };
114
115  };
116
117
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;
125   
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) { }
133
134    class EdgeIt;
135    class OutEdgeIt;
136    friend class EdgeIt;
137    friend class OutEdgeIt;
138
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    };
166
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    };
200
201    void getFirst(OutEdgeIt& e, NodeIt v) const {
202      e=OutEdgeIt(*this, v);
203    }
204    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
205   
206    template< typename It >
207    It first() const {
208      It e;
209      getFirst(e);
210      return e;
211    }
212
213    template< typename It >
214    It first(NodeIt v) const {
215      It e;
216      getFirst(e, v);
217      return e;
218    }
219
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)); }
224
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)); }
229
230    int id(NodeIt v) const { return G.id(v); }
231
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  };
242
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;
250   
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) { }
258
259    class EdgeIt;
260    class OutEdgeIt;
261    friend class EdgeIt;
262    friend class OutEdgeIt;
263
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    };
294
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    };
330
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); }
335   
336    template< typename It >
337    It first() const {
338      It e;
339      getFirst(e);
340      return e;
341    }
342
343    template< typename It >
344    It first(NodeIt v) const {
345      It e;
346      getFirst(e, v);
347      return e;
348    }
349
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)); }
354
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)); }
359
360    int id(NodeIt v) const { return G.id(v); }
361
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    };
371
372  };
373
374
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;
390
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;
403     
404      typedef typename AugGraph::NodeMap<bool> ReachedMap;
405      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
406      res_bfs.pushAndSetReached(s);
407       
408      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
409      //filled up with invalid iterators
410      //pred.set(s, AugEdgeIt());
411     
412      typename AugGraph::NodeMap<int> free(res_graph);
413       
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        }
428       
429        ++res_bfs;
430      } //end of searching augmenting path
431
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      }
441
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  };
455
456
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*/
501
502 
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;
535     
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);
543       
544      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
545      //filled up with invalid iterators
546     
547      typename AugGraph::NodeMap<int> free(res_graph);
548       
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        }
567       
568        ++res_bfs;
569      } //end of searching augmenting path
570
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      }
580
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  };
600
601
602
603} // namespace marci
604
605#endif //EDMONDS_KARP_HH
Note: See TracBrowser for help on using the repository browser.