COIN-OR::LEMON - Graph Library

Changeset 269:07af3069c0b8 in lemon-0.x for src/work/edmonds_karp.h


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

Working on-the-fly with wrappers

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/edmonds_karp.h

    r268 r269  
    250250  template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
    251251  class MaxFlow {
    252   public:
    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;
    258 
    259   private:
     252  protected:
     253    typedef GraphWrapper GW;
     254    typedef typename GW::Node Node;
     255    typedef typename GW::Edge Edge;
     256    typedef typename GW::EdgeIt EdgeIt;
     257    typedef typename GW::OutEdgeIt OutEdgeIt;
     258    typedef typename GW::InEdgeIt InEdgeIt;
    260259    //const Graph* G;
    261     GraphWrapper gw;
     260    GW gw;
    262261    Node s;
    263262    Node t;
    264263    FlowMap* flow;
    265264    const CapacityMap* capacity;
    266     typedef ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap >
    267     AugGraph;
    268     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    269     typedef typename AugGraph::Edge AugEdge;
    270 
     265    typedef ResGraphWrapper<GW, Number, FlowMap, CapacityMap > ResGW;
     266    typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
     267    typedef typename ResGW::Edge ResGWEdge;
    271268  public:
    272     MaxFlow(const GraphWrapper& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
     269
     270    MaxFlow(const GW& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
    273271      gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
     272
    274273    bool augmentOnShortestPath() {
    275       AugGraph res_graph(gw, *flow, *capacity);
     274      ResGW res_graph(gw, *flow, *capacity);
    276275      bool _augment=false;
    277276     
    278       typedef typename AugGraph::NodeMap<bool> ReachedMap;
    279       BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
    280       res_bfs.pushAndSetReached(s);
     277      typedef typename ResGW::NodeMap<bool> ReachedMap;
     278      BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
     279      bfs.pushAndSetReached(s);
    281280       
    282       typename AugGraph::NodeMap<AugEdge> pred(res_graph);
    283       pred.set(s, AugEdge(INVALID));
     281      typename ResGW::NodeMap<ResGWEdge> pred(res_graph);
     282      pred.set(s, INVALID);
    284283     
    285       typename AugGraph::NodeMap<Number> free(res_graph);
     284      typename ResGW::NodeMap<Number> free(res_graph);
    286285       
    287286      //searching for augmenting path
    288       while ( !res_bfs.finished() ) {
    289         AugOutEdgeIt e=res_bfs;
    290         if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
     287      while ( !bfs.finished() ) {
     288        ResGWOutEdgeIt e=bfs;
     289        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    291290          Node v=res_graph.tail(e);
    292291          Node w=res_graph.head(e);
    293292          pred.set(w, e);
    294293          if (res_graph.valid(pred.get(v))) {
    295             free.set(w, std::min(free.get(v), res_graph.free(e)));
     294            free.set(w, std::min(free.get(v), res_graph.resCap(e)));
    296295          } else {
    297             free.set(w, res_graph.free(e));
     296            free.set(w, res_graph.resCap(e));
    298297          }
    299298          if (res_graph.head(e)==t) { _augment=true; break; }
    300299        }
    301300       
    302         ++res_bfs;
     301        ++bfs;
    303302      } //end of searching augmenting path
    304303
     
    307306        Number augment_value=free.get(t);
    308307        while (res_graph.valid(pred.get(n))) {
    309           AugEdge e=pred.get(n);
     308          ResGWEdge e=pred.get(n);
    310309          res_graph.augment(e, augment_value);
    311310          n=res_graph.tail(e);
     
    331330
    332331    template<typename MutableGraph> bool augmentOnBlockingFlow() {     
     332      typedef MutableGraph MG;
    333333      bool _augment=false;
    334334
    335       AugGraph res_graph(gw, *flow, *capacity);
    336 
    337       typedef typename AugGraph::NodeMap<bool> ReachedMap;
    338       BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
     335      ResGW res_graph(gw, *flow, *capacity);
     336
     337      typedef typename ResGW::NodeMap<bool> ReachedMap;
     338      BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
    339339
    340340      bfs.pushAndSetReached(s);
    341       //typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
    342       DistanceMap<AugGraph> dist(res_graph);
     341      //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
     342      DistanceMap<ResGW> dist(res_graph);
    343343      while ( !bfs.finished() ) {
    344         AugOutEdgeIt e=bfs;
     344        ResGWOutEdgeIt e=bfs;
    345345        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    346346          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     
    349349      } //computing distances from s in the residual graph
    350350
    351       MutableGraph F;
    352       typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph;
    353       FilterResGraph filter_res_graph(res_graph, dist);
    354       typename AugGraph::NodeMap<typename MutableGraph::Node>
    355         res_graph_to_F(res_graph);
    356       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
     351      MG F;
     352      typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
     353      FilterResGW filter_res_graph(res_graph, dist);
     354      typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
     355      for(typename ResGW::NodeIt n=res_graph.template first<typename ResGW::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
    357356        res_graph_to_F.set(n, F.addNode());
    358357      }
    359      
    360       typename MutableGraph::Node sF=res_graph_to_F.get(s);
    361       typename MutableGraph::Node tF=res_graph_to_F.get(t);
    362 
    363       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
    364       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
     358
     359      typename MG::Node sF=res_graph_to_F.get(s);
     360      typename MG::Node tF=res_graph_to_F.get(t);
     361      typename MG::EdgeMap<ResGWEdge> original_edge(F);
     362      typename MG::EdgeMap<Number> residual_capacity(F);
    365363
    366364      //Making F to the graph containing the edges of the residual graph
    367365      //which are in some shortest paths
    368       for(typename FilterResGraph::EdgeIt e=filter_res_graph.template first<typename FilterResGraph::EdgeIt>(); filter_res_graph.valid(e); filter_res_graph.next(e)) {
     366      for(typename FilterResGW::EdgeIt e=filter_res_graph.template first<typename FilterResGW::EdgeIt>(); filter_res_graph.valid(e); filter_res_graph.next(e)) {
    369367        //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
    370           typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
     368          typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    371369          original_edge.update();
    372370          original_edge.set(f, e);
    373371          residual_capacity.update();
    374           residual_capacity.set(f, res_graph.free(e));
     372          residual_capacity.set(f, res_graph.resCap(e));
    375373          //}
    376374      }
     
    381379        __augment=false;
    382380        //computing blocking flow with dfs
    383         typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
    384         DfsIterator5< TrivGraphWrapper<MutableGraph>, BlockingReachedMap > dfs(F);
    385         typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
    386         pred.set(sF, typename MutableGraph::Edge(INVALID));
     381        typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap;
     382        DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F);
     383        typename MG::NodeMap<typename MG::Edge> pred(F);
     384        pred.set(sF, INVALID);
    387385        //invalid iterators for sources
    388386
    389         typename MutableGraph::NodeMap<Number> free(F);
     387        typename MG::NodeMap<Number> free(F);
    390388
    391389        dfs.pushAndSetReached(sF);     
    392390        while (!dfs.finished()) {
    393391          ++dfs;
    394           if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
     392          if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
    395393            if (dfs.isBNodeNewlyReached()) {
    396               typename MutableGraph::Node v=F.aNode(dfs);
    397               typename MutableGraph::Node w=F.bNode(dfs);
     394              typename MG::Node v=F.aNode(dfs);
     395              typename MG::Node w=F.bNode(dfs);
    398396              pred.set(w, dfs);
    399397              if (F.valid(pred.get(v))) {
     
    409407             
    410408            } else {
    411               F.erase(typename MutableGraph::OutEdgeIt(dfs));
     409              F.erase(/*typename MG::OutEdgeIt*/(dfs));
    412410            }
    413411          }
     
    415413
    416414        if (__augment) {
    417           typename MutableGraph::Node n=tF;
     415          typename MG::Node n=tF;
    418416          Number augment_value=free.get(tF);
    419417          while (F.valid(pred.get(n))) {
    420             typename MutableGraph::Edge e=pred.get(n);
     418            typename MG::Edge e=pred.get(n);
    421419            res_graph.augment(original_edge.get(e), augment_value);
    422420            n=F.tail(e);
     
    434432
    435433    template<typename MutableGraph> bool augmentOnBlockingFlow1() {     
     434      typedef MutableGraph MG;
    436435      bool _augment=false;
    437436
    438       AugGraph res_graph(gw, *flow, *capacity);
     437      ResGW res_graph(gw, *flow, *capacity);
    439438
    440439      //bfs for distances on the residual graph
    441       typedef typename AugGraph::NodeMap<bool> ReachedMap;
    442       BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
     440      typedef typename ResGW::NodeMap<bool> ReachedMap;
     441      BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
    443442      bfs.pushAndSetReached(s);
    444       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
     443      typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
    445444
    446445      //F will contain the physical copy of the residual graph
    447       //with the set of edges which areon shortest paths
    448       MutableGraph F;
    449       typename AugGraph::NodeMap<typename MutableGraph::Node>
    450         res_graph_to_F(res_graph);
    451       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
     446      //with the set of edges which are on shortest paths
     447      MG F;
     448      typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
     449      for(typename ResGW::NodeIt n=res_graph.template first<typename ResGW::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
    452450        res_graph_to_F.set(n, F.addNode());
    453451      }
    454       typename MutableGraph::Node sF=res_graph_to_F.get(s);
    455       typename MutableGraph::Node tF=res_graph_to_F.get(t);
    456       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
    457       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
     452
     453      typename MG::Node sF=res_graph_to_F.get(s);
     454      typename MG::Node tF=res_graph_to_F.get(t);
     455      typename MG::EdgeMap<ResGWEdge> original_edge(F);
     456      typename MG::EdgeMap<Number> residual_capacity(F);
    458457
    459458      while ( !bfs.finished() ) {
    460         AugOutEdgeIt e=bfs;
     459        ResGWOutEdgeIt e=bfs;
    461460        if (res_graph.valid(e)) {
    462461          if (bfs.isBNodeNewlyReached()) {
    463462            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)));
     463            typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    465464            original_edge.update();
    466465            original_edge.set(f, e);
    467466            residual_capacity.update();
    468             residual_capacity.set(f, res_graph.free(e));
     467            residual_capacity.set(f, res_graph.resCap(e));
    469468          } else {
    470469            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)));
     470              typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    472471              original_edge.update();
    473472              original_edge.set(f, e);
    474473              residual_capacity.update();
    475               residual_capacity.set(f, res_graph.free(e));
     474              residual_capacity.set(f, res_graph.resCap(e));
    476475            }
    477476          }
     
    485484        __augment=false;
    486485        //computing blocking flow with dfs
    487         typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
    488         DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
    489         typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
    490         pred.set(sF, typename MutableGraph::Edge(INVALID));
     486        typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap;
     487        DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F);
     488        typename MG::NodeMap<typename MG::Edge> pred(F);
     489        pred.set(sF, INVALID);
    491490        //invalid iterators for sources
    492491
    493         typename MutableGraph::NodeMap<Number> free(F);
     492        typename MG::NodeMap<Number> free(F);
    494493
    495494        dfs.pushAndSetReached(sF);     
    496495        while (!dfs.finished()) {
    497496          ++dfs;
    498           if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
     497          if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
    499498            if (dfs.isBNodeNewlyReached()) {
    500               typename MutableGraph::Node v=F.aNode(dfs);
    501               typename MutableGraph::Node w=F.bNode(dfs);
     499              typename MG::Node v=F.aNode(dfs);
     500              typename MG::Node w=F.bNode(dfs);
    502501              pred.set(w, dfs);
    503502              if (F.valid(pred.get(v))) {
     
    513512             
    514513            } else {
    515               F.erase(typename MutableGraph::OutEdgeIt(dfs));
     514              F.erase(/*typename MG::OutEdgeIt*/(dfs));
    516515            }
    517516          }
     
    519518
    520519        if (__augment) {
    521           typename MutableGraph::Node n=tF;
     520          typename MG::Node n=tF;
    522521          Number augment_value=free.get(tF);
    523522          while (F.valid(pred.get(n))) {
    524             typename MutableGraph::Edge e=pred.get(n);
     523            typename MG::Edge e=pred.get(n);
    525524            res_graph.augment(original_edge.get(e), augment_value);
    526525            n=F.tail(e);
     
    533532       
    534533      }
     534           
     535      return _augment;
     536    }
     537
     538    bool augmentOnBlockingFlow2() {
     539      bool _augment=false;
     540
     541      ResGW res_graph(gw, *flow, *capacity);
     542
     543      typedef typename ResGW::NodeMap<bool> ReachedMap;
     544      BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
     545
     546      bfs.pushAndSetReached(s);
     547      DistanceMap<ResGW> dist(res_graph);
     548      while ( !bfs.finished() ) {
     549        ResGWOutEdgeIt e=bfs;
     550        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     551          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     552        }
     553        ++bfs;
     554      } //computing distances from s in the residual graph
     555
     556      //Subgraph containing the edges on some shortest paths
     557      typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
     558      FilterResGW filter_res_graph(res_graph, dist);
     559
     560      //Subgraph, which is able to delete edges which are already
     561      //met by the dfs
     562      typename FilterResGW::NodeMap<typename FilterResGW::OutEdgeIt>
     563        first_out_edges(filter_res_graph);
     564      typename FilterResGW::NodeIt v;
     565      for(filter_res_graph.first(v); filter_res_graph.valid(v);
     566          filter_res_graph.next(v))
     567      {
     568        typename FilterResGW::OutEdgeIt e;
     569        filter_res_graph.first(e, v);
     570        first_out_edges.set(v, e);
     571      }
     572      typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
     573        NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
     574      ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
     575
     576      bool __augment=true;
     577
     578      while (__augment) {
     579
     580        __augment=false;
     581        //computing blocking flow with dfs
     582        typedef typename ErasingResGW::NodeMap<bool> BlockingReachedMap;
     583        DfsIterator5< ErasingResGW, BlockingReachedMap >
     584          dfs(erasing_res_graph);
     585        typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt>
     586          pred(erasing_res_graph);
     587        pred.set(s, INVALID);
     588        //invalid iterators for sources
     589
     590        typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);
     591
     592        dfs.pushAndSetReached(s);
     593        while (!dfs.finished()) {
     594          ++dfs;
     595          if (erasing_res_graph.valid(
     596                /*typename ErasingResGW::OutEdgeIt*/(dfs)))
     597          {
     598            if (dfs.isBNodeNewlyReached()) {
     599         
     600              typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
     601              typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
     602
     603              pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
     604              if (erasing_res_graph.valid(pred.get(v))) {
     605                free.set(w, std::min(free.get(v), res_graph.resCap(dfs)));
     606              } else {
     607                free.set(w, res_graph.resCap(dfs));
     608              }
     609             
     610              if (w==t) {
     611                __augment=true;
     612                _augment=true;
     613                break;
     614              }
     615            } else {
     616              erasing_res_graph.erase(dfs);
     617            }
     618          }
     619        }       
     620
     621        if (__augment) {
     622          typename ErasingResGW::Node n=t;
     623          Number augment_value=free.get(n);
     624          while (erasing_res_graph.valid(pred.get(n))) {
     625            typename ErasingResGW::OutEdgeIt e=pred.get(n);
     626            res_graph.augment(e, augment_value);
     627            n=erasing_res_graph.tail(e);
     628            if (res_graph.resCap(e)==0)
     629              erasing_res_graph.erase(e);
     630          }
     631        }
     632     
     633      } //while (__augment)
    535634           
    536635      return _augment;
     
    625724//       return _augment;
    626725//     }
    627 //     void run() {
    628 //       //int num_of_augmentations=0;
    629 //       while (augmentOnShortestPath()) {
    630 //      //while (augmentOnBlockingFlow<MutableGraph>()) {
    631 //      //std::cout << ++num_of_augmentations << " ";
    632 //      //std::cout<<std::endl;
    633 //       }
    634 //     }
    635 //     template<typename MutableGraph> void run() {
    636 //       //int num_of_augmentations=0;
    637 //       //while (augmentOnShortestPath()) {
    638 //      while (augmentOnBlockingFlow<MutableGraph>()) {
    639 //      //std::cout << ++num_of_augmentations << " ";
    640 //      //std::cout<<std::endl;
    641 //       }
    642 //     }
     726
     727    void run() {
     728      //int num_of_augmentations=0;
     729      while (augmentOnShortestPath()) {
     730        //while (augmentOnBlockingFlow<MutableGraph>()) {
     731        //std::cout << ++num_of_augmentations << " ";
     732        //std::cout<<std::endl;
     733      }
     734    }
     735
     736    template<typename MutableGraph> void run() {
     737      //int num_of_augmentations=0;
     738      //while (augmentOnShortestPath()) {
     739        while (augmentOnBlockingFlow<MutableGraph>()) {
     740        //std::cout << ++num_of_augmentations << " ";
     741        //std::cout<<std::endl;
     742      }
     743    }
     744
    643745    Number flowValue() {
    644746      Number a=0;
     
    649751      return a;
    650752    }
     753
    651754  };
    652755
     
    685788     
    686789//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
    687 //       BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
     790//       BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph);
    688791//       typename AugGraph::NodeMap<AugEdge> pred(res_graph);
    689792//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
     
    693796//        //u+=flow->get(e);
    694797//        //if (u<1) {
    695 //          res_bfs.pushAndSetReached(s);
     798//          bfs.pushAndSetReached(s);
    696799//          pred.set(s, AugEdge(INVALID));
    697800//          //}
     
    703806//       Node n;
    704807//       //searching for augmenting path
    705 //       while ( !res_bfs.finished() ) {
    706 //      AugOutEdgeIt e=res_bfs;
    707 //      if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
     808//       while ( !bfs.finished() ) {
     809//      AugOutEdgeIt e=bfs;
     810//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    708811//        Node v=res_graph.tail(e);
    709812//        Node w=res_graph.head(e);
     
    726829//      }
    727830       
    728 //      ++res_bfs;
     831//      ++bfs;
    729832//       } //end of searching augmenting path
    730833
     
    763866// //       u+=flow->get(e);
    764867// //     if (u<1) {
    765 // //       res_bfs.pushAndSetReached(s);
     868// //       bfs.pushAndSetReached(s);
    766869// //       //pred.set(s, AugEdge(INVALID));
    767870// //     }
     
    10571160     
    10581161// //       typedef typename AugGraph::NodeMap<bool> ReachedMap;
    1059 // //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
     1162// //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
    10601163// //       for(typename std::list<Node>::const_iterator i=S.begin();
    10611164// //     i!=S.end(); ++i) {
    1062 // //   res_bfs.pushAndSetReached(*i);
     1165// //   bfs.pushAndSetReached(*i);
    10631166// //       }
    1064 // //       //res_bfs.pushAndSetReached(s);
     1167// //       //bfs.pushAndSetReached(s);
    10651168       
    10661169// //       typename AugGraph::NodeMap<AugEdge> pred(res_graph);
     
    10701173       
    10711174// //       //searching for augmenting path
    1072 // //       while ( !res_bfs.finished() ) {
    1073 // //   AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
    1074 // //   if (e.valid() && res_bfs.isBNodeNewlyReached()) {
     1175// //       while ( !bfs.finished() ) {
     1176// //   AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
     1177// //   if (e.valid() && bfs.isBNodeNewlyReached()) {
    10751178// //     Node v=res_graph.tail(e);
    10761179// //     Node w=res_graph.head(e);
     
    10881191// //   }
    10891192       
    1090 // //   ++res_bfs;
     1193// //   ++bfs;
    10911194// //       } //end of searching augmenting path
    10921195
Note: See TracChangeset for help on using the changeset viewer.