COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
02/18/04 15:42:38 (16 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@126
Message:

javitott valtozat

File:
1 edited

Legend:

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

    r88 r97  
    44by jacint.
    55Runs the highest label variant of the preflow push algorithm with
    6 running time O(n^2\sqrt(m)).
     6running time O(n^2\sqrt(m)), and with the 'empty level' heuristic.
     7
     8'A' is a parameter for the empty_level heuristic
    79
    810Member functions:
     
    1618T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
    1719
    18 Graph::EdgeMap<T> allflow() : returns the fixed maximum flow x
    19 
    20 Graph::NodeMap<bool> mincut() : returns a
    21      characteristic vector of a minimum cut. (An empty level
    22      in the algorithm gives a minimum cut.)
     20FlowMap allflow() : returns the fixed maximum flow x
     21
     22void mincut(CutMap& M) : sets M to the characteristic vector of a
     23     minimum cut. M should be a map of bools initialized to false.
     24
     25void min_mincut(CutMap& M) : sets M to the characteristic vector of the
     26     minimum min cut. M should be a map of bools initialized to false.
     27
     28void max_mincut(CutMap& M) : sets M to the characteristic vector of the
     29     maximum min cut. M should be a map of bools initialized to false.
     30
    2331*/
    2432
     
    3038#include <vector>
    3139#include <stack>
    32 
    33 #include <reverse_bfs.h>
     40#include <queue>
    3441
    3542namespace marci {
    3643
    37   template <typename Graph, typename T>
     44  template <typename Graph, typename T,
     45    typename FlowMap=typename Graph::EdgeMap<T>, typename CapMap=typename Graph::EdgeMap<T>,
     46    typename IntMap=typename Graph::NodeMap<int>, typename TMap=typename Graph::NodeMap<T> >
    3847  class preflow_push_hl {
    3948   
     
    4756    NodeIt s;
    4857    NodeIt t;
    49     typename Graph::EdgeMap<T> flow;
    50     typename Graph::EdgeMap<T> capacity;
     58    FlowMap flow;
     59    CapMap& capacity;
    5160    T value;
    52     typename Graph::NodeMap<bool> mincutvector;
    53 
     61   
    5462  public:
    5563
    56     preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t,
    57                     typename Graph::EdgeMap<T>& _capacity) :
    58       G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity),
    59       mincutvector(_G, true) { }
    60 
    61 
    62     /*
    63       The run() function runs the highest label preflow-push,
    64       running time: O(n^2\sqrt(m))
    65     */
     64    preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
     65      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
     66
     67
     68   
     69
    6670    void run() {
    6771 
    68       std::cout<<"A is "<<A<<" ";
    69 
    70       typename Graph::NodeMap<int> level(G);     
    71       typename Graph::NodeMap<T> excess(G);
    72 
    7372      int n=G.nodeNum();
    7473      int b=n-2;
    7574      /*
    7675        b is a bound on the highest level of an active node.
    77         In the beginning it is at most n-2.
    7876      */
    7977
    80       std::vector<int> numb(n);     //The number of nodes on level i < n.
     78      IntMap level(G,n);     
     79      TMap excess(G);
     80
     81      std::vector<int> numb(n);   
     82      /*
     83        The number of nodes on level i < n. It is
     84        initialized to n+1, because of the reverse_bfs-part.
     85      */
     86
    8187      std::vector<std::stack<NodeIt> > stack(2*n-1);   
    8288      //Stack of the active nodes in level i.
     
    8490
    8591      /*Reverse_bfs from t, to find the starting level.*/
    86       reverse_bfs<Graph> bfs(G, t);
    87       bfs.run();
    88       for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v)
    89         {
    90           int dist=bfs.dist(v);
    91           level.set(v, dist);
    92           ++numb[dist];
    93         }
    94 
     92      level.set(t,0);
     93      std::queue<NodeIt> bfs_queue;
     94      bfs_queue.push(t);
     95
     96      while (!bfs_queue.empty()) {
     97
     98        NodeIt v=bfs_queue.front();     
     99        bfs_queue.pop();
     100        int l=level.get(v)+1;
     101
     102        for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
     103          NodeIt w=G.tail(e);
     104          if ( level.get(w) == n ) {
     105            bfs_queue.push(w);
     106            ++numb[l];
     107            level.set(w, l);
     108          }
     109        }
     110      }
     111       
    95112      level.set(s,n);
     113
    96114
    97115
     
    99117      for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e)
    100118        {
    101           if ( capacity.get(e) > 0 ) {
    102             NodeIt w=G.head(e);
    103             if ( w!=s ) {         
    104               if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w);
    105               flow.set(e, capacity.get(e));
    106               excess.set(w, excess.get(w)+capacity.get(e));
    107             }
    108           }
    109         }
    110 
     119          if ( capacity.get(e) == 0 ) continue;
     120          NodeIt w=G.head(e);
     121          if ( w!=s ) {   
     122            if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w);
     123            flow.set(e, capacity.get(e));
     124            excess.set(w, excess.get(w)+capacity.get(e));
     125          }
     126        }
     127     
    111128      /*
    112129         End of preprocessing
     
    114131
    115132
    116 
    117133      /*
    118134        Push/relabel on the highest level active nodes.
    119135      */
    120        
    121136      /*While there exists an active node.*/
    122137      while (b) {
    123 
    124         /*We decrease the bound if there is no active node of level b.*/
    125         if (stack[b].empty()) {
     138        if ( stack[b].empty() ) {
    126139          --b;
    127         } else {
    128 
    129           NodeIt w=stack[b].top();        //w is a highest label active node.
    130           stack[b].pop();           
    131        
    132           int newlevel=2*n-2;             //In newlevel we bound the next level of w.
    133        
     140          continue;
     141        }
     142       
     143        NodeIt w=stack[b].top();        //w is a highest label active node.
     144        stack[b].pop();           
     145        int lev=level.get(w);
     146        int exc=excess.get(w);
     147        int newlevel=2*n-2;      //In newlevel we bound the next level of w.
     148       
     149        //  if ( level.get(w) < n ) { //Nem tudom ez mukodik-e
    134150          for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
    135151           
    136             if ( flow.get(e) < capacity.get(e) ) {             
    137               /*e is an edge of the residual graph */
    138 
    139               NodeIt v=G.head(e);               /*e is the edge wv.*/
    140 
    141               if( level.get(w) == level.get(v)+1 ) {     
    142                 /*Push is allowed now*/
    143 
    144                 if ( excess.get(v)==0 && v != s && v !=t ) stack[level.get(v)].push(v);
    145                 /*v becomes active.*/
    146 
    147                 if ( capacity.get(e)-flow.get(e) > excess.get(w) ) {       
    148                   /*A nonsaturating push.*/
    149                  
    150                   flow.set(e, flow.get(e)+excess.get(w));
    151                   excess.set(v, excess.get(v)+excess.get(w));
    152                   excess.set(w,0);
    153                   break;
    154 
    155                 } else {
    156                   /*A saturating push.*/
    157 
    158                   excess.set(v, excess.get(v)+capacity.get(e)-flow.get(e));
    159                   excess.set(w, excess.get(w)-capacity.get(e)+flow.get(e));
    160                   flow.set(e, capacity.get(e));
    161                   if ( excess.get(w)==0 ) break;
    162                   /*If w is not active any more, then we go on to the next node.*/
    163                  
    164                 }
    165               } else {
    166                 newlevel = newlevel < level.get(v) ? newlevel : level.get(v);
     152            if ( flow.get(e) == capacity.get(e) ) continue;
     153            NodeIt v=G.head(e);           
     154            //e=wv         
     155           
     156            if( lev > level.get(v) ) {     
     157              /*Push is allowed now*/
     158             
     159              if ( excess.get(v)==0 && v != s && v !=t )
     160                stack[level.get(v)].push(v);
     161              /*v becomes active.*/
     162             
     163              int cap=capacity.get(e);
     164              int flo=flow.get(e);
     165              int remcap=cap-flo;
     166             
     167              if ( remcap >= exc ) {       
     168                /*A nonsaturating push.*/
     169               
     170                flow.set(e, flo+exc);
     171                excess.set(v, excess.get(v)+exc);
     172                exc=0;
     173                break;
     174               
     175              } else {
     176                /*A saturating push.*/
     177               
     178                flow.set(e, cap );
     179                excess.set(v, excess.get(v)+remcap);
     180                exc-=remcap;
    167181              }
    168            
    169             } //if the out edge wv is in the res graph
    170          
     182            } else if ( newlevel > level.get(v) ) newlevel = level.get(v);
     183           
    171184          } //for out edges wv
     185       
     186       
     187        if ( exc > 0 ) {       
     188          for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
     189           
     190            if( flow.get(e) == 0 ) continue;
     191            NodeIt v=G.tail(e); 
     192            //e=vw
     193           
     194            if( lev > level.get(v) ) { 
     195              /*Push is allowed now*/
     196             
     197              if ( excess.get(v)==0 && v != s && v !=t)
     198                stack[level.get(v)].push(v);
     199              /*v becomes active.*/
     200             
     201              int flo=flow.get(e);
     202             
     203              if ( flo >= exc ) {
     204                /*A nonsaturating push.*/
     205               
     206                flow.set(e, flo-exc);
     207                excess.set(v, excess.get(v)+exc);
     208                exc=0;
     209                break;
     210              } else {                                               
     211                /*A saturating push.*/
     212               
     213                excess.set(v, excess.get(v)+flo);
     214                exc-=flo;
     215                flow.set(e,0);
     216              } 
     217            } else if ( newlevel > level.get(v) ) newlevel = level.get(v);
     218           
     219          } //for in edges vw
    172220         
    173 
    174           if ( excess.get(w) > 0 ) {   
    175            
    176             for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
    177               NodeIt v=G.tail(e);  /*e is the edge vw.*/
    178 
    179               if( flow.get(e) > 0 ) {             
    180                 /*e is an edge of the residual graph */
    181 
    182                 if( level.get(w)==level.get(v)+1 ) { 
    183                   /*Push is allowed now*/
    184                
    185                   if ( excess.get(v)==0 && v != s && v !=t) stack[level.get(v)].push(v);
    186                   /*v becomes active.*/
    187 
    188                   if ( flow.get(e) > excess.get(w) ) {
    189                     /*A nonsaturating push.*/
    190                  
    191                     flow.set(e, flow.get(e)-excess.get(w));
    192                     excess.set(v, excess.get(v)+excess.get(w));
    193                     excess.set(w,0);
    194                     break;
    195                   } else {                                               
    196                     /*A saturating push.*/
    197                    
    198                     excess.set(v, excess.get(v)+flow.get(e));
    199                     excess.set(w, excess.get(w)-flow.get(e));
    200                     flow.set(e,0);
    201                     if ( excess.get(w)==0 ) break;
    202                   } 
    203                 } else {
    204                   newlevel = newlevel < level.get(v) ? newlevel : level.get(v);
    205                 }
    206                
    207               } //if in edge vw is in the res graph
    208 
    209             } //for in edges vw
    210 
    211           } // if w still has excess after the out edge for cycle
    212 
    213 
    214           /*
    215             Relabel
    216           */
     221        } // if w still has excess after the out edge for cycle
     222       
     223        excess.set(w, exc);
     224       
     225
     226       
     227
     228        /*
     229          Relabel
     230        */
     231       
     232        if ( exc > 0 ) {
     233          //now 'lev' is the old level of w
     234          level.set(w,++newlevel);
    217235         
    218           if ( excess.get(w) > 0 ) {
    219            
    220             int oldlevel=level.get(w);     
    221             level.set(w,++newlevel);
    222 
    223             if ( oldlevel < n ) {
    224               --numb[oldlevel];
    225 
    226               if ( !numb[oldlevel] && oldlevel < A*n ) {  //If the level of w gets empty.
    227                
    228                 for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
    229                   if (level.get(v) > oldlevel && level.get(v) < n ) level.set(v,n); 
    230                 }
    231                 for (int i=oldlevel+1 ; i!=n ; ++i) numb[i]=0;
    232                 if ( newlevel < n ) newlevel=n;
    233               } else {
    234                 if ( newlevel < n ) ++numb[newlevel];
     236          if ( lev < n ) {
     237            --numb[lev];
     238           
     239            if ( !numb[lev] && lev < A*n ) {  //If the level of w gets empty.
     240             
     241              for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
     242                if (level.get(v) > lev && level.get(v) < n ) level.set(v,n); 
    235243              }
     244              for (int i=lev+1 ; i!=n ; ++i) numb[i]=0;
     245              if ( newlevel < n ) newlevel=n;
    236246            } else {
    237             if ( newlevel < n ) ++numb[newlevel];
     247              if ( newlevel < n ) ++numb[newlevel];
    238248            }
    239            
    240             stack[newlevel].push(w);
    241             b=newlevel;
    242 
    243           }
    244 
    245         } // if stack[b] is nonempty
    246 
     249          }
     250         
     251          stack[newlevel].push(w);
     252          b=newlevel;
     253         
     254        }
     255       
    247256      } // while(b)
    248 
    249 
     257     
     258     
    250259      value = excess.get(t);
    251260      /*Max flow value.*/
     
    272281    */
    273282
    274     T flowonedge(EdgeIt e) {
     283    T flowonedge(const EdgeIt e) {
    275284      return flow.get(e);
    276285    }
     
    282291    */
    283292
    284     typename Graph::EdgeMap<T> allflow() {
     293    FlowMap allflow() {
    285294      return flow;
    286295    }
     
    288297
    289298
    290     /*
    291       Returns a minimum cut by using a reverse bfs from t in the residual graph.
     299
     300    /*
     301      Returns the minimum min cut, by a bfs from s in the residual graph.
    292302    */
    293303   
    294     typename Graph::NodeMap<bool> mincut() {
     304    template<typename CutMap>
     305    void mincut(CutMap& M) {
    295306   
    296307      std::queue<NodeIt> queue;
    297308     
    298       mincutvector.set(t,false);     
    299       queue.push(t);
     309      M.set(s,true);     
     310      queue.push(s);
    300311
    301312      while (!queue.empty()) {
    302313        NodeIt w=queue.front();
    303314        queue.pop();
     315       
     316        for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
     317          NodeIt v=G.head(e);
     318          if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
     319            queue.push(v);
     320            M.set(v, true);
     321          }
     322        }
    304323
    305324        for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
    306325          NodeIt v=G.tail(e);
    307           if (mincutvector.get(v) && flow.get(e) < capacity.get(e) ) {
     326          if (!M.get(v) && flow.get(e) > 0 ) {
    308327            queue.push(v);
    309             mincutvector.set(v, false);
    310           }
    311         } // for
     328            M.set(v, true);
     329          }
     330        }
     331
     332      }
     333    }
     334
     335
     336
     337    /*
     338      Returns the maximum min cut, by a reverse bfs
     339      from t in the residual graph.
     340    */
     341   
     342    template<typename CutMap>
     343    void max_mincut(CutMap& M) {
     344   
     345      std::queue<NodeIt> queue;
     346     
     347      M.set(t,true);       
     348      queue.push(t);
     349
     350      while (!queue.empty()) {
     351        NodeIt w=queue.front();
     352        queue.pop();
     353
     354        for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
     355          NodeIt v=G.tail(e);
     356          if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
     357            queue.push(v);
     358            M.set(v, true);
     359          }
     360        }
    312361
    313362        for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
    314363          NodeIt v=G.head(e);
    315           if (mincutvector.get(v) && flow.get(e) > 0 ) {
     364          if (!M.get(v) && flow.get(e) > 0 ) {
    316365            queue.push(v);
    317             mincutvector.set(v, false);
    318           }
    319         } // for
    320 
     366            M.set(v, true);
     367          }
     368        }
    321369      }
    322370
    323       return mincutvector;
    324    
    325     }
     371      for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) {
     372        M.set(v, !M.get(v));
     373      }
     374
     375    }
     376
     377
     378
     379    template<typename CutMap>
     380    void min_mincut(CutMap& M) {
     381      mincut(M);
     382    }
     383
     384
     385
    326386  };
    327387}//namespace marci
Note: See TracChangeset for help on using the changeset viewer.