source: lemon-0.x/src/work/jacint/preflow_hl4.h @ 137:6364b07f8cd4

// -*- C++ -*-
/*
preflow_h5.h
by jacint. 
Heuristics: 
 2 phase
 gap
 list 'level_list' on the nodes on level i implemented by hand
 highest label
 relevel: in phase 0, after BFS*n relabels, it runs a reverse 
   bfs from t in the res graph to relevel the nodes reachable from t.
   BFS is initialized to 20

Due to the last heuristic, this algorithm is quite fast on very 
sparse graphs, but relatively bad on even the dense graphs.

'NodeMap<bool> cut' is a member, in this way we can count it fast, after
the algorithm was run.

The constructor runs the algorithm.

Members:

T maxFlow() : returns the value of a maximum flow

T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 

FlowMap Flow() : returns the fixed maximum flow x

void Flow(FlowMap& _flow ) : returns the fixed maximum flow x

void minMinCut(CutMap& M) : sets M to the characteristic vector of the 
     minimum min cut. M should be a map of bools initialized to false.

void maxMinCut(CutMap& M) : sets M to the characteristic vector of the 
     maximum min cut. M should be a map of bools initialized to false.

void minCut(CutMap& M) : fast function, sets M to the characteristic 
     vector of a minimum cut. 

Different member from the other preflow_hl-s (here we have a member 
'NodeMap<bool> cut').

CutMap minCut() : fast function, giving the characteristic 
     vector of a minimum cut.


*/

#ifndef PREFLOW_HL4_H
#define PREFLOW_HL4_H

#define BFS 20

#include <vector>
#include <queue>

#include <time_measure.h>  //for test

namespace hugo {

  template <typename Graph, typename T, 
    typename FlowMap=typename Graph::EdgeMap<T>, 
    typename CutMap=typename Graph::NodeMap<bool>,
    typename CapMap=typename Graph::EdgeMap<T> >
  class preflow_hl4 {
    
    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::EdgeIt EdgeIt;
    typedef typename Graph::EachNodeIt EachNodeIt;
    typedef typename Graph::OutEdgeIt OutEdgeIt;
    typedef typename Graph::InEdgeIt InEdgeIt;
    
    Graph& G;
    NodeIt s;
    NodeIt t;
    FlowMap flow;
    CapMap& capacity;  
    CutMap cut;
    T value;
    
  public:

    double time;

    preflow_hl4(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), 
      cut(G, false) {

      bool phase=0;   //phase 0 is the 1st phase, phase 1 is the 2nd
      int n=G.nodeNum(); 
      int relabel=0;
      int heur=(int)BFS*n;
      int k=n-2;
      int b=k;
      /*
        b is a bound on the highest level of the stack. 
        k is a bound on the highest nonempty level i < n.
      */

      typename Graph::NodeMap<int> level(G,n);      
      typename Graph::NodeMap<T> excess(G); 
      
      std::vector<NodeIt> active(n);
      typename Graph::NodeMap<NodeIt> next(G);
      //Stack of the active nodes in level i < n.
      //We use it in both phases.

      typename Graph::NodeMap<NodeIt> left(G);
      typename Graph::NodeMap<NodeIt> right(G);
      std::vector<NodeIt> level_list(n);
      /*
        Needed for the list of the nodes in level i.
      */

      /*Reverse_bfs from t, to find the starting level.*/
      level.set(t,0);
      std::queue<NodeIt> bfs_queue;
      bfs_queue.push(t);

      while (!bfs_queue.empty()) {

        NodeIt v=bfs_queue.front();     
        bfs_queue.pop();
        int l=level.get(v)+1;

        for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
          NodeIt w=G.tail(e);
          if ( level.get(w) == n && w !=s ) {
            bfs_queue.push(w);
            NodeIt first=level_list[l];
            if ( first != 0 ) left.set(first,w);
            right.set(w,first);
            level_list[l]=w;
            level.set(w, l);
          }
        }
      }
      
      level.set(s,n);


      /* Starting flow. It is everywhere 0 at the moment. */     
      for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) 
        {
          T c=capacity.get(e);
          if ( c == 0 ) continue;
          NodeIt w=G.head(e);
          if ( level.get(w) < n ) {       
            if ( excess.get(w) == 0 && w!=t ) {
              next.set(w,active[level.get(w)]);
              active[level.get(w)]=w;
            }
            flow.set(e, c); 
            excess.set(w, excess.get(w)+c);
          }
        }
      /* 
         End of preprocessing 
      */


