COIN-OR::LEMON - Graph Library

Changeset 451:6b36be4cffa4 in lemon-0.x for src/work/jacint/preflow.h


Ignore:
Timestamp:
04/28/04 00:59:15 (21 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@599
Message:

Changes in the interface and new test program added.

File:
1 edited

Legend:

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

    r389 r451  
    11// -*- C++ -*-
    2 
    3 //run gyorsan tudna adni a minmincutot a 2 fazis elejen , ne vegyuk be konstruktorba egy cutmapet?
    4 //constzero jo igy?
    5 
    6 //majd marci megmondja betegyem-e bfs-t meg resgraphot
    72
    83/*
     
    116 gap
    127 list 'level_list' on the nodes on level i implemented by hand
    13  stack 'active' on the active nodes on level i implemented by hand
     8 stack 'active' on the active nodes on level i
    149 runs heuristic 'highest label' for H1*n relabels
    1510 runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
    1611 
    17 Parameters H0 and H1 are initialized to 20 and 10.
     12Parameters H0 and H1 are initialized to 20 and 1.
    1813
    1914Constructors:
     
    2924
    3025void minMinCut(CutMap& M) : sets M to the characteristic vector of the
    31      minimum min cut. M should be a map of bools initialized to false.
     26     minimum min cut. M should be a map of bools initialized to false. ??Is it OK?
    3227
    3328void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
     
    3732     a min cut. M should be a map of bools initialized to false.
    3833
    39 FIXME reset
    40 
    4134*/
    4235
     
    4942#include <vector>
    5043#include <queue>
     44#include <stack>
    5145
    5246namespace hugo {
     
    5852   
    5953    typedef typename Graph::Node Node;
    60     typedef typename Graph::Edge Edge;
    6154    typedef typename Graph::NodeIt NodeIt;
    6255    typedef typename Graph::OutEdgeIt OutEdgeIt;
    6356    typedef typename Graph::InEdgeIt InEdgeIt;
    64    
     57
     58    typedef typename std::vector<std::stack<Node> > VecStack;
     59    typedef typename Graph::template NodeMap<Node> NNMap;
     60    typedef typename std::vector<Node> VecNode;
     61
    6562    const Graph& G;
    6663    Node s;
    6764    Node t;
    68     const CapMap& capacity; 
    69     FlowMap& flow;
    70     T value;
    71     bool constzero;
     65    CapMap* capacity; 
     66    FlowMap* flow;
     67    int n;      //the number of nodes of G
     68    typename Graph::template NodeMap<int> level;     
     69    typename Graph::template NodeMap<T> excess;
     70
    7271
    7372  public:
     73 
     74    enum flowEnum{
     75      ZERO_FLOW=0,
     76      GEN_FLOW=1,
     77      PREFLOW=2
     78    };
     79
    7480    Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity,
    75             FlowMap& _flow, bool _constzero ) :
    76       G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero) {}
     81            FlowMap& _flow) :
     82      G(_G), s(_s), t(_t), capacity(&_capacity),
     83      flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
     84
     85    void run() {
     86      preflow( ZERO_FLOW );
     87    }
    7788   
    78    
    79     void run() {
    80      
    81       value=0;                //for the subsequent runs
    82 
    83       bool phase=0;        //phase 0 is the 1st phase, phase 1 is the 2nd
    84       int n=G.nodeNum();
     89    void preflow( flowEnum fe ) {
     90      preflowPhase0(fe);
     91      preflowPhase1();
     92    }
     93
     94    void preflowPhase0( flowEnum fe ) {
     95     
    8596      int heur0=(int)(H0*n);  //time while running 'bound decrease'
    8697      int heur1=(int)(H1*n);  //time while running 'highest label'
    8798      int heur=heur1;         //starting time interval (#of relabels)
     99      int numrelabel=0;
     100     
    88101      bool what_heur=1;       
    89       /*
    90         what_heur is 0 in case 'bound decrease'
    91         and 1 in case 'highest label'
    92       */
     102      //It is 0 in case 'bound decrease' and 1 in case 'highest label'
     103
    93104      bool end=false;     
    94       /*
    95         Needed for 'bound decrease', 'true'
    96         means no active nodes are above bound b.
    97       */
    98       int relabel=0;
     105      //Needed for 'bound decrease', true means no active nodes are above bound b.
     106
    99107      int k=n-2;  //bound on the highest level under n containing a node
    100108      int b=k;    //bound on the highest level under n of an active node
    101109     
    102       typename Graph::template NodeMap<int> level(G,n);     
    103       typename Graph::template NodeMap<T> excess(G);
    104 
    105       std::vector<Node> active(n-1,INVALID);
    106       typename Graph::template NodeMap<Node> next(G,INVALID);
    107       //Stack of the active nodes in level i < n.
    108       //We use it in both phases.
    109 
    110       typename Graph::template NodeMap<Node> left(G,INVALID);
    111       typename Graph::template NodeMap<Node> right(G,INVALID);
    112       std::vector<Node> level_list(n,INVALID);
    113       /*
    114         List of the nodes in level i<n.
    115       */
    116 
    117 
    118       if ( constzero ) {
    119      
    120         /*Reverse_bfs from t, to find the starting level.*/
    121         level.set(t,0);
    122         std::queue<Node> bfs_queue;
    123         bfs_queue.push(t);
    124        
    125         while (!bfs_queue.empty()) {
    126          
    127           Node v=bfs_queue.front();     
    128           bfs_queue.pop();
    129           int l=level[v]+1;
     110      VecStack active(n);
     111     
     112      NNMap left(G,INVALID);
     113      NNMap right(G,INVALID);
     114      VecNode level_list(n,INVALID);
     115      //List of the nodes in level i<n, set to n.
     116
     117      NodeIt v;
     118      for(G.first(v); G.valid(v); G.next(v)) level.set(v,n);
     119      //setting each node to level n
     120     
     121      switch ( fe ) {
     122      case PREFLOW:
     123        {
     124          //counting the excess
     125          NodeIt v;
     126          for(G.first(v); G.valid(v); G.next(v)) {
     127            T exc=0;
     128         
     129            InEdgeIt e;
     130            for(G.first(e,v); G.valid(e); G.next(e)) exc+=(*flow)[e];
     131            OutEdgeIt f;
     132            for(G.first(f,v); G.valid(f); G.next(f)) exc-=(*flow)[f];
     133           
     134            excess.set(v,exc);   
     135           
     136            //putting the active nodes into the stack
     137            int lev=level[v];
     138            if ( exc > 0 && lev < n && v != t ) active[lev].push(v);
     139          }
     140          break;
     141        }
     142      case GEN_FLOW:
     143        {
     144          //Counting the excess of t
     145          T exc=0;
    130146         
    131147          InEdgeIt e;
    132           for(G.first(e,v); G.valid(e); G.next(e)) {
    133             Node w=G.tail(e);
    134             if ( level[w] == n && w != s ) {
    135               bfs_queue.push(w);
    136               Node first=level_list[l];
    137               if ( G.valid(first) ) left.set(first,w);
    138               right.set(w,first);
    139               level_list[l]=w;
    140               level.set(w, l);
    141             }
    142           }
    143         }
    144 
    145         //the starting flow
    146         OutEdgeIt e;
    147         for(G.first(e,s); G.valid(e); G.next(e))
    148         {
    149           T c=capacity[e];
    150           if ( c == 0 ) continue;
    151           Node w=G.head(e);
    152           if ( level[w] < n ) {   
    153             if ( excess[w] == 0 && w!=t ) {
    154               next.set(w,active[level[w]]);
    155               active[level[w]]=w;
    156             }
    157             flow.set(e, c);
    158             excess.set(w, excess[w]+c);
    159           }
     148          for(G.first(e,t); G.valid(e); G.next(e)) exc+=(*flow)[e];
     149          OutEdgeIt f;
     150          for(G.first(f,t); G.valid(f); G.next(f)) exc-=(*flow)[f];
     151         
     152          excess.set(t,exc);   
     153         
     154          break;
    160155        }
    161156      }
    162       else
    163       {
    164        
    165         /*
    166           Reverse_bfs from t in the residual graph,
    167           to find the starting level.
    168         */
    169         level.set(t,0);
    170         std::queue<Node> bfs_queue;
    171         bfs_queue.push(t);
    172        
    173         while (!bfs_queue.empty()) {
    174          
    175           Node v=bfs_queue.front();     
    176           bfs_queue.pop();
    177           int l=level[v]+1;
    178          
    179           InEdgeIt e;
    180           for(G.first(e,v); G.valid(e); G.next(e)) {
    181             if ( capacity[e] == flow[e] ) continue;
    182             Node w=G.tail(e);
    183             if ( level[w] == n && w != s ) {
    184               bfs_queue.push(w);
    185               Node first=level_list[l];
    186               if ( G.valid(first) ) left.set(first,w);
    187               right.set(w,first);
    188               level_list[l]=w;
    189               level.set(w, l);
    190             }
    191           }
    192            
    193           OutEdgeIt f;
    194           for(G.first(f,v); G.valid(f); G.next(f)) {
    195             if ( 0 == flow[f] ) continue;
    196             Node w=G.head(f);
    197             if ( level[w] == n && w != s ) {
    198               bfs_queue.push(w);
    199               Node first=level_list[l];
    200               if ( G.valid(first) ) left.set(first,w);
    201               right.set(w,first);
    202               level_list[l]=w;
    203               level.set(w, l);
    204             }
    205           }
    206         }
    207      
    208        
    209         /*
    210           Counting the excess
    211         */
    212         NodeIt v;
    213         for(G.first(v); G.valid(v); G.next(v)) {
    214           T exc=0;
    215 
    216           InEdgeIt e;
    217           for(G.first(e,v); G.valid(e); G.next(e)) exc+=flow[e];
    218           OutEdgeIt f;
    219           for(G.first(f,v); G.valid(f); G.next(f)) exc-=flow[e];
    220 
    221           excess.set(v,exc);     
    222 
    223           //putting the active nodes into the stack
    224           int lev=level[v];
    225           if ( exc > 0 && lev < n ) {
    226             next.set(v,active[lev]);
    227             active[lev]=v;
    228           }
    229         }
    230 
    231 
    232         //the starting flow
    233         OutEdgeIt e;
    234         for(G.first(e,s); G.valid(e); G.next(e))
    235         {
    236           T rem=capacity[e]-flow[e];
    237           if ( rem == 0 ) continue;
    238           Node w=G.head(e);
    239           if ( level[w] < n ) {   
    240             if ( excess[w] == 0 && w!=t ) {
    241               next.set(w,active[level[w]]);
    242               active[level[w]]=w;
    243             }
    244             flow.set(e, capacity[e]);
    245             excess.set(w, excess[w]+rem);
    246           }
    247         }
    248        
    249         InEdgeIt f;
    250         for(G.first(f,s); G.valid(f); G.next(f))
    251         {
    252           if ( flow[f] == 0 ) continue;
    253           Node w=G.head(f);
    254           if ( level[w] < n ) {   
    255             if ( excess[w] == 0 && w!=t ) {
    256               next.set(w,active[level[w]]);
    257               active[level[w]]=w;
    258             }
    259             excess.set(w, excess[w]+flow[f]);
    260             flow.set(f, 0);
    261           }
    262         }
    263       }
    264 
    265 
    266 
    267 
    268       /*
    269          End of preprocessing
    270       */
    271 
    272 
    273 
    274       /*
    275         Push/relabel on the highest level active nodes.
    276       */       
     157     
     158      preflowPreproc( fe, active, level_list, left, right );
     159      //End of preprocessing
     160     
     161     
     162      //Push/relabel on the highest level active nodes.
    277163      while ( true ) {
    278        
    279164        if ( b == 0 ) {
    280           if ( phase ) break;
    281          
    282165          if ( !what_heur && !end && k > 0 ) {
    283166            b=k;
    284167            end=true;
    285           } else {
    286             phase=1;
    287             level.set(s,0);
    288             std::queue<Node> bfs_queue;
    289             bfs_queue.push(s);
    290            
    291             while (!bfs_queue.empty()) {
    292              
    293               Node v=bfs_queue.front();
    294               bfs_queue.pop();
    295               int l=level[v]+1;
    296              
    297               InEdgeIt e;
    298               for(G.first(e,v); G.valid(e); G.next(e)) {
    299                 if ( capacity[e] == flow[e] ) continue;
    300                 Node u=G.tail(e);
    301                 if ( level[u] >= n ) {
    302                   bfs_queue.push(u);
    303                   level.set(u, l);
    304                   if ( excess[u] > 0 ) {
    305                     next.set(u,active[l]);
    306                     active[l]=u;
    307                   }
    308                 }
    309               }
    310            
    311               OutEdgeIt f;
    312               for(G.first(f,v); G.valid(f); G.next(f)) {
    313                 if ( 0 == flow[f] ) continue;
    314                 Node u=G.head(f);
    315                 if ( level[u] >= n ) {
    316                   bfs_queue.push(u);
    317                   level.set(u, l);
    318                   if ( excess[u] > 0 ) {
    319                     next.set(u,active[l]);
    320                     active[l]=u;
    321                   }
    322                 }
    323               }
    324             }
    325             b=n-2;
    326             }
    327            
    328         }
    329          
    330          
    331         if ( !G.valid(active[b]) ) --b;
     168          } else break;
     169        }
     170       
     171        if ( active[b].empty() ) --b;
    332172        else {
    333173          end=false; 
    334 
    335           Node w=active[b];
    336           active[b]=next[w];
    337           int lev=level[w];
    338           T exc=excess[w];
    339           int newlevel=n;       //bound on the next level of w
    340          
    341           OutEdgeIt e;
    342           for(G.first(e,w); G.valid(e); G.next(e)) {
    343            
    344             if ( flow[e] == capacity[e] ) continue;
    345             Node v=G.head(e);           
    346             //e=wv         
    347            
    348             if( lev > level[v] ) {     
    349               /*Push is allowed now*/
     174          Node w=active[b].top();
     175          active[b].pop();
     176          int newlevel=push(w,active);
     177          if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list,
     178                                       left, right, b, k, what_heur);
     179         
     180          ++numrelabel;
     181          if ( numrelabel >= heur ) {
     182            numrelabel=0;
     183            if ( what_heur ) {
     184              what_heur=0;
     185              heur=heur0;
     186              end=false;
     187            } else {
     188              what_heur=1;
     189              heur=heur1;
     190              b=k;
     191            }
     192          }
     193        }
     194      }
     195    }
     196
     197
     198    void preflowPhase1() {
     199     
     200      int k=n-2;  //bound on the highest level under n containing a node
     201      int b=k;    //bound on the highest level under n of an active node
     202     
     203      VecStack active(n);
     204      level.set(s,0);
     205      std::queue<Node> bfs_queue;
     206      bfs_queue.push(s);
     207           
     208      while (!bfs_queue.empty()) {
     209       
     210        Node v=bfs_queue.front();       
     211        bfs_queue.pop();
     212        int l=level[v]+1;
    350213             
    351               if ( excess[v]==0 && v!=t && v!=s ) {
    352                 int lev_v=level[v];
    353                 next.set(v,active[lev_v]);
    354                 active[lev_v]=v;
    355               }
    356              
    357               T cap=capacity[e];
    358               T flo=flow[e];
    359               T remcap=cap-flo;
    360              
    361               if ( remcap >= exc ) {       
    362                 /*A nonsaturating push.*/
    363                
    364                 flow.set(e, flo+exc);
    365                 excess.set(v, excess[v]+exc);
    366                 exc=0;
    367                 break;
    368                
    369               } else {
    370                 /*A saturating push.*/
    371                
    372                 flow.set(e, cap);
    373                 excess.set(v, excess[v]+remcap);
    374                 exc-=remcap;
    375               }
    376             } else if ( newlevel > level[v] ){
    377               newlevel = level[v];
    378             }       
    379            
    380           } //for out edges wv
    381        
    382        
    383         if ( exc > 0 ) {       
    384           InEdgeIt e;
    385           for(G.first(e,w); G.valid(e); G.next(e)) {
    386            
    387             if( flow[e] == 0 ) continue;
    388             Node v=G.tail(e); 
    389             //e=vw
    390            
    391             if( lev > level[v] ) { 
    392               /*Push is allowed now*/
    393              
    394               if ( excess[v]==0 && v!=t && v!=s ) {
    395                 int lev_v=level[v];
    396                 next.set(v,active[lev_v]);
    397                 active[lev_v]=v;
    398               }
    399              
    400               T flo=flow[e];
    401              
    402               if ( flo >= exc ) {
    403                 /*A nonsaturating push.*/
    404                
    405                 flow.set(e, flo-exc);
    406                 excess.set(v, excess[v]+exc);
    407                 exc=0;
    408                 break;
    409               } else {                                               
    410                 /*A saturating push.*/
    411                
    412                 excess.set(v, excess[v]+flo);
    413                 exc-=flo;
    414                 flow.set(e,0);
    415               } 
    416             } else if ( newlevel > level[v] ) {
    417               newlevel = level[v];
    418             }       
    419           } //for in edges vw
    420          
    421         } // if w still has excess after the out edge for cycle
    422        
    423         excess.set(w, exc);
    424          
    425         /*
    426           Relabel
    427         */
    428        
    429 
    430         if ( exc > 0 ) {
    431           //now 'lev' is the old level of w
    432        
    433           if ( phase ) {
     214        InEdgeIt e;
     215        for(G.first(e,v); G.valid(e); G.next(e)) {
     216          if ( (*capacity)[e] == (*flow)[e] ) continue;
     217          Node u=G.tail(e);
     218          if ( level[u] >= n ) {
     219            bfs_queue.push(u);
     220            level.set(u, l);
     221            if ( excess[u] > 0 ) active[l].push(u);
     222          }
     223        }
     224       
     225        OutEdgeIt f;
     226        for(G.first(f,v); G.valid(f); G.next(f)) {
     227          if ( 0 == (*flow)[f] ) continue;
     228          Node u=G.head(f);
     229          if ( level[u] >= n ) {
     230            bfs_queue.push(u);
     231            level.set(u, l);
     232            if ( excess[u] > 0 ) active[l].push(u);
     233          }
     234        }
     235      }
     236      b=n-2;
     237
     238      while ( true ) {
     239       
     240        if ( b == 0 ) break;
     241
     242        if ( active[b].empty() ) --b;
     243        else {
     244          Node w=active[b].top();
     245          active[b].pop();
     246          int newlevel=push(w,active);   
     247
     248          //relabel
     249          if ( excess[w] > 0 ) {
    434250            level.set(w,++newlevel);
    435             next.set(w,active[newlevel]);
    436             active[newlevel]=w;
     251            active[newlevel].push(w);
    437252            b=newlevel;
    438           } else {
    439             //unlacing starts
    440             Node right_n=right[w];
    441             Node left_n=left[w];
    442 
    443             if ( G.valid(right_n) ) {
    444               if ( G.valid(left_n) ) {
    445                 right.set(left_n, right_n);
    446                 left.set(right_n, left_n);
    447               } else {
    448                 level_list[lev]=right_n;   
    449                 left.set(right_n, INVALID);
    450               }
    451             } else {
    452               if ( G.valid(left_n) ) {
    453                 right.set(left_n, INVALID);
    454               } else {
    455                 level_list[lev]=INVALID;   
    456               }
    457             }
    458             //unlacing ends
    459                
    460             if ( !G.valid(level_list[lev]) ) {
    461              
    462                //gapping starts
    463               for (int i=lev; i!=k ; ) {
    464                 Node v=level_list[++i];
    465                 while ( G.valid(v) ) {
    466                   level.set(v,n);
    467                   v=right[v];
    468                 }
    469                 level_list[i]=INVALID;
    470                 if ( !what_heur ) active[i]=INVALID;
    471               }     
    472 
    473               level.set(w,n);
    474               b=lev-1;
    475               k=b;
    476               //gapping ends
    477            
    478             } else {
    479              
    480               if ( newlevel == n ) level.set(w,n);
    481               else {
    482                 level.set(w,++newlevel);
    483                 next.set(w,active[newlevel]);
    484                 active[newlevel]=w;
    485                 if ( what_heur ) b=newlevel;
    486                 if ( k < newlevel ) ++k;      //now k=newlevel
    487                 Node first=level_list[newlevel];
    488                 if ( G.valid(first) ) left.set(first,w);
    489                 right.set(w,first);
    490                 left.set(w,INVALID);
    491                 level_list[newlevel]=w;
    492               }
    493             }
    494 
    495 
    496             ++relabel;
    497             if ( relabel >= heur ) {
    498               relabel=0;
    499               if ( what_heur ) {
    500                 what_heur=0;
    501                 heur=heur0;
    502                 end=false;
    503               } else {
    504                 what_heur=1;
    505                 heur=heur1;
    506                 b=k;
    507               }
    508             }
    509           } //phase 0
    510          
    511          
    512         } // if ( exc > 0 )
    513          
    514        
     253          }
    515254        }  // if stack[b] is nonempty
    516        
    517255      } // while(true)
    518 
    519 
    520       value = excess[t];
    521       /*Max flow value.*/
    522      
    523     } //void run()
    524 
    525 
    526 
    527 
    528 
    529     /*
    530       Returns the maximum value of a flow.
    531      */
    532 
     256    }
     257
     258
     259    //Returns the maximum value of a flow.
    533260    T flowValue() {
    534       return value;
    535     }
    536 
    537 
    538     FlowMap Flow() {
    539       return flow;
    540       }
    541 
    542 
    543    
    544     void Flow(FlowMap& _flow ) {
     261      return excess[t];
     262    }
     263
     264    //should be used only between preflowPhase0 and preflowPhase1
     265    template<typename _CutMap>
     266    void actMinCut(_CutMap& M) {
    545267      NodeIt v;
    546       for(G.first(v) ; G.valid(v); G.next(v))
    547         _flow.set(v,flow[v]);
     268      for(G.first(v); G.valid(v); G.next(v))
     269        if ( level[v] < n ) M.set(v,false);
     270        else M.set(v,true);
    548271    }
    549272
     
    553276      Returns the minimum min cut, by a bfs from s in the residual graph.
    554277    */
    555    
    556278    template<typename _CutMap>
    557279    void minMinCut(_CutMap& M) {
     
    569291        for(G.first(e,w) ; G.valid(e); G.next(e)) {
    570292          Node v=G.head(e);
    571           if (!M[v] && flow[e] < capacity[e] ) {
     293          if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
    572294            queue.push(v);
    573295            M.set(v, true);
     
    578300        for(G.first(f,w) ; G.valid(f); G.next(f)) {
    579301          Node v=G.tail(f);
    580           if (!M[v] && flow[f] > 0 ) {
     302          if (!M[v] && (*flow)[f] > 0 ) {
    581303            queue.push(v);
    582304            M.set(v, true);
     
    595317    template<typename _CutMap>
    596318    void maxMinCut(_CutMap& M) {
    597    
     319
     320      NodeIt v;
     321      for(G.first(v) ; G.valid(v); G.next(v)) {
     322        M.set(v, true);
     323      }
     324
    598325      std::queue<Node> queue;
    599326     
    600       M.set(t,true);       
     327      M.set(t,false);       
    601328      queue.push(t);
    602329
     
    609336        for(G.first(e,w) ; G.valid(e); G.next(e)) {
    610337          Node v=G.tail(e);
    611           if (!M[v] && flow[e] < capacity[e] ) {
     338          if (M[v] && (*flow)[e] < (*capacity)[e] ) {
    612339            queue.push(v);
    613             M.set(v, true);
     340            M.set(v, false);
    614341          }
    615342        }
     
    618345        for(G.first(f,w) ; G.valid(f); G.next(f)) {
    619346          Node v=G.head(f);
    620           if (!M[v] && flow[f] > 0 ) {
     347          if (M[v] && (*flow)[f] > 0 ) {
    621348            queue.push(v);
    622             M.set(v, true);
     349            M.set(v, false);
    623350          }
    624351        }
    625352      }
    626 
    627       NodeIt v;
    628       for(G.first(v) ; G.valid(v); G.next(v)) {
    629         M.set(v, !M[v]);
    630       }
    631 
    632     }
    633 
     353    }
    634354
    635355
     
    640360
    641361   
    642     void reset_target (Node _t) {t=_t;}
    643     void reset_source (Node _s) {s=_s;}
     362    void resetTarget (const Node _t) {t=_t;}
     363
     364    void resetSource (const Node _s) {s=_s;}
    644365   
    645     template<typename _CapMap>   
    646     void reset_cap (_CapMap _cap) {capacity=_cap;}
    647 
    648     template<typename _FlowMap>   
    649     void reset_cap (_FlowMap _flow, bool _constzero) {
    650       flow=_flow;
    651       constzero=_constzero;
    652     }
    653 
    654 
     366    void resetCap (const CapMap& _cap) {
     367      capacity=&_cap;
     368    }
     369   
     370    void resetFlow (FlowMap& _flow) {
     371      flow=&_flow;
     372    }
     373
     374
     375  private:
     376
     377    int push(const Node w, VecStack& active) {
     378     
     379      int lev=level[w];
     380      T exc=excess[w];
     381      int newlevel=n;       //bound on the next level of w
     382         
     383      OutEdgeIt e;
     384      for(G.first(e,w); G.valid(e); G.next(e)) {
     385           
     386        if ( (*flow)[e] == (*capacity)[e] ) continue;
     387        Node v=G.head(e);           
     388           
     389        if( lev > level[v] ) { //Push is allowed now
     390         
     391          if ( excess[v]==0 && v!=t && v!=s ) {
     392            int lev_v=level[v];
     393            active[lev_v].push(v);
     394          }
     395         
     396          T cap=(*capacity)[e];
     397          T flo=(*flow)[e];
     398          T remcap=cap-flo;
     399         
     400          if ( remcap >= exc ) { //A nonsaturating push.
     401           
     402            flow->set(e, flo+exc);
     403            excess.set(v, excess[v]+exc);
     404            exc=0;
     405            break;
     406           
     407          } else { //A saturating push.
     408            flow->set(e, cap);
     409            excess.set(v, excess[v]+remcap);
     410            exc-=remcap;
     411          }
     412        } else if ( newlevel > level[v] ) newlevel = level[v];
     413      } //for out edges wv
     414     
     415      if ( exc > 0 ) { 
     416        InEdgeIt e;
     417        for(G.first(e,w); G.valid(e); G.next(e)) {
     418         
     419          if( (*flow)[e] == 0 ) continue;
     420          Node v=G.tail(e);
     421         
     422          if( lev > level[v] ) { //Push is allowed now
     423           
     424            if ( excess[v]==0 && v!=t && v!=s ) {
     425              int lev_v=level[v];
     426              active[lev_v].push(v);
     427            }
     428           
     429            T flo=(*flow)[e];
     430           
     431            if ( flo >= exc ) { //A nonsaturating push.
     432             
     433              flow->set(e, flo-exc);
     434              excess.set(v, excess[v]+exc);
     435              exc=0;
     436              break;
     437            } else {  //A saturating push.
     438             
     439              excess.set(v, excess[v]+flo);
     440              exc-=flo;
     441              flow->set(e,0);
     442            } 
     443          } else if ( newlevel > level[v] ) newlevel = level[v];
     444        } //for in edges vw
     445       
     446      } // if w still has excess after the out edge for cycle
     447     
     448      excess.set(w, exc);
     449     
     450      return newlevel;
     451     }
     452
     453
     454    void preflowPreproc ( flowEnum fe, VecStack& active,
     455                          VecNode& level_list, NNMap& left, NNMap& right ) {
     456
     457      std::queue<Node> bfs_queue;
     458     
     459      switch ( fe ) {
     460      case ZERO_FLOW:
     461        {
     462          //Reverse_bfs from t, to find the starting level.
     463          level.set(t,0);
     464          bfs_queue.push(t);
     465       
     466          while (!bfs_queue.empty()) {
     467           
     468            Node v=bfs_queue.front();   
     469            bfs_queue.pop();
     470            int l=level[v]+1;
     471           
     472            InEdgeIt e;
     473            for(G.first(e,v); G.valid(e); G.next(e)) {
     474              Node w=G.tail(e);
     475              if ( level[w] == n && w != s ) {
     476                bfs_queue.push(w);
     477                Node first=level_list[l];
     478                if ( G.valid(first) ) left.set(first,w);
     479                right.set(w,first);
     480                level_list[l]=w;
     481                level.set(w, l);
     482              }
     483            }
     484          }
     485         
     486          //the starting flow
     487          OutEdgeIt e;
     488          for(G.first(e,s); G.valid(e); G.next(e))
     489            {
     490              T c=(*capacity)[e];
     491              if ( c == 0 ) continue;
     492              Node w=G.head(e);
     493              if ( level[w] < n ) {       
     494                if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
     495                flow->set(e, c);
     496                excess.set(w, excess[w]+c);
     497              }
     498            }
     499          break;
     500        }
     501       
     502      case GEN_FLOW:
     503      case PREFLOW:
     504        {
     505          //Reverse_bfs from t in the residual graph,
     506          //to find the starting level.
     507          level.set(t,0);
     508          bfs_queue.push(t);
     509         
     510          while (!bfs_queue.empty()) {
     511           
     512            Node v=bfs_queue.front();   
     513            bfs_queue.pop();
     514            int l=level[v]+1;
     515           
     516            InEdgeIt e;
     517            for(G.first(e,v); G.valid(e); G.next(e)) {
     518              if ( (*capacity)[e] == (*flow)[e] ) continue;
     519              Node w=G.tail(e);
     520              if ( level[w] == n && w != s ) {
     521                bfs_queue.push(w);
     522                Node first=level_list[l];
     523                if ( G.valid(first) ) left.set(first,w);
     524                right.set(w,first);
     525                level_list[l]=w;
     526                level.set(w, l);
     527              }
     528            }
     529           
     530            OutEdgeIt f;
     531            for(G.first(f,v); G.valid(f); G.next(f)) {
     532              if ( 0 == (*flow)[f] ) continue;
     533              Node w=G.head(f);
     534              if ( level[w] == n && w != s ) {
     535                bfs_queue.push(w);
     536                Node first=level_list[l];
     537                if ( G.valid(first) ) left.set(first,w);
     538                right.set(w,first);
     539                level_list[l]=w;
     540                level.set(w, l);
     541              }
     542            }
     543          }
     544         
     545         
     546          //the starting flow
     547          OutEdgeIt e;
     548          for(G.first(e,s); G.valid(e); G.next(e))
     549            {
     550              T rem=(*capacity)[e]-(*flow)[e];
     551              if ( rem == 0 ) continue;
     552              Node w=G.head(e);
     553              if ( level[w] < n ) {       
     554                if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
     555                flow->set(e, (*capacity)[e]);
     556                excess.set(w, excess[w]+rem);
     557              }
     558            }
     559         
     560          InEdgeIt f;
     561          for(G.first(f,s); G.valid(f); G.next(f))
     562            {
     563              if ( (*flow)[f] == 0 ) continue;
     564              Node w=G.tail(f);
     565              if ( level[w] < n ) {       
     566                if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
     567                excess.set(w, excess[w]+(*flow)[f]);
     568                flow->set(f, 0);
     569              }
     570            } 
     571          break;
     572        } //case PREFLOW
     573      }
     574    } //preflowPreproc
     575
     576
     577
     578    void relabel( const Node w, int newlevel, VecStack& active, 
     579                  VecNode& level_list, NNMap& left,
     580                  NNMap& right, int& b, int& k, const bool what_heur ) {
     581
     582      T lev=level[w];   
     583     
     584      Node right_n=right[w];
     585      Node left_n=left[w];
     586     
     587      //unlacing starts
     588      if ( G.valid(right_n) ) {
     589        if ( G.valid(left_n) ) {
     590          right.set(left_n, right_n);
     591          left.set(right_n, left_n);
     592        } else {
     593          level_list[lev]=right_n;   
     594          left.set(right_n, INVALID);
     595        }
     596      } else {
     597        if ( G.valid(left_n) ) {
     598          right.set(left_n, INVALID);
     599        } else {
     600          level_list[lev]=INVALID;   
     601        }
     602      }
     603      //unlacing ends
     604               
     605      if ( !G.valid(level_list[lev]) ) {
     606             
     607        //gapping starts
     608        for (int i=lev; i!=k ; ) {
     609          Node v=level_list[++i];
     610          while ( G.valid(v) ) {
     611            level.set(v,n);
     612            v=right[v];
     613          }
     614          level_list[i]=INVALID;
     615          if ( !what_heur ) {
     616            while ( !active[i].empty() ) {
     617              active[i].pop();    //FIXME: ezt szebben kene
     618            }
     619          }         
     620        }
     621       
     622        level.set(w,n);
     623        b=lev-1;
     624        k=b;
     625        //gapping ends
     626       
     627      } else {
     628       
     629        if ( newlevel == n ) level.set(w,n);
     630        else {
     631          level.set(w,++newlevel);
     632          active[newlevel].push(w);
     633          if ( what_heur ) b=newlevel;
     634          if ( k < newlevel ) ++k;      //now k=newlevel
     635          Node first=level_list[newlevel];
     636          if ( G.valid(first) ) left.set(first,w);
     637          right.set(w,first);
     638          left.set(w,INVALID);
     639          level_list[newlevel]=w;
     640        }
     641      }
     642     
     643    } //relabel
     644   
    655645
    656646  };
     
    658648} //namespace hugo
    659649
    660 #endif //PREFLOW_H
    661 
    662 
    663 
    664 
     650#endif //HUGO_PREFLOW_H
     651
     652
     653
     654
Note: See TracChangeset for help on using the changeset viewer.