COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.hh @ 163:c5fbd2c1d75f

Last change on this file since 163:c5fbd2c1d75f was 155:8c6292ec54c6, checked in by marci, 20 years ago

graph wrappers

File size: 16.9 KB
RevLine 
[59]1#ifndef EDMONDS_KARP_HH
2#define EDMONDS_KARP_HH
[43]3
4#include <algorithm>
[75]5#include <list>
6#include <iterator>
[43]7
8#include <bfs_iterator.hh>
[133]9//#include <time_measure.h>
[43]10
[107]11namespace hugo {
[43]12
[75]13  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
[43]14  class ResGraph {
[127]15  public:
[43]16    typedef typename Graph::NodeIt NodeIt;
17    typedef typename Graph::EachNodeIt EachNodeIt;
[127]18  private:
[43]19    typedef typename Graph::SymEdgeIt OldSymEdgeIt;
20    const Graph& G;
[59]21    FlowMap& flow;
22    const CapacityMap& capacity;
[43]23  public:
[59]24    ResGraph(const Graph& _G, FlowMap& _flow,
25             const CapacityMap& _capacity) :
[43]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 {
[75]34      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
[43]35    protected:
[75]36      const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
[43]37      OldSymEdgeIt sym;
38    public:
39      EdgeIt() { }
40      //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
[75]41      Number free() const {
[43]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(); }
[75]49      void augment(Number a) const {
[43]50        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
51          resG->flow.set(sym, resG->flow.get(sym)+a);
[75]52          //resG->flow[sym]+=a;
[43]53        } else {
54          resG->flow.set(sym, resG->flow.get(sym)-a);
[75]55          //resG->flow[sym]-=a;
[43]56        }
57      }
58    };
59
60    class OutEdgeIt : public EdgeIt {
[75]61      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
[43]62    public:
63      OutEdgeIt() { }
64      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
65    private:
[75]66      OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
[43]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
[64]79    void getFirst(OutEdgeIt& e, NodeIt v) const {
[43]80      e=OutEdgeIt(*this, v);
81    }
82    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
83   
84    template< typename It >
85    It first() const {
[75]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 {
[127]123  public:
[75]124    typedef typename Graph::NodeIt NodeIt;
125    typedef typename Graph::EachNodeIt EachNodeIt;
[127]126  private:
[75]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;
[148]151      bool out_or_in; //true, iff out
[75]152    public:
[148]153      EdgeIt() : out_or_in(true) { }
[75]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 {
[43]213      It e;
214      getFirst(e);
215      return e;
216    }
217
218    template< typename It >
[64]219    It first(NodeIt v) const {
[43]220      It e;
221      getFirst(e, v);
222      return e;
223    }
224
[75]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)); }
[43]229
[75]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)); }
[43]234
[64]235    int id(NodeIt v) const { return G.id(v); }
[43]236
[69]237    template <typename S>
[43]238    class NodeMap {
[69]239      typename Graph::NodeMap<S> node_map;
[43]240    public:
[75]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
[43]248
[75]249  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
[59]250  class MaxFlow {
[127]251  public:
[43]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;
[127]257
258  private:
[148]259    const Graph* G;
[64]260    NodeIt s;
261    NodeIt t;
[148]262    FlowMap* flow;
263    const CapacityMap* capacity;
264    typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
[59]265    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
266    typedef typename AugGraph::EdgeIt AugEdgeIt;
[75]267
268    //AugGraph res_graph;   
269    //typedef typename AugGraph::NodeMap<bool> ReachedMap;
270    //typename AugGraph::NodeMap<AugEdgeIt> pred;
[133]271    //typename AugGraph::NodeMap<Number> free;
[59]272  public:
[75]273    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
[148]274      G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //, 
[75]275      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
276      { }
[133]277    bool augmentOnShortestPath() {
[148]278      AugGraph res_graph(*G, *flow, *capacity);
[59]279      bool _augment=false;
280     
281      typedef typename AugGraph::NodeMap<bool> ReachedMap;
[148]282      BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
[59]283      res_bfs.pushAndSetReached(s);
284       
285      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
[75]286      //filled up with invalid iterators
287      //pred.set(s, AugEdgeIt());
[59]288     
[133]289      typename AugGraph::NodeMap<Number> free(res_graph);
[59]290       
291      //searching for augmenting path
292      while ( !res_bfs.finished() ) {
[141]293        AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
[148]294        if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
[59]295          NodeIt v=res_graph.tail(e);
296          NodeIt w=res_graph.head(e);
297          pred.set(w, e);
[148]298          if (res_graph.valid(pred.get(v))) {
[59]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
[43]308
[59]309      if (_augment) {
310        NodeIt n=t;
[75]311        Number augment_value=free.get(t);
[148]312        while (res_graph.valid(pred.get(n))) {
[59]313          AugEdgeIt e=pred.get(n);
314          e.augment(augment_value);
315          n=res_graph.tail(e);
316        }
317      }
318
319      return _augment;
320    }
[141]321
[133]322    template<typename MutableGraph> bool augmentOnBlockingFlow() {
323      bool _augment=false;
324
[148]325      AugGraph res_graph(*G, *flow, *capacity);
[133]326
327      typedef typename AugGraph::NodeMap<bool> ReachedMap;
328      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
329
[100]330      bfs.pushAndSetReached(s);
[133]331      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
[100]332      while ( !bfs.finished() ) {
[141]333        AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
[148]334        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
[133]335          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
[100]336        }
337       
338        ++bfs;
[133]339      } //computing distances from s in the residual graph
[100]340
341      MutableGraph F;
[133]342      typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
[148]343      for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
[133]344        res_graph_to_F.set(n, F.addNode());
[100]345      }
[133]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);
[148]351      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
[133]352
353      //Making F to the graph containing the edges of the residual graph
354      //which are in some shortest paths
[148]355      for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
[133]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);
[148]360          residual_capacity.update();
361          residual_capacity.set(f, e.free());
[133]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;
[148]378          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
[133]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);
[148]386            if (F.valid(pred.get(v))) {
387              free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
[133]388            } else {
[148]389              free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/);
[133]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;
[100]417        }
[133]418
419        if (__augment) {
420          typename MutableGraph::NodeIt n=tF;
421          Number augment_value=free.get(tF);
[148]422          while (F.valid(pred.get(n))) {
[133]423            typename MutableGraph::EdgeIt e=pred.get(n);
424            original_edge.get(e).augment(augment_value);
425            n=F.tail(e);
[148]426            if (residual_capacity.get(e)==augment_value)
[135]427              F.erase(e);
428            else
[148]429              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
[133]430          }
431        }
[135]432     
[100]433      }
[133]434           
435      return _augment;
[100]436    }
[43]437    void run() {
[100]438      //int num_of_augmentations=0;
[133]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>()) {
[100]449        //std::cout << ++num_of_augmentations << " ";
450        //std::cout<<std::endl;
451      }
[43]452    }
[75]453    Number flowValue() {
454      Number a=0;
[148]455      OutEdgeIt e;
456      for(G->getFirst(e, s); G->valid(e); G->next(e)) {
457        a+=flow->get(e);
[69]458      }
459      return a;
460    }
[43]461  };
462
[75]463 
[155]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;
[75]498     
[155]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);
[75]506       
[155]507//       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
508//       //filled up with invalid iterators
[75]509     
[155]510//       typename AugGraph::NodeMap<Number> free(res_graph);
[75]511       
[155]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//      }
[75]530       
[155]531//      ++res_bfs;
532//       } //end of searching augmenting path
[75]533
[155]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//       }
[75]543
[155]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//   };
[75]563
564
565
[107]566} // namespace hugo
[43]567
[59]568#endif //EDMONDS_KARP_HH
Note: See TracBrowser for help on using the repository browser.