COIN-OR::LEMON - Graph Library

Changeset 191:efea403c9595 in lemon-0.x


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

.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/edmonds_karp.h

    r175 r191  
    267267    typedef typename AugGraph::Edge AugEdge;
    268268
    269     //AugGraph res_graph;   
    270     //typedef typename AugGraph::NodeMap<bool> ReachedMap;
    271     //typename AugGraph::NodeMap<AugEdge> pred;
    272     //typename AugGraph::NodeMap<Number> free;
    273269  public:
    274270    MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
    275       G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //, 
    276       //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
    277       { }
     271      G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
    278272    bool augmentOnShortestPath() {
    279273      AugGraph res_graph(*G, *flow, *capacity);
     
    291285      //searching for augmenting path
    292286      while ( !res_bfs.finished() ) {
    293         AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
     287        AugOutEdgeIt e=res_bfs;
    294288        if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
    295289          Node v=res_graph.tail(e);
     
    313307          AugEdge e=pred.get(n);
    314308          res_graph.augment(e, augment_value);
    315           //e.augment(augment_value);
    316309          n=res_graph.tail(e);
    317310        }
     
    321314    }
    322315
    323     template<typename MutableGraph> bool augmentOnBlockingFlow() {
    324      
    325 //       std::cout << "number of nodes: " << G->nodeNum() << std::endl;
    326 //       typename Graph::NodeIt n;
    327 //       G->first(n);
    328 //       for( ; G->valid(n); G->next(n)) {
    329 //      std::cout << G->id(n) << std::endl;
    330 //       }
    331 //       std::cout << "meg elek 1";
    332 
    333 //       for(typename Graph::NodeIt n=G->template first<typename Graph::NodeIt>(); G->valid(n); G->next(n)) {
    334 //      std::cout << G->id(n) << std::endl;
    335 //       }
    336 //       std::cout << "meg elek 2";
    337      
     316    template<typename MutableGraph> bool augmentOnBlockingFlow() {     
    338317      bool _augment=false;
    339318
     
    346325      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
    347326      while ( !bfs.finished() ) {
    348         AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
     327        AugOutEdgeIt e=bfs;
    349328        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    350329          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     
    353332        ++bfs;
    354333      } //computing distances from s in the residual graph
    355 
    356 //       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
    357 //      std::cout << res_graph.id(n) << std::endl;
    358 //       }
    359 //       std::cout << "meg elek";
    360334
    361335      MutableGraph F;
     
    384358      }
    385359
    386 //       for(typename MutableGraph::NodeIt n=F.template first<typename MutableGraph::NodeIt>(); F.valid(n); F.next(n)) {
    387 //      std::cout << F.id(n) << std::endl;
    388 //       }
    389 
    390360      bool __augment=true;
    391361
     
    406376          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
    407377            if (dfs.isBNodeNewlyReached()) {
    408 //            std::cout << "OutEdgeIt: " << dfs;
    409 //            std::cout << " aNode: " << F.aNode(dfs);
    410 //            std::cout << " bNode: " << F.bNode(dfs) << " ";
    411          
    412378              typename MutableGraph::Node v=F.aNode(dfs);
    413379              typename MutableGraph::Node w=F.bNode(dfs);
     
    419385              }
    420386              if (w==tF) {
    421                 //std::cout << "AUGMENTATION"<<std::endl;
    422387                __augment=true;
    423388                _augment=true;
     
    437402            typename MutableGraph::Edge e=pred.get(n);
    438403            res_graph.augment(original_edge.get(e), augment_value);
    439             //original_edge.get(e).augment(augment_value);
    440404            n=F.tail(e);
    441405            if (residual_capacity.get(e)==augment_value)
     
    460424      EAugGraph res_graph(*G, *flow, *capacity);
    461425
    462       //std::cout << "meg jo1" << std::endl;
    463 
    464426      //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
    465427      BfsIterator4<
     
    468430        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
    469431     
    470       //std::cout << "meg jo2" << std::endl;
    471 
    472432      bfs.pushAndSetReached(s);
    473       //std::cout << "meg jo2.5" << std::endl;
    474 
    475       //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
     433
    476434      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
    477435        NodeMap<int>& dist=res_graph.dist;
    478       //std::cout << "meg jo2.6" << std::endl;
    479436
    480437      while ( !bfs.finished() ) {
    481438        typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
    482 //      EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
    483         //if (res_graph.valid(e)) {
    484         //    std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;
    485         //}
    486439        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    487440          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    488441        }
    489        
    490442        ++bfs; 
    491443      } //computing distances from s in the residual graph
    492444
    493 
    494       //std::cout << "meg jo3" << std::endl;
    495 
    496 //       typedef typename EAugGraph::NodeIt EAugNodeIt;
    497 //       for(EAugNodeIt n=res_graph.template first<EAugNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
    498 //      std::cout << "dist: " << dist.get(n) << std::endl;
    499 //       }
    500 
    501445      bool __augment=true;
    502446
    503447      while (__augment) {
    504 //      std::cout << "new iteration"<< std::endl;
    505448
    506449        __augment=false;
     
    520463          if (res_graph.valid(EAugOutEdgeIt(dfs))) {
    521464            if (dfs.isBNodeNewlyReached()) {
    522 //            std::cout << "OutEdgeIt: " << dfs;
    523 //            std::cout << " aNode: " << res_graph.aNode(dfs);
    524 //            std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
    525 //            std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
    526465         
    527466              typename EAugGraph::Node v=res_graph.aNode(dfs);
     
    529468
    530469              pred.set(w, EAugOutEdgeIt(dfs));
    531 
    532               //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;
    533470              if (res_graph.valid(pred.get(v))) {
    534                 free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs))));
     471                free.set(w, std::min(free.get(v), res_graph.free(dfs)));
    535472              } else {
    536                 free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs)));
     473                free.set(w, res_graph.free(dfs));
    537474              }
    538475             
    539476              if (w==t) {
    540 //              std::cout << "t is reached, AUGMENTATION"<<std::endl;
    541477                __augment=true;
    542478                _augment=true;
     
    544480              }
    545481            } else {
    546 //            std::cout << "<<DELETE ";
    547 //            std::cout << " aNode: " << res_graph.aNode(dfs);
    548 //            std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
    549 //            std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
    550 //            std::cout << "DELETE>> ";
    551 
    552482              res_graph.erase(dfs);
    553483            }
     
    559489          typename EAugGraph::Node n=t;
    560490          Number augment_value=free.get(t);
    561 //        std::cout << "av:" << augment_value << std::endl;
    562491          while (res_graph.valid(pred.get(n))) {
    563492            EAugEdge e=pred.get(n);
    564493            res_graph.augment(e, augment_value);
    565             //e.augment(augment_value);
    566494            n=res_graph.tail(e);
    567495            if (res_graph.free(e)==0)
Note: See TracChangeset for help on using the changeset viewer.