COIN-OR::LEMON - Graph Library

Changeset 109:fc5982b39e10 in lemon-0.x for src/work/jacint/preflow_hl2.h


Ignore:
Timestamp:
02/21/04 22:01:22 (16 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@144
Message:

Flows with test files. The best is preflow.h

File:
1 edited

Legend:

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

    r105 r109  
    44by jacint.
    55Runs the highest label variant of the preflow push algorithm with
    6 running time O(n^2\sqrt(m)), with the 'empty level' and with the
    7 heuristic that the bound b on the active nodes is not increased
    8 only when b=0, when we put b=2*n-2.
    9 
    10 'A' is a parameter for the empty_level heuristic
    11 
    12 Member functions:
    13 
    14 void run() : runs the algorithm
    15 
    16  The following functions should be used after run() was already run.
    17 
    18 T maxflow() : returns the value of a maximum flow
    19 
    20 T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
    21 
    22 FlowMap allflow() : returns the fixed maximum flow x
    23 
    24 void mincut(CutMap& M) : sets M to the characteristic vector of a
     6running time O(n^2\sqrt(m)).
     7
     8Heuristics:
     9
     10  gap: we iterate through the nodes for finding the nodes above
     11       the gap and under level n. So it is quite slow.
     12  numb: we maintain the number of nodes in level i.
     13  highest label
     14 
     15'A' is a parameter for the gap, we only upgrade the nodes to level n,
     16  if the gap is under A*n.
     17
     18The constructor runs the algorithm.
     19
     20Members:
     21
     22T maxFlow() : returns the value of a maximum flow
     23
     24T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
     25
     26FlowMap Flow() : returns the fixed maximum flow x
     27
     28void minCut(CutMap& M) : sets M to the characteristic vector of a
    2529     minimum cut. M should be a map of bools initialized to false.
    2630
    27 void min_mincut(CutMap& M) : sets M to the characteristic vector of the
     31void minMinCut(CutMap& M) : sets M to the characteristic vector of the
    2832     minimum min cut. M should be a map of bools initialized to false.
    2933
    30 void max_mincut(CutMap& M) : sets M to the characteristic vector of the
     34void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
    3135     maximum min cut. M should be a map of bools initialized to false.
    3236
     
    3640#define PREFLOW_HL2_H
    3741
    38 #define A 1
     42#define A .9
    3943
    4044#include <vector>
     
    4549
    4650  template <typename Graph, typename T,
    47     typename FlowMap=typename Graph::EdgeMap<T>, typename CapMap=typename Graph::EdgeMap<T>,
    48     typename IntMap=typename Graph::NodeMap<int>, typename TMap=typename Graph::NodeMap<T> >
     51    typename FlowMap=typename Graph::EdgeMap<T>,
     52    typename CapMap=typename Graph::EdgeMap<T> >
    4953  class preflow_hl2 {
    5054   
     
    6569
    6670    preflow_hl2(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
    67       G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
    68 
    69 
    70     void run() {
    71  
    72       bool no_end=true;
     71      G(_G), s(_s), t(_t), flow(_G), capacity(_capacity) {
     72
    7373      int n=G.nodeNum();
    7474      int b=n-2;
    7575      /*
    7676        b is a bound on the highest level of an active node.
    77         In the beginning it is at most n-2.
    7877      */
    7978
    80       IntMap level(G,n);     
    81       TMap excess(G);
    82      
     79      typename Graph::NodeMap<int> level(G,n);     
     80      typename Graph::NodeMap<T> excess(G);
     81
    8382      std::vector<int> numb(n);   
    8483      /*
     
    111110        }
    112111      }
    113      
     112       
    114113      level.set(s,n);
    115114
     
    128127          }
    129128        }
    130 
     129     
    131130      /*
    132131         End of preprocessing
     
    134133
    135134
    136 
    137135      /*
    138136        Push/relabel on the highest level active nodes.
    139       */       
     137      */
    140138      /*While there exists an active node.*/
    141139      while (b) {
    142         if ( stack[b].empty() ) {
    143           if ( b==1 ) {
    144             if ( !no_end ) break;
    145             else {
    146               b=2*n-2;
    147               no_end=false;
    148             }
    149           }
     140        if ( stack[b].empty() ) {
    150141          --b;
    151         } else {
    152          
    153           no_end=true;
    154          
    155           NodeIt w=stack[b].top();        //w is a highest label active node.
    156           stack[b].pop();           
    157           int lev=level.get(w);
    158           int exc=excess.get(w);
    159           int newlevel=2*n;      //In newlevel we bound the next level of w.
    160          
    161           //  if ( level.get(w) < n ) { //Nem tudom ez mukodik-e
     142          continue;
     143        }
     144       
     145        NodeIt w=stack[b].top();   
     146        stack[b].pop();           
     147        int lev=level.get(w);
     148        T exc=excess.get(w);
     149        int newlevel=2*n;      //In newlevel we bound the next level of w.
     150       
    162151          for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
    163152           
     
    173162              /*v becomes active.*/
    174163             
    175               int cap=capacity.get(e);
    176               int flo=flow.get(e);
    177               int remcap=cap-flo;
     164              T cap=capacity.get(e);
     165              T flo=flow.get(e);
     166              T remcap=cap-flo;
    178167             
    179168              if ( remcap >= exc ) {       
     
    211200              /*v becomes active.*/
    212201             
    213               int flo=flow.get(e);
     202              T flo=flow.get(e);
    214203             
    215204              if ( flo >= exc ) {
     
    232221         
    233222        } // if w still has excess after the out edge for cycle
    234          
    235           excess.set(w, exc);
     223       
     224        excess.set(w, exc);
     225       
     226
     227       
     228
     229        /*
     230          Relabel
     231        */
     232       
     233        if ( exc > 0 ) {
     234          //now 'lev' is the old level of w
     235          level.set(w,++newlevel);
    236236         
    237 
    238           /*
    239             Relabel
    240           */
     237          if ( lev < n ) {
     238            --numb[lev];
     239           
     240            if ( !numb[lev] && lev < A*n ) {  //If the level of w gets empty.
     241             
     242              for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
     243                if (level.get(v) > lev && level.get(v) < n ) level.set(v,n); 
     244              }
     245              for (int i=lev+1 ; i!=n ; ++i) numb[i]=0;
     246              if ( newlevel < n ) newlevel=n;
     247            } else {
     248              if ( newlevel < n ) ++numb[newlevel];
     249            }
     250          }
    241251         
    242           if ( exc > 0 ) {
    243             //now 'lev' is the old level of w
    244             level.set(w,++newlevel);
    245            
    246             if ( lev < n ) {
    247               --numb[lev];
    248 
    249               if ( !numb[lev] && lev < A*n ) {  //If the level of w gets empty.
    250                
    251                 for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
    252                   if (level.get(v) > lev && level.get(v) < n ) level.set(v,n); 
    253                 }
    254                 for (int i=lev+1 ; i!=n ; ++i) numb[i]=0;
    255                 if ( newlevel < n ) newlevel=n;
    256               } else {
    257                 if ( newlevel < n ) ++numb[newlevel];
    258               }
    259             }
    260            
    261             stack[newlevel].push(w);
    262 
    263           }
    264 
    265         } // if stack[b] is nonempty
    266 
     252          stack[newlevel].push(w);
     253          b=newlevel;
     254         
     255        }
     256       
    267257      } // while(b)
    268 
    269 
     258     
     259     
    270260      value = excess.get(t);
    271261      /*Max flow value.*/
     
    282272     */
    283273
    284     T maxflow() {
     274    T maxFlow() {
    285275      return value;
    286276    }
     
    289279
    290280    /*
    291       For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e).
     281      For the maximum flow x found by the algorithm,
     282      it returns the flow value on edge e, i.e. x(e).
    292283    */
    293284
    294     T flowonedge(EdgeIt e) {
     285    T flowOnEdge(const EdgeIt e) {
    295286      return flow.get(e);
    296287    }
     
    302293    */
    303294
    304     FlowMap allflow() {
     295    FlowMap Flow() {
    305296      return flow;
    306297    }
     
    314305   
    315306    template<typename CutMap>
    316     void mincut(CutMap& M) {
     307    void minCut(CutMap& M) {
    317308   
    318309      std::queue<NodeIt> queue;
     
    324315        NodeIt w=queue.front();
    325316        queue.pop();
    326 
     317       
    327318        for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
    328319          NodeIt v=G.head(e);
     
    339330            M.set(v, true);
    340331          }
    341         } 
     332        }
    342333
    343334      }
    344 
    345335    }
    346336
     
    353343   
    354344    template<typename CutMap>
    355     void max_mincut(CutMap& M) {
     345    void maxMinCut(CutMap& M) {
    356346   
    357347      std::queue<NodeIt> queue;
     
    390380
    391381    template<typename CutMap>
    392     void min_mincut(CutMap& M) {
    393       mincut(M);
     382    void minMinCut(CutMap& M) {
     383      minCut(M);
    394384    }
    395385
     
    397387
    398388  };
    399 }//namespace hugo
     389}//namespace marci
    400390#endif
    401391
Note: See TracChangeset for help on using the changeset viewer.