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


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

GraphWrappers?, MapWrappers?

Location:
src/work
Files:
3 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

  • src/work/marci/edmonds_karp_demo.cc

    r243 r266  
    99#include <time_measure.h>
    1010#include <graph_wrapper.h>
     11
     12class CM {
     13public:
     14  template<typename T> int get(T) const {return 1;}
     15};
    1116
    1217using namespace hugo;
    … …  
    8792  {
    8893    //std::cout << "SmartGraph..." << std::endl;
     94    typedef TrivGraphWrapper<const Graph> GW;
     95    GW gw(G);
    8996    std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
    90     Graph::EdgeMap<int> flow(G); //0 flow
     97    GW::EdgeMap<int> flow(G); //0 flow
    9198
    9299    Timer ts;
    93100    ts.reset();
    94101
    95     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    96     //max_flow_test.augmentWithBlockingFlow<Graph>();
     102    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
     103    EMW cw(cap);
     104    MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(G, s, t, flow, cw);
    97105    int i=0;
    98106    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
    … …  
    114122  }
    115123
     124//   {
     125//     //std::cout << "SmartGraph..." << std::endl;
     126//     std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
     127//     Graph::EdgeMap<int> flow(G); //0 flow
     128
     129//     Timer ts;
     130//     ts.reset();
     131
     132//     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
     133//     int i=0;
     134//     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
     135// //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
     136// //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     137// //     }
     138// //     std::cout<<std::endl;
     139//       ++i;
     140//     }
     141
     142// //   std::cout << "maximum flow: "<< std::endl;
     143// //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
     144// //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     145// //   }
     146// //   std::cout<<std::endl;
     147//     std::cout << "elapsed time: " << ts << std::endl;
     148//     std::cout << "number of augmentation phases: " << i << std::endl;
     149//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     150//   }
     151
     152//   {
     153//     std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
     154//     Graph::EdgeMap<int> flow(G); //0 flow
     155
     156//     Timer ts;
     157//     ts.reset();
     158
     159//     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
     160//     int i=0;
     161//     while (max_flow_test.augmentOnBlockingFlow2()) {
     162// //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
     163// //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     164// //     }
     165// //     std::cout<<std::endl;
     166//       ++i;
     167//     }
     168
     169// //   std::cout << "maximum flow: "<< std::endl;
     170// //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
     171// //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     172// //   }
     173// //   std::cout<<std::endl;
     174//     std::cout << "elapsed time: " << ts << std::endl;
     175//     std::cout << "number of augmentation phases: " << i << std::endl;
     176//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     177//   }
     178
    116179  {
    117     //std::cout << "SmartGraph..." << std::endl;
    118     std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
    119     Graph::EdgeMap<int> flow(G); //0 flow
     180    typedef TrivGraphWrapper<const Graph> GW;
     181    GW gw(G);
     182    std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
     183    GW::EdgeMap<int> flow(gw); //0 flow
    120184
    121185    Timer ts;
    122186    ts.reset();
    123187
    124     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    125     //max_flow_test.augmentWithBlockingFlow<Graph>();
     188    //CM cm;
     189    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
     190    EMW cw(cap);
     191    MaxFlow<GW, int, GW::EdgeMap<int>, EMW> max_flow_test(gw, s, t, flow, cw);
    126192    int i=0;
    127     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
     193    while (max_flow_test.augmentOnShortestPath()) {
    128194//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    129195//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    … …  
    143209  }
    144210
    145   {
    146     std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
    147     Graph::EdgeMap<int> flow(G); //0 flow
    148 
    149     Timer ts;
    150     ts.reset();
    151 
    152     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    153     //max_flow_test.augmentWithBlockingFlow<Graph>();
    154     int i=0;
    155     while (max_flow_test.augmentOnBlockingFlow2()) {
    156 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    157 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    158 //     }
    159 //     std::cout<<std::endl;
    160       ++i;
    161     }
    162 
    163 //   std::cout << "maximum flow: "<< std::endl;
    164 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
    165 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    166 //   }
    167 //   std::cout<<std::endl;
    168     std::cout << "elapsed time: " << ts << std::endl;
    169     std::cout << "number of augmentation phases: " << i << std::endl;
    170     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    171   }
    172 
    173   {
    174     std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
    175     Graph::EdgeMap<int> flow(G); //0 flow
    176 
    177     Timer ts;
    178     ts.reset();
    179 
    180     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    181     //max_flow_test.augmentWithBlockingFlow<Graph>();
    182     int i=0;
    183     while (max_flow_test.augmentOnShortestPath()) {
    184 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    185 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    186 //     }
    187 //     std::cout<<std::endl;
    188       ++i;
    189     }
    190 
    191 //   std::cout << "maximum flow: "<< std::endl;
    192 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
    193 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    194 //   }
    195 //   std::cout<<std::endl;
    196     std::cout << "elapsed time: " << ts << std::endl;
    197     std::cout << "number of augmentation phases: " << i << std::endl;
    198     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    199   }
    200 
    201211
    202212  return 0;

  • src/work/marci/graph_wrapper.h

    r265 r266  
    124124    template<typename T> class NodeMap : public Graph::NodeMap<T> {
    125125    public:
    126       NodeMap(const TrivGraphWrapper<Graph>& _G) :
     126      NodeMap(const TrivGraphWrapper<Graph>& _G) :  
    127127        Graph::NodeMap<T>(*(_G.graph)) { }
    128128      NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
    … …  
    132132    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
    133133    public:
    134       EdgeMap(const TrivGraphWrapper<Graph>& _G) :
     134      EdgeMap(const TrivGraphWrapper<Graph>& _G) :  
    135135        Graph::EdgeMap<T>(*(_G.graph)) { }
    136136      EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
    137137        Graph::EdgeMap<T>(*(_G.graph), a) { }
     138    };
     139
     140    template<typename Map, typename T> class NodeMapWrapper {
     141    protected:
     142      Map* map;
     143    public:
     144      NodeMapWrapper(Map& _map) : map(&_map) { }
     145      //template<typename T>
     146      void set(Node n, T a) { map->set(n, a); }
     147      //template<typename T>
     148      T get(Node n) const { return map->get(n); }
     149    };
     150
     151    template<typename Map, typename T> class EdgeMapWrapper {
     152    protected:
     153      Map* map;
     154    public:
     155      EdgeMapWrapper(Map& _map) : map(&_map) { }
     156      //template<typename T>
     157      void set(Edge n, T a) { map->set(n, a); }
     158      //template<typename T>
     159      T get(Edge n) const { return map->get(n); }
    138160    };
    139161  };
    … …  
    248270    template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
    249271    public:
    250       NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
     272      NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :  
    251273        GraphWrapper::NodeMap<T>(_G.gw) { }
    252274      NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
    … …  
    256278    template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
    257279    public:
    258       EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
     280      EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :  
    259281        GraphWrapper::EdgeMap<T>(_G.gw) { }
    260282      EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
    … …  
    760782    template<typename I> I& first(I& i) const { gw.first(i); return i; }
    761783    template<typename I, typename P> I& first(I& i, const P& p) const {
    762       graph->first(i, p); return i; }
     784      gw.first(i, p); return i; }
    763785
    764786    OutEdgeIt& next(OutEdgeIt& e) const {
    … …  
    912934
    913935
    914   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    915   class ResGraphWrapper {
     936  template<typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
     937  class ResGraphWrapper : public GraphWrapperSkeleton<GraphWrapper>{
    916938  public:
    917939    //typedef Graph BaseGraph;
    918     typedef TrivGraphWrapper<const Graph> GraphWrapper;
    919     typedef typename GraphWrapper::Node Node;
    920     typedef typename GraphWrapper::NodeIt NodeIt;
     940    //typedef TrivGraphWrapper<const Graph> GraphWrapper;
     941    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
     942    typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
    921943  private:
    922     typedef typename GraphWrapper::OutEdgeIt OldOutEdgeIt;
    923     typedef typename GraphWrapper::InEdgeIt OldInEdgeIt;
     944    typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OldOutEdgeIt;
     945    typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt OldInEdgeIt;
    924946  protected:
    925947    //const Graph* graph;
    926     GraphWrapper gw;
     948    //GraphWrapper gw;
    927949    FlowMap* flow;
    928950    const CapacityMap* capacity;
    929951  public:
    930952
    931     ResGraphWrapper(const Graph& _G, FlowMap& _flow,
    932              const CapacityMap& _capacity) :
    933       gw(_G), flow(&_flow), capacity(&_capacity) { }
     953    ResGraphWrapper(const GraphWrapper& _gw, FlowMap& _flow,
     954                    const CapacityMap& _capacity) :
     955      GraphWrapperSkeleton<GraphWrapper>(_gw),
     956      flow(&_flow), capacity(&_capacity) { }
    934957
    935958    //void setGraph(const Graph& _graph) { graph = &_graph; }
    … …  
    942965
    943966    class Edge {
    944       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     967      friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
    945968    protected:
    946969      bool out_or_in; //true, iff out
    … …  
    968991
    969992    class OutEdgeIt : public Edge {
    970       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     993      friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
    971994    public:
    972995      OutEdgeIt() { }
    … …  
    975998      OutEdgeIt(const Invalid& i) : Edge(i) { }
    976999    protected:
    977       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
     1000      OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
    9781001        resG.gw.first(out, v);
    9791002        while( resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
    … …  
    10071030
    10081031    class EdgeIt : public Edge {
    1009       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     1032      friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
    10101033      NodeIt v;
    10111034    public:
    … …  
    10131036      //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
    10141037      EdgeIt(const Invalid& i) : Edge(i) { }
    1015       EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
     1038      EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {
    10161039        resG.gw.first(v);
    10171040        if (resG.gw.valid(v)) resG.gw.first(out, v); else out=/*OldOutEdgeIt*/(INVALID);
    … …  
    10671090    };
    10681091
    1069     NodeIt& first(NodeIt& v) const { return gw.first(v); }
     1092    NodeIt& first(NodeIt& v) const { gw.first(v); return v; }
    10701093    OutEdgeIt& first(OutEdgeIt& e, Node v) const {
    10711094      e=OutEdgeIt(*this, v);
    … …  
    11861209    }
    11871210
    1188     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
    1189     public:
    1190       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
    1191         : GraphWrapper::NodeMap<T>(_G.gw) { }
    1192       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
    1193               T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }
    1194     };
     1211//     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
     1212//     public:
     1213//       NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G)
     1214//      : GraphWrapper::NodeMap<T>(_G.gw) { }
     1215//       NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G,
     1216//            T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }
     1217//     };
    11951218
    11961219//     template <typename T>
    … …  
    12081231      typename GraphWrapper::EdgeMap<T> forward_map, backward_map;
    12091232    public:
    1210       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }
    1211       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }
     1233      EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }
     1234      EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }
    12121235      void set(Edge e, T a) {
    12131236        if (e.out_or_in)
    … …  
    12251248  };
    12261249
    1227   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    1228   class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
    1229   protected:
    1230     ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
    1231     //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
    1232   public:
    1233     ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
    1234                            const CapacityMap& _capacity) :
    1235       ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
    1236       first_out_edges(*this) /*, dist(*this)*/ {
    1237       for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
    1238         OutEdgeIt e;
    1239         ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
    1240         first_out_edges.set(n, e);
    1241       }
    1242     }
    1243 
    1244     //void setGraph(Graph& _graph) { graph = &_graph; }
    1245     //Graph& getGraph() const { return (*graph); }
    1246  
    1247     //TrivGraphWrapper() : graph(0) { }
    1248     //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
    1249 
    1250     //typedef Graph BaseGraph;
    1251 
    1252     //typedef typename Graph::Node Node;
    1253     //typedef typename Graph::NodeIt NodeIt;
    1254 
    1255     //typedef typename Graph::Edge Edge;
    1256     //typedef typename Graph::OutEdgeIt OutEdgeIt;
    1257     //typedef typename Graph::InEdgeIt InEdgeIt;
    1258     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    1259     //typedef typename Graph::EdgeIt EdgeIt;
    1260 
    1261     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
    1262     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
    1263 
    1264     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
    1265     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
    1266     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
    1267     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    1268     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
    1269 
    1270     NodeIt& first(NodeIt& n) const {
    1271       return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
    1272     }
    1273 
    1274     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
    1275       e=first_out_edges.get(n);
    1276       return e;
    1277     }
    1278    
    1279     //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
    1280     //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
    1281     //  return first(i, p); }
    1282    
    1283     //template<typename I> I getNext(const I& i) const {
    1284     //  return gw.getNext(i); }
    1285     //template<typename I> I& next(I &i) const { return gw.next(i); }   
    1286 
    1287     template< typename It > It first() const {
    1288       It e; first(e); return e; }
    1289 
    1290     template< typename It > It first(const Node& v) const {
    1291       It e; first(e, v); return e; }
    1292 
    1293     //Node head(const Edge& e) const { return gw.head(e); }
    1294     //Node tail(const Edge& e) const { return gw.tail(e); }
    1295 
    1296     //template<typename I> bool valid(const I& i) const
    1297     //  { return gw.valid(i); }
    1298  
    1299     //int nodeNum() const { return gw.nodeNum(); }
    1300     //int edgeNum() const { return gw.edgeNum(); }
    1301  
    1302     //template<typename I> Node aNode(const I& e) const {
    1303     //  return gw.aNode(e); }
    1304     //template<typename I> Node bNode(const I& e) const {
    1305     //  return gw.bNode(e); }
    1306  
    1307     //Node addNode() const { return gw.addNode(); }
    1308     //Edge addEdge(const Node& tail, const Node& head) const {
    1309     //  return gw.addEdge(tail, head); }
    1310  
    1311     //void erase(const OutEdgeIt& e) {
    1312     //  first_out_edge(this->tail(e))=e;
    1313     //}
    1314     void erase(const Edge& e) {
    1315       OutEdgeIt f(e);
    1316       next(f);
    1317       first_out_edges.set(this->tail(e), f);
    1318     }
    1319     //template<typename I> void erase(const I& i) const { gw.erase(i); }
    1320  
    1321     //void clear() const { gw.clear(); }
    1322    
    1323     template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
    1324     public:
    1325       NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
    1326         ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
    1327       NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
    1328         ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
    1329     };
    1330 
    1331     template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
    1332     public:
    1333       EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
    1334         ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
    1335       EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
    1336         ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
    1337     };
    1338   };
    1339 
    1340   template<typename GraphWrapper>
    1341   class FilterGraphWrapper {
    1342   };
    1343 
    1344   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    1345   class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
    1346 
    1347     //Graph* graph;
    1348  
    1349   public:
    1350     //typedef Graph BaseGraph;
    1351 
    1352     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
    1353     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
    1354 
    1355     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
    1356     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
    1357     //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
    1358     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    1359     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
    1360 
    1361     //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
    1362    
    1363   public:
    1364     FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
    1365                            const CapacityMap& _capacity) :
    1366       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {
    1367     }
    1368 
    1369     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
    1370       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
    1371       while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
    1372         ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
    1373       return e;
    1374     }
    1375 
    1376     NodeIt& next(NodeIt& e) const {
    1377       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
    1378     }
    1379 
    1380     OutEdgeIt& next(OutEdgeIt& e) const {
    1381       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
    1382       while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))
    1383         ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
    1384       return e;
    1385     }
    1386 
    1387     NodeIt& first(NodeIt& n) const {
    1388       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
    1389     }
    1390 
    1391     void erase(const Edge& e) {
    1392       OutEdgeIt f(e);
    1393       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
    1394       while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))
    1395         ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
    1396       first_out_edges.set(this->tail(e), f);
    1397     }
    1398 
    1399     //TrivGraphWrapper() : graph(0) { }
    1400     //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
    1401 
    1402     //void setGraph(Graph& _graph) { graph = &_graph; }
    1403     //Graph& getGraph() const { return (*graph); }
    1404    
    1405     //template<typename I> I& first(I& i) const { return gw.first(i); }
    1406     //template<typename I, typename P> I& first(I& i, const P& p) const {
    1407     //  return gw.first(i, p); }
    1408    
    1409     //template<typename I> I getNext(const I& i) const {
    1410     //  return gw.getNext(i); }
    1411     //template<typename I> I& next(I &i) const { return gw.next(i); }   
    1412 
    1413     template< typename It > It first() const {
    1414       It e; first(e); return e; }
    1415 
    1416     template< typename It > It first(const Node& v) const {
    1417       It e; first(e, v); return e; }
    1418 
    1419     //Node head(const Edge& e) const { return gw.head(e); }
    1420     //Node tail(const Edge& e) const { return gw.tail(e); }
    1421 
    1422     //template<typename I> bool valid(const I& i) const
    1423     //  { return gw.valid(i); }
    1424  
    1425     //template<typename I> void setInvalid(const I &i);
    1426     //{ return gw.setInvalid(i); }
    1427 
    1428     //int nodeNum() const { return gw.nodeNum(); }
    1429     //int edgeNum() const { return gw.edgeNum(); }
    1430  
    1431     //template<typename I> Node aNode(const I& e) const {
    1432     //  return gw.aNode(e); }
    1433     //template<typename I> Node bNode(const I& e) const {
    1434     //  return gw.bNode(e); }
    1435  
    1436     //Node addNode() const { return gw.addNode(); }
    1437     //Edge addEdge(const Node& tail, const Node& head) const {
    1438     //  return gw.addEdge(tail, head); }
    1439  
    1440     //template<typename I> void erase(const I& i) const { gw.erase(i); }
    1441  
    1442     //void clear() const { gw.clear(); }
    1443    
    1444     template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
    1445     public:
    1446       NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
    1447         ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
    1448       NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
    1449         ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
    1450     };
    1451 
    1452     template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
    1453     public:
    1454       EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
    1455         ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
    1456       EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
    1457         ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
    1458     };
    1459 
    1460   public:
    1461     ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
    1462 
    1463   };
     1250//   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     1251//   class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
     1252//   protected:
     1253//     ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
     1254//     //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
     1255//   public:
     1256//     ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
     1257//                         const CapacityMap& _capacity) :
     1258//       ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
     1259//       first_out_edges(*this) /*, dist(*this)*/ {
     1260//       for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
     1261//      OutEdgeIt e;
     1262//      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
     1263//      first_out_edges.set(n, e);
     1264//       }
     1265//     }
     1266
     1267//     //void setGraph(Graph& _graph) { graph = &_graph; }
     1268//     //Graph& getGraph() const { return (*graph); }
     1269 
     1270//     //TrivGraphWrapper() : graph(0) { }
     1271//     //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
     1272
     1273//     //typedef Graph BaseGraph;
     1274
     1275//     //typedef typename Graph::Node Node;
     1276//     //typedef typename Graph::NodeIt NodeIt;
     1277
     1278//     //typedef typename Graph::Edge Edge;
     1279//     //typedef typename Graph::OutEdgeIt OutEdgeIt;
     1280//     //typedef typename Graph::InEdgeIt InEdgeIt;
     1281//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
     1282//     //typedef typename Graph::EdgeIt EdgeIt;
     1283
     1284//     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
     1285//     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
     1286
     1287//     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
     1288//     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
     1289//     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
     1290//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
     1291//     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
     1292
     1293//     NodeIt& first(NodeIt& n) const {
     1294//       return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
     1295//     }
     1296
     1297//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
     1298//       e=first_out_edges.get(n);
     1299//       return e;
     1300//     }
     1301   
     1302//     //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
     1303//     //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
     1304//     //  return first(i, p); }
     1305   
     1306//     //template<typename I> I getNext(const I& i) const {
     1307//     //  return gw.getNext(i); }
     1308//     //template<typename I> I& next(I &i) const { return gw.next(i); }   
     1309
     1310//     template< typename It > It first() const {
     1311//       It e; first(e); return e; }
     1312
     1313//     template< typename It > It first(const Node& v) const {
     1314//       It e; first(e, v); return e; }
     1315
     1316//     //Node head(const Edge& e) const { return gw.head(e); }
     1317//     //Node tail(const Edge& e) const { return gw.tail(e); }
     1318
     1319//     //template<typename I> bool valid(const I& i) const
     1320//     //  { return gw.valid(i); }
     1321 
     1322//     //int nodeNum() const { return gw.nodeNum(); }
     1323//     //int edgeNum() const { return gw.edgeNum(); }
     1324 
     1325//     //template<typename I> Node aNode(const I& e) const {
     1326//     //  return gw.aNode(e); }
     1327//     //template<typename I> Node bNode(const I& e) const {
     1328//     //  return gw.bNode(e); }
     1329 
     1330//     //Node addNode() const { return gw.addNode(); }
     1331//     //Edge addEdge(const Node& tail, const Node& head) const {
     1332//     //  return gw.addEdge(tail, head); }
     1333 
     1334//     //void erase(const OutEdgeIt& e) {
     1335//     //  first_out_edge(this->tail(e))=e;
     1336//     //}
     1337//     void erase(const Edge& e) {
     1338//       OutEdgeIt f(e);
     1339//       next(f);
     1340//       first_out_edges.set(this->tail(e), f);
     1341//     }
     1342//     //template<typename I> void erase(const I& i) const { gw.erase(i); }
     1343 
     1344//     //void clear() const { gw.clear(); }
     1345   
     1346//     template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
     1347//     public:
     1348//       NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
     1349//      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
     1350//       NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
     1351//      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
     1352//     };
     1353
     1354//     template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
     1355//     public:
     1356//       EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
     1357//      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
     1358//       EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
     1359//      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
     1360//     };
     1361//   };
     1362
     1363//   template<typename GraphWrapper>
     1364//   class FilterGraphWrapper {
     1365//   };
     1366
     1367//   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     1368//   class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
     1369
     1370//     //Graph* graph;
     1371 
     1372//   public:
     1373//     //typedef Graph BaseGraph;
     1374
     1375//     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
     1376//     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
     1377
     1378//     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
     1379//     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
     1380//     //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
     1381//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
     1382//     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
     1383
     1384//     //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
     1385   
     1386//   public:
     1387//     FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
     1388//                         const CapacityMap& _capacity) :
     1389//       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {
     1390//     }
     1391
     1392//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
     1393//       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
     1394//       while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
     1395//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
     1396//       return e;
     1397//     }
     1398
     1399//     NodeIt& next(NodeIt& e) const {
     1400//       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
     1401//     }
     1402
     1403//     OutEdgeIt& next(OutEdgeIt& e) const {
     1404//       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
     1405//       while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))
     1406//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
     1407//       return e;
     1408//     }
     1409
     1410//     NodeIt& first(NodeIt& n) const {
     1411//       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
     1412//     }
     1413
     1414//     void erase(const Edge& e) {
     1415//       OutEdgeIt f(e);
     1416//       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
     1417//       while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))
     1418//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
     1419//       first_out_edges.set(this->tail(e), f);
     1420//     }
     1421
     1422//     //TrivGraphWrapper() : graph(0) { }
     1423//     //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
     1424
     1425//     //void setGraph(Graph& _graph) { graph = &_graph; }
     1426//     //Graph& getGraph() const { return (*graph); }
     1427   
     1428//     //template<typename I> I& first(I& i) const { return gw.first(i); }
     1429//     //template<typename I, typename P> I& first(I& i, const P& p) const {
     1430//     //  return gw.first(i, p); }
     1431   
     1432//     //template<typename I> I getNext(const I& i) const {
     1433//     //  return gw.getNext(i); }
     1434//     //template<typename I> I& next(I &i) const { return gw.next(i); }   
     1435
     1436//     template< typename It > It first() const {
     1437//       It e; first(e); return e; }
     1438
     1439//     template< typename It > It first(const Node& v) const {
     1440//       It e; first(e, v); return e; }
     1441
     1442//     //Node head(const Edge& e) const { return gw.head(e); }
     1443//     //Node tail(const Edge& e) const { return gw.tail(e); }
     1444
     1445//     //template<typename I> bool valid(const I& i) const
     1446//     //  { return gw.valid(i); }
     1447 
     1448//     //template<typename I> void setInvalid(const I &i);
     1449//     //{ return gw.setInvalid(i); }
     1450
     1451//     //int nodeNum() const { return gw.nodeNum(); }
     1452//     //int edgeNum() const { return gw.edgeNum(); }
     1453 
     1454//     //template<typename I> Node aNode(const I& e) const {
     1455//     //  return gw.aNode(e); }
     1456//     //template<typename I> Node bNode(const I& e) const {
     1457//     //  return gw.bNode(e); }
     1458 
     1459//     //Node addNode() const { return gw.addNode(); }
     1460//     //Edge addEdge(const Node& tail, const Node& head) const {
     1461//     //  return gw.addEdge(tail, head); }
     1462 
     1463//     //template<typename I> void erase(const I& i) const { gw.erase(i); }
     1464 
     1465//     //void clear() const { gw.clear(); }
     1466   
     1467//     template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
     1468//     public:
     1469//       NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
     1470//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
     1471//       NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
     1472//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
     1473//     };
     1474
     1475//     template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
     1476//     public:
     1477//       EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
     1478//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
     1479//       EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
     1480//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
     1481//     };
     1482
     1483//   public:
     1484//     ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
     1485
     1486//   };
    14641487
    14651488
Note: See TracChangeset for help on using the changeset viewer.