COIN-OR::LEMON - Graph Library

Changeset 602:580b329c2a0c in lemon-0.x for src/work/jacint


Ignore:
Timestamp:
05/10/04 18:59:20 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@782
Message:

bfs_iterator -> bfs_dfs.h, some docs

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/max_flow.h

    r586 r602  
    4545
    4646#include <hugo/graph_wrapper.h>
    47 #include <bfs_iterator.h>
     47#include <bfs_dfs.h>
    4848#include <hugo/invalid.h>
    4949#include <hugo/maps.h>
     
    5656
    5757
    58 //  ///\author Marton Makai, Jacint Szabo
     58  //  ///\author Marton Makai, Jacint Szabo
    5959  /// A class for computing max flows and related quantities.
    6060  template <typename Graph, typename Num,
     
    8989    //typename Graph::template NodeMap<int> level;   
    9090    typename Graph::template NodeMap<Num> excess;
    91 //   protected:
    92 //     MaxFlow() { }
    93 //     void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
    94 //           FlowMap& _flow)
    95 //       {
    96 //      g=&_G;
    97 //      s=_s;
    98 //      t=_t;
    99 //      capacity=&_capacity;
    100 //      flow=&_flow;
    101 //      n=_G.nodeNum;
    102 //      level.set (_G); //kellene vmi ilyesmi fv
    103 //      excess(_G,0); //itt is
    104 //       }
     91    //   protected:
     92    //     MaxFlow() { }
     93    //     void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
     94    //       FlowMap& _flow)
     95    //       {
     96    //  g=&_G;
     97    //  s=_s;
     98    //  t=_t;
     99    //  capacity=&_capacity;
     100    //  flow=&_flow;
     101    //  n=_G.nodeNum;
     102    //  level.set (_G); //kellene vmi ilyesmi fv
     103    //  excess(_G,0); //itt is
     104    //       }
    105105
    106106  public:
     
    363363
    364364    void preflowPreproc ( flowEnum fe, VecStack& active,
    365                           VecNode& level_list, NNMap& left, NNMap& right ) {
    366 
    367                             std::queue<Node> bfs_queue;
    368      
    369                             switch ( fe ) {
    370                             case ZERO_FLOW:
    371                               {
    372                                 //Reverse_bfs from t, to find the starting level.
    373                                 level.set(t,0);
    374                                 bfs_queue.push(t);
    375        
    376                                 while (!bfs_queue.empty()) {
    377            
    378                                   Node v=bfs_queue.front();     
    379                                   bfs_queue.pop();
    380                                   int l=level[v]+1;
    381            
    382                                   InEdgeIt e;
    383                                   for(g->first(e,v); g->valid(e); g->next(e)) {
    384                                     Node w=g->tail(e);
    385                                     if ( level[w] == n && w != s ) {
    386                                       bfs_queue.push(w);
    387                                       Node first=level_list[l];
    388                                       if ( g->valid(first) ) left.set(first,w);
    389                                       right.set(w,first);
    390                                       level_list[l]=w;
    391                                       level.set(w, l);
    392                                     }
    393                                   }
    394                                 }
    395          
    396                                 //the starting flow
    397                                 OutEdgeIt e;
    398                                 for(g->first(e,s); g->valid(e); g->next(e))
    399                                   {
    400                                     Num c=(*capacity)[e];
    401                                     if ( c <= 0 ) continue;
    402                                     Node w=g->head(e);
    403                                     if ( level[w] < n ) {         
    404                                       if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    405                                       flow->set(e, c);
    406                                       excess.set(w, excess[w]+c);
    407                                     }
    408                                   }
    409                                 break;
    410                               }
    411        
    412                             case GEN_FLOW:
    413                             case PREFLOW:
    414                               {
    415                                 //Reverse_bfs from t in the residual graph,
    416                                 //to find the starting level.
    417                                 level.set(t,0);
    418                                 bfs_queue.push(t);
    419          
    420                                 while (!bfs_queue.empty()) {
    421            
    422                                   Node v=bfs_queue.front();     
    423                                   bfs_queue.pop();
    424                                   int l=level[v]+1;
    425            
    426                                   InEdgeIt e;
    427                                   for(g->first(e,v); g->valid(e); g->next(e)) {
    428                                     if ( (*capacity)[e] <= (*flow)[e] ) continue;
    429                                     Node w=g->tail(e);
    430                                     if ( level[w] == n && w != s ) {
    431                                       bfs_queue.push(w);
    432                                       Node first=level_list[l];
    433                                       if ( g->valid(first) ) left.set(first,w);
    434                                       right.set(w,first);
    435                                       level_list[l]=w;
    436                                       level.set(w, l);
    437                                     }
    438                                   }
    439            
    440                                   OutEdgeIt f;
    441                                   for(g->first(f,v); g->valid(f); g->next(f)) {
    442                                     if ( 0 >= (*flow)[f] ) continue;
    443                                     Node w=g->head(f);
    444                                     if ( level[w] == n && w != s ) {
    445                                       bfs_queue.push(w);
    446                                       Node first=level_list[l];
    447                                       if ( g->valid(first) ) left.set(first,w);
    448                                       right.set(w,first);
    449                                       level_list[l]=w;
    450                                       level.set(w, l);
    451                                     }
    452                                   }
    453                                 }
    454          
    455          
    456                                 //the starting flow
    457                                 OutEdgeIt e;
    458                                 for(g->first(e,s); g->valid(e); g->next(e))
    459                                   {
    460                                     Num rem=(*capacity)[e]-(*flow)[e];
    461                                     if ( rem <= 0 ) continue;
    462                                     Node w=g->head(e);
    463                                     if ( level[w] < n ) {         
    464                                       if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    465                                       flow->set(e, (*capacity)[e]);
    466                                       excess.set(w, excess[w]+rem);
    467                                     }
    468                                   }
    469          
    470                                 InEdgeIt f;
    471                                 for(g->first(f,s); g->valid(f); g->next(f))
    472                                   {
    473                                     if ( (*flow)[f] <= 0 ) continue;
    474                                     Node w=g->tail(f);
    475                                     if ( level[w] < n ) {         
    476                                       if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    477                                       excess.set(w, excess[w]+(*flow)[f]);
    478                                       flow->set(f, 0);
    479                                     }
    480                                   } 
    481                                 break;
    482                               } //case PREFLOW
    483                             }
    484                           } //preflowPreproc
     365                          VecNode& level_list, NNMap& left, NNMap& right )
     366    {
     367
     368      std::queue<Node> bfs_queue;
     369     
     370      switch ( fe ) {
     371      case ZERO_FLOW:
     372        {
     373          //Reverse_bfs from t, to find the starting level.
     374          level.set(t,0);
     375          bfs_queue.push(t);
     376       
     377          while (!bfs_queue.empty()) {
     378           
     379            Node v=bfs_queue.front();   
     380            bfs_queue.pop();
     381            int l=level[v]+1;
     382           
     383            InEdgeIt e;
     384            for(g->first(e,v); g->valid(e); g->next(e)) {
     385              Node w=g->tail(e);
     386              if ( level[w] == n && w != s ) {
     387                bfs_queue.push(w);
     388                Node first=level_list[l];
     389                if ( g->valid(first) ) left.set(first,w);
     390                right.set(w,first);
     391                level_list[l]=w;
     392                level.set(w, l);
     393              }
     394            }
     395          }
     396         
     397          //the starting flow
     398          OutEdgeIt e;
     399          for(g->first(e,s); g->valid(e); g->next(e))
     400            {
     401              Num c=(*capacity)[e];
     402              if ( c <= 0 ) continue;
     403              Node w=g->head(e);
     404              if ( level[w] < n ) {       
     405                if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
     406                flow->set(e, c);
     407                excess.set(w, excess[w]+c);
     408              }
     409            }
     410          break;
     411        }
     412       
     413      case GEN_FLOW:
     414      case PREFLOW:
     415        {
     416          //Reverse_bfs from t in the residual graph,
     417          //to find the starting level.
     418          level.set(t,0);
     419          bfs_queue.push(t);
     420         
     421          while (!bfs_queue.empty()) {
     422           
     423            Node v=bfs_queue.front();   
     424            bfs_queue.pop();
     425            int l=level[v]+1;
     426           
     427            InEdgeIt e;
     428            for(g->first(e,v); g->valid(e); g->next(e)) {
     429              if ( (*capacity)[e] <= (*flow)[e] ) continue;
     430              Node w=g->tail(e);
     431              if ( level[w] == n && w != s ) {
     432                bfs_queue.push(w);
     433                Node first=level_list[l];
     434                if ( g->valid(first) ) left.set(first,w);
     435                right.set(w,first);
     436                level_list[l]=w;
     437                level.set(w, l);
     438              }
     439            }
     440           
     441            OutEdgeIt f;
     442            for(g->first(f,v); g->valid(f); g->next(f)) {
     443              if ( 0 >= (*flow)[f] ) continue;
     444              Node w=g->head(f);
     445              if ( level[w] == n && w != s ) {
     446                bfs_queue.push(w);
     447                Node first=level_list[l];
     448                if ( g->valid(first) ) left.set(first,w);
     449                right.set(w,first);
     450                level_list[l]=w;
     451                level.set(w, l);
     452              }
     453            }
     454          }
     455         
     456         
     457          //the starting flow
     458          OutEdgeIt e;
     459          for(g->first(e,s); g->valid(e); g->next(e))
     460            {
     461              Num rem=(*capacity)[e]-(*flow)[e];
     462              if ( rem <= 0 ) continue;
     463              Node w=g->head(e);
     464              if ( level[w] < n ) {       
     465                if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
     466                flow->set(e, (*capacity)[e]);
     467                excess.set(w, excess[w]+rem);
     468              }
     469            }
     470         
     471          InEdgeIt f;
     472          for(g->first(f,s); g->valid(f); g->next(f))
     473            {
     474              if ( (*flow)[f] <= 0 ) continue;
     475              Node w=g->tail(f);
     476              if ( level[w] < n ) {       
     477                if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
     478                excess.set(w, excess[w]+(*flow)[f]);
     479                flow->set(f, 0);
     480              }
     481            } 
     482          break;
     483        } //case PREFLOW
     484      }
     485    } //preflowPreproc
    485486
    486487
Note: See TracChangeset for help on using the changeset viewer.