COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.hh @ 99:f26897fb91fd

Last change on this file since 99:f26897fb91fd was 94:90a35f45fa6a, checked in by Alpar Juttner, 17 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 {
245public:
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;
251   
252private:
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) { }
260
261    class EdgeIt;
262    class OutEdgeIt;
263    friend class EdgeIt;
264    friend class OutEdgeIt;
265
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    };
296
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    };
332
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); }
337   
338    template< typename It >
339    It first() const {
340      It e;
341      getFirst(e);
342      return e;
343    }
344
345    template< typename It >
346    It first(NodeIt v) const {
347      It e;
348      getFirst(e, v);
349      return e;
350    }
351
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)); }
356
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)); }
361
362    int id(NodeIt v) const { return G.id(v); }
363
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    };
373
374  };
375
376
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;
392
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;
405     
406      typedef typename AugGraph::NodeMap<bool> ReachedMap;
407      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
408      res_bfs.pushAndSetReached(s);
409       
410      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
411      //filled up with invalid iterators
412      //pred.set(s, AugEdgeIt());
413     
414      typename AugGraph::NodeMap<int> free(res_graph);
415       
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        }
430       
431        ++res_bfs;
432      } //end of searching augmenting path
433
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      }
443
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  };
457
458
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*/
503
504 
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;
537     
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);
545       
546      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
547      //filled up with invalid iterators
548     
549      typename AugGraph::NodeMap<int> free(res_graph);
550       
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        }
569       
570        ++res_bfs;
571      } //end of searching augmenting path
572
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      }
582
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  };
602
603
604
605} // namespace marci
606
607#endif //EDMONDS_KARP_HH
Note: See TracBrowser for help on using the repository browser.