      /*
        Push/relabel on the highest level active nodes.
      */        
      while ( true ) {

        if ( b == 0 ) {
          if ( phase ) break;
          
          /*
            In the end of phase 0 we apply a bfs from s in
            the residual graph.
          */
          phase=1;
          
          //Now have a min cut.
          for( EachNodeIt v=G.template first<EachNodeIt>(); 
               v.valid(); ++v) 
            if (level.get(v) >= n ) cut.set(v,true);
          
          time=currTime();
          level.set(s,0);
          std::queue<NodeIt> bfs_queue;
          bfs_queue.push(s);
          
          while (!bfs_queue.empty()) {
            
            NodeIt v=bfs_queue.front(); 
            bfs_queue.pop();
            int l=level.get(v)+1;

            for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
              if ( capacity.get(e) == flow.get(e) ) continue;
              NodeIt u=G.tail(e);
              if ( level.get(u) >= n ) { 
                bfs_queue.push(u);
                level.set(u, l);
                if ( excess.get(u) > 0 ) {
                    next.set(u,active[l]);
                    active[l]=u;
                }
              }
            }

            for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
              if ( 0 == flow.get(e) ) continue;
              NodeIt u=G.head(e);
              if ( level.get(u) >= n ) { 
                bfs_queue.push(u);
                level.set(u, l);
                if ( excess.get(u) > 0 ) {
                    next.set(u,active[l]);
                    active[l]=u;
                }
              }
            }
          }
          b=n-2;
        }


        if ( active[b] == 0 ) --b;
        else {
          
          NodeIt w=active[b];
          active[b]=next.get(w);
          int lev=level.get(w);
          T exc=excess.get(w);
          int newlevel=n;          //bound on the next level of w.
          
          for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
            
            if ( flow.get(e) == capacity.get(e) ) continue; 
            NodeIt v=G.head(e);            
            //e=wv          
            
            if( lev > level.get(v) ) {      
              /*Push is allowed now*/
              
              if ( excess.get(v)==0 && v!=t && v!=s )  {
                int lev_v=level.get(v);
                next.set(v,active[lev_v]);
                active[lev_v]=v;
              }
              
              T cap=capacity.get(e);
              T flo=flow.get(e);
              T remcap=cap-flo;
              
              if ( remcap >= exc ) {       
                /*A nonsaturating push.*/
                
                flow.set(e, flo+exc);
                excess.set(v, excess.get(v)+exc);
                exc=0;
                break; 
                
              } else { 
                /*A saturating push.*/
                
                flow.set(e, cap);
                excess.set(v, excess.get(v)+remcap);
                exc-=remcap;
              }
            } else if ( newlevel > level.get(v) ){
              newlevel = level.get(v);
            }       
            
          } //for out edges wv 
        
        
        if ( exc > 0 ) {        
          for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
            
            if( flow.get(e) == 0 ) continue; 
            NodeIt v=G.tail(e);  
            //e=vw
            
            if( lev > level.get(v) ) {  
              /*Push is allowed now*/
              
              if ( excess.get(v)==0 && v!=t && v!=s ) {
                int lev_v=level.get(v);
                next.set(v,active[lev_v]);
                active[lev_v]=v;
              }
              
              T flo=flow.get(e);
              
              if ( flo >= exc ) { 
                /*A nonsaturating push.*/
                
                flow.set(e, flo-exc);
                excess.set(v, excess.get(v)+exc);
                exc=0;
                break; 
              } else {                                               
                /*A saturating push.*/
                
                excess.set(v, excess.get(v)+flo);
                exc-=flo;
                flow.set(e,0);
              }  
            } else if ( newlevel > level.get(v) ) {
              newlevel = level.get(v);
            }       
          } //for in edges vw
          
        } // if w still has excess after the out edge for cycle
        
        excess.set(w, exc);
         
        /*
          Relabel
        */
        
        if ( exc > 0 ) {
          //now 'lev' is the old level of w
        
          if ( phase ) {
            level.set(w,++newlevel);
            next.set(w,active[newlevel]);
            active[newlevel]=w;
            b=newlevel;
          } else {
            //unlacing
            NodeIt right_n=right.get(w);
            NodeIt left_n=left.get(w);

            if ( right_n != 0 ) {
              if ( left_n != 0 ) {
                right.set(left_n, right_n);
                left.set(right_n, left_n);
              } else {
                level_list[lev]=right_n;
                left.set(right_n, 0);
              } 
            } else {
              if ( left_n != 0 ) {
                right.set(left_n, 0);
              } else { 
                level_list[lev]=0;
              } 
            }
            //unlacing ends
                

            if ( level_list[lev]==0 ) {

              for (int i=lev; i!=k ; ) {
                NodeIt v=level_list[++i];
                while ( v != 0 ) {
                  level.set(v,n);
                  v=right.get(v);
                }
                level_list[i]=0;
              }      

              level.set(w,n);

              b=--lev;
              k=b;

            } else {

              if ( newlevel == n ) {
                level.set(w,n);
              } else {
                
                level.set(w,++newlevel);
                next.set(w,active[newlevel]);
                active[newlevel]=w;
                b=newlevel;
                if ( k < newlevel ) ++k;
                NodeIt first=level_list[newlevel];
                if ( first != 0 ) left.set(first,w);
                right.set(w,first);
                left.set(w,0);
                level_list[newlevel]=w;
              }
            }

            ++relabel;
            if ( relabel >= heur ) {
              relabel=0;
              b=n-2;
              k=b;
                
              for ( int i=1; i!=n; ++i ) { 
                active[i]=0;
                level_list[i]=0;
              }

              //bfs from t in the res graph to relevel the nodes
              for( EachNodeIt v=G.template first<EachNodeIt>(); 
                   v.valid(); ++v) level.set(v,n);

              level.set(t,0);
              std::queue<NodeIt> bfs_queue;
              bfs_queue.push(t);
              
              while (!bfs_queue.empty()) {
                
                NodeIt v=bfs_queue.front();     
                bfs_queue.pop();
                int l=level.get(v)+1;
                
                for(InEdgeIt e=G.template first<InEdgeIt>(v); 
                    e.valid(); ++e) {
                  if ( capacity.get(e) == flow.get(e) ) continue;
                  NodeIt u=G.tail(e);
                  if ( level.get(u) == n ) { 
                    bfs_queue.push(u);
                    level.set(u, l);
                    if ( excess.get(u) > 0 ) {
                      next.set(u,active[l]);
                      active[l]=u;
                    }
                    NodeIt first=level_list[l];
                    if ( first != 0 ) left.set(first,w);
                    right.set(w,first);
                    left.set(w,0);
                    level_list[l]=w;
                  }
                }
                
                
                for(OutEdgeIt e=G.template first<OutEdgeIt>(v); 
                    e.valid(); ++e) {
                  if ( 0 == flow.get(e) ) continue;
                  NodeIt u=G.head(e);
                  if ( level.get(u) == n ) { 
                    bfs_queue.push(u);
                    level.set(u, l);
                    if ( excess.get(u) > 0 ) {
                      next.set(u,active[l]);
                      active[l]=u;
                    }
                    NodeIt first=level_list[l];
                    if ( first != 0 ) left.set(first,w);
                    right.set(w,first);
                    left.set(w,0);
                    level_list[l]=w;
                  }
                }
              }
              
              level.set(s,n);
            }
          
          } //phase 0
        } // if ( exc > 0 )
        
        
        } // if stack[b] is nonempty
        
      } // while(true)


      value = excess.get(t);
      /*Max flow value.*/


    } //void run()





    /*
      Returns the maximum value of a flow.
     */

    T maxFlow() {
      return value;
    }



    /*
      For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e). 
    */

    T flowOnEdge(EdgeIt e) {
      return flow.get(e);
    }



    FlowMap Flow() {
      return flow;
    }


    
    void Flow(FlowMap& _flow ) {
      for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v)
        _flow.set(v,flow.get(v));
    }



    /*
      Returns the minimum min cut, by a bfs from s in the residual graph.
    */
    
    template<typename _CutMap>
    void minMinCut(_CutMap& M) {
    
      std::queue<NodeIt> queue;
      
      M.set(s,true);      
      queue.push(s);

      while (!queue.empty()) {
        NodeIt w=queue.front();
        queue.pop();

        for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
          NodeIt v=G.head(e);
          if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
            queue.push(v);
            M.set(v, true);
          }
        } 

        for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
          NodeIt v=G.tail(e);
          if (!M.get(v) && flow.get(e) > 0 ) {
            queue.push(v);
            M.set(v, true);
          }
        } 

      }

    }



    /*
      Returns the maximum min cut, by a reverse bfs 
      from t in the residual graph.
    */
    
    template<typename _CutMap>
    void maxMinCut(_CutMap& M) {
    
      std::queue<NodeIt> queue;
      
      M.set(t,true);        
      queue.push(t);

      while (!queue.empty()) {
        NodeIt w=queue.front();
        queue.pop();

        for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
          NodeIt v=G.tail(e);
          if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
            queue.push(v);
            M.set(v, true);
          }
        }

        for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
          NodeIt v=G.head(e);
          if (!M.get(v) && flow.get(e) > 0 ) {
            queue.push(v);
            M.set(v, true);
          }
        }
      }

      for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) {
        M.set(v, !M.get(v));
      }

    }


    template<typename _CutMap>
    void minCut(_CutMap& M) {
      for( EachNodeIt v=G.template first<EachNodeIt>(); 
           v.valid(); ++v) 
        M.set(v, cut.get(v));
    }

   
    CutMap minCut() {
      return cut;
    }


  };
}//namespace marci
#endif