COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.h @ 263:f24f276e0b6b

Last change on this file since 263:f24f276e0b6b was 263:f24f276e0b6b, checked in by marci, 16 years ago

ResGraphWrapper? ...

File size: 38.5 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_EDMONDS_KARP_H
3#define HUGO_EDMONDS_KARP_H
4
5#include <algorithm>
6#include <list>
7#include <iterator>
8
9#include <bfs_iterator.h>
10#include <invalid.h>
11
12namespace hugo {
13
14  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
15  class ResGraph {
16  public:
17    typedef typename Graph::Node Node;
18    typedef typename Graph::NodeIt NodeIt;
19  private:
20    typedef typename Graph::SymEdgeIt OldSymEdgeIt;
21    const Graph& G;
22    FlowMap& flow;
23    const CapacityMap& capacity;
24  public:
25    ResGraph(const Graph& _G, FlowMap& _flow,
26             const CapacityMap& _capacity) :
27      G(_G), flow(_flow), capacity(_capacity) { }
28
29    class Edge;
30    class OutEdgeIt;
31    friend class Edge;
32    friend class OutEdgeIt;
33
34    class Edge {
35      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
36    protected:
37      const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
38      OldSymEdgeIt sym;
39    public:
40      Edge() { }
41      //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
42      Number free() const {
43        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
44          return (resG->capacity.get(sym)-resG->flow.get(sym));
45        } else {
46          return (resG->flow.get(sym));
47        }
48      }
49      bool valid() const { return sym.valid(); }
50      void augment(Number a) const {
51        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
52          resG->flow.set(sym, resG->flow.get(sym)+a);
53          //resG->flow[sym]+=a;
54        } else {
55          resG->flow.set(sym, resG->flow.get(sym)-a);
56          //resG->flow[sym]-=a;
57        }
58      }
59    };
60
61    class OutEdgeIt : public Edge {
62      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
63    public:
64      OutEdgeIt() { }
65      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
66    private:
67      OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
68        resG=&_resG;
69        sym=resG->G.template first<OldSymEdgeIt>(v);
70        while( sym.valid() && !(free()>0) ) { ++sym; }
71      }
72    public:
73      OutEdgeIt& operator++() {
74        ++sym;
75        while( sym.valid() && !(free()>0) ) { ++sym; }
76        return *this;
77      }
78    };
79
80    void /*getF*/first(OutEdgeIt& e, Node v) const {
81      e=OutEdgeIt(*this, v);
82    }
83    void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
84   
85    template< typename It >
86    It first() const {
87      It e;     
88      /*getF*/first(e);
89      return e;
90    }
91
92    template< typename It >
93    It first(Node v) const {
94      It e;
95      /*getF*/first(e, v);
96      return e;
97    }
98
99    Node tail(Edge e) const { return G.aNode(e.sym); }
100    Node head(Edge e) const { return G.bNode(e.sym); }
101
102    Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
103    Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
104
105    int id(Node v) const { return G.id(v); }
106
107    template <typename S>
108    class NodeMap {
109      typename Graph::NodeMap<S> node_map;
110    public:
111      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
112      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
113      void set(Node nit, S a) { node_map.set(nit, a); }
114      S get(Node nit) const { return node_map.get(nit); }
115      S& operator[](Node nit) { return node_map[nit]; }
116      const S& operator[](Node nit) const { return node_map[nit]; }
117    };
118
119  };
120
121
122  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
123  class ResGraph2 {
124  public:
125    typedef typename Graph::Node Node;
126    typedef typename Graph::NodeIt NodeIt;
127  private:
128    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
129    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
130    typedef typename Graph::InEdgeIt OldInEdgeIt;
131   
132    const Graph& G;
133    FlowMap& flow;
134    const CapacityMap& capacity;
135  public:
136    ResGraph2(const Graph& _G, FlowMap& _flow,
137             const CapacityMap& _capacity) :
138      G(_G), flow(_flow), capacity(_capacity) { }
139
140    class Edge;
141    class OutEdgeIt;
142    friend class Edge;
143    friend class OutEdgeIt;
144
145    class Edge {
146      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
147    protected:
148      const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
149      //OldSymEdgeIt sym;
150      OldOutEdgeIt out;
151      OldInEdgeIt in;
152      bool out_or_in; //true, iff out
153    public:
154      Edge() : out_or_in(true) { }
155      Number free() const {
156        if (out_or_in) {
157          return (resG->capacity.get(out)-resG->flow.get(out));
158        } else {
159          return (resG->flow.get(in));
160        }
161      }
162      bool valid() const {
163        return out_or_in && out.valid() || in.valid(); }
164      void augment(Number a) const {
165        if (out_or_in) {
166          resG->flow.set(out, resG->flow.get(out)+a);
167        } else {
168          resG->flow.set(in, resG->flow.get(in)-a);
169        }
170      }
171    };
172
173    class OutEdgeIt : public Edge {
174      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
175    public:
176      OutEdgeIt() { }
177    private:
178      OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
179        resG=&_resG;
180        out=resG->G.template first<OldOutEdgeIt>(v);
181        while( out.valid() && !(free()>0) ) { ++out; }
182        if (!out.valid()) {
183          out_or_in=0;
184          in=resG->G.template first<OldInEdgeIt>(v);
185          while( in.valid() && !(free()>0) ) { ++in; }
186        }
187      }
188    public:
189      OutEdgeIt& operator++() {
190        if (out_or_in) {
191          Node v=resG->G.aNode(out);
192          ++out;
193          while( out.valid() && !(free()>0) ) { ++out; }
194          if (!out.valid()) {
195            out_or_in=0;
196            in=resG->G.template first<OldInEdgeIt>(v);
197            while( in.valid() && !(free()>0) ) { ++in; }
198          }
199        } else {
200          ++in;
201          while( in.valid() && !(free()>0) ) { ++in; }
202        }
203        return *this;
204      }
205    };
206
207    void /*getF*/first(OutEdgeIt& e, Node v) const {
208      e=OutEdgeIt(*this, v);
209    }
210    void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
211   
212    template< typename It >
213    It first() const {
214      It e;
215      /*getF*/first(e);
216      return e;
217    }
218
219    template< typename It >
220    It first(Node v) const {
221      It e;
222      /*getF*/first(e, v);
223      return e;
224    }
225
226    Node tail(Edge e) const {
227      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
228    Node head(Edge e) const {
229      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
230
231    Node aNode(OutEdgeIt e) const {
232      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
233    Node bNode(OutEdgeIt e) const {
234      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
235
236    int id(Node v) const { return G.id(v); }
237
238    template <typename S>
239    class NodeMap {
240      typename Graph::NodeMap<S> node_map;
241    public:
242      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
243      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
244      void set(Node nit, S a) { node_map.set(nit, a); }
245      S get(Node nit) const { return node_map.get(nit); }
246    };
247  };
248
249
250  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
251  class MaxFlow {
252  public:
253    typedef typename Graph::Node Node;
254    typedef typename Graph::Edge Edge;
255    typedef typename Graph::EdgeIt EdgeIt;
256    typedef typename Graph::OutEdgeIt OutEdgeIt;
257    typedef typename Graph::InEdgeIt InEdgeIt;
258
259  private:
260    const Graph* G;
261    Node s;
262    Node t;
263    FlowMap* flow;
264    const CapacityMap* capacity;
265    typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
266    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
267    typedef typename AugGraph::Edge AugEdge;
268
269  public:
270    MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
271      G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
272    bool augmentOnShortestPath() {
273      AugGraph res_graph(*G, *flow, *capacity);
274      bool _augment=false;
275     
276      typedef typename AugGraph::NodeMap<bool> ReachedMap;
277      BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
278      res_bfs.pushAndSetReached(s);
279       
280      typename AugGraph::NodeMap<AugEdge> pred(res_graph);
281      pred.set(s, AugEdge(INVALID));
282     
283      typename AugGraph::NodeMap<Number> free(res_graph);
284       
285      //searching for augmenting path
286      while ( !res_bfs.finished() ) {
287        AugOutEdgeIt e=res_bfs;
288        if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
289          Node v=res_graph.tail(e);
290          Node w=res_graph.head(e);
291          pred.set(w, e);
292          if (res_graph.valid(pred.get(v))) {
293            free.set(w, std::min(free.get(v), res_graph.free(e)));
294          } else {
295            free.set(w, res_graph.free(e));
296          }
297          if (res_graph.head(e)==t) { _augment=true; break; }
298        }
299       
300        ++res_bfs;
301      } //end of searching augmenting path
302
303      if (_augment) {
304        Node n=t;
305        Number augment_value=free.get(t);
306        while (res_graph.valid(pred.get(n))) {
307          AugEdge e=pred.get(n);
308          res_graph.augment(e, augment_value);
309          n=res_graph.tail(e);
310        }
311      }
312
313      return _augment;
314    }
315
316//     template<typename MutableGraph> bool augmentOnBlockingFlow() {     
317//       bool _augment=false;
318
319//       AugGraph res_graph(*G, *flow, *capacity);
320
321//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
322//       BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
323
324//       bfs.pushAndSetReached(s);
325//       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
326//       while ( !bfs.finished() ) {
327//      AugOutEdgeIt e=bfs;
328//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
329//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
330//      }
331       
332//      ++bfs;
333//       } //computing distances from s in the residual graph
334
335//       MutableGraph F;
336//       typename AugGraph::NodeMap<typename MutableGraph::Node>
337//      res_graph_to_F(res_graph);
338//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
339//      res_graph_to_F.set(n, F.addNode());
340//       }
341     
342//       typename MutableGraph::Node sF=res_graph_to_F.get(s);
343//       typename MutableGraph::Node tF=res_graph_to_F.get(t);
344
345//       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
346//       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
347
348//       //Making F to the graph containing the edges of the residual graph
349//       //which are in some shortest paths
350//       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
351//      if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
352//        typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
353//        original_edge.update();
354//        original_edge.set(f, e);
355//        residual_capacity.update();
356//        residual_capacity.set(f, res_graph.free(e));
357//      }
358//       }
359
360//       bool __augment=true;
361
362//       while (__augment) {
363//      __augment=false;
364//      //computing blocking flow with dfs
365//      typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
366//      DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
367//      typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
368//      pred.set(sF, typename MutableGraph::Edge(INVALID));
369//      //invalid iterators for sources
370
371//      typename MutableGraph::NodeMap<Number> free(F);
372
373//      dfs.pushAndSetReached(sF);     
374//      while (!dfs.finished()) {
375//        ++dfs;
376//        if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
377//          if (dfs.isBNodeNewlyReached()) {
378//            typename MutableGraph::Node v=F.aNode(dfs);
379//            typename MutableGraph::Node w=F.bNode(dfs);
380//            pred.set(w, dfs);
381//            if (F.valid(pred.get(v))) {
382//              free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
383//            } else {
384//              free.set(w, residual_capacity.get(dfs));
385//            }
386//            if (w==tF) {
387//              __augment=true;
388//              _augment=true;
389//              break;
390//            }
391             
392//          } else {
393//            F.erase(typename MutableGraph::OutEdgeIt(dfs));
394//          }
395//        }
396//      }
397
398//      if (__augment) {
399//        typename MutableGraph::Node n=tF;
400//        Number augment_value=free.get(tF);
401//        while (F.valid(pred.get(n))) {
402//          typename MutableGraph::Edge e=pred.get(n);
403//          res_graph.augment(original_edge.get(e), augment_value);
404//          n=F.tail(e);
405//          if (residual_capacity.get(e)==augment_value)
406//            F.erase(e);
407//          else
408//            residual_capacity.set(e, residual_capacity.get(e)-augment_value);
409//        }
410//      }
411       
412//       }
413           
414//       return _augment;
415//     }
416
417    template<typename GraphWrapper>
418    class DistanceMap {
419    protected:
420      GraphWrapper gw;
421      typename GraphWrapper::NodeMap<int> dist;
422    public:
423      DistanceMap(GraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
424      //NodeMap(const ListGraph& _G, T a) :
425      //G(_G), container(G.node_id, a) { }
426      void set(const typename GraphWrapper::Node& n, int a) { dist[n]=a; }
427      int get(const typename GraphWrapper::Node& n) const { return dist[n]; }
428      bool get(const typename GraphWrapper::Edge& e) const {
429        return (dist.get(gw.tail(e))<dist.get(gw.head(e)));
430      }
431      //typename std::vector<T>::reference operator[](Node n) {
432      //return container[/*G.id(n)*/n.node->id]; }
433      //typename std::vector<T>::const_reference operator[](Node n) const {
434      //return container[/*G.id(n)*/n.node->id];
435    };
436
437    template<typename MutableGraph> bool augmentOnBlockingFlow() {     
438      bool _augment=false;
439
440      AugGraph res_graph(*G, *flow, *capacity);
441
442      typedef typename AugGraph::NodeMap<bool> ReachedMap;
443      BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
444
445      bfs.pushAndSetReached(s);
446      //typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
447      DistanceMap<AugGraph> dist(res_graph);
448      while ( !bfs.finished() ) {
449        AugOutEdgeIt e=bfs;
450        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
451          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
452        }
453        ++bfs;
454      } //computing distances from s in the residual graph
455
456//       MutableGraph F;
457//       typename AugGraph::NodeMap<typename MutableGraph::Node>
458//      res_graph_to_F(res_graph);
459//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
460//      res_graph_to_F.set(n, F.addNode());
461//       }
462     
463//       typename MutableGraph::Node sF=res_graph_to_F.get(s);
464//       typename MutableGraph::Node tF=res_graph_to_F.get(t);
465
466//       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
467//       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
468
469//       //Making F to the graph containing the edges of the residual graph
470//       //which are in some shortest paths
471//       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
472//      if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
473//        typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
474//        original_edge.update();
475//        original_edge.set(f, e);
476//        residual_capacity.update();
477//        residual_capacity.set(f, res_graph.free(e));
478//      }
479//       }
480
481      MutableGraph F;
482      typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph;
483      FilterResGraph filter_res_graph(res_graph, dist);
484      typename AugGraph::NodeMap<typename MutableGraph::Node>
485        res_graph_to_F(res_graph);
486      for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
487        res_graph_to_F.set(n, F.addNode());
488      }
489     
490      typename MutableGraph::Node sF=res_graph_to_F.get(s);
491      typename MutableGraph::Node tF=res_graph_to_F.get(t);
492
493      typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
494      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
495
496      //Making F to the graph containing the edges of the residual graph
497      //which are in some shortest paths
498      for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
499        if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
500          typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
501          original_edge.update();
502          original_edge.set(f, e);
503          residual_capacity.update();
504          residual_capacity.set(f, res_graph.free(e));
505        }
506      }
507
508      bool __augment=true;
509
510      while (__augment) {
511        __augment=false;
512        //computing blocking flow with dfs
513        typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
514        DfsIterator5< TrivGraphWrapper<MutableGraph>, BlockingReachedMap > dfs(F);
515        typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
516        pred.set(sF, typename MutableGraph::Edge(INVALID));
517        //invalid iterators for sources
518
519        typename MutableGraph::NodeMap<Number> free(F);
520
521        dfs.pushAndSetReached(sF);     
522        while (!dfs.finished()) {
523          ++dfs;
524          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
525            if (dfs.isBNodeNewlyReached()) {
526              typename MutableGraph::Node v=F.aNode(dfs);
527              typename MutableGraph::Node w=F.bNode(dfs);
528              pred.set(w, dfs);
529              if (F.valid(pred.get(v))) {
530                free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
531              } else {
532                free.set(w, residual_capacity.get(dfs));
533              }
534              if (w==tF) {
535                __augment=true;
536                _augment=true;
537                break;
538              }
539             
540            } else {
541              F.erase(typename MutableGraph::OutEdgeIt(dfs));
542            }
543          }
544        }
545
546        if (__augment) {
547          typename MutableGraph::Node n=tF;
548          Number augment_value=free.get(tF);
549          while (F.valid(pred.get(n))) {
550            typename MutableGraph::Edge e=pred.get(n);
551            res_graph.augment(original_edge.get(e), augment_value);
552            n=F.tail(e);
553            if (residual_capacity.get(e)==augment_value)
554              F.erase(e);
555            else
556              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
557          }
558        }
559       
560      }
561           
562      return _augment;
563    }
564
565    template<typename MutableGraph> bool augmentOnBlockingFlow1() {     
566      bool _augment=false;
567
568      AugGraph res_graph(*G, *flow, *capacity);
569
570      //bfs for distances on the residual graph
571      typedef typename AugGraph::NodeMap<bool> ReachedMap;
572      BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
573      bfs.pushAndSetReached(s);
574      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
575
576      //F will contain the physical copy of the residual graph
577      //with the set of edges which areon shortest paths
578      MutableGraph F;
579      typename AugGraph::NodeMap<typename MutableGraph::Node>
580        res_graph_to_F(res_graph);
581      for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
582        res_graph_to_F.set(n, F.addNode());
583      }
584      typename MutableGraph::Node sF=res_graph_to_F.get(s);
585      typename MutableGraph::Node tF=res_graph_to_F.get(t);
586      typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
587      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
588
589      while ( !bfs.finished() ) {
590        AugOutEdgeIt e=bfs;
591        if (res_graph.valid(e)) {
592          if (bfs.isBNodeNewlyReached()) {
593            dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
594            typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
595            original_edge.update();
596            original_edge.set(f, e);
597            residual_capacity.update();
598            residual_capacity.set(f, res_graph.free(e));
599          } else {
600            if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
601              typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
602              original_edge.update();
603              original_edge.set(f, e);
604              residual_capacity.update();
605              residual_capacity.set(f, res_graph.free(e));
606            }
607          }
608        }
609        ++bfs;
610      } //computing distances from s in the residual graph
611
612      bool __augment=true;
613
614      while (__augment) {
615        __augment=false;
616        //computing blocking flow with dfs
617        typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
618        DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
619        typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
620        pred.set(sF, typename MutableGraph::Edge(INVALID));
621        //invalid iterators for sources
622
623        typename MutableGraph::NodeMap<Number> free(F);
624
625        dfs.pushAndSetReached(sF);     
626        while (!dfs.finished()) {
627          ++dfs;
628          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
629            if (dfs.isBNodeNewlyReached()) {
630              typename MutableGraph::Node v=F.aNode(dfs);
631              typename MutableGraph::Node w=F.bNode(dfs);
632              pred.set(w, dfs);
633              if (F.valid(pred.get(v))) {
634                free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
635              } else {
636                free.set(w, residual_capacity.get(dfs));
637              }
638              if (w==tF) {
639                __augment=true;
640                _augment=true;
641                break;
642              }
643             
644            } else {
645              F.erase(typename MutableGraph::OutEdgeIt(dfs));
646            }
647          }
648        }
649
650        if (__augment) {
651          typename MutableGraph::Node n=tF;
652          Number augment_value=free.get(tF);
653          while (F.valid(pred.get(n))) {
654            typename MutableGraph::Edge e=pred.get(n);
655            res_graph.augment(original_edge.get(e), augment_value);
656            n=F.tail(e);
657            if (residual_capacity.get(e)==augment_value)
658              F.erase(e);
659            else
660              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
661          }
662        }
663       
664      }
665           
666      return _augment;
667    }
668    bool augmentOnBlockingFlow2() {
669      bool _augment=false;
670
671      //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
672      typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
673      typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
674      typedef typename EAugGraph::Edge EAugEdge;
675
676      EAugGraph res_graph(*G, *flow, *capacity);
677
678      //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
679      BfsIterator5<
680        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
681        /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
682        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
683     
684      bfs.pushAndSetReached(s);
685
686      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
687        NodeMap<int>& dist=res_graph.dist;
688
689      while ( !bfs.finished() ) {
690        typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
691        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
692          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
693        }
694        ++bfs; 
695      } //computing distances from s in the residual graph
696
697      bool __augment=true;
698
699      while (__augment) {
700
701        __augment=false;
702        //computing blocking flow with dfs
703        typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
704        DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
705          dfs(res_graph);
706        typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
707        pred.set(s, EAugEdge(INVALID));
708        //invalid iterators for sources
709
710        typename EAugGraph::NodeMap<Number> free(res_graph);
711
712        dfs.pushAndSetReached(s);
713        while (!dfs.finished()) {
714          ++dfs;
715          if (res_graph.valid(EAugOutEdgeIt(dfs))) {
716            if (dfs.isBNodeNewlyReached()) {
717         
718              typename EAugGraph::Node v=res_graph.aNode(dfs);
719              typename EAugGraph::Node w=res_graph.bNode(dfs);
720
721              pred.set(w, EAugOutEdgeIt(dfs));
722              if (res_graph.valid(pred.get(v))) {
723                free.set(w, std::min(free.get(v), res_graph.free(dfs)));
724              } else {
725                free.set(w, res_graph.free(dfs));
726              }
727             
728              if (w==t) {
729                __augment=true;
730                _augment=true;
731                break;
732              }
733            } else {
734              res_graph.erase(dfs);
735            }
736          }
737
738        }
739
740        if (__augment) {
741          typename EAugGraph::Node n=t;
742          Number augment_value=free.get(t);
743          while (res_graph.valid(pred.get(n))) {
744            EAugEdge e=pred.get(n);
745            res_graph.augment(e, augment_value);
746            n=res_graph.tail(e);
747            if (res_graph.free(e)==0)
748              res_graph.erase(e);
749          }
750        }
751     
752      }
753           
754      return _augment;
755    }
756    void run() {
757      //int num_of_augmentations=0;
758      while (augmentOnShortestPath()) {
759        //while (augmentOnBlockingFlow<MutableGraph>()) {
760        //std::cout << ++num_of_augmentations << " ";
761        //std::cout<<std::endl;
762      }
763    }
764    template<typename MutableGraph> void run() {
765      //int num_of_augmentations=0;
766      //while (augmentOnShortestPath()) {
767        while (augmentOnBlockingFlow<MutableGraph>()) {
768        //std::cout << ++num_of_augmentations << " ";
769        //std::cout<<std::endl;
770      }
771    }
772    Number flowValue() {
773      Number a=0;
774      OutEdgeIt e;
775      for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) {
776        a+=flow->get(e);
777      }
778      return a;
779    }
780  };
781
782
783  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
784  class MaxMatching {
785  public:
786    typedef typename Graph::Node Node;
787    typedef typename Graph::NodeIt NodeIt;
788    typedef typename Graph::Edge Edge;
789    typedef typename Graph::EdgeIt EdgeIt;
790    typedef typename Graph::OutEdgeIt OutEdgeIt;
791    typedef typename Graph::InEdgeIt InEdgeIt;
792
793    typedef typename Graph::NodeMap<bool> SMap;
794    typedef typename Graph::NodeMap<bool> TMap;
795  private:
796    const Graph* G;
797    SMap* S;
798    TMap* T;
799    //Node s;
800    //Node t;
801    FlowMap* flow;
802    const CapacityMap* capacity;
803    typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
804    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
805    typedef typename AugGraph::Edge AugEdge;
806    typename Graph::NodeMap<int> used; //0
807
808  public:
809    MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
810      G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
811    bool augmentOnShortestPath() {
812      AugGraph res_graph(*G, *flow, *capacity);
813      bool _augment=false;
814     
815      typedef typename AugGraph::NodeMap<bool> ReachedMap;
816      BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
817      typename AugGraph::NodeMap<AugEdge> pred(res_graph);
818      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
819        if ((S->get(s)) && (used.get(s)<1) ) {
820          //Number u=0;
821          //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
822          //u+=flow->get(e);
823          //if (u<1) {
824            res_bfs.pushAndSetReached(s);
825            pred.set(s, AugEdge(INVALID));
826            //}
827        }
828      }
829     
830      typename AugGraph::NodeMap<Number> free(res_graph);
831       
832      Node n;
833      //searching for augmenting path
834      while ( !res_bfs.finished() ) {
835        AugOutEdgeIt e=res_bfs;
836        if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
837          Node v=res_graph.tail(e);
838          Node w=res_graph.head(e);
839          pred.set(w, e);
840          if (res_graph.valid(pred.get(v))) {
841            free.set(w, std::min(free.get(v), res_graph.free(e)));
842          } else {
843            free.set(w, res_graph.free(e));
844          }
845          n=res_graph.head(e);
846          if (T->get(n) && (used.get(n)<1) ) {
847            //Number u=0;
848            //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
849            //u+=flow->get(f);
850            //if (u<1) {
851              _augment=true;
852              break;
853              //}
854          }
855        }
856       
857        ++res_bfs;
858      } //end of searching augmenting path
859
860      if (_augment) {
861        //Node n=t;
862        used.set(n, 1); //mind2 vegen jav
863        Number augment_value=free.get(n);
864        while (res_graph.valid(pred.get(n))) {
865          AugEdge e=pred.get(n);
866          res_graph.augment(e, augment_value);
867          n=res_graph.tail(e);
868        }
869        used.set(n, 1); //mind2 vegen jav
870      }
871
872      return _augment;
873    }
874
875//     template<typename MutableGraph> bool augmentOnBlockingFlow() {     
876//       bool _augment=false;
877
878//       AugGraph res_graph(*G, *flow, *capacity);
879
880//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
881//       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
882
883
884
885
886
887//       //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
888//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
889//      if (S->get(s)) {
890//        Number u=0;
891//        for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
892//          u+=flow->get(e);
893//        if (u<1) {
894//          res_bfs.pushAndSetReached(s);
895//          //pred.set(s, AugEdge(INVALID));
896//        }
897//      }
898//       }
899
900
901
902
903//       //bfs.pushAndSetReached(s);
904//       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
905//       while ( !bfs.finished() ) {
906//      AugOutEdgeIt e=bfs;
907//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
908//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
909//      }
910       
911//      ++bfs;
912//       } //computing distances from s in the residual graph
913
914//       MutableGraph F;
915//       typename AugGraph::NodeMap<typename MutableGraph::Node>
916//      res_graph_to_F(res_graph);
917//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
918//      res_graph_to_F.set(n, F.addNode());
919//       }
920     
921//       typename MutableGraph::Node sF=res_graph_to_F.get(s);
922//       typename MutableGraph::Node tF=res_graph_to_F.get(t);
923
924//       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
925//       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
926
927//       //Making F to the graph containing the edges of the residual graph
928//       //which are in some shortest paths
929//       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
930//      if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
931//        typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
932//        original_edge.update();
933//        original_edge.set(f, e);
934//        residual_capacity.update();
935//        residual_capacity.set(f, res_graph.free(e));
936//      }
937//       }
938
939//       bool __augment=true;
940
941//       while (__augment) {
942//      __augment=false;
943//      //computing blocking flow with dfs
944//      typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
945//      DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
946//      typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
947//      pred.set(sF, typename MutableGraph::Edge(INVALID));
948//      //invalid iterators for sources
949
950//      typename MutableGraph::NodeMap<Number> free(F);
951
952//      dfs.pushAndSetReached(sF);     
953//      while (!dfs.finished()) {
954//        ++dfs;
955//        if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
956//          if (dfs.isBNodeNewlyReached()) {
957//            typename MutableGraph::Node v=F.aNode(dfs);
958//            typename MutableGraph::Node w=F.bNode(dfs);
959//            pred.set(w, dfs);
960//            if (F.valid(pred.get(v))) {
961//              free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
962//            } else {
963//              free.set(w, residual_capacity.get(dfs));
964//            }
965//            if (w==tF) {
966//              __augment=true;
967//              _augment=true;
968//              break;
969//            }
970             
971//          } else {
972//            F.erase(typename MutableGraph::OutEdgeIt(dfs));
973//          }
974//        }
975//      }
976
977//      if (__augment) {
978//        typename MutableGraph::Node n=tF;
979//        Number augment_value=free.get(tF);
980//        while (F.valid(pred.get(n))) {
981//          typename MutableGraph::Edge e=pred.get(n);
982//          res_graph.augment(original_edge.get(e), augment_value);
983//          n=F.tail(e);
984//          if (residual_capacity.get(e)==augment_value)
985//            F.erase(e);
986//          else
987//            residual_capacity.set(e, residual_capacity.get(e)-augment_value);
988//        }
989//      }
990       
991//       }
992           
993//       return _augment;
994//     }
995    bool augmentOnBlockingFlow2() {
996      bool _augment=false;
997
998      //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
999      typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
1000      typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
1001      typedef typename EAugGraph::Edge EAugEdge;
1002
1003      EAugGraph res_graph(*G, *flow, *capacity);
1004
1005      //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
1006      BfsIterator5<
1007        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
1008        /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
1009        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
1010
1011
1012      //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1013      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1014        if (S->get(s)) {
1015          Number u=0;
1016          for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1017            u+=flow->get(e);
1018          if (u<1) {
1019            bfs.pushAndSetReached(s);
1020            //pred.set(s, AugEdge(INVALID));
1021          }
1022        }
1023      }
1024
1025     
1026      //bfs.pushAndSetReached(s);
1027
1028      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
1029        NodeMap<int>& dist=res_graph.dist;
1030
1031      while ( !bfs.finished() ) {
1032        typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1033        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1034          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1035        }
1036        ++bfs; 
1037      } //computing distances from s in the residual graph
1038
1039      bool __augment=true;
1040
1041      while (__augment) {
1042
1043        __augment=false;
1044        //computing blocking flow with dfs
1045        typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
1046        DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
1047          dfs(res_graph);
1048        typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
1049        //pred.set(s, EAugEdge(INVALID));
1050        //invalid iterators for sources
1051
1052        typename EAugGraph::NodeMap<Number> free(res_graph);
1053
1054
1055        //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1056      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1057        if (S->get(s)) {
1058          Number u=0;
1059          for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1060            u+=flow->get(e);
1061          if (u<1) {
1062            dfs.pushAndSetReached(s);
1063            //pred.set(s, AugEdge(INVALID));
1064          }
1065        }
1066      }
1067
1068
1069
1070      //dfs.pushAndSetReached(s);
1071      typename EAugGraph::Node n;
1072        while (!dfs.finished()) {
1073          ++dfs;
1074          if (res_graph.valid(EAugOutEdgeIt(dfs))) {
1075            if (dfs.isBNodeNewlyReached()) {
1076         
1077              typename EAugGraph::Node v=res_graph.aNode(dfs);
1078              typename EAugGraph::Node w=res_graph.bNode(dfs);
1079
1080              pred.set(w, EAugOutEdgeIt(dfs));
1081              if (res_graph.valid(pred.get(v))) {
1082                free.set(w, std::min(free.get(v), res_graph.free(dfs)));
1083              } else {
1084                free.set(w, res_graph.free(dfs));
1085              }
1086             
1087              n=w;
1088              if (T->get(w)) {
1089                Number u=0;
1090                for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1091                  u+=flow->get(f);
1092                if (u<1) {
1093                  __augment=true;
1094                  _augment=true;
1095                  break;
1096                }
1097              }
1098            } else {
1099              res_graph.erase(dfs);
1100            }
1101          }
1102
1103        }
1104
1105        if (__augment) {
1106          // typename EAugGraph::Node n=t;
1107          Number augment_value=free.get(n);
1108          while (res_graph.valid(pred.get(n))) {
1109            EAugEdge e=pred.get(n);
1110            res_graph.augment(e, augment_value);
1111            n=res_graph.tail(e);
1112            if (res_graph.free(e)==0)
1113              res_graph.erase(e);
1114          }
1115        }
1116     
1117      }
1118           
1119      return _augment;
1120    }
1121    void run() {
1122      //int num_of_augmentations=0;
1123      while (augmentOnShortestPath()) {
1124        //while (augmentOnBlockingFlow<MutableGraph>()) {
1125        //std::cout << ++num_of_augmentations << " ";
1126        //std::cout<<std::endl;
1127      }
1128    }
1129//     template<typename MutableGraph> void run() {
1130//       //int num_of_augmentations=0;
1131//       //while (augmentOnShortestPath()) {
1132//      while (augmentOnBlockingFlow<MutableGraph>()) {
1133//      //std::cout << ++num_of_augmentations << " ";
1134//      //std::cout<<std::endl;
1135//       }
1136//     }
1137    Number flowValue() {
1138      Number a=0;
1139      EdgeIt e;
1140      for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
1141        a+=flow->get(e);
1142      }
1143      return a;
1144    }
1145  };
1146
1147
1148
1149
1150
1151 
1152//   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1153//   class MaxFlow2 {
1154//   public:
1155//     typedef typename Graph::Node Node;
1156//     typedef typename Graph::Edge Edge;
1157//     typedef typename Graph::EdgeIt EdgeIt;
1158//     typedef typename Graph::OutEdgeIt OutEdgeIt;
1159//     typedef typename Graph::InEdgeIt InEdgeIt;
1160//   private:
1161//     const Graph& G;
1162//     std::list<Node>& S;
1163//     std::list<Node>& T;
1164//     FlowMap& flow;
1165//     const CapacityMap& capacity;
1166//     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1167//     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1168//     typedef typename AugGraph::Edge AugEdge;
1169//     typename Graph::NodeMap<bool> SMap;
1170//     typename Graph::NodeMap<bool> TMap;
1171//   public:
1172//     MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
1173//       for(typename std::list<Node>::const_iterator i=S.begin();
1174//        i!=S.end(); ++i) {
1175//      SMap.set(*i, true);
1176//       }
1177//       for (typename std::list<Node>::const_iterator i=T.begin();
1178//         i!=T.end(); ++i) {
1179//      TMap.set(*i, true);
1180//       }
1181//     }
1182//     bool augment() {
1183//       AugGraph res_graph(G, flow, capacity);
1184//       bool _augment=false;
1185//       Node reached_t_node;
1186     
1187//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
1188//       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1189//       for(typename std::list<Node>::const_iterator i=S.begin();
1190//        i!=S.end(); ++i) {
1191//      res_bfs.pushAndSetReached(*i);
1192//       }
1193//       //res_bfs.pushAndSetReached(s);
1194       
1195//       typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1196//       //filled up with invalid iterators
1197     
1198//       typename AugGraph::NodeMap<Number> free(res_graph);
1199       
1200//       //searching for augmenting path
1201//       while ( !res_bfs.finished() ) {
1202//      AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
1203//      if (e.valid() && res_bfs.isBNodeNewlyReached()) {
1204//        Node v=res_graph.tail(e);
1205//        Node w=res_graph.head(e);
1206//        pred.set(w, e);
1207//        if (pred.get(v).valid()) {
1208//          free.set(w, std::min(free.get(v), e.free()));
1209//        } else {
1210//          free.set(w, e.free());
1211//        }
1212//        if (TMap.get(res_graph.head(e))) {
1213//          _augment=true;
1214//          reached_t_node=res_graph.head(e);
1215//          break;
1216//        }
1217//      }
1218       
1219//      ++res_bfs;
1220//       } //end of searching augmenting path
1221
1222//       if (_augment) {
1223//      Node n=reached_t_node;
1224//      Number augment_value=free.get(reached_t_node);
1225//      while (pred.get(n).valid()) {
1226//        AugEdge e=pred.get(n);
1227//        e.augment(augment_value);
1228//        n=res_graph.tail(e);
1229//      }
1230//       }
1231
1232//       return _augment;
1233//     }
1234//     void run() {
1235//       while (augment()) { }
1236//     }
1237//     Number flowValue() {
1238//       Number a=0;
1239//       for(typename std::list<Node>::const_iterator i=S.begin();
1240//        i!=S.end(); ++i) {
1241//      for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
1242//        a+=flow.get(e);
1243//      }
1244//      for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
1245//        a-=flow.get(e);
1246//      }
1247//       }
1248//       return a;
1249//     }
1250//   };
1251
1252
1253
1254} // namespace hugo
1255
1256#endif //HUGO_EDMONDS_KARP_H
Note: See TracBrowser for help on using the repository browser.