COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
02/21/04 22:01:22 (17 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

Location:
src/work/jacint
Files:
12 added
4 deleted
3 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
  • src/work/jacint/preflow_hl3.h

    r105 r109  
    33preflow_hl3.h
    44by jacint.
    5 Runs the highest label variant of the preflow push algorithm with
    6 running time O(n^2\sqrt(m)), with the felszippantos 'empty level'
    7 and with the two-phase heuristic: if there is no active node of
    8 level at most n, then we go into phase 1, do a bfs
    9 from s, and flow the excess back to s.
    10 
    11 In phase 1 we shift everything downwards by n.
    12 
    13 'A' is a parameter for the empty_level heuristic
    14 
    15 Member functions:
    16 
    17 void run() : runs the algorithm
    18 
    19  The following functions should be used after run() was already run.
    20 
    21 T maxflow() : returns the value of a maximum flow
    22 
    23 T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
    24 
    25 FlowMap allflow() : returns the fixed maximum flow x
    26 
    27 void mincut(CutMap& M) : sets M to the characteristic vector of a
     5
     6Heuristics:
     7
     8 suck gap : if there is a gap, then we put all
     9   nodes reachable from the relabelled node to level n
     10 2 phase
     11 highest label
     12
     13The constructor runs the algorithm.
     14
     15Members:
     16
     17T maxFlow() : returns the value of a maximum flow
     18
     19T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
     20
     21FlowMap Flow() : returns the fixed maximum flow x
     22
     23void minCut(CutMap& M) : sets M to the characteristic vector of a
    2824     minimum cut. M should be a map of bools initialized to false.
    2925
    30 void min_mincut(CutMap& M) : sets M to the characteristic vector of the
     26void minMinCut(CutMap& M) : sets M to the characteristic vector of the
    3127     minimum min cut. M should be a map of bools initialized to false.
    3228
    33 void max_mincut(CutMap& M) : sets M to the characteristic vector of the
     29void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
    3430     maximum min cut. M should be a map of bools initialized to false.
    3531
     
    3834#ifndef PREFLOW_HL3_H
    3935#define PREFLOW_HL3_H
    40 
    41 #define A 1
    4236
    4337#include <vector>
     
    4539#include <queue>
    4640
     41#include <time_measure.h> //for test
     42
    4743namespace hugo {
    4844
    4945  template <typename Graph, typename T,
    50     typename FlowMap=typename Graph::EdgeMap<T>, typename CapMap=typename Graph::EdgeMap<T>,
    51     typename IntMap=typename Graph::NodeMap<int>, typename TMap=typename Graph::NodeMap<T> >
     46    typename FlowMap=typename Graph::EdgeMap<T>,
     47    typename CapMap=typename Graph::EdgeMap<T> >
    5248  class preflow_hl3 {
    5349   
     
    6763  public:
    6864
     65    double time; //for test
     66
    6967    preflow_hl3(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
    70       G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
    71 
    72 
    73     void run() {
    74  
     68      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) {
     69     
    7570      bool phase=0;
    7671      int n=G.nodeNum();
     
    8176      */
    8277
    83       IntMap level(G,n);     
    84       TMap excess(G);
     78      typename Graph::NodeMap<int> level(G,n);     
     79      typename Graph::NodeMap<T> excess(G);
    8580     
    8681      std::vector<int> numb(n);   
     
    149144          if ( phase ) break;
    150145          phase=1;
    151 
     146          time=currTime();
     147         
    152148          level.set(s,0);
    153149
     
    188184        else {
    189185         
    190           NodeIt w=stack[b].top();        //w is a highest label active node.
     186          NodeIt w=stack[b].top();
    191187          stack[b].pop();           
    192188          int lev=level.get(w);
    193           int exc=excess.get(w);
    194           int newlevel=n;                 //In newlevel we bound the next level of w.
     189          T exc=excess.get(w);
     190          int newlevel=n;          //bound on the next level of w.
    195191         
    196192          for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
     
    207203              /*v becomes active.*/
    208204             
    209               int cap=capacity.get(e);
    210               int flo=flow.get(e);
    211               int remcap=cap-flo;
     205              T cap=capacity.get(e);
     206              T flo=flow.get(e);
     207              T remcap=cap-flo;
    212208             
    213209              if ( remcap >= exc ) {       
     
    245241              /*v becomes active.*/
    246242             
    247               int flo=flow.get(e);
     243              T flo=flow.get(e);
    248244             
    249245              if ( flo >= exc ) {
     
    350346     */
    351347
    352     T maxflow() {
     348    T maxFlow() {
    353349      return value;
    354350    }
     
    357353
    358354    /*
    359       For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e).
     355      For the maximum flow x found by the algorithm,
     356      it returns the flow value on edge e, i.e. x(e).
    360357    */
    361358
    362     T flowonedge(EdgeIt e) {
     359    T flowOnEdge(EdgeIt e) {
    363360      return flow.get(e);
    364361    }
     
    370367    */
    371368
    372     FlowMap allflow() {
     369    FlowMap Flow() {
    373370      return flow;
    374371    }
     
    382379   
    383380    template<typename CutMap>
    384     void mincut(CutMap& M) {
     381    void minCut(CutMap& M) {
    385382   
    386383      std::queue<NodeIt> queue;
     
    421418   
    422419    template<typename CutMap>
    423     void max_mincut(CutMap& M) {
     420    void maxMinCut(CutMap& M) {
    424421   
    425422      std::queue<NodeIt> queue;
     
    458455
    459456    template<typename CutMap>
    460     void min_mincut(CutMap& M) {
    461       mincut(M);
     457    void minMinCut(CutMap& M) {
     458      minCut(M);
    462459    }
    463460
     
    465462
    466463  };
    467 }//namespace hugo
     464}//namespace
    468465#endif
    469466
  • src/work/jacint/preflow_hl4.h

    r105 r109  
    11// -*- C++ -*-
    22/*
    3 preflow_hl4.h
     3preflow_h5.h
    44by jacint.
    5 Runs the two phase highest label preflow push algorithm. In phase 0
    6 we maintain in a list the nodes in level i < n, and we maintain a
    7 bound k on the max level i < n containing a node, so we can do
    8 the gap heuristic fast. Phase 1 is the same. (The algorithm is the
    9 same as preflow.hl3, the only diff is that here we use the gap
    10 heuristic with the list of the nodes on level i, and not a bfs form the
    11 upgraded node.)
    12 
    13 In phase 1 we shift everything downwards by n.
    14 
    15 Member functions:
    16 
    17 void run() : runs the algorithm
    18 
    19  The following functions should be used after run() was already run.
    20 
    21 T maxflow() : returns the value of a maximum flow
    22 
    23 T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
    24 
    25 FlowMap allflow() : returns a maximum flow
    26 
    27 void allflow(FlowMap& _flow ) : returns a maximum flow
    28 
    29 void mincut(CutMap& M) : sets M to the characteristic vector of a
    30      minimum cut. M should be a map of bools initialized to false.
    31 
    32 void min_mincut(CutMap& M) : sets M to the characteristic vector of the
     5Heuristics:
     6 2 phase
     7 gap
     8 list 'level_list' on the nodes on level i implemented by hand
     9 highest label
     10 relevel: in phase 0, after BFS*n relabels, it runs a reverse
     11   bfs from t in the res graph to relevel the nodes reachable from t.
     12   BFS is initialized to 20
     13
     14Due to the last heuristic, this algorithm is quite fast on very
     15sparse graphs, but relatively bad on even the dense graphs.
     16
     17'NodeMap<bool> cut' is a member, in this way we can count it fast, after
     18the algorithm was run.
     19
     20The constructor runs the algorithm.
     21
     22Members:
     23
     24T maxFlow() : returns the value of a maximum flow
     25
     26T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
     27
     28FlowMap Flow() : returns the fixed maximum flow x
     29
     30void Flow(FlowMap& _flow ) : returns the fixed maximum flow x
     31
     32void minMinCut(CutMap& M) : sets M to the characteristic vector of the
    3333     minimum min cut. M should be a map of bools initialized to false.
    3434
    35 void max_mincut(CutMap& M) : sets M to the characteristic vector of the
     35void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
    3636     maximum min cut. M should be a map of bools initialized to false.
     37
     38void minCut(CutMap& M) : fast function, sets M to the characteristic
     39     vector of a minimum cut.
     40
     41Different member from the other preflow_hl-s (here we have a member
     42'NodeMap<bool> cut').
     43
     44CutMap minCut() : fast function, giving the characteristic
     45     vector of a minimum cut.
     46
    3747
    3848*/
     
    4151#define PREFLOW_HL4_H
    4252
     53#define BFS 20
     54
    4355#include <vector>
    44 #include <stack>
    4556#include <queue>
     57
     58#include <time_measure.h>  //for test
    4659
    4760namespace hugo {
     
    4962  template <typename Graph, typename T,
    5063    typename FlowMap=typename Graph::EdgeMap<T>,
     64    typename CutMap=typename Graph::NodeMap<bool>,
    5165    typename CapMap=typename Graph::EdgeMap<T> >
    5266  class preflow_hl4 {
     
    6377    FlowMap flow;
    6478    CapMap& capacity; 
     79    CutMap cut;
    6580    T value;
    6681   
    6782  public:
    6883
     84    double time;
     85
    6986    preflow_hl4(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
    70       G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
    71 
    72 
    73     void run() {
    74  
    75       bool phase=0;
     87      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity),
     88      cut(G, false) {
     89
     90      bool phase=0;   //phase 0 is the 1st phase, phase 1 is the 2nd
    7691      int n=G.nodeNum();
     92      int relabel=0;
     93      int heur=(int)BFS*n;
    7794      int k=n-2;
    7895      int b=k;
     
    84101      typename Graph::NodeMap<int> level(G,n);     
    85102      typename Graph::NodeMap<T> excess(G);
    86       std::vector<std::stack<NodeIt> > stack(n);   
     103     
     104      std::vector<NodeIt> active(n);
     105      typename Graph::NodeMap<NodeIt> next(G);
    87106      //Stack of the active nodes in level i < n.
    88107      //We use it in both phases.
     
    108127        for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
    109128          NodeIt w=G.tail(e);
    110           if ( level.get(w) == n ) {
     129          if ( level.get(w) == n && w !=s ) {
    111130            bfs_queue.push(w);
    112131            NodeIt first=level_list[l];
     
    129148          NodeIt w=G.head(e);
    130149          if ( level.get(w) < n ) {       
    131             if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w);
     150            if ( excess.get(w) == 0 && w!=t ) {
     151              next.set(w,active[level.get(w)]);
     152              active[level.get(w)]=w;
     153            }
    132154            flow.set(e, c);
    133155            excess.set(w, excess.get(w)+c);
     
    152174          */
    153175          phase=1;
     176         
     177          //Now have a min cut.
     178          for( EachNodeIt v=G.template first<EachNodeIt>();
     179               v.valid(); ++v)
     180            if (level.get(v) >= n ) cut.set(v,true);
     181         
     182          time=currTime();
    154183          level.set(s,0);
    155184          std::queue<NodeIt> bfs_queue;
     
    168197                bfs_queue.push(u);
    169198                level.set(u, l);
    170                 if ( excess.get(u) > 0 ) stack[l].push(u);
     199                if ( excess.get(u) > 0 ) {
     200                    next.set(u,active[l]);
     201                    active[l]=u;
     202                }
    171203              }
    172204            }
     
    178210                bfs_queue.push(u);
    179211                level.set(u, l);
    180                 if ( excess.get(u) > 0 ) stack[l].push(u);
     212                if ( excess.get(u) > 0 ) {
     213                    next.set(u,active[l]);
     214                    active[l]=u;
     215                }
    181216              }
    182217            }
     
    186221
    187222
    188         if ( stack[b].empty() ) --b;
     223        if ( active[b] == 0 ) --b;
    189224        else {
    190225         
    191           NodeIt w=stack[b].top();        //w is a highest label active node.
    192           stack[b].pop();           
     226          NodeIt w=active[b];
     227          active[b]=next.get(w);
    193228          int lev=level.get(w);
    194229          T exc=excess.get(w);
    195           int newlevel=n;          //In newlevel we bound the next level of w.
     230          int newlevel=n;          //bound on the next level of w.
    196231         
    197232          for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
     
    204239              /*Push is allowed now*/
    205240             
    206               if ( excess.get(v)==0 && v!=t && v!=s )
    207                 stack[level.get(v)].push(v);
    208               /*v becomes active.*/
     241              if ( excess.get(v)==0 && v!=t && v!=s )  {
     242                int lev_v=level.get(v);
     243                next.set(v,active[lev_v]);
     244                active[lev_v]=v;
     245              }
    209246             
    210247              T cap=capacity.get(e);
     
    244281              /*Push is allowed now*/
    245282             
    246               if ( excess.get(v)==0 && v!=t && v!=s )
    247                 stack[level.get(v)].push(v);
    248               /*v becomes active.*/
     283              if ( excess.get(v)==0 && v!=t && v!=s ) {
     284                int lev_v=level.get(v);
     285                next.set(v,active[lev_v]);
     286                active[lev_v]=v;
     287              }
    249288             
    250289              T flo=flow.get(e);
     
    282321          if ( phase ) {
    283322            level.set(w,++newlevel);
    284             stack[newlevel].push(w);
     323            next.set(w,active[newlevel]);
     324            active[newlevel]=w;
    285325            b=newlevel;
    286326          } else {
     
    304344              }
    305345            }
     346            //unlacing ends
    306347               
    307348
     
    329370               
    330371                level.set(w,++newlevel);
    331                 stack[newlevel].push(w);
     372                next.set(w,active[newlevel]);
     373                active[newlevel]=w;
    332374                b=newlevel;
    333375                if ( k < newlevel ) ++k;
     
    339381              }
    340382            }
     383
     384            ++relabel;
     385            if ( relabel >= heur ) {
     386              relabel=0;
     387              b=n-2;
     388              k=b;
     389               
     390              for ( int i=1; i!=n; ++i ) {
     391                active[i]=0;
     392                level_list[i]=0;
     393              }
     394
     395              //bfs from t in the res graph to relevel the nodes
     396              for( EachNodeIt v=G.template first<EachNodeIt>();
     397                   v.valid(); ++v) level.set(v,n);
     398
     399              level.set(t,0);
     400              std::queue<NodeIt> bfs_queue;
     401              bfs_queue.push(t);
     402             
     403              while (!bfs_queue.empty()) {
     404               
     405                NodeIt v=bfs_queue.front();     
     406                bfs_queue.pop();
     407                int l=level.get(v)+1;
     408               
     409                for(InEdgeIt e=G.template first<InEdgeIt>(v);
     410                    e.valid(); ++e) {
     411                  if ( capacity.get(e) == flow.get(e) ) continue;
     412                  NodeIt u=G.tail(e);
     413                  if ( level.get(u) == n ) {
     414                    bfs_queue.push(u);
     415                    level.set(u, l);
     416                    if ( excess.get(u) > 0 ) {
     417                      next.set(u,active[l]);
     418                      active[l]=u;
     419                    }
     420                    NodeIt first=level_list[l];
     421                    if ( first != 0 ) left.set(first,w);
     422                    right.set(w,first);
     423                    left.set(w,0);
     424                    level_list[l]=w;
     425                  }
     426                }
     427               
     428               
     429                for(OutEdgeIt e=G.template first<OutEdgeIt>(v);
     430                    e.valid(); ++e) {
     431                  if ( 0 == flow.get(e) ) continue;
     432                  NodeIt u=G.head(e);
     433                  if ( level.get(u) == n ) {
     434                    bfs_queue.push(u);
     435                    level.set(u, l);
     436                    if ( excess.get(u) > 0 ) {
     437                      next.set(u,active[l]);
     438                      active[l]=u;
     439                    }
     440                    NodeIt first=level_list[l];
     441                    if ( first != 0 ) left.set(first,w);
     442                    right.set(w,first);
     443                    left.set(w,0);
     444                    level_list[l]=w;
     445                  }
     446                }
     447              }
     448             
     449              level.set(s,n);
     450            }
     451         
    341452          } //phase 0
    342453        } // if ( exc > 0 )
    343  
     454       
    344455       
    345456        } // if stack[b] is nonempty
     
    362473     */
    363474
    364     T maxflow() {
     475    T maxFlow() {
    365476      return value;
    366477    }
     
    372483    */
    373484
    374     T flowonedge(EdgeIt e) {
     485    T flowOnEdge(EdgeIt e) {
    375486      return flow.get(e);
    376487    }
     
    378489
    379490
    380     FlowMap allflow() {
     491    FlowMap Flow() {
    381492      return flow;
    382493    }
     
    384495
    385496   
    386     void allflow(FlowMap& _flow ) {
     497    void Flow(FlowMap& _flow ) {
    387498      for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v)
    388499        _flow.set(v,flow.get(v));
     
    395506    */
    396507   
    397     template<typename CutMap>
    398     void mincut(CutMap& M) {
     508    template<typename _CutMap>
     509    void minMinCut(_CutMap& M) {
    399510   
    400511      std::queue<NodeIt> queue;
     
    434545    */
    435546   
    436     template<typename CutMap>
    437     void max_mincut(CutMap& M) {
     547    template<typename _CutMap>
     548    void maxMinCut(_CutMap& M) {
    438549   
    439550      std::queue<NodeIt> queue;
     
    470581
    471582
    472 
    473     template<typename CutMap>
    474     void min_mincut(CutMap& M) {
    475       mincut(M);
    476     }
    477 
     583    template<typename _CutMap>
     584    void minCut(_CutMap& M) {
     585      for( EachNodeIt v=G.template first<EachNodeIt>();
     586           v.valid(); ++v)
     587        M.set(v, cut.get(v));
     588    }
     589
     590   
     591    CutMap minCut() {
     592      return cut;
     593    }
    478594
    479595
    480596  };
    481 }//namespace hugo
     597}//namespace marci
    482598#endif
    483599
Note: See TracChangeset for help on using the changeset viewer.