COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.hh @ 175:ebccffe4d47b

Last change on this file since 175:ebccffe4d47b was 168:27fbd1559fb7, checked in by marci, 20 years ago

graph wrapper improvements, blocking flow on fly

File size: 20.5 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), res_graph.free(e)));
300          } else {
301            free.set(w, res_graph.free(e));
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          res_graph.augment(e, augment_value);
315          //e.augment(augment_value);
316          n=res_graph.tail(e);
317        }
318      }
319
320      return _augment;
321    }
322
323    template<typename MutableGraph> bool augmentOnBlockingFlow() {
324      bool _augment=false;
325
326      AugGraph res_graph(*G, *flow, *capacity);
327
328      typedef typename AugGraph::NodeMap<bool> ReachedMap;
329      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
330
331      bfs.pushAndSetReached(s);
332      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
333      while ( !bfs.finished() ) {
334        AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
335        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
336          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
337        }
338       
339        ++bfs;
340      } //computing distances from s in the residual graph
341
342      MutableGraph F;
343      typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
344      for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
345        res_graph_to_F.set(n, F.addNode());
346      }
347     
348      typename MutableGraph::NodeIt sF=res_graph_to_F.get(s);
349      typename MutableGraph::NodeIt tF=res_graph_to_F.get(t);
350
351      typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);
352      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
353
354      //Making F to the graph containing the edges of the residual graph
355      //which are in some shortest paths
356      for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
357        if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
358          typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
359          original_edge.update();
360          original_edge.set(f, e);
361          residual_capacity.update();
362          residual_capacity.set(f, res_graph.free(e));
363        }
364      }
365
366      bool __augment=true;
367
368      while (__augment) {
369        __augment=false;
370        //computing blocking flow with dfs
371        typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
372        DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
373        typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators
374        typename MutableGraph::NodeMap<Number> free(F);
375
376        dfs.pushAndSetReached(sF);     
377        while (!dfs.finished()) {
378          ++dfs;
379          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
380            if (dfs.isBNodeNewlyReached()) {
381//            std::cout << "OutEdgeIt: " << dfs;
382//            std::cout << " aNode: " << F.aNode(dfs);
383//            std::cout << " bNode: " << F.bNode(dfs) << " ";
384         
385              typename MutableGraph::NodeIt v=F.aNode(dfs);
386              typename MutableGraph::NodeIt w=F.bNode(dfs);
387              pred.set(w, dfs);
388              if (F.valid(pred.get(v))) {
389                free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
390              } else {
391                free.set(w, residual_capacity.get(dfs));
392              }
393              if (w==tF) {
394                //std::cout << "AUGMENTATION"<<std::endl;
395                __augment=true;
396                _augment=true;
397                break;
398              }
399             
400            } else {
401              F.erase(typename MutableGraph::OutEdgeIt(dfs));
402            }
403          }
404        }
405
406        if (__augment) {
407          typename MutableGraph::NodeIt n=tF;
408          Number augment_value=free.get(tF);
409          while (F.valid(pred.get(n))) {
410            typename MutableGraph::EdgeIt e=pred.get(n);
411            res_graph.augment(original_edge.get(e), augment_value);
412            //original_edge.get(e).augment(augment_value);
413            n=F.tail(e);
414            if (residual_capacity.get(e)==augment_value)
415              F.erase(e);
416            else
417              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
418          }
419        }
420       
421      }
422           
423      return _augment;
424    }
425    bool augmentOnBlockingFlow2() {
426      bool _augment=false;
427
428      //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
429      typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
430      typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
431      typedef typename EAugGraph::EdgeIt EAugEdgeIt;
432
433      EAugGraph res_graph(*G, *flow, *capacity);
434
435      //std::cout << "meg jo1" << std::endl;
436
437      //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
438      BfsIterator4<
439        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
440        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
441        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
442     
443      //std::cout << "meg jo2" << std::endl;
444
445      bfs.pushAndSetReached(s);
446      //std::cout << "meg jo2.5" << std::endl;
447
448      //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
449      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
450        NodeMap<int>& dist=res_graph.dist;
451      //std::cout << "meg jo2.6" << std::endl;
452
453      while ( !bfs.finished() ) {
454        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
455//      EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
456        //if (res_graph.valid(e)) {
457        //    std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;
458        //}
459        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
460          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
461        }
462       
463        ++bfs; 
464      } //computing distances from s in the residual graph
465
466
467      //std::cout << "meg jo3" << std::endl;
468
469//       typedef typename EAugGraph::EachNodeIt EAugEachNodeIt;
470//       for(EAugEachNodeIt n=res_graph.template first<EAugEachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
471//      std::cout << "dist: " << dist.get(n) << std::endl;
472//       }
473
474      bool __augment=true;
475
476      while (__augment) {
477//      std::cout << "new iteration"<< std::endl;
478
479        __augment=false;
480        //computing blocking flow with dfs
481        typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
482        DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
483          dfs(res_graph);
484        typename EAugGraph::NodeMap<EAugEdgeIt> pred(res_graph); //invalid iterators
485        typename EAugGraph::NodeMap<Number> free(res_graph);
486
487        dfs.pushAndSetReached(s);
488        while (!dfs.finished()) {
489          ++dfs;
490          if (res_graph.valid(EAugOutEdgeIt(dfs))) {
491            if (dfs.isBNodeNewlyReached()) {
492//            std::cout << "OutEdgeIt: " << dfs;
493//            std::cout << " aNode: " << res_graph.aNode(dfs);
494//            std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
495//            std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
496         
497              typename EAugGraph::NodeIt v=res_graph.aNode(dfs);
498              typename EAugGraph::NodeIt w=res_graph.bNode(dfs);
499
500              pred.set(w, EAugOutEdgeIt(dfs));
501
502              //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;
503              if (res_graph.valid(pred.get(v))) {
504                free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs))));
505              } else {
506                free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs)));
507              }
508             
509              if (w==t) {
510//              std::cout << "t is reached, AUGMENTATION"<<std::endl;
511                __augment=true;
512                _augment=true;
513                break;
514              }
515            } else {
516//            std::cout << "<<DELETE ";
517//            std::cout << " aNode: " << res_graph.aNode(dfs);
518//            std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
519//            std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
520//            std::cout << "DELETE>> ";
521
522              res_graph.erase(dfs);
523            }
524          }
525
526        }
527
528        if (__augment) {
529          typename EAugGraph::NodeIt n=t;
530          Number augment_value=free.get(t);
531//        std::cout << "av:" << augment_value << std::endl;
532          while (res_graph.valid(pred.get(n))) {
533            EAugEdgeIt e=pred.get(n);
534            res_graph.augment(e, augment_value);
535            //e.augment(augment_value);
536            n=res_graph.tail(e);
537            if (res_graph.free(e)==0)
538              res_graph.erase(e);
539          }
540        }
541     
542      }
543           
544      return _augment;
545    }
546    void run() {
547      //int num_of_augmentations=0;
548      while (augmentOnShortestPath()) {
549        //while (augmentOnBlockingFlow<MutableGraph>()) {
550        //std::cout << ++num_of_augmentations << " ";
551        //std::cout<<std::endl;
552      }
553    }
554    template<typename MutableGraph> void run() {
555      //int num_of_augmentations=0;
556      //while (augmentOnShortestPath()) {
557        while (augmentOnBlockingFlow<MutableGraph>()) {
558        //std::cout << ++num_of_augmentations << " ";
559        //std::cout<<std::endl;
560      }
561    }
562    Number flowValue() {
563      Number a=0;
564      OutEdgeIt e;
565      for(G->getFirst(e, s); G->valid(e); G->next(e)) {
566        a+=flow->get(e);
567      }
568      return a;
569    }
570  };
571
572 
573//   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
574//   class MaxFlow2 {
575//   public:
576//     typedef typename Graph::NodeIt NodeIt;
577//     typedef typename Graph::EdgeIt EdgeIt;
578//     typedef typename Graph::EachEdgeIt EachEdgeIt;
579//     typedef typename Graph::OutEdgeIt OutEdgeIt;
580//     typedef typename Graph::InEdgeIt InEdgeIt;
581//   private:
582//     const Graph& G;
583//     std::list<NodeIt>& S;
584//     std::list<NodeIt>& T;
585//     FlowMap& flow;
586//     const CapacityMap& capacity;
587//     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
588//     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
589//     typedef typename AugGraph::EdgeIt AugEdgeIt;
590//     typename Graph::NodeMap<bool> SMap;
591//     typename Graph::NodeMap<bool> TMap;
592//   public:
593//     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) {
594//       for(typename std::list<NodeIt>::const_iterator i=S.begin();
595//        i!=S.end(); ++i) {
596//      SMap.set(*i, true);
597//       }
598//       for (typename std::list<NodeIt>::const_iterator i=T.begin();
599//         i!=T.end(); ++i) {
600//      TMap.set(*i, true);
601//       }
602//     }
603//     bool augment() {
604//       AugGraph res_graph(G, flow, capacity);
605//       bool _augment=false;
606//       NodeIt reached_t_node;
607     
608//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
609//       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
610//       for(typename std::list<NodeIt>::const_iterator i=S.begin();
611//        i!=S.end(); ++i) {
612//      res_bfs.pushAndSetReached(*i);
613//       }
614//       //res_bfs.pushAndSetReached(s);
615       
616//       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
617//       //filled up with invalid iterators
618     
619//       typename AugGraph::NodeMap<Number> free(res_graph);
620       
621//       //searching for augmenting path
622//       while ( !res_bfs.finished() ) {
623//      AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
624//      if (e.valid() && res_bfs.isBNodeNewlyReached()) {
625//        NodeIt v=res_graph.tail(e);
626//        NodeIt w=res_graph.head(e);
627//        pred.set(w, e);
628//        if (pred.get(v).valid()) {
629//          free.set(w, std::min(free.get(v), e.free()));
630//        } else {
631//          free.set(w, e.free());
632//        }
633//        if (TMap.get(res_graph.head(e))) {
634//          _augment=true;
635//          reached_t_node=res_graph.head(e);
636//          break;
637//        }
638//      }
639       
640//      ++res_bfs;
641//       } //end of searching augmenting path
642
643//       if (_augment) {
644//      NodeIt n=reached_t_node;
645//      Number augment_value=free.get(reached_t_node);
646//      while (pred.get(n).valid()) {
647//        AugEdgeIt e=pred.get(n);
648//        e.augment(augment_value);
649//        n=res_graph.tail(e);
650//      }
651//       }
652
653//       return _augment;
654//     }
655//     void run() {
656//       while (augment()) { }
657//     }
658//     Number flowValue() {
659//       Number a=0;
660//       for(typename std::list<NodeIt>::const_iterator i=S.begin();
661//        i!=S.end(); ++i) {
662//      for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
663//        a+=flow.get(e);
664//      }
665//      for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
666//        a-=flow.get(e);
667//      }
668//       }
669//       return a;
670//     }
671//   };
672
673
674
675} // namespace hugo
676
677#endif //EDMONDS_KARP_HH
Note: See TracBrowser for help on using the repository browser.