COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.hh @ 127:dcace15b1874

Last change on this file since 127:dcace15b1874 was 127:dcace15b1874, checked in by Mihaly Barasz, 16 years ago

private typedef problemak

File size: 18.6 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; //1, iff out
152    public:
153      EdgeIt() : out_or_in(1) { }
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  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
249  class ResGraph3 {
250  public:
251    typedef typename Graph::NodeIt NodeIt;
252    typedef typename Graph::EachNodeIt EachNodeIt;
253
254  private:
255    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
256    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
257    typedef typename Graph::InEdgeIt OldInEdgeIt;
258    const Graph& G;
259    FlowMap& flow;
260    const CapacityMap& capacity;
261  public:
262    ResGraph3(const Graph& _G, FlowMap& _flow,
263             const CapacityMap& _capacity) :
264      G(_G), flow(_flow), capacity(_capacity) { }
265
266    class EdgeIt;
267    class OutEdgeIt;
268    friend class EdgeIt;
269    friend class OutEdgeIt;
270
271    class EdgeIt {
272      friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
273    protected:
274      //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
275      const Graph* G;
276      FlowMap* flow;
277      const CapacityMap* capacity;
278      //OldSymEdgeIt sym;
279      OldOutEdgeIt out;
280      OldInEdgeIt in;
281      bool out_or_in; //1, iff out
282    public:
283      EdgeIt() : out_or_in(1) { }
284      Number free() const {
285        if (out_or_in) {
286          return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
287        } else {
288          return (/*resG->*/flow->get(in));
289        }
290      }
291      bool valid() const {
292        return out_or_in && out.valid() || in.valid(); }
293      void augment(Number a) const {
294        if (out_or_in) {
295          /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
296        } else {
297          /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
298        }
299      }
300    };
301
302    class OutEdgeIt : public EdgeIt {
303      friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
304    public:
305      OutEdgeIt() { }
306    private:
307      OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) {
308        G=&_G;
309        flow=&_flow;
310        capacity=&_capacity;
311        out=/*resG->*/G->template first<OldOutEdgeIt>(v);
312        while( out.valid() && !(free()>0) ) { ++out; }
313        if (!out.valid()) {
314          out_or_in=0;
315          in=/*resG->*/G->template first<OldInEdgeIt>(v);
316          while( in.valid() && !(free()>0) ) { ++in; }
317        }
318      }
319    public:
320      OutEdgeIt& operator++() {
321        if (out_or_in) {
322          NodeIt v=/*resG->*/G->aNode(out);
323          ++out;
324          while( out.valid() && !(free()>0) ) { ++out; }
325          if (!out.valid()) {
326            out_or_in=0;
327            in=/*resG->*/G->template first<OldInEdgeIt>(v);
328            while( in.valid() && !(free()>0) ) { ++in; }
329          }
330        } else {
331          ++in;
332          while( in.valid() && !(free()>0) ) { ++in; }
333        }
334        return *this;
335      }
336    };
337
338    void getFirst(OutEdgeIt& e, NodeIt v) const {
339      e=OutEdgeIt(G, v, flow, capacity);
340    }
341    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
342   
343    template< typename It >
344    It first() const {
345      It e;
346      getFirst(e);
347      return e;
348    }
349
350    template< typename It >
351    It first(NodeIt v) const {
352      It e;
353      getFirst(e, v);
354      return e;
355    }
356
357    NodeIt tail(EdgeIt e) const {
358      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
359    NodeIt head(EdgeIt e) const {
360      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
361
362    NodeIt aNode(OutEdgeIt e) const {
363      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
364    NodeIt bNode(OutEdgeIt e) const {
365      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
366
367    int id(NodeIt v) const { return G.id(v); }
368
369    template <typename S>
370    class NodeMap {
371      typename Graph::NodeMap<S> node_map;
372    public:
373      NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
374      NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
375      void set(NodeIt nit, S a) { node_map.set(nit, a); }
376      S get(NodeIt nit) const { return node_map.get(nit); }
377    };
378
379  };
380
381
382  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
383  class MaxFlow {
384  public:
385    typedef typename Graph::NodeIt NodeIt;
386    typedef typename Graph::EdgeIt EdgeIt;
387    typedef typename Graph::EachEdgeIt EachEdgeIt;
388    typedef typename Graph::OutEdgeIt OutEdgeIt;
389    typedef typename Graph::InEdgeIt InEdgeIt;
390
391  private:
392    const Graph& G;
393    NodeIt s;
394    NodeIt t;
395    FlowMap& flow;
396    const CapacityMap& capacity;
397    typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;
398    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
399    typedef typename AugGraph::EdgeIt AugEdgeIt;
400
401    //AugGraph res_graph;   
402    //typedef typename AugGraph::NodeMap<bool> ReachedMap;
403    //typename AugGraph::NodeMap<AugEdgeIt> pred;
404    //typename AugGraph::NodeMap<int> free;
405  public:
406    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
407      G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //, 
408      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
409      { }
410    bool augment() {
411      AugGraph res_graph(G, flow, capacity);
412      bool _augment=false;
413     
414      typedef typename AugGraph::NodeMap<bool> ReachedMap;
415      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
416      res_bfs.pushAndSetReached(s);
417       
418      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
419      //filled up with invalid iterators
420      //pred.set(s, AugEdgeIt());
421     
422      typename AugGraph::NodeMap<int> free(res_graph);
423       
424      //searching for augmenting path
425      while ( !res_bfs.finished() ) {
426        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
427        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
428          NodeIt v=res_graph.tail(e);
429          NodeIt w=res_graph.head(e);
430          pred.set(w, e);
431          if (pred.get(v).valid()) {
432            free.set(w, std::min(free.get(v), e.free()));
433          } else {
434            free.set(w, e.free());
435          }
436          if (res_graph.head(e)==t) { _augment=true; break; }
437        }
438       
439        ++res_bfs;
440      } //end of searching augmenting path
441
442      if (_augment) {
443        NodeIt n=t;
444        Number augment_value=free.get(t);
445        while (pred.get(n).valid()) {
446          AugEdgeIt e=pred.get(n);
447          e.augment(augment_value);
448          n=res_graph.tail(e);
449        }
450      }
451
452      return _augment;
453    }
454    bool augmentWithBlockingFlow() {
455      BfsIterator4< Graph, OutEdgeIt, typename Graph::NodeMap<bool> > bfs(G);
456      bfs.pushAndSetReached(s);
457      typename Graph::NodeMap<int> dist(G); //filled up with 0's
458      while ( !bfs.finished() ) {
459        OutEdgeIt e=OutEdgeIt(bfs);
460        if (e.valid() && bfs.isBNodeNewlyReached()) {
461          dist.set(G.head(e), dist.get(G.tail(e))+1);
462          //NodeIt v=res_graph.tail(e);
463          //NodeIt w=res_graph.head(e);
464          //pred.set(w, e);
465          //if (pred.get(v).valid()) {
466          //  free.set(w, std::min(free.get(v), e.free()));
467          //} else {
468          //  free.set(w, e.free());
469          //}
470          //if (res_graph.head(e)==t) { _augment=true; break; }
471        }
472       
473        ++bfs;
474      } //end of searching augmenting path
475
476      double pre_time_copy=currTime();
477      typedef Graph MutableGraph;
478      MutableGraph F;
479      typename Graph::NodeMap<NodeIt> G_to_F(G);
480      for(typename Graph::EachNodeIt n=G.template first<typename Graph::EachNodeIt>(); n.valid(); ++n) {
481        G_to_F.set(n, F.addNode());
482      }
483      for(typename Graph::EachEdgeIt e=G.template first<typename Graph::EachEdgeIt>(); e.valid(); ++e) {
484        if (dist.get(G.head(e))==dist.get(G.tail(e))+1) {
485          F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e)));
486        }
487      }
488      double post_time_copy=currTime();
489      std::cout << "copy time: " << post_time_copy-pre_time_copy << " sec"<< std::endl;
490
491      return 0;
492    }
493    void run() {
494      //int num_of_augmentations=0;
495      while (augment()) {
496        //std::cout << ++num_of_augmentations << " ";
497        //std::cout<<std::endl;
498      }
499    }
500    Number flowValue() {
501      Number a=0;
502      for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
503        a+=flow.get(i);
504      }
505      return a;
506    }
507  };
508
509
510/*
511  template <typename Graph>
512  class IteratorBoolNodeMap {
513    typedef typename Graph::NodeIt NodeIt;
514    typedef typename Graph::EachNodeIt EachNodeIt;
515    class BoolItem {
516    public:
517      bool value;
518      NodeIt prev;
519      NodeIt next;
520      BoolItem() : value(false), prev(), next() {}
521    };
522    NodeIt first_true;
523    //NodeIt last_true;
524    NodeIt first_false;
525    //NodeIt last_false;
526    const Graph& G;
527    typename Graph::NodeMap<BoolItem> container;
528  public:
529    typedef bool ValueType;
530    typedef NodeIt KeyType;
531    IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) {
532      //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
533      //BoolItem b=container.get(e);
534      //b.me=e;
535      //container.set(b);
536      //}
537      G.getFirst(first_false);
538      NodeIt e_prev;
539      for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
540        container[e].prev=e_prev;
541        if (e_prev.valid()) container[e_prev].next=e;
542        e_prev=e;
543      }
544    }
545    //NodeMap(const Graph& _G, T a) :
546    //  G(_G), container(G.node_id, a) { }
547    //FIXME
548    void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
549    T get(NodeIt nit) const { return container[G.id(nit)]; }
550    //void update() { container.resize(G.node_id); }
551    //void update(T a) { container.resize(G.node_id, a); }
552  };
553*/
554
555 
556  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
557  class MaxFlow2 {
558  public:
559    typedef typename Graph::NodeIt NodeIt;
560    typedef typename Graph::EdgeIt EdgeIt;
561    typedef typename Graph::EachEdgeIt EachEdgeIt;
562    typedef typename Graph::OutEdgeIt OutEdgeIt;
563    typedef typename Graph::InEdgeIt InEdgeIt;
564  private:
565    const Graph& G;
566    std::list<NodeIt>& S;
567    std::list<NodeIt>& T;
568    FlowMap& flow;
569    const CapacityMap& capacity;
570    typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;
571    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
572    typedef typename AugGraph::EdgeIt AugEdgeIt;
573    typename Graph::NodeMap<bool> SMap;
574    typename Graph::NodeMap<bool> TMap;
575  public:
576    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) {
577      for(typename std::list<NodeIt>::const_iterator i=S.begin();
578          i!=S.end(); ++i) {
579        SMap.set(*i, true);
580      }
581      for (typename std::list<NodeIt>::const_iterator i=T.begin();
582           i!=T.end(); ++i) {
583        TMap.set(*i, true);
584      }
585    }
586    bool augment() {
587      AugGraph res_graph(G, flow, capacity);
588      bool _augment=false;
589      NodeIt reached_t_node;
590     
591      typedef typename AugGraph::NodeMap<bool> ReachedMap;
592      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
593      for(typename std::list<NodeIt>::const_iterator i=S.begin();
594          i!=S.end(); ++i) {
595        res_bfs.pushAndSetReached(*i);
596      }
597      //res_bfs.pushAndSetReached(s);
598       
599      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
600      //filled up with invalid iterators
601     
602      typename AugGraph::NodeMap<int> free(res_graph);
603       
604      //searching for augmenting path
605      while ( !res_bfs.finished() ) {
606        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
607        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
608          NodeIt v=res_graph.tail(e);
609          NodeIt w=res_graph.head(e);
610          pred.set(w, e);
611          if (pred.get(v).valid()) {
612            free.set(w, std::min(free.get(v), e.free()));
613          } else {
614            free.set(w, e.free());
615          }
616          if (TMap.get(res_graph.head(e))) {
617            _augment=true;
618            reached_t_node=res_graph.head(e);
619            break;
620          }
621        }
622       
623        ++res_bfs;
624      } //end of searching augmenting path
625
626      if (_augment) {
627        NodeIt n=reached_t_node;
628        Number augment_value=free.get(reached_t_node);
629        while (pred.get(n).valid()) {
630          AugEdgeIt e=pred.get(n);
631          e.augment(augment_value);
632          n=res_graph.tail(e);
633        }
634      }
635
636      return _augment;
637    }
638    void run() {
639      while (augment()) { }
640    }
641    Number flowValue() {
642      Number a=0;
643      for(typename std::list<NodeIt>::const_iterator i=S.begin();
644          i!=S.end(); ++i) {
645        for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
646          a+=flow.get(e);
647        }
648        for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
649          a-=flow.get(e);
650        }
651      }
652      return a;
653    }
654  };
655
656
657
658} // namespace hugo
659
660#endif //EDMONDS_KARP_HH
Note: See TracBrowser for help on using the repository browser.