COIN-OR::LEMON - Graph Library

Changeset 269:07af3069c0b8 in lemon-0.x


Ignore:
Timestamp:
03/31/04 17:50:21 (20 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

Location:
src/work
Files:
3 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
  • src/work/marci/edmonds_karp_demo.cc

    r268 r269  
    9191
    9292  {
    93     //std::cout << "SmartGraph..." << std::endl;
    9493    typedef TrivGraphWrapper<const Graph> GW;
    9594    GW gw(G);
     
    123122
    124123  {
    125     //std::cout << "SmartGraph..." << std::endl;
    126124    typedef TrivGraphWrapper<const Graph> GW;
    127125    GW gw(G);
     
    154152  }
    155153
    156 //   {
    157 //     std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
    158 //     Graph::EdgeMap<int> flow(G); //0 flow
    159 
    160 //     Timer ts;
    161 //     ts.reset();
    162 
    163 //     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    164 //     int i=0;
    165 //     while (max_flow_test.augmentOnBlockingFlow2()) {
    166 // //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    167 // //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    168 // //     }
    169 // //     std::cout<<std::endl;
    170 //       ++i;
    171 //     }
    172 
    173 // //   std::cout << "maximum flow: "<< std::endl;
    174 // //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
    175 // //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    176 // //   }
    177 // //   std::cout<<std::endl;
    178 //     std::cout << "elapsed time: " << ts << std::endl;
    179 //     std::cout << "number of augmentation phases: " << i << std::endl;
    180 //     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    181 //   }
     154  {
     155    typedef TrivGraphWrapper<const Graph> GW;
     156    GW gw(G);
     157    std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
     158    GW::EdgeMap<int> flow(G); //0 flow
     159
     160    Timer ts;
     161    ts.reset();
     162
     163    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
     164    EMW cw(cap);
     165    MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
     166    int i=0;
     167    while (max_flow_test.augmentOnBlockingFlow2()) {
     168//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
     169//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     170//     }
     171//     std::cout<<std::endl;
     172      ++i;
     173    }
     174
     175//   std::cout << "maximum flow: "<< std::endl;
     176//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
     177//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     178//   }
     179//   std::cout<<std::endl;
     180    std::cout << "elapsed time: " << ts << std::endl;
     181    std::cout << "number of augmentation phases: " << i << std::endl;
     182    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     183  }
    182184
    183185  {
     
    190192    ts.reset();
    191193
    192     //CM cm;
    193194    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
    194195    EMW cw(cap);
  • src/work/marci/graph_wrapper.h

    r266 r269  
    10001000      OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
    10011001        resG.gw.first(out, v);
    1002         while( resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
     1002        while( resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
    10031003        if (!resG.gw.valid(out)) {
    10041004          out_or_in=0;
    10051005          resG.gw.first(in, v);
    1006           while( resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
     1006          while( resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
    10071007        }
    10081008      }
     
    10121012//        Node v=/*resG->*/G->aNode(out);
    10131013//        ++out;
    1014 //        while( out.valid() && !(Edge::free()>0) ) { ++out; }
     1014//        while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
    10151015//        if (!out.valid()) {
    10161016//          out_or_in=0;
    10171017//          G->first(in, v);
    1018 //          while( in.valid() && !(Edge::free()>0) ) { ++in; }
     1018//          while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
    10191019//        }
    10201020//      } else {
    10211021//        ++in;
    1022 //        while( in.valid() && !(Edge::free()>0) ) { ++in; }
     1022//        while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
    10231023//      }
    10241024//      return *this;
     
    10381038      EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {
    10391039        resG.gw.first(v);
    1040         if (resG.gw.valid(v)) resG.gw.first(out, v); else out=/*OldOutEdgeIt*/(INVALID);
    1041         while (resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
     1040        if (resG.gw.valid(v)) resG.gw.first(out, v); else out=INVALID;
     1041        while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
    10421042        while (resG.gw.valid(v) && !resG.gw.valid(out)) {
    10431043          resG.gw.next(v);
    10441044          if (resG.gw.valid(v)) resG.gw.first(out, v);
    1045           while (resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
     1045          while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
    10461046        }
    10471047        if (!resG.gw.valid(out)) {
    10481048          out_or_in=0;
    10491049          resG.gw.first(v);
    1050           if (resG.gw.valid(v)) resG.gw.first(in, v); else in=/*OldInEdgeIt*/(INVALID);
    1051           while (resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
     1050          if (resG.gw.valid(v)) resG.gw.first(in, v); else in=INVALID;
     1051          while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
    10521052          while (resG.gw.valid(v) && !resG.gw.valid(in)) {
    10531053            resG.gw.next(v);
    10541054            if (resG.gw.valid(v)) resG.gw.first(in, v);
    1055             while (resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
     1055            while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
    10561056          }
    10571057        }
     
    10601060//      if (out_or_in) {
    10611061//        ++out;
    1062 //        while (out.valid() && !(Edge::free()>0) ) { ++out; }
     1062//        while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
    10631063//        while (v.valid() && !out.valid()) {
    10641064//          ++v;
    10651065//          if (v.valid()) G->first(out, v);
    1066 //          while (out.valid() && !(Edge::free()>0) ) { ++out; }
     1066//          while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
    10671067//        }
    10681068//        if (!out.valid()) {
     
    10701070//          G->first(v);
    10711071//          if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
    1072 //          while (in.valid() && !(Edge::free()>0) ) { ++in; }
     1072//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
    10731073//          while (v.valid() && !in.valid()) {
    10741074//            ++v;
    10751075//            if (v.valid()) G->first(in, v);
    1076 //            while (in.valid() && !(Edge::free()>0) ) { ++in; }
     1076//            while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
    10771077//          } 
    10781078//        }
    10791079//      } else {
    10801080//        ++in;
    1081 //        while (in.valid() && !(Edge::free()>0) ) { ++in; }
     1081//        while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
    10821082//        while (v.valid() && !in.valid()) {
    10831083//          ++v;
    10841084//          if (v.valid()) G->first(in, v);
    1085 //          while (in.valid() && !(Edge::free()>0) ) { ++in; }
     1085//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
    10861086//        }
    10871087//      }
     
    11061106        Node v=gw.aNode(e.out);
    11071107        gw.next(e.out);
    1108         while( gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
     1108        while( gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
    11091109        if (!gw.valid(e.out)) {
    11101110          e.out_or_in=0;
    11111111          gw.first(e.in, v);
    1112           while( gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
     1112          while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
    11131113        }
    11141114      } else {
    11151115        gw.next(e.in);
    1116         while( gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
     1116        while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
    11171117      }
    11181118      return e;
     
    11221122      if (e.out_or_in) {
    11231123        gw.next(e.out);
    1124         while (gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
     1124        while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
    11251125          while (gw.valid(e.v) && !gw.valid(e.out)) {
    11261126            gw.next(e.v);
    11271127            if (gw.valid(e.v)) gw.first(e.out, e.v);
    1128             while (gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
     1128            while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
    11291129          }
    11301130          if (!gw.valid(e.out)) {
    11311131            e.out_or_in=0;
    11321132            gw.first(e.v);
    1133             if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=/*OldInEdgeIt*/(INVALID);
    1134             while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
     1133            if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=INVALID;
     1134            while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
    11351135            while (gw.valid(e.v) && !gw.valid(e.in)) {
    11361136              gw.next(e.v);
    11371137              if (gw.valid(e.v)) gw.first(e.in, e.v);
    1138               while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
     1138              while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
    11391139            } 
    11401140          }
    11411141        } else {
    11421142          gw.next(e.in);
    1143           while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
     1143          while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
    11441144          while (gw.valid(e.v) && !gw.valid(e.in)) {
    11451145            gw.next(e.v);
    11461146            if (gw.valid(e.v)) gw.first(e.in, e.v);
    1147             while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
     1147            while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
    11481148          }
    11491149        }
     
    11941194    }
    11951195
    1196     Number free(const Edge& e) const {
     1196    Number resCap(const Edge& e) const {
    11971197      if (e.out_or_in)
    11981198        return (capacity->get(e.out)-flow->get(e.out));
     
    12011201    }
    12021202
    1203     Number free(OldOutEdgeIt out) const {
     1203    Number resCap(OldOutEdgeIt out) const {
    12041204      return (capacity->get(out)-flow->get(out));
    12051205    }
    12061206   
    1207     Number free(OldInEdgeIt in) const {
     1207    Number resCap(OldInEdgeIt in) const {
    12081208      return (flow->get(in));
    12091209    }
     
    12461246      }
    12471247    };
     1248  };
     1249
     1250  //Subgraph on the same node-set and partial edge-set
     1251  template<typename GraphWrapper, typename FirstOutEdgesMap>
     1252  class ErasingFirstGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
     1253  protected:
     1254    FirstOutEdgesMap* first_out_edges;
     1255  public:
     1256    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
     1257    typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
     1258    typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
     1259    typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
     1260    typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
     1261    typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
     1262
     1263    ErasingFirstGraphWrapper(GraphWrapper _gw, FirstOutEdgesMap& _first_out_edges) :
     1264      GraphWrapperSkeleton<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { } 
     1265
     1266    template<typename I> I& first(I& i) const {
     1267      gw.first(i);
     1268      //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
     1269      return i;
     1270    }
     1271    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
     1272      e=first_out_edges->get(n);
     1273      return e;
     1274    }
     1275    template<typename I, typename P> I& first(I& i, const P& p) const {
     1276      gw.first(i, p);
     1277      //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
     1278      return i;
     1279    }
     1280   
     1281    //template<typename I> I getNext(const I& i) const {
     1282    //  return gw.getNext(i);
     1283    //}
     1284    template<typename I> I& next(I &i) const {
     1285      gw.next(i);
     1286      //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
     1287      return i;
     1288    }
     1289   
     1290    template< typename It > It first() const {
     1291      It e; this->first(e); return e; }
     1292   
     1293    template< typename It > It first(const Node& v) const {
     1294      It e; this->first(e, v); return e; }
     1295
     1296    void erase(const OutEdgeIt& e) const {
     1297      OutEdgeIt f=e;
     1298      this->next(f);
     1299      first_out_edges->set(this->tail(e), f);
     1300    }
    12481301  };
    12491302
Note: See TracChangeset for help on using the changeset viewer.