COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.hh @ 107:8d62f0072ff0

Last change on this file since 107:8d62f0072ff0 was 107:8d62f0072ff0, checked in by Alpar Juttner, 17 years ago

marci -> hugo
resize -> update

File size: 18.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    typedef typename Graph::NodeIt NodeIt;
16    typedef typename Graph::EachNodeIt EachNodeIt;
17    typedef typename Graph::SymEdgeIt OldSymEdgeIt;
18    const Graph& G;
19    FlowMap& flow;
20    const CapacityMap& capacity;
21  public:
22    ResGraph(const Graph& _G, FlowMap& _flow,
23             const CapacityMap& _capacity) :
24      G(_G), flow(_flow), capacity(_capacity) { }
25
26    class EdgeIt;
27    class OutEdgeIt;
28    friend class EdgeIt;
29    friend class OutEdgeIt;
30
31    class EdgeIt {
32      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
33    protected:
34      const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
35      OldSymEdgeIt sym;
36    public:
37      EdgeIt() { }
38      //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
39      Number free() const {
40        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
41          return (resG->capacity.get(sym)-resG->flow.get(sym));
42        } else {
43          return (resG->flow.get(sym));
44        }
45      }
46      bool valid() const { return sym.valid(); }
47      void augment(Number a) const {
48        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
49          resG->flow.set(sym, resG->flow.get(sym)+a);
50          //resG->flow[sym]+=a;
51        } else {
52          resG->flow.set(sym, resG->flow.get(sym)-a);
53          //resG->flow[sym]-=a;
54        }
55      }
56    };
57
58    class OutEdgeIt : public EdgeIt {
59      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
60    public:
61      OutEdgeIt() { }
62      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
63    private:
64      OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
65        resG=&_resG;
66        sym=resG->G.template first<OldSymEdgeIt>(v);
67        while( sym.valid() && !(free()>0) ) { ++sym; }
68      }
69    public:
70      OutEdgeIt& operator++() {
71        ++sym;
72        while( sym.valid() && !(free()>0) ) { ++sym; }
73        return *this;
74      }
75    };
76
77    void getFirst(OutEdgeIt& e, NodeIt v) const {
78      e=OutEdgeIt(*this, v);
79    }
80    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
81   
82    template< typename It >
83    It first() const {
84      It e;     
85      getFirst(e);
86      return e;
87    }
88
89    template< typename It >
90    It first(NodeIt v) const {
91      It e;
92      getFirst(e, v);
93      return e;
94    }
95
96    NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
97    NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
98
99    NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
100    NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
101
102    int id(NodeIt v) const { return G.id(v); }
103
104    template <typename S>
105    class NodeMap {
106      typename Graph::NodeMap<S> node_map;
107    public:
108      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
109      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
110      void set(NodeIt nit, S a) { node_map.set(nit, a); }
111      S get(NodeIt nit) const { return node_map.get(nit); }
112      S& operator[](NodeIt nit) { return node_map[nit]; }
113      const S& operator[](NodeIt nit) const { return node_map[nit]; }
114    };
115
116  };
117
118
119  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
120  class ResGraph2 {
121    typedef typename Graph::NodeIt NodeIt;
122    typedef typename Graph::EachNodeIt EachNodeIt;
123    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
124    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
125    typedef typename Graph::InEdgeIt OldInEdgeIt;
126   
127    const Graph& G;
128    FlowMap& flow;
129    const CapacityMap& capacity;
130  public:
131    ResGraph2(const Graph& _G, FlowMap& _flow,
132             const CapacityMap& _capacity) :
133      G(_G), flow(_flow), capacity(_capacity) { }
134
135    class EdgeIt;
136    class OutEdgeIt;
137    friend class EdgeIt;
138    friend class OutEdgeIt;
139
140    class EdgeIt {
141      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
142    protected:
143      const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
144      //OldSymEdgeIt sym;
145      OldOutEdgeIt out;
146      OldInEdgeIt in;
147      bool out_or_in; //1, iff out
148    public:
149      EdgeIt() : out_or_in(1) { }
150      Number free() const {
151        if (out_or_in) {
152          return (resG->capacity.get(out)-resG->flow.get(out));
153        } else {
154          return (resG->flow.get(in));
155        }
156      }
157      bool valid() const {
158        return out_or_in && out.valid() || in.valid(); }
159      void augment(Number a) const {
160        if (out_or_in) {
161          resG->flow.set(out, resG->flow.get(out)+a);
162        } else {
163          resG->flow.set(in, resG->flow.get(in)-a);
164        }
165      }
166    };
167
168    class OutEdgeIt : public EdgeIt {
169      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
170    public:
171      OutEdgeIt() { }
172    private:
173      OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
174        resG=&_resG;
175        out=resG->G.template first<OldOutEdgeIt>(v);
176        while( out.valid() && !(free()>0) ) { ++out; }
177        if (!out.valid()) {
178          out_or_in=0;
179          in=resG->G.template first<OldInEdgeIt>(v);
180          while( in.valid() && !(free()>0) ) { ++in; }
181        }
182      }
183    public:
184      OutEdgeIt& operator++() {
185        if (out_or_in) {
186          NodeIt v=resG->G.aNode(out);
187          ++out;
188          while( out.valid() && !(free()>0) ) { ++out; }
189          if (!out.valid()) {
190            out_or_in=0;
191            in=resG->G.template first<OldInEdgeIt>(v);
192            while( in.valid() && !(free()>0) ) { ++in; }
193          }
194        } else {
195          ++in;
196          while( in.valid() && !(free()>0) ) { ++in; }
197        }
198        return *this;
199      }
200    };
201
202    void getFirst(OutEdgeIt& e, NodeIt v) const {
203      e=OutEdgeIt(*this, v);
204    }
205    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
206   
207    template< typename It >
208    It first() const {
209      It e;
210      getFirst(e);
211      return e;
212    }
213
214    template< typename It >
215    It first(NodeIt v) const {
216      It e;
217      getFirst(e, v);
218      return e;
219    }
220
221    NodeIt tail(EdgeIt e) const {
222      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
223    NodeIt head(EdgeIt e) const {
224      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
225
226    NodeIt aNode(OutEdgeIt e) const {
227      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
228    NodeIt bNode(OutEdgeIt e) const {
229      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
230
231    int id(NodeIt v) const { return G.id(v); }
232
233    template <typename S>
234    class NodeMap {
235      typename Graph::NodeMap<S> node_map;
236    public:
237      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
238      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
239      void set(NodeIt nit, S a) { node_map.set(nit, a); }
240      S get(NodeIt nit) const { return node_map.get(nit); }
241    };
242  };
243
244  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
245  class ResGraph3 {
246public:
247    typedef typename Graph::NodeIt NodeIt;
248    typedef typename Graph::EachNodeIt EachNodeIt;
249    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
250    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
251    typedef typename Graph::InEdgeIt OldInEdgeIt;
252   
253private:
254    const Graph& G;
255    FlowMap& flow;
256    const CapacityMap& capacity;
257  public:
258    ResGraph3(const Graph& _G, FlowMap& _flow,
259             const CapacityMap& _capacity) :
260      G(_G), flow(_flow), capacity(_capacity) { }
261
262    class EdgeIt;
263    class OutEdgeIt;
264    friend class EdgeIt;
265    friend class OutEdgeIt;
266
267    class EdgeIt {
268      friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
269    protected:
270      //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
271      const Graph* G;
272      FlowMap* flow;
273      const CapacityMap* capacity;
274      //OldSymEdgeIt sym;
275      OldOutEdgeIt out;
276      OldInEdgeIt in;
277      bool out_or_in; //1, iff out
278    public:
279      EdgeIt() : out_or_in(1) { }
280      Number free() const {
281        if (out_or_in) {
282          return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
283        } else {
284          return (/*resG->*/flow->get(in));
285        }
286      }
287      bool valid() const {
288        return out_or_in && out.valid() || in.valid(); }
289      void augment(Number a) const {
290        if (out_or_in) {
291          /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
292        } else {
293          /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
294        }
295      }
296    };
297
298    class OutEdgeIt : public EdgeIt {
299      friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
300    public:
301      OutEdgeIt() { }
302    private:
303      OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) {
304        G=&_G;
305        flow=&_flow;
306        capacity=&_capacity;
307        out=/*resG->*/G->template first<OldOutEdgeIt>(v);
308        while( out.valid() && !(free()>0) ) { ++out; }
309        if (!out.valid()) {
310          out_or_in=0;
311          in=/*resG->*/G->template first<OldInEdgeIt>(v);
312          while( in.valid() && !(free()>0) ) { ++in; }
313        }
314      }
315    public:
316      OutEdgeIt& operator++() {
317        if (out_or_in) {
318          NodeIt v=/*resG->*/G->aNode(out);
319          ++out;
320          while( out.valid() && !(free()>0) ) { ++out; }
321          if (!out.valid()) {
322            out_or_in=0;
323            in=/*resG->*/G->template first<OldInEdgeIt>(v);
324            while( in.valid() && !(free()>0) ) { ++in; }
325          }
326        } else {
327          ++in;
328          while( in.valid() && !(free()>0) ) { ++in; }
329        }
330        return *this;
331      }
332    };
333
334    void getFirst(OutEdgeIt& e, NodeIt v) const {
335      e=OutEdgeIt(G, v, flow, capacity);
336    }
337    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
338   
339    template< typename It >
340    It first() const {
341      It e;
342      getFirst(e);
343      return e;
344    }
345
346    template< typename It >
347    It first(NodeIt v) const {
348      It e;
349      getFirst(e, v);
350      return e;
351    }
352
353    NodeIt tail(EdgeIt e) const {
354      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
355    NodeIt head(EdgeIt e) const {
356      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
357
358    NodeIt aNode(OutEdgeIt e) const {
359      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
360    NodeIt bNode(OutEdgeIt e) const {
361      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
362
363    int id(NodeIt v) const { return G.id(v); }
364
365    template <typename S>
366    class NodeMap {
367      typename Graph::NodeMap<S> node_map;
368    public:
369      NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
370      NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
371      void set(NodeIt nit, S a) { node_map.set(nit, a); }
372      S get(NodeIt nit) const { return node_map.get(nit); }
373    };
374
375  };
376
377
378  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
379  class MaxFlow {
380    typedef typename Graph::NodeIt NodeIt;
381    typedef typename Graph::EdgeIt EdgeIt;
382    typedef typename Graph::EachEdgeIt EachEdgeIt;
383    typedef typename Graph::OutEdgeIt OutEdgeIt;
384    typedef typename Graph::InEdgeIt InEdgeIt;
385    const Graph& G;
386    NodeIt s;
387    NodeIt t;
388    FlowMap& flow;
389    const CapacityMap& capacity;
390    typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;
391    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
392    typedef typename AugGraph::EdgeIt AugEdgeIt;
393
394    //AugGraph res_graph;   
395    //typedef typename AugGraph::NodeMap<bool> ReachedMap;
396    //typename AugGraph::NodeMap<AugEdgeIt> pred;
397    //typename AugGraph::NodeMap<int> free;
398  public:
399    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
400      G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //, 
401      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
402      { }
403    bool augment() {
404      AugGraph res_graph(G, flow, capacity);
405      bool _augment=false;
406     
407      typedef typename AugGraph::NodeMap<bool> ReachedMap;
408      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
409      res_bfs.pushAndSetReached(s);
410       
411      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
412      //filled up with invalid iterators
413      //pred.set(s, AugEdgeIt());
414     
415      typename AugGraph::NodeMap<int> free(res_graph);
416       
417      //searching for augmenting path
418      while ( !res_bfs.finished() ) {
419        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
420        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
421          NodeIt v=res_graph.tail(e);
422          NodeIt w=res_graph.head(e);
423          pred.set(w, e);
424          if (pred.get(v).valid()) {
425            free.set(w, std::min(free.get(v), e.free()));
426          } else {
427            free.set(w, e.free());
428          }
429          if (res_graph.head(e)==t) { _augment=true; break; }
430        }
431       
432        ++res_bfs;
433      } //end of searching augmenting path
434
435      if (_augment) {
436        NodeIt n=t;
437        Number augment_value=free.get(t);
438        while (pred.get(n).valid()) {
439          AugEdgeIt e=pred.get(n);
440          e.augment(augment_value);
441          n=res_graph.tail(e);
442        }
443      }
444
445      return _augment;
446    }
447    bool augmentWithBlockingFlow() {
448      BfsIterator4< Graph, OutEdgeIt, typename Graph::NodeMap<bool> > bfs(G);
449      bfs.pushAndSetReached(s);
450      typename Graph::NodeMap<int> dist(G); //filled up with 0's
451      while ( !bfs.finished() ) {
452        OutEdgeIt e=OutEdgeIt(bfs);
453        if (e.valid() && bfs.isBNodeNewlyReached()) {
454          dist.set(G.head(e), dist.get(G.tail(e))+1);
455          //NodeIt v=res_graph.tail(e);
456          //NodeIt w=res_graph.head(e);
457          //pred.set(w, e);
458          //if (pred.get(v).valid()) {
459          //  free.set(w, std::min(free.get(v), e.free()));
460          //} else {
461          //  free.set(w, e.free());
462          //}
463          //if (res_graph.head(e)==t) { _augment=true; break; }
464        }
465       
466        ++bfs;
467      } //end of searching augmenting path
468
469      double pre_time_copy=currTime();
470      typedef Graph MutableGraph;
471      MutableGraph F;
472      typename Graph::NodeMap<NodeIt> G_to_F(G);
473      for(typename Graph::EachNodeIt n=G.template first<typename Graph::EachNodeIt>(); n.valid(); ++n) {
474        G_to_F.set(n, F.addNode());
475      }
476      for(typename Graph::EachEdgeIt e=G.template first<typename Graph::EachEdgeIt>(); e.valid(); ++e) {
477        if (dist.get(G.head(e))==dist.get(G.tail(e))+1) {
478          F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e)));
479        }
480      }
481      double post_time_copy=currTime();
482      std::cout << "copy time: " << post_time_copy-pre_time_copy << " sec"<< std::endl;
483
484      return 0;
485    }
486    void run() {
487      //int num_of_augmentations=0;
488      while (augment()) {
489        //std::cout << ++num_of_augmentations << " ";
490        //std::cout<<std::endl;
491      }
492    }
493    Number flowValue() {
494      Number a=0;
495      for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
496        a+=flow.get(i);
497      }
498      return a;
499    }
500  };
501
502
503/*
504  template <typename Graph>
505  class IteratorBoolNodeMap {
506    typedef typename Graph::NodeIt NodeIt;
507    typedef typename Graph::EachNodeIt EachNodeIt;
508    class BoolItem {
509    public:
510      bool value;
511      NodeIt prev;
512      NodeIt next;
513      BoolItem() : value(false), prev(), next() {}
514    };
515    NodeIt first_true;
516    //NodeIt last_true;
517    NodeIt first_false;
518    //NodeIt last_false;
519    const Graph& G;
520    typename Graph::NodeMap<BoolItem> container;
521  public:
522    typedef bool ValueType;
523    typedef NodeIt KeyType;
524    IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) {
525      //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
526      //BoolItem b=container.get(e);
527      //b.me=e;
528      //container.set(b);
529      //}
530      G.getFirst(first_false);
531      NodeIt e_prev;
532      for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
533        container[e].prev=e_prev;
534        if (e_prev.valid()) container[e_prev].next=e;
535        e_prev=e;
536      }
537    }
538    //NodeMap(const Graph& _G, T a) :
539    //  G(_G), container(G.node_id, a) { }
540    //FIXME
541    void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
542    T get(NodeIt nit) const { return container[G.id(nit)]; }
543    //void update() { container.resize(G.node_id); }
544    //void update(T a) { container.resize(G.node_id, a); }
545  };
546*/
547
548 
549  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
550  class MaxFlow2 {
551    typedef typename Graph::NodeIt NodeIt;
552    typedef typename Graph::EdgeIt EdgeIt;
553    typedef typename Graph::EachEdgeIt EachEdgeIt;
554    typedef typename Graph::OutEdgeIt OutEdgeIt;
555    typedef typename Graph::InEdgeIt InEdgeIt;
556    const Graph& G;
557    std::list<NodeIt>& S;
558    std::list<NodeIt>& T;
559    FlowMap& flow;
560    const CapacityMap& capacity;
561    typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;
562    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
563    typedef typename AugGraph::EdgeIt AugEdgeIt;
564    typename Graph::NodeMap<bool> SMap;
565    typename Graph::NodeMap<bool> TMap;
566  public:
567    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) {
568      for(typename std::list<NodeIt>::const_iterator i=S.begin();
569          i!=S.end(); ++i) {
570        SMap.set(*i, true);
571      }
572      for (typename std::list<NodeIt>::const_iterator i=T.begin();
573           i!=T.end(); ++i) {
574        TMap.set(*i, true);
575      }
576    }
577    bool augment() {
578      AugGraph res_graph(G, flow, capacity);
579      bool _augment=false;
580      NodeIt reached_t_node;
581     
582      typedef typename AugGraph::NodeMap<bool> ReachedMap;
583      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
584      for(typename std::list<NodeIt>::const_iterator i=S.begin();
585          i!=S.end(); ++i) {
586        res_bfs.pushAndSetReached(*i);
587      }
588      //res_bfs.pushAndSetReached(s);
589       
590      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
591      //filled up with invalid iterators
592     
593      typename AugGraph::NodeMap<int> free(res_graph);
594       
595      //searching for augmenting path
596      while ( !res_bfs.finished() ) {
597        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
598        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
599          NodeIt v=res_graph.tail(e);
600          NodeIt w=res_graph.head(e);
601          pred.set(w, e);
602          if (pred.get(v).valid()) {
603            free.set(w, std::min(free.get(v), e.free()));
604          } else {
605            free.set(w, e.free());
606          }
607          if (TMap.get(res_graph.head(e))) {
608            _augment=true;
609            reached_t_node=res_graph.head(e);
610            break;
611          }
612        }
613       
614        ++res_bfs;
615      } //end of searching augmenting path
616
617      if (_augment) {
618        NodeIt n=reached_t_node;
619        Number augment_value=free.get(reached_t_node);
620        while (pred.get(n).valid()) {
621          AugEdgeIt e=pred.get(n);
622          e.augment(augment_value);
623          n=res_graph.tail(e);
624        }
625      }
626
627      return _augment;
628    }
629    void run() {
630      while (augment()) { }
631    }
632    Number flowValue() {
633      Number a=0;
634      for(typename std::list<NodeIt>::const_iterator i=S.begin();
635          i!=S.end(); ++i) {
636        for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
637          a+=flow.get(e);
638        }
639        for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
640          a-=flow.get(e);
641        }
642      }
643      return a;
644    }
645  };
646
647
648
649} // namespace hugo
650
651#endif //EDMONDS_KARP_HH
Note: See TracBrowser for help on using the repository browser.