COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 266:4cec4981dfd1 in lemon-0.x for src/work/edmonds_karp.h


Ignore:
Timestamp:
03/30/04 19:16:53 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@372
Message:

GraphWrappers?, MapWrappers?

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/work/edmonds_karp.h

    r265 r266  
    248248
    249249
    250   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     250  template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
    251251  class MaxFlow {
    252252  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;
     253    typedef typename GraphWrapper::Node Node;
     254    typedef typename GraphWrapper::Edge Edge;
     255    typedef typename GraphWrapper::EdgeIt EdgeIt;
     256    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
     257    typedef typename GraphWrapper::InEdgeIt InEdgeIt;
    258258
    259259  private:
    260     const Graph* G;
     260    //const Graph* G;
     261    GraphWrapper gw;
    261262    Node s;
    262263    Node t;
    263264    FlowMap* flow;
    264265    const CapacityMap* capacity;
    265     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
     266    typedef ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap >
     267    AugGraph;
    266268    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    267269    typedef typename AugGraph::Edge AugEdge;
    268270
    269271  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    MaxFlow(const GraphWrapper& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
     273      gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
    272274    bool augmentOnShortestPath() {
    273       AugGraph res_graph(*G, *flow, *capacity);
     275      AugGraph res_graph(gw, *flow, *capacity);
    274276      bool _augment=false;
    275277     
    … …  
    314316    }
    315317
    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>
     318    template<typename MapGraphWrapper>
    418319    class DistanceMap {
    419320    protected:
    420       GraphWrapper gw;
    421       typename GraphWrapper::NodeMap<int> dist;
     321      MapGraphWrapper gw;
     322      typename MapGraphWrapper::NodeMap<int> dist;
    422323    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 {
     324      DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
     325      void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
     326      int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; }
     327      bool get(const typename MapGraphWrapper::Edge& e) const {
    429328        return (dist.get(gw.tail(e))<dist.get(gw.head(e)));
    430329      }
    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];
    435330    };
    436331
    … …  
    438333      bool _augment=false;
    439334
    440       AugGraph res_graph(*G, *flow, *capacity);
     335      AugGraph res_graph(gw, *flow, *capacity);
    441336
    442337      typedef typename AugGraph::NodeMap<bool> ReachedMap;
    … …  
    454349      } //computing distances from s in the residual graph
    455350
    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 
    481351      MutableGraph F;
    482       //typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph;
    483       //FilterResGraph filter_res_graph(res_graph, dist);
     352      typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph;
     353      FilterResGraph filter_res_graph(res_graph, dist);
    484354      typename AugGraph::NodeMap<typename MutableGraph::Node>
    485355        res_graph_to_F(res_graph);
    … …  
    496366      //Making F to the graph containing the edges of the residual graph
    497367      //which are in some shortest paths
    498       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>();
    499           res_graph.valid(e);
    500           res_graph.next(e)) {
    501         if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
     368      for(typename FilterResGraph::EdgeIt e=filter_res_graph.template first<typename FilterResGraph::EdgeIt>(); filter_res_graph.valid(e); filter_res_graph.next(e)) {
     369        //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
    502370          typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    503371          original_edge.update();
    … …  
    505373          residual_capacity.update();
    506374          residual_capacity.set(f, res_graph.free(e));
    507         }
     375          //}
    508376      }
    509377
    … …  
    565433    }
    566434
    567     template<typename MutableGraph> bool augmentOnBlockingFlow1() {     
    568       bool _augment=false;
    569 
    570       AugGraph res_graph(*G, *flow, *capacity);
    571 
    572       //bfs for distances on the residual graph
    573       typedef typename AugGraph::NodeMap<bool> ReachedMap;
    574       BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
    575       bfs.pushAndSetReached(s);
    576       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
    577 
    578       //F will contain the physical copy of the residual graph
    579       //with the set of edges which areon shortest paths
    580       MutableGraph F;
    581       typename AugGraph::NodeMap<typename MutableGraph::Node>
    582         res_graph_to_F(res_graph);
    583       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
    584         res_graph_to_F.set(n, F.addNode());
    585       }
    586       typename MutableGraph::Node sF=res_graph_to_F.get(s);
    587       typename MutableGraph::Node tF=res_graph_to_F.get(t);
    588       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
    589       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
    590 
    591       while ( !bfs.finished() ) {
    592         AugOutEdgeIt e=bfs;
    593         if (res_graph.valid(e)) {
    594           if (bfs.isBNodeNewlyReached()) {
    595             dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    596             typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    597             original_edge.update();
    598             original_edge.set(f, e);
    599             residual_capacity.update();
    600             residual_capacity.set(f, res_graph.free(e));
    601           } else {
    602             if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
    603               typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    604               original_edge.update();
    605               original_edge.set(f, e);
    606               residual_capacity.update();
    607               residual_capacity.set(f, res_graph.free(e));
    608             }
    609           }
    610         }
    611         ++bfs;
    612       } //computing distances from s in the residual graph
    613 
    614       bool __augment=true;
    615 
    616       while (__augment) {
    617         __augment=false;
    618         //computing blocking flow with dfs
    619         typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
    620         DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
    621         typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
    622         pred.set(sF, typename MutableGraph::Edge(INVALID));
    623         //invalid iterators for sources
    624 
    625         typename MutableGraph::NodeMap<Number> free(F);
    626 
    627         dfs.pushAndSetReached(sF);     
    628         while (!dfs.finished()) {
    629           ++dfs;
    630           if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
    631             if (dfs.isBNodeNewlyReached()) {
    632               typename MutableGraph::Node v=F.aNode(dfs);
    633               typename MutableGraph::Node w=F.bNode(dfs);
    634               pred.set(w, dfs);
    635               if (F.valid(pred.get(v))) {
    636                 free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
    637               } else {
    638                 free.set(w, residual_capacity.get(dfs));
    639               }
    640               if (w==tF) {
    641                 __augment=true;
    642                 _augment=true;
    643                 break;
    644               }
    645              
    646             } else {
    647               F.erase(typename MutableGraph::OutEdgeIt(dfs));
    648             }
    649           }
    650         }
    651 
    652         if (__augment) {
    653           typename MutableGraph::Node n=tF;
    654           Number augment_value=free.get(tF);
    655           while (F.valid(pred.get(n))) {
    656             typename MutableGraph::Edge e=pred.get(n);
    657             res_graph.augment(original_edge.get(e), augment_value);
    658             n=F.tail(e);
    659             if (residual_capacity.get(e)==augment_value)
    660               F.erase(e);
    661             else
    662               residual_capacity.set(e, residual_capacity.get(e)-augment_value);
    663           }
    664         }
    665        
    666       }
    667            
    668       return _augment;
    669     }
    670     bool augmentOnBlockingFlow2() {
    671       bool _augment=false;
    672 
    673       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
    674       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
    675       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
    676       typedef typename EAugGraph::Edge EAugEdge;
    677 
    678       EAugGraph res_graph(*G, *flow, *capacity);
    679 
    680       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
    681       BfsIterator5<
    682         ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
    683         /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
    684         ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
    685      
    686       bfs.pushAndSetReached(s);
    687 
    688       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
    689         NodeMap<int>& dist=res_graph.dist;
    690 
    691       while ( !bfs.finished() ) {
    692         typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
    693         if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    694           dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    695         }
    696         ++bfs; 
    697       } //computing distances from s in the residual graph
    698 
    699       bool __augment=true;
    700 
    701       while (__augment) {
    702 
    703         __augment=false;
    704         //computing blocking flow with dfs
    705         typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
    706         DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
    707           dfs(res_graph);
    708         typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
    709         pred.set(s, EAugEdge(INVALID));
    710         //invalid iterators for sources
    711 
    712         typename EAugGraph::NodeMap<Number> free(res_graph);
    713 
    714         dfs.pushAndSetReached(s);
    715         while (!dfs.finished()) {
    716           ++dfs;
    717           if (res_graph.valid(EAugOutEdgeIt(dfs))) {
    718             if (dfs.isBNodeNewlyReached()) {
    719          
    720               typename EAugGraph::Node v=res_graph.aNode(dfs);
    721               typename EAugGraph::Node w=res_graph.bNode(dfs);
    722 
    723               pred.set(w, EAugOutEdgeIt(dfs));
    724               if (res_graph.valid(pred.get(v))) {
    725                 free.set(w, std::min(free.get(v), res_graph.free(dfs)));
    726               } else {
    727                 free.set(w, res_graph.free(dfs));
    728               }
    729              
    730               if (w==t) {
    731                 __augment=true;
    732                 _augment=true;
    733                 break;
    734               }
    735             } else {
    736               res_graph.erase(dfs);
    737             }
    738           }
    739 
    740         }
    741 
    742         if (__augment) {
    743           typename EAugGraph::Node n=t;
    744           Number augment_value=free.get(t);
    745           while (res_graph.valid(pred.get(n))) {
    746             EAugEdge e=pred.get(n);
    747             res_graph.augment(e, augment_value);
    748             n=res_graph.tail(e);
    749             if (res_graph.free(e)==0)
    750               res_graph.erase(e);
    751           }
    752         }
    753      
    754       }
    755            
    756       return _augment;
    757     }
    758     void run() {
    759       //int num_of_augmentations=0;
    760       while (augmentOnShortestPath()) {
    761         //while (augmentOnBlockingFlow<MutableGraph>()) {
    762         //std::cout << ++num_of_augmentations << " ";
    763         //std::cout<<std::endl;
    764       }
    765     }
    766     template<typename MutableGraph> void run() {
    767       //int num_of_augmentations=0;
    768       //while (augmentOnShortestPath()) {
    769         while (augmentOnBlockingFlow<MutableGraph>()) {
    770         //std::cout << ++num_of_augmentations << " ";
    771         //std::cout<<std::endl;
    772       }
    773     }
    774     Number flowValue() {
    775       Number a=0;
    776       OutEdgeIt e;
    777       for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) {
    778         a+=flow->get(e);
    779       }
    780       return a;
    781     }
    782   };
    783 
    784 
    785   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    786   class MaxMatching {
    787   public:
    788     typedef typename Graph::Node Node;
    789     typedef typename Graph::NodeIt NodeIt;
    790     typedef typename Graph::Edge Edge;
    791     typedef typename Graph::EdgeIt EdgeIt;
    792     typedef typename Graph::OutEdgeIt OutEdgeIt;
    793     typedef typename Graph::InEdgeIt InEdgeIt;
    794 
    795     typedef typename Graph::NodeMap<bool> SMap;
    796     typedef typename Graph::NodeMap<bool> TMap;
    797   private:
    798     const Graph* G;
    799     SMap* S;
    800     TMap* T;
    801     //Node s;
    802     //Node t;
    803     FlowMap* flow;
    804     const CapacityMap* capacity;
    805     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
    806     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    807     typedef typename AugGraph::Edge AugEdge;
    808     typename Graph::NodeMap<int> used; //0
    809 
    810   public:
    811     MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
    812       G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
    813     bool augmentOnShortestPath() {
    814       AugGraph res_graph(*G, *flow, *capacity);
    815       bool _augment=false;
    816      
    817       typedef typename AugGraph::NodeMap<bool> ReachedMap;
    818       BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
    819       typename AugGraph::NodeMap<AugEdge> pred(res_graph);
    820       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
    821         if ((S->get(s)) && (used.get(s)<1) ) {
    822           //Number u=0;
    823           //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
    824           //u+=flow->get(e);
    825           //if (u<1) {
    826             res_bfs.pushAndSetReached(s);
    827             pred.set(s, AugEdge(INVALID));
    828             //}
    829         }
    830       }
    831      
    832       typename AugGraph::NodeMap<Number> free(res_graph);
    833        
    834       Node n;
    835       //searching for augmenting path
    836       while ( !res_bfs.finished() ) {
    837         AugOutEdgeIt e=res_bfs;
    838         if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
    839           Node v=res_graph.tail(e);
    840           Node w=res_graph.head(e);
    841           pred.set(w, e);
    842           if (res_graph.valid(pred.get(v))) {
    843             free.set(w, std::min(free.get(v), res_graph.free(e)));
    844           } else {
    845             free.set(w, res_graph.free(e));
    846           }
    847           n=res_graph.head(e);
    848           if (T->get(n) && (used.get(n)<1) ) {
    849             //Number u=0;
    850             //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
    851             //u+=flow->get(f);
    852             //if (u<1) {
    853               _augment=true;
    854               break;
    855               //}
    856           }
    857         }
    858        
    859         ++res_bfs;
    860       } //end of searching augmenting path
    861 
    862       if (_augment) {
    863         //Node n=t;
    864         used.set(n, 1); //mind2 vegen jav
    865         Number augment_value=free.get(n);
    866         while (res_graph.valid(pred.get(n))) {
    867           AugEdge e=pred.get(n);
    868           res_graph.augment(e, augment_value);
    869           n=res_graph.tail(e);
    870         }
    871         used.set(n, 1); //mind2 vegen jav
    872       }
    873 
    874       return _augment;
    875     }
    876 
    877 //     template<typename MutableGraph> bool augmentOnBlockingFlow() {     
     435//     template<typename MutableGraph> bool augmentOnBlockingFlow1() {     
    878436//       bool _augment=false;
    879437
    880438//       AugGraph res_graph(*G, *flow, *capacity);
    881439
     440//       //bfs for distances on the residual graph
    882441//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
    883 //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
    884 
    885 
    886 
    887 
    888 
    889 //       //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
    890 //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
    891 //      if (S->get(s)) {
    892 //        Number u=0;
    893 //        for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
    894 //          u+=flow->get(e);
    895 //        if (u<1) {
    896 //          res_bfs.pushAndSetReached(s);
    897 //          //pred.set(s, AugEdge(INVALID));
    898 //        }
    899 //      }
    900 //       }
    901 
    902 
    903 
    904 
    905 //       //bfs.pushAndSetReached(s);
     442//       BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
     443//       bfs.pushAndSetReached(s);
    906444//       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
    907 //       while ( !bfs.finished() ) {
    908 //      AugOutEdgeIt e=bfs;
    909 //      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    910 //        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    911 //      }
    912        
    913 //      ++bfs;
    914 //       } //computing distances from s in the residual graph
    915 
     445
     446//       //F will contain the physical copy of the residual graph
     447//       //with the set of edges which areon shortest paths
    916448//       MutableGraph F;
    917449//       typename AugGraph::NodeMap<typename MutableGraph::Node>
    … …  
    920452//      res_graph_to_F.set(n, F.addNode());
    921453//       }
    922      
    923454//       typename MutableGraph::Node sF=res_graph_to_F.get(s);
    924455//       typename MutableGraph::Node tF=res_graph_to_F.get(t);
    925 
    926456//       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
    927457//       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
    928458
    929 //       //Making F to the graph containing the edges of the residual graph
    930 //       //which are in some shortest paths
    931 //       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
    932 //      if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
    933 //        typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    934 //        original_edge.update();
    935 //        original_edge.set(f, e);
    936 //        residual_capacity.update();
    937 //        residual_capacity.set(f, res_graph.free(e));
    938 //      }
    939 //       }
     459//       while ( !bfs.finished() ) {
     460//      AugOutEdgeIt e=bfs;
     461//      if (res_graph.valid(e)) {
     462//        if (bfs.isBNodeNewlyReached()) {
     463//          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     464//          typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
     465//          original_edge.update();
     466//          original_edge.set(f, e);
     467//          residual_capacity.update();
     468//          residual_capacity.set(f, res_graph.free(e));
     469//        } else {
     470//          if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
     471//            typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
     472//            original_edge.update();
     473//            original_edge.set(f, e);
     474//            residual_capacity.update();
     475//            residual_capacity.set(f, res_graph.free(e));
     476//          }
     477//        }
     478//      }
     479//      ++bfs;
     480//       } //computing distances from s in the residual graph
    940481
    941482//       bool __augment=true;
    … …  
    944485//      __augment=false;
    945486//      //computing blocking flow with dfs
    946 //      typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
    947 //      DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
     487//      typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
     488//      DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
    948489//      typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
    949490//      pred.set(sF, typename MutableGraph::Edge(INVALID));
    … …  
    995536//       return _augment;
    996537//     }
    997     bool augmentOnBlockingFlow2() {
    998       bool _augment=false;
    999 
    1000       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
    1001       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
    1002       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
    1003       typedef typename EAugGraph::Edge EAugEdge;
    1004 
    1005       EAugGraph res_graph(*G, *flow, *capacity);
    1006 
    1007       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
    1008       BfsIterator5<
    1009         ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
    1010         /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
    1011         ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
    1012 
    1013 
    1014       //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
    1015       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
    1016         if (S->get(s)) {
    1017           Number u=0;
    1018           for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
    1019             u+=flow->get(e);
    1020           if (u<1) {
    1021             bfs.pushAndSetReached(s);
    1022             //pred.set(s, AugEdge(INVALID));
    1023           }
    1024         }
    1025       }
    1026 
     538//     bool augmentOnBlockingFlow2() {
     539//       bool _augment=false;
     540
     541//       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
     542//       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
     543//       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
     544//       typedef typename EAugGraph::Edge EAugEdge;
     545
     546//       EAugGraph res_graph(*G, *flow, *capacity);
     547
     548//       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
     549//       BfsIterator5<
     550//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
     551//      /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
     552//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
    1027553     
    1028       //bfs.pushAndSetReached(s);
    1029 
    1030       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
    1031         NodeMap<int>& dist=res_graph.dist;
    1032 
    1033       while ( !bfs.finished() ) {
    1034         typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
    1035         if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    1036           dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    1037         }
    1038         ++bfs; 
    1039       } //computing distances from s in the residual graph
    1040 
    1041       bool __augment=true;
    1042 
    1043       while (__augment) {
    1044 
    1045         __augment=false;
    1046         //computing blocking flow with dfs
    1047         typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
    1048         DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
    1049           dfs(res_graph);
    1050         typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
    1051         //pred.set(s, EAugEdge(INVALID));
    1052         //invalid iterators for sources
    1053 
    1054         typename EAugGraph::NodeMap<Number> free(res_graph);
    1055 
    1056 
    1057         //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
    1058       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
    1059         if (S->get(s)) {
    1060           Number u=0;
    1061           for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
    1062             u+=flow->get(e);
    1063           if (u<1) {
    1064             dfs.pushAndSetReached(s);
    1065             //pred.set(s, AugEdge(INVALID));
    1066           }
    1067         }
    1068       }
    1069 
    1070 
    1071 
    1072       //dfs.pushAndSetReached(s);
    1073       typename EAugGraph::Node n;
    1074         while (!dfs.finished()) {
    1075           ++dfs;
    1076           if (res_graph.valid(EAugOutEdgeIt(dfs))) {
    1077             if (dfs.isBNodeNewlyReached()) {
     554//       bfs.pushAndSetReached(s);
     555
     556//       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
     557//      NodeMap<int>& dist=res_graph.dist;
     558
     559//       while ( !bfs.finished() ) {
     560//      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
     561//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     562//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     563//      }
     564//      ++bfs; 
     565//       } //computing distances from s in the residual graph
     566
     567//       bool __augment=true;
     568
     569//       while (__augment) {
     570
     571//      __augment=false;
     572//      //computing blocking flow with dfs
     573//      typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
     574//      DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
     575//        dfs(res_graph);
     576//      typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
     577//      pred.set(s, EAugEdge(INVALID));
     578//      //invalid iterators for sources
     579
     580//      typename EAugGraph::NodeMap<Number> free(res_graph);
     581
     582//      dfs.pushAndSetReached(s);
     583//      while (!dfs.finished()) {
     584//        ++dfs;
     585//        if (res_graph.valid(EAugOutEdgeIt(dfs))) {
     586//          if (dfs.isBNodeNewlyReached()) {
    1078587         
    1079               typename EAugGraph::Node v=res_graph.aNode(dfs);
    1080               typename EAugGraph::Node w=res_graph.bNode(dfs);
    1081 
    1082               pred.set(w, EAugOutEdgeIt(dfs));
    1083               if (res_graph.valid(pred.get(v))) {
    1084                 free.set(w, std::min(free.get(v), res_graph.free(dfs)));
    1085               } else {
    1086                 free.set(w, res_graph.free(dfs));
    1087               }
    1088              
    1089               n=w;
    1090               if (T->get(w)) {
    1091                 Number u=0;
    1092                 for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
    1093                   u+=flow->get(f);
    1094                 if (u<1) {
    1095                   __augment=true;
    1096                   _augment=true;
    1097                   break;
    1098                 }
    1099               }
    1100             } else {
    1101               res_graph.erase(dfs);
    1102             }
    1103           }
    1104 
    1105         }
    1106 
    1107         if (__augment) {
    1108           // typename EAugGraph::Node n=t;
    1109           Number augment_value=free.get(n);
    1110           while (res_graph.valid(pred.get(n))) {
    1111             EAugEdge e=pred.get(n);
    1112             res_graph.augment(e, augment_value);
    1113             n=res_graph.tail(e);
    1114             if (res_graph.free(e)==0)
    1115               res_graph.erase(e);
    1116           }
    1117         }
     588//            typename EAugGraph::Node v=res_graph.aNode(dfs);
     589//            typename EAugGraph::Node w=res_graph.bNode(dfs);
     590
     591//            pred.set(w, EAugOutEdgeIt(dfs));
     592//            if (res_graph.valid(pred.get(v))) {
     593//              free.set(w, std::min(free.get(v), res_graph.free(dfs)));
     594//            } else {
     595//              free.set(w, res_graph.free(dfs));
     596//            }
     597             
     598//            if (w==t) {
     599//              __augment=true;
     600//              _augment=true;
     601//              break;
     602//            }
     603//          } else {
     604//            res_graph.erase(dfs);
     605//          }
     606//        }
     607
     608//      }
     609
     610//      if (__augment) {
     611//        typename EAugGraph::Node n=t;
     612//        Number augment_value=free.get(t);
     613//        while (res_graph.valid(pred.get(n))) {
     614//          EAugEdge e=pred.get(n);
     615//          res_graph.augment(e, augment_value);
     616//          n=res_graph.tail(e);
     617//          if (res_graph.free(e)==0)
     618//            res_graph.erase(e);
     619//        }
     620//      }
    1118621     
    1119       }
     622//       }
    1120623           
    1121       return _augment;
    1122     }
    1123     void run() {
    1124       //int num_of_augmentations=0;
    1125       while (augmentOnShortestPath()) {
    1126         //while (augmentOnBlockingFlow<MutableGraph>()) {
    1127         //std::cout << ++num_of_augmentations << " ";
    1128         //std::cout<<std::endl;
    1129       }
    1130     }
     624//       return _augment;
     625//     }
     626//     void run() {
     627//       //int num_of_augmentations=0;
     628//       while (augmentOnShortestPath()) {
     629//      //while (augmentOnBlockingFlow<MutableGraph>()) {
     630//      //std::cout << ++num_of_augmentations << " ";
     631//      //std::cout<<std::endl;
     632//       }
     633//     }
    1131634//     template<typename MutableGraph> void run() {
    1132635//       //int num_of_augmentations=0;
    … …  
    1136639//      //std::cout<<std::endl;
    1137640//       }
    1138 //     } 
     641//     }
    1139642    Number flowValue() {
    1140643      Number a=0;
    1141       EdgeIt e;
    1142       for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
     644      OutEdgeIt e;
     645      for(gw.first(e, s); gw.valid(e); gw.next(e)) {
    1143646        a+=flow->get(e);
    1144647      }
    … …  
    1148651
    1149652
    1150 
    1151 
    1152 
    1153  
    1154653//   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    1155 //   class MaxFlow2 {
     654//   class MaxMatching {
    1156655//   public:
    1157656//     typedef typename Graph::Node Node;
     657//     typedef typename Graph::NodeIt NodeIt;
    1158658//     typedef typename Graph::Edge Edge;
    1159659//     typedef typename Graph::EdgeIt EdgeIt;
    1160660//     typedef typename Graph::OutEdgeIt OutEdgeIt;
    1161661//     typedef typename Graph::InEdgeIt InEdgeIt;
     662
     663//     typedef typename Graph::NodeMap<bool> SMap;
     664//     typedef typename Graph::NodeMap<bool> TMap;
    1162665//   private:
    1163 //     const Graph& G;
    1164 //     std::list<Node>& S;
    1165 //     std::list<Node>& T;
    1166 //     FlowMap& flow;
    1167 //     const CapacityMap& capacity;
     666//     const Graph* G;
     667//     SMap* S;
     668//     TMap* T;
     669//     //Node s;
     670//     //Node t;
     671//     FlowMap* flow;
     672//     const CapacityMap* capacity;
    1168673//     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
    1169674//     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    1170675//     typedef typename AugGraph::Edge AugEdge;
    1171 //     typename Graph::NodeMap<bool> SMap;
    1172 //     typename Graph::NodeMap<bool> TMap;
     676//     typename Graph::NodeMap<int> used; //0
     677
    1173678//   public:
    1174 //     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) {
    1175 //       for(typename std::list<Node>::const_iterator i=S.begin();
    1176 //        i!=S.end(); ++i) {
    1177 //      SMap.set(*i, true);
    1178 //       }
    1179 //       for (typename std::list<Node>::const_iterator i=T.begin();
    1180 //         i!=T.end(); ++i) {
    1181 //      TMap.set(*i, true);
    1182 //       }
    1183 //     }
    1184 //     bool augment() {
    1185 //       AugGraph res_graph(G, flow, capacity);
     679//     MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
     680//       G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
     681//     bool augmentOnShortestPath() {
     682//       AugGraph res_graph(*G, *flow, *capacity);
    1186683//       bool _augment=false;
    1187 //       Node reached_t_node;
    1188684     
    1189685//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
    1190 //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
    1191 //       for(typename std::list<Node>::const_iterator i=S.begin();
    1192 //        i!=S.end(); ++i) {
    1193 //      res_bfs.pushAndSetReached(*i);
     686//       BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
     687//       typename AugGraph::NodeMap<AugEdge> pred(res_graph);
     688//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
     689//      if ((S->get(s)) && (used.get(s)<1) ) {
     690//        //Number u=0;
     691//        //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
     692//        //u+=flow->get(e);
     693//        //if (u<1) {
     694//          res_bfs.pushAndSetReached(s);
     695//          pred.set(s, AugEdge(INVALID));
     696//          //}
     697//      }
    1194698//       }
    1195 //       //res_bfs.pushAndSetReached(s);
    1196        
    1197 //       typename AugGraph::NodeMap<AugEdge> pred(res_graph);
    1198 //       //filled up with invalid iterators
    1199699     
    1200700//       typename AugGraph::NodeMap<Number> free(res_graph);
    1201701       
     702//       Node n;
    1202703//       //searching for augmenting path
    1203704//       while ( !res_bfs.finished() ) {
    1204 //      AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
    1205 //      if (e.valid() && res_bfs.isBNodeNewlyReached()) {
     705//      AugOutEdgeIt e=res_bfs;
     706//      if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
    1206707//        Node v=res_graph.tail(e);
    1207708//        Node w=res_graph.head(e);
    1208709//        pred.set(w, e);
    1209 //        if (pred.get(v).valid()) {
    1210 //          free.set(w, std::min(free.get(v), e.free()));
     710//        if (res_graph.valid(pred.get(v))) {
     711//          free.set(w, std::min(free.get(v), res_graph.free(e)));
    1211712//        } else {
    1212 //          free.set(w, e.free());
     713//          free.set(w, res_graph.free(e));
    1213714//        }
    1214 //        if (TMap.get(res_graph.head(e))) {
    1215 //          _augment=true;
    1216 //          reached_t_node=res_graph.head(e);
    1217 //          break;
     715//        n=res_graph.head(e);
     716//        if (T->get(n) && (used.get(n)<1) ) {
     717//          //Number u=0;
     718//          //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
     719//          //u+=flow->get(f);
     720//          //if (u<1) {
     721//            _augment=true;
     722//            break;
     723//            //}
    1218724//        }
    1219725//      }
    … …  
    1223729
    1224730//       if (_augment) {
    1225 //      Node n=reached_t_node;
    1226 //      Number augment_value=free.get(reached_t_node);
    1227 //      while (pred.get(n).valid()) {
     731//      //Node n=t;
     732//      used.set(n, 1); //mind2 vegen jav
     733//      Number augment_value=free.get(n);
     734//      while (res_graph.valid(pred.get(n))) {
    1228735//        AugEdge e=pred.get(n);
    1229 //        e.augment(augment_value);
     736//        res_graph.augment(e, augment_value);
    1230737//        n=res_graph.tail(e);
    1231738//      }
     739//      used.set(n, 1); //mind2 vegen jav
    1232740//       }
    1233741
     742//       return _augment;
     743//     }
     744
     745// //     template<typename MutableGraph> bool augmentOnBlockingFlow() {     
     746// //       bool _augment=false;
     747
     748// //       AugGraph res_graph(*G, *flow, *capacity);
     749
     750// //       typedef typename AugGraph::NodeMap<bool> ReachedMap;
     751// //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
     752
     753
     754
     755
     756
     757// //       //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
     758// //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
     759// //   if (S->get(s)) {
     760// //     Number u=0;
     761// //     for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
     762// //       u+=flow->get(e);
     763// //     if (u<1) {
     764// //       res_bfs.pushAndSetReached(s);
     765// //       //pred.set(s, AugEdge(INVALID));
     766// //     }
     767// //   }
     768// //       }
     769
     770
     771
     772
     773// //       //bfs.pushAndSetReached(s);
     774// //       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
     775// //       while ( !bfs.finished() ) {
     776// //   AugOutEdgeIt e=bfs;
     777// //   if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     778// //     dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     779// //   }
     780       
     781// //   ++bfs;
     782// //       } //computing distances from s in the residual graph
     783
     784// //       MutableGraph F;
     785// //       typename AugGraph::NodeMap<typename MutableGraph::Node>
     786// //   res_graph_to_F(res_graph);
     787// //       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
     788// //   res_graph_to_F.set(n, F.addNode());
     789// //       }
     790     
     791// //       typename MutableGraph::Node sF=res_graph_to_F.get(s);
     792// //       typename MutableGraph::Node tF=res_graph_to_F.get(t);
     793
     794// //       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
     795// //       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
     796
     797// //       //Making F to the graph containing the edges of the residual graph
     798// //       //which are in some shortest paths
     799// //       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
     800// //   if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
     801// //     typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
     802// //     original_edge.update();
     803// //     original_edge.set(f, e);
     804// //     residual_capacity.update();
     805// //     residual_capacity.set(f, res_graph.free(e));
     806// //   }
     807// //       }
     808
     809// //       bool __augment=true;
     810
     811// //       while (__augment) {
     812// //   __augment=false;
     813// //   //computing blocking flow with dfs
     814// //   typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
     815// //   DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
     816// //   typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
     817// //   pred.set(sF, typename MutableGraph::Edge(INVALID));
     818// //   //invalid iterators for sources
     819
     820// //   typename MutableGraph::NodeMap<Number> free(F);
     821
     822// //   dfs.pushAndSetReached(sF);     
     823// //   while (!dfs.finished()) {
     824// //     ++dfs;
     825// //     if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
     826// //       if (dfs.isBNodeNewlyReached()) {
     827// //         typename MutableGraph::Node v=F.aNode(dfs);
     828// //         typename MutableGraph::Node w=F.bNode(dfs);
     829// //         pred.set(w, dfs);
     830// //         if (F.valid(pred.get(v))) {
     831// //           free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
     832// //         } else {
     833// //           free.set(w, residual_capacity.get(dfs));
     834// //         }
     835// //         if (w==tF) {
     836// //           __augment=true;
     837// //           _augment=true;
     838// //           break;
     839// //         }
     840             
     841// //       } else {
     842// //         F.erase(typename MutableGraph::OutEdgeIt(dfs));
     843// //       }
     844// //     }
     845// //   }
     846
     847// //   if (__augment) {
     848// //     typename MutableGraph::Node n=tF;
     849// //     Number augment_value=free.get(tF);
     850// //     while (F.valid(pred.get(n))) {
     851// //       typename MutableGraph::Edge e=pred.get(n);
     852// //       res_graph.augment(original_edge.get(e), augment_value);
     853// //       n=F.tail(e);
     854// //       if (residual_capacity.get(e)==augment_value)
     855// //         F.erase(e);
     856// //       else
     857// //         residual_capacity.set(e, residual_capacity.get(e)-augment_value);
     858// //     }
     859// //   }
     860       
     861// //       }
     862           
     863// //       return _augment;
     864// //     }
     865//     bool augmentOnBlockingFlow2() {
     866//       bool _augment=false;
     867
     868//       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
     869//       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
     870//       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
     871//       typedef typename EAugGraph::Edge EAugEdge;
     872
     873//       EAugGraph res_graph(*G, *flow, *capacity);
     874
     875//       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
     876//       BfsIterator5<
     877//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
     878//      /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
     879//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
     880
     881
     882//       //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
     883//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
     884//      if (S->get(s)) {
     885//        Number u=0;
     886//        for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
     887//          u+=flow->get(e);
     888//        if (u<1) {
     889//          bfs.pushAndSetReached(s);
     890//          //pred.set(s, AugEdge(INVALID));
     891//        }
     892//      }
     893//       }
     894
     895     
     896//       //bfs.pushAndSetReached(s);
     897
     898//       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
     899//      NodeMap<int>& dist=res_graph.dist;
     900
     901//       while ( !bfs.finished() ) {
     902//      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
     903//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     904//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     905//      }
     906//      ++bfs; 
     907//       } //computing distances from s in the residual graph
     908
     909//       bool __augment=true;
     910
     911//       while (__augment) {
     912
     913//      __augment=false;
     914//      //computing blocking flow with dfs
     915//      typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
     916//      DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
     917//        dfs(res_graph);
     918//      typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
     919//      //pred.set(s, EAugEdge(INVALID));
     920//      //invalid iterators for sources
     921
     922//      typename EAugGraph::NodeMap<Number> free(res_graph);
     923
     924
     925//      //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
     926//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
     927//      if (S->get(s)) {
     928//        Number u=0;
     929//        for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
     930//          u+=flow->get(e);
     931//        if (u<1) {
     932//          dfs.pushAndSetReached(s);
     933//          //pred.set(s, AugEdge(INVALID));
     934//        }
     935//      }
     936//       }
     937
     938
     939
     940//       //dfs.pushAndSetReached(s);
     941//       typename EAugGraph::Node n;
     942//      while (!dfs.finished()) {
     943//        ++dfs;
     944//        if (res_graph.valid(EAugOutEdgeIt(dfs))) {
     945//          if (dfs.isBNodeNewlyReached()) {
     946         
     947//            typename EAugGraph::Node v=res_graph.aNode(dfs);
     948//            typename EAugGraph::Node w=res_graph.bNode(dfs);
     949
     950//            pred.set(w, EAugOutEdgeIt(dfs));
     951//            if (res_graph.valid(pred.get(v))) {
     952//              free.set(w, std::min(free.get(v), res_graph.free(dfs)));
     953//            } else {
     954//              free.set(w, res_graph.free(dfs));
     955//            }
     956             
     957//            n=w;
     958//            if (T->get(w)) {
     959//              Number u=0;
     960//              for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
     961//                u+=flow->get(f);
     962//              if (u<1) {
     963//                __augment=true;
     964//                _augment=true;
     965//                break;
     966//              }
     967//            }
     968//          } else {
     969//            res_graph.erase(dfs);
     970//          }
     971//        }
     972
     973//      }
     974
     975//      if (__augment) {
     976//        // typename EAugGraph::Node n=t;
     977//        Number augment_value=free.get(n);
     978//        while (res_graph.valid(pred.get(n))) {
     979//          EAugEdge e=pred.get(n);
     980//          res_graph.augment(e, augment_value);
     981//          n=res_graph.tail(e);
     982//          if (res_graph.free(e)==0)
     983//            res_graph.erase(e);
     984//        }
     985//      }
     986     
     987//       }
     988           
    1234989//       return _augment;
    1235990//     }
    1236991//     void run() {
    1237 //       while (augment()) { }
     992//       //int num_of_augmentations=0;
     993//       while (augmentOnShortestPath()) {
     994//      //while (augmentOnBlockingFlow<MutableGraph>()) {
     995//      //std::cout << ++num_of_augmentations << " ";
     996//      //std::cout<<std::endl;
     997//       }
    1238998//     }
     999// //     template<typename MutableGraph> void run() {
     1000// //       //int num_of_augmentations=0;
     1001// //       //while (augmentOnShortestPath()) {
     1002// //   while (augmentOnBlockingFlow<MutableGraph>()) {
     1003// //   //std::cout << ++num_of_augmentations << " ";
     1004// //   //std::cout<<std::endl;
     1005// //       }
     1006// //     }
    12391007//     Number flowValue() {
    12401008//       Number a=0;
    1241 //       for(typename std::list<Node>::const_iterator i=S.begin();
    1242 //        i!=S.end(); ++i) {
    1243 //      for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
    1244 //        a+=flow.get(e);
    1245 //      }
    1246 //      for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
    1247 //        a-=flow.get(e);
    1248 //      }
     1009//       EdgeIt e;
     1010//       for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
     1011//      a+=flow->get(e);
    12491012//       }
    12501013//       return a;
    … …  
    12541017
    12551018
     1019
     1020
     1021 
     1022// //   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     1023// //   class MaxFlow2 {
     1024// //   public:
     1025// //     typedef typename Graph::Node Node;
     1026// //     typedef typename Graph::Edge Edge;
     1027// //     typedef typename Graph::EdgeIt EdgeIt;
     1028// //     typedef typename Graph::OutEdgeIt OutEdgeIt;
     1029// //     typedef typename Graph::InEdgeIt InEdgeIt;
     1030// //   private:
     1031// //     const Graph& G;
     1032// //     std::list<Node>& S;
     1033// //     std::list<Node>& T;
     1034// //     FlowMap& flow;
     1035// //     const CapacityMap& capacity;
     1036// //     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
     1037// //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
     1038// //     typedef typename AugGraph::Edge AugEdge;
     1039// //     typename Graph::NodeMap<bool> SMap;
     1040// //     typename Graph::NodeMap<bool> TMap;
     1041// //   public:
     1042// //     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) {
     1043// //       for(typename std::list<Node>::const_iterator i=S.begin();
     1044// //     i!=S.end(); ++i) {
     1045// //   SMap.set(*i, true);
     1046// //       }
     1047// //       for (typename std::list<Node>::const_iterator i=T.begin();
     1048// //      i!=T.end(); ++i) {
     1049// //   TMap.set(*i, true);
     1050// //       }
     1051// //     }
     1052// //     bool augment() {
     1053// //       AugGraph res_graph(G, flow, capacity);
     1054// //       bool _augment=false;
     1055// //       Node reached_t_node;
     1056     
     1057// //       typedef typename AugGraph::NodeMap<bool> ReachedMap;
     1058// //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
     1059// //       for(typename std::list<Node>::const_iterator i=S.begin();
     1060// //     i!=S.end(); ++i) {
     1061// //   res_bfs.pushAndSetReached(*i);
     1062// //       }
     1063// //       //res_bfs.pushAndSetReached(s);
     1064       
     1065// //       typename AugGraph::NodeMap<AugEdge> pred(res_graph);
     1066// //       //filled up with invalid iterators
     1067     
     1068// //       typename AugGraph::NodeMap<Number> free(res_graph);
     1069       
     1070// //       //searching for augmenting path
     1071// //       while ( !res_bfs.finished() ) {
     1072// //   AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
     1073// //   if (e.valid() && res_bfs.isBNodeNewlyReached()) {
     1074// //     Node v=res_graph.tail(e);
     1075// //     Node w=res_graph.head(e);
     1076// //     pred.set(w, e);
     1077// //     if (pred.get(v).valid()) {
     1078// //       free.set(w, std::min(free.get(v), e.free()));
     1079// //     } else {
     1080// //       free.set(w, e.free());
     1081// //     }
     1082// //     if (TMap.get(res_graph.head(e))) {
     1083// //       _augment=true;
     1084// //       reached_t_node=res_graph.head(e);
     1085// //       break;
     1086// //     }
     1087// //   }
     1088       
     1089// //   ++res_bfs;
     1090// //       } //end of searching augmenting path
     1091
     1092// //       if (_augment) {
     1093// //   Node n=reached_t_node;
     1094// //   Number augment_value=free.get(reached_t_node);
     1095// //   while (pred.get(n).valid()) {
     1096// //     AugEdge e=pred.get(n);
     1097// //     e.augment(augment_value);
     1098// //     n=res_graph.tail(e);
     1099// //   }
     1100// //       }
     1101
     1102// //       return _augment;
     1103// //     }
     1104// //     void run() {
     1105// //       while (augment()) { }
     1106// //     }
     1107// //     Number flowValue() {
     1108// //       Number a=0;
     1109// //       for(typename std::list<Node>::const_iterator i=S.begin();
     1110// //     i!=S.end(); ++i) {
     1111// //   for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
     1112// //     a+=flow.get(e);
     1113// //   }
     1114// //   for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
     1115// //     a-=flow.get(e);
     1116// //   }
     1117// //       }
     1118// //       return a;
     1119// //     }
     1120// //   };
     1121
     1122
    12561123} // namespace hugo
    12571124
Note: See TracChangeset for help on using the changeset viewer.