COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.hh @ 157:ee17030e5f47

Last change on this file since 157:ee17030e5f47 was 155:8c6292ec54c6, checked in by marci, 17 years ago

graph wrappers

File size: 16.9 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//#include <time_measure.h>
10
11namespace hugo {
12
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) { }
27
28    class EdgeIt;
29    class OutEdgeIt;
30    friend class EdgeIt;
31    friend class OutEdgeIt;
32
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    };
59
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    };
78
79    void getFirst(OutEdgeIt& e, NodeIt v) const {
80      e=OutEdgeIt(*this, v);
81    }
82    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
83   
84    template< typename It >
85    It first() const {
86      It e;     
87      getFirst(e);
88      return e;
89    }
90
91    template< typename It >
92    It first(NodeIt v) const {
93      It e;
94      getFirst(e, v);
95      return e;
96    }
97
98    NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
99    NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
100
101    NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
102    NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
103
104    int id(NodeIt v) const { return G.id(v); }
105
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    };
117
118  };
119
120
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;
130   
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) { }
138
139    class EdgeIt;
140    class OutEdgeIt;
141    friend class EdgeIt;
142    friend class OutEdgeIt;
143
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; //true, iff out
152    public:
153      EdgeIt() : out_or_in(true) { }
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    };
171
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    };
205
206    void getFirst(OutEdgeIt& e, NodeIt v) const {
207      e=OutEdgeIt(*this, v);
208    }
209    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
210   
211    template< typename It >
212    It first() const {
213      It e;
214      getFirst(e);
215      return e;
216    }
217
218    template< typename It >
219    It first(NodeIt v) const {
220      It e;
221      getFirst(e, v);
222      return e;
223    }
224
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)); }
229
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)); }
234
235    int id(NodeIt v) const { return G.id(v); }
236
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  };
247
248
249  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
250  class MaxFlow {
251  public:
252    typedef typename Graph::NodeIt NodeIt;
253    typedef typename Graph::EdgeIt EdgeIt;
254    typedef typename Graph::EachEdgeIt EachEdgeIt;
255    typedef typename Graph::OutEdgeIt OutEdgeIt;
256    typedef typename Graph::InEdgeIt InEdgeIt;
257
258  private:
259    const Graph* G;
260    NodeIt s;
261    NodeIt t;
262    FlowMap* flow;
263    const CapacityMap* capacity;
264    typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
265    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
266    typedef typename AugGraph::EdgeIt AugEdgeIt;
267
268    //AugGraph res_graph;   
269    //typedef typename AugGraph::NodeMap<bool> ReachedMap;
270    //typename AugGraph::NodeMap<AugEdgeIt> pred;
271    //typename AugGraph::NodeMap<Number> free;
272  public:
273    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
274      G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //, 
275      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
276      { }
277    bool augmentOnShortestPath() {
278      AugGraph res_graph(*G, *flow, *capacity);
279      bool _augment=false;
280     
281      typedef typename AugGraph::NodeMap<bool> ReachedMap;
282      BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
283      res_bfs.pushAndSetReached(s);
284       
285      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
286      //filled up with invalid iterators
287      //pred.set(s, AugEdgeIt());
288     
289      typename AugGraph::NodeMap<Number> free(res_graph);
290       
291      //searching for augmenting path
292      while ( !res_bfs.finished() ) {
293        AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
294        if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
295          NodeIt v=res_graph.tail(e);
296          NodeIt w=res_graph.head(e);
297          pred.set(w, e);
298          if (res_graph.valid(pred.get(v))) {
299            free.set(w, std::min(free.get(v), e.free()));
300          } else {
301            free.set(w, e.free());
302          }
303          if (res_graph.head(e)==t) { _augment=true; break; }
304        }
305       
306        ++res_bfs;
307      } //end of searching augmenting path
308
309      if (_augment) {
310        NodeIt n=t;
311        Number augment_value=free.get(t);
312        while (res_graph.valid(pred.get(n))) {
313          AugEdgeIt e=pred.get(n);
314          e.augment(augment_value);
315          n=res_graph.tail(e);
316        }
317      }
318
319      return _augment;
320    }
321
322    template<typename MutableGraph> bool augmentOnBlockingFlow() {
323      bool _augment=false;
324
325      AugGraph res_graph(*G, *flow, *capacity);
326
327      typedef typename AugGraph::NodeMap<bool> ReachedMap;
328      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
329
330      bfs.pushAndSetReached(s);
331      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
332      while ( !bfs.finished() ) {
333        AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
334        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
335          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
336        }
337       
338        ++bfs;
339      } //computing distances from s in the residual graph
340
341      MutableGraph F;
342      typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
343      for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
344        res_graph_to_F.set(n, F.addNode());
345      }
346     
347      typename MutableGraph::NodeIt sF=res_graph_to_F.get(s);
348      typename MutableGraph::NodeIt tF=res_graph_to_F.get(t);
349
350      typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);
351      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
352
353      //Making F to the graph containing the edges of the residual graph
354      //which are in some shortest paths
355      for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
356        if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
357          typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
358          original_edge.update();
359          original_edge.set(f, e);
360          residual_capacity.update();
361          residual_capacity.set(f, e.free());
362        }
363      }
364
365      bool __augment=true;
366
367      while (__augment) {
368        __augment=false;
369        //computing blocking flow with dfs
370        typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
371        DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
372        typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators
373        typename MutableGraph::NodeMap<Number> free(F);
374
375        dfs.pushAndSetReached(sF);     
376        while (!dfs.finished()) {
377          ++dfs;
378          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
379            //std::cout << "OutEdgeIt: " << dfs;
380            //std::cout << " aNode: " << F.aNode(dfs);
381            //std::cout << " bNode: " << F.bNode(dfs) << " ";
382         
383            typename MutableGraph::NodeIt v=F.aNode(dfs);
384            typename MutableGraph::NodeIt w=F.bNode(dfs);
385            pred.set(w, dfs);
386            if (F.valid(pred.get(v))) {
387              free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
388            } else {
389              free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/);
390            }
391            if (w==tF) {
392              //std::cout << "AUGMENTATION"<<std::endl;
393              __augment=true;
394              _augment=true;
395              break;
396            }
397          } else {
398            //std::cout << "OutEdgeIt: " << "invalid";
399            //std::cout << " aNode: " << dfs.aNode();
400            //std::cout << " bNode: " << "invalid" << " ";
401          }
402          if (dfs.isBNodeNewlyReached()) {
403            //std::cout << "bNodeIsNewlyReached ";
404          } else {
405            //std::cout << "bNodeIsNotNewlyReached ";
406            if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
407              //std::cout << "DELETE ";
408              F.erase(typename MutableGraph::OutEdgeIt(dfs));
409            }
410          }
411          //if (dfs.isANodeExamined()) {
412            //std::cout << "aNodeIsExamined ";
413            //} else {
414            //std::cout << "aNodeIsNotExamined ";
415            //}
416          //std::cout<<std::endl;
417        }
418
419        if (__augment) {
420          typename MutableGraph::NodeIt n=tF;
421          Number augment_value=free.get(tF);
422          while (F.valid(pred.get(n))) {
423            typename MutableGraph::EdgeIt e=pred.get(n);
424            original_edge.get(e).augment(augment_value);
425            n=F.tail(e);
426            if (residual_capacity.get(e)==augment_value)
427              F.erase(e);
428            else
429              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
430          }
431        }
432     
433      }
434           
435      return _augment;
436    }
437    void run() {
438      //int num_of_augmentations=0;
439      while (augmentOnShortestPath()) {
440        //while (augmentOnBlockingFlow<MutableGraph>()) {
441        //std::cout << ++num_of_augmentations << " ";
442        //std::cout<<std::endl;
443      }
444    }
445    template<typename MutableGraph> void run() {
446      //int num_of_augmentations=0;
447      //while (augmentOnShortestPath()) {
448        while (augmentOnBlockingFlow<MutableGraph>()) {
449        //std::cout << ++num_of_augmentations << " ";
450        //std::cout<<std::endl;
451      }
452    }
453    Number flowValue() {
454      Number a=0;
455      OutEdgeIt e;
456      for(G->getFirst(e, s); G->valid(e); G->next(e)) {
457        a+=flow->get(e);
458      }
459      return a;
460    }
461  };
462
463 
464//   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
465//   class MaxFlow2 {
466//   public:
467//     typedef typename Graph::NodeIt NodeIt;
468//     typedef typename Graph::EdgeIt EdgeIt;
469//     typedef typename Graph::EachEdgeIt EachEdgeIt;
470//     typedef typename Graph::OutEdgeIt OutEdgeIt;
471//     typedef typename Graph::InEdgeIt InEdgeIt;
472//   private:
473//     const Graph& G;
474//     std::list<NodeIt>& S;
475//     std::list<NodeIt>& T;
476//     FlowMap& flow;
477//     const CapacityMap& capacity;
478//     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
479//     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
480//     typedef typename AugGraph::EdgeIt AugEdgeIt;
481//     typename Graph::NodeMap<bool> SMap;
482//     typename Graph::NodeMap<bool> TMap;
483//   public:
484//     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) {
485//       for(typename std::list<NodeIt>::const_iterator i=S.begin();
486//        i!=S.end(); ++i) {
487//      SMap.set(*i, true);
488//       }
489//       for (typename std::list<NodeIt>::const_iterator i=T.begin();
490//         i!=T.end(); ++i) {
491//      TMap.set(*i, true);
492//       }
493//     }
494//     bool augment() {
495//       AugGraph res_graph(G, flow, capacity);
496//       bool _augment=false;
497//       NodeIt reached_t_node;
498     
499//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
500//       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
501//       for(typename std::list<NodeIt>::const_iterator i=S.begin();
502//        i!=S.end(); ++i) {
503//      res_bfs.pushAndSetReached(*i);
504//       }
505//       //res_bfs.pushAndSetReached(s);
506       
507//       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
508//       //filled up with invalid iterators
509     
510//       typename AugGraph::NodeMap<Number> free(res_graph);
511       
512//       //searching for augmenting path
513//       while ( !res_bfs.finished() ) {
514//      AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
515//      if (e.valid() && res_bfs.isBNodeNewlyReached()) {
516//        NodeIt v=res_graph.tail(e);
517//        NodeIt w=res_graph.head(e);
518//        pred.set(w, e);
519//        if (pred.get(v).valid()) {
520//          free.set(w, std::min(free.get(v), e.free()));
521//        } else {
522//          free.set(w, e.free());
523//        }
524//        if (TMap.get(res_graph.head(e))) {
525//          _augment=true;
526//          reached_t_node=res_graph.head(e);
527//          break;
528//        }
529//      }
530       
531//      ++res_bfs;
532//       } //end of searching augmenting path
533
534//       if (_augment) {
535//      NodeIt n=reached_t_node;
536//      Number augment_value=free.get(reached_t_node);
537//      while (pred.get(n).valid()) {
538//        AugEdgeIt e=pred.get(n);
539//        e.augment(augment_value);
540//        n=res_graph.tail(e);
541//      }
542//       }
543
544//       return _augment;
545//     }
546//     void run() {
547//       while (augment()) { }
548//     }
549//     Number flowValue() {
550//       Number a=0;
551//       for(typename std::list<NodeIt>::const_iterator i=S.begin();
552//        i!=S.end(); ++i) {
553//      for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
554//        a+=flow.get(e);
555//      }
556//      for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
557//        a-=flow.get(e);
558//      }
559//       }
560//       return a;
561//     }
562//   };
563
564
565
566} // namespace hugo
567
568#endif //EDMONDS_KARP_HH
Note: See TracBrowser for help on using the repository browser.