COIN-OR::LEMON - Graph Library

Changeset 168:27fbd1559fb7 in lemon-0.x for src/work/edmonds_karp.hh


Ignore:
Timestamp:
03/11/04 15:15:07 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@239
Message:

graph wrapper improvements, blocking flow on fly

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/edmonds_karp.hh

    r155 r168  
    280280     
    281281      typedef typename AugGraph::NodeMap<bool> ReachedMap;
    282       BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
     282      BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
    283283      res_bfs.pushAndSetReached(s);
    284284       
     
    297297          pred.set(w, e);
    298298          if (res_graph.valid(pred.get(v))) {
    299             free.set(w, std::min(free.get(v), e.free()));
     299            free.set(w, std::min(free.get(v), res_graph.free(e)));
    300300          } else {
    301             free.set(w, e.free());
     301            free.set(w, res_graph.free(e));
    302302          }
    303303          if (res_graph.head(e)==t) { _augment=true; break; }
     
    312312        while (res_graph.valid(pred.get(n))) {
    313313          AugEdgeIt e=pred.get(n);
    314           e.augment(augment_value);
     314          res_graph.augment(e, augment_value);
     315          //e.augment(augment_value);
    315316          n=res_graph.tail(e);
    316317        }
     
    359360          original_edge.set(f, e);
    360361          residual_capacity.update();
    361           residual_capacity.set(f, e.free());
     362          residual_capacity.set(f, res_graph.free(e));
    362363        }
    363364      }
     
    377378          ++dfs;
    378379          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
    379             //std::cout << "OutEdgeIt: " << dfs;
    380             //std::cout << " aNode: " << F.aNode(dfs);
    381             //std::cout << " bNode: " << F.bNode(dfs) << " ";
     380            if (dfs.isBNodeNewlyReached()) {
     381//            std::cout << "OutEdgeIt: " << dfs;
     382//            std::cout << " aNode: " << F.aNode(dfs);
     383//            std::cout << " bNode: " << F.bNode(dfs) << " ";
    382384         
    383             typename MutableGraph::NodeIt v=F.aNode(dfs);
    384             typename MutableGraph::NodeIt w=F.bNode(dfs);
    385             pred.set(w, dfs);
    386             if (F.valid(pred.get(v))) {
    387               free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
     385              typename MutableGraph::NodeIt v=F.aNode(dfs);
     386              typename MutableGraph::NodeIt w=F.bNode(dfs);
     387              pred.set(w, dfs);
     388              if (F.valid(pred.get(v))) {
     389                free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
     390              } else {
     391                free.set(w, residual_capacity.get(dfs));
     392              }
     393              if (w==tF) {
     394                //std::cout << "AUGMENTATION"<<std::endl;
     395                __augment=true;
     396                _augment=true;
     397                break;
     398              }
     399             
    388400            } else {
    389               free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/);
    390             }
    391             if (w==tF) {
    392               //std::cout << "AUGMENTATION"<<std::endl;
    393               __augment=true;
    394               _augment=true;
    395               break;
    396             }
    397           } else {
    398             //std::cout << "OutEdgeIt: " << "invalid";
    399             //std::cout << " aNode: " << dfs.aNode();
    400             //std::cout << " bNode: " << "invalid" << " ";
    401           }
    402           if (dfs.isBNodeNewlyReached()) {
    403             //std::cout << "bNodeIsNewlyReached ";
    404           } else {
    405             //std::cout << "bNodeIsNotNewlyReached ";
    406             if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
    407               //std::cout << "DELETE ";
    408401              F.erase(typename MutableGraph::OutEdgeIt(dfs));
    409402            }
    410403          }
    411           //if (dfs.isANodeExamined()) {
    412             //std::cout << "aNodeIsExamined ";
    413             //} else {
    414             //std::cout << "aNodeIsNotExamined ";
    415             //}
    416           //std::cout<<std::endl;
    417404        }
    418405
     
    422409          while (F.valid(pred.get(n))) {
    423410            typename MutableGraph::EdgeIt e=pred.get(n);
    424             original_edge.get(e).augment(augment_value);
     411            res_graph.augment(original_edge.get(e), augment_value);
     412            //original_edge.get(e).augment(augment_value);
    425413            n=F.tail(e);
    426414            if (residual_capacity.get(e)==augment_value)
     
    428416            else
    429417              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
     418          }
     419        }
     420       
     421      }
     422           
     423      return _augment;
     424    }
     425    bool augmentOnBlockingFlow2() {
     426      bool _augment=false;
     427
     428      //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
     429      typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
     430      typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
     431      typedef typename EAugGraph::EdgeIt EAugEdgeIt;
     432
     433      EAugGraph res_graph(*G, *flow, *capacity);
     434
     435      //std::cout << "meg jo1" << std::endl;
     436
     437      //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
     438      BfsIterator4<
     439        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
     440        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
     441        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
     442     
     443      //std::cout << "meg jo2" << std::endl;
     444
     445      bfs.pushAndSetReached(s);
     446      //std::cout << "meg jo2.5" << std::endl;
     447
     448      //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
     449      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
     450        NodeMap<int>& dist=res_graph.dist;
     451      //std::cout << "meg jo2.6" << std::endl;
     452
     453      while ( !bfs.finished() ) {
     454        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
     455//      EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
     456        //if (res_graph.valid(e)) {
     457        //    std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;
     458        //}
     459        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     460          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     461        }
     462       
     463        ++bfs; 
     464      } //computing distances from s in the residual graph
     465
     466
     467      //std::cout << "meg jo3" << std::endl;
     468
     469//       typedef typename EAugGraph::EachNodeIt EAugEachNodeIt;
     470//       for(EAugEachNodeIt n=res_graph.template first<EAugEachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
     471//      std::cout << "dist: " << dist.get(n) << std::endl;
     472//       }
     473
     474      bool __augment=true;
     475
     476      while (__augment) {
     477//      std::cout << "new iteration"<< std::endl;
     478
     479        __augment=false;
     480        //computing blocking flow with dfs
     481        typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
     482        DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
     483          dfs(res_graph);
     484        typename EAugGraph::NodeMap<EAugEdgeIt> pred(res_graph); //invalid iterators
     485        typename EAugGraph::NodeMap<Number> free(res_graph);
     486
     487        dfs.pushAndSetReached(s);
     488        while (!dfs.finished()) {
     489          ++dfs;
     490          if (res_graph.valid(EAugOutEdgeIt(dfs))) {
     491            if (dfs.isBNodeNewlyReached()) {
     492//            std::cout << "OutEdgeIt: " << dfs;
     493//            std::cout << " aNode: " << res_graph.aNode(dfs);
     494//            std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
     495//            std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
     496         
     497              typename EAugGraph::NodeIt v=res_graph.aNode(dfs);
     498              typename EAugGraph::NodeIt w=res_graph.bNode(dfs);
     499
     500              pred.set(w, EAugOutEdgeIt(dfs));
     501
     502              //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;
     503              if (res_graph.valid(pred.get(v))) {
     504                free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs))));
     505              } else {
     506                free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs)));
     507              }
     508             
     509              if (w==t) {
     510//              std::cout << "t is reached, AUGMENTATION"<<std::endl;
     511                __augment=true;
     512                _augment=true;
     513                break;
     514              }
     515            } else {
     516//            std::cout << "<<DELETE ";
     517//            std::cout << " aNode: " << res_graph.aNode(dfs);
     518//            std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
     519//            std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
     520//            std::cout << "DELETE>> ";
     521
     522              res_graph.erase(dfs);
     523            }
     524          }
     525
     526        }
     527
     528        if (__augment) {
     529          typename EAugGraph::NodeIt n=t;
     530          Number augment_value=free.get(t);
     531//        std::cout << "av:" << augment_value << std::endl;
     532          while (res_graph.valid(pred.get(n))) {
     533            EAugEdgeIt e=pred.get(n);
     534            res_graph.augment(e, augment_value);
     535            //e.augment(augment_value);
     536            n=res_graph.tail(e);
     537            if (res_graph.free(e)==0)
     538              res_graph.erase(e);
    430539          }
    431540        }
Note: See TracChangeset for help on using the changeset viewer.