COIN-OR::LEMON - Graph Library

Changeset 109:fc5982b39e10 in lemon-0.x for src/work/jacint/preflow_hl4.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_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.