COIN-OR::LEMON - Graph Library

Changeset 471:a40985a922d0 in lemon-0.x


Ignore:
Timestamp:
04/29/04 17:01:52 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@624
Message:

misc

File:
1 edited

Legend:

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

    r470 r471  
    4444#include <stack>
    4545
     46#include <graph_wrapper.h>
     47
    4648namespace hugo {
    4749
     
    6668    FlowMap* flow;
    6769    int n;      //the number of nodes of G
    68     typename Graph::template NodeMap<int> level;     
     70    typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
     71    typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
     72    typedef typename ResGW::Edge ResGWEdge;
     73    //typedef typename ResGW::template NodeMap<bool> ReachedMap;
     74    typedef typename Graph::template NodeMap<int> ReachedMap;
     75    ReachedMap level;
     76    //level works as a bool map in augmenting path algorithms
     77    //and is used by bfs for storing reached information.
     78    //In preflow, it shows levels of nodes.
     79    //typename Graph::template NodeMap<int> level;   
    6980    typename Graph::template NodeMap<Num> excess;
    70 
    7181
    7282  public:
     
    92102    }
    93103
    94     void preflowPhase0( flowEnum fe ) {
    95      
    96       int heur0=(int)(H0*n);  //time while running 'bound decrease'
    97       int heur1=(int)(H1*n);  //time while running 'highest label'
    98       int heur=heur1;         //starting time interval (#of relabels)
    99       int numrelabel=0;
    100      
    101       bool what_heur=1;       
    102       //It is 0 in case 'bound decrease' and 1 in case 'highest label'
    103 
    104       bool end=false;     
    105       //Needed for 'bound decrease', true means no active nodes are above bound b.
    106 
    107       int k=n-2;  //bound on the highest level under n containing a node
    108       int b=k;    //bound on the highest level under n of an active node
    109      
    110       VecStack active(n);
    111      
    112       NNMap left(*g, INVALID);
    113       NNMap right(*g, INVALID);
    114       VecNode level_list(n,INVALID);
    115       //List of the nodes in level i<n, set to n.
    116 
    117       NodeIt v;
    118       for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
    119       //setting each node to level n
    120      
    121       switch ( fe ) {
    122       case PREFLOW:
    123         {
    124           //counting the excess
    125           NodeIt v;
    126           for(g->first(v); g->valid(v); g->next(v)) {
    127             Num exc=0;
    128          
    129             InEdgeIt e;
    130             for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
    131             OutEdgeIt f;
    132             for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
    133            
    134             excess.set(v,exc);   
    135            
    136             //putting the active nodes into the stack
    137             int lev=level[v];
    138             if ( exc > 0 && lev < n && v != t ) active[lev].push(v);
    139           }
    140           break;
    141         }
    142       case GEN_FLOW:
    143         {
    144           //Counting the excess of t
    145           Num exc=0;
    146          
    147           InEdgeIt e;
    148           for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
    149           OutEdgeIt f;
    150           for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
    151          
    152           excess.set(t,exc);   
    153          
    154           break;
    155         }
    156       default:
    157         break;
    158       }
    159      
    160       preflowPreproc( fe, active, level_list, left, right );
    161       //End of preprocessing
    162      
    163      
    164       //Push/relabel on the highest level active nodes.
    165       while ( true ) {
    166         if ( b == 0 ) {
    167           if ( !what_heur && !end && k > 0 ) {
    168             b=k;
    169             end=true;
    170           } else break;
    171         }
    172        
    173         if ( active[b].empty() ) --b;
    174         else {
    175           end=false; 
    176           Node w=active[b].top();
    177           active[b].pop();
    178           int newlevel=push(w,active);
    179           if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list,
    180                                        left, right, b, k, what_heur);
    181          
    182           ++numrelabel;
    183           if ( numrelabel >= heur ) {
    184             numrelabel=0;
    185             if ( what_heur ) {
    186               what_heur=0;
    187               heur=heur0;
    188               end=false;
    189             } else {
    190               what_heur=1;
    191               heur=heur1;
    192               b=k;
    193             }
    194           }
    195         }
    196       }
    197     }
    198 
    199 
    200     void preflowPhase1() {
    201      
    202       int k=n-2;  //bound on the highest level under n containing a node
    203       int b=k;    //bound on the highest level under n of an active node
    204      
    205       VecStack active(n);
    206       level.set(s,0);
    207       std::queue<Node> bfs_queue;
    208       bfs_queue.push(s);
    209            
    210       while (!bfs_queue.empty()) {
    211        
    212         Node v=bfs_queue.front();       
    213         bfs_queue.pop();
    214         int l=level[v]+1;
    215              
    216         InEdgeIt e;
    217         for(g->first(e,v); g->valid(e); g->next(e)) {
    218           if ( (*capacity)[e] <= (*flow)[e] ) continue;
    219           Node u=g->tail(e);
    220           if ( level[u] >= n ) {
    221             bfs_queue.push(u);
    222             level.set(u, l);
    223             if ( excess[u] > 0 ) active[l].push(u);
    224           }
    225         }
    226        
    227         OutEdgeIt f;
    228         for(g->first(f,v); g->valid(f); g->next(f)) {
    229           if ( 0 >= (*flow)[f] ) continue;
    230           Node u=g->head(f);
    231           if ( level[u] >= n ) {
    232             bfs_queue.push(u);
    233             level.set(u, l);
    234             if ( excess[u] > 0 ) active[l].push(u);
    235           }
    236         }
    237       }
    238       b=n-2;
    239 
    240       while ( true ) {
    241        
    242         if ( b == 0 ) break;
    243 
    244         if ( active[b].empty() ) --b;
    245         else {
    246           Node w=active[b].top();
    247           active[b].pop();
    248           int newlevel=push(w,active);   
    249 
    250           //relabel
    251           if ( excess[w] > 0 ) {
    252             level.set(w,++newlevel);
    253             active[newlevel].push(w);
    254             b=newlevel;
    255           }
    256         }  // if stack[b] is nonempty
    257       } // while(true)
    258     }
    259 
     104    void preflowPhase0( flowEnum fe );
     105
     106    void preflowPhase1();
     107
     108    bool augmentOnShortestPath();
     109
     110    template<typename MutableGraph> bool augmentOnBlockingFlow();
     111
     112    bool augmentOnBlockingFlow2();
    260113
    261114    //Returns the maximum value of a flow.
     
    646499    } //relabel
    647500   
    648 
    649501  };
    650502
     503
     504  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
     505  void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe )
     506  {
     507     
     508      int heur0=(int)(H0*n);  //time while running 'bound decrease'
     509      int heur1=(int)(H1*n);  //time while running 'highest label'
     510      int heur=heur1;         //starting time interval (#of relabels)
     511      int numrelabel=0;
     512     
     513      bool what_heur=1;       
     514      //It is 0 in case 'bound decrease' and 1 in case 'highest label'
     515
     516      bool end=false;     
     517      //Needed for 'bound decrease', true means no active nodes are above bound b.
     518
     519      int k=n-2;  //bound on the highest level under n containing a node
     520      int b=k;    //bound on the highest level under n of an active node
     521     
     522      VecStack active(n);
     523     
     524      NNMap left(*g, INVALID);
     525      NNMap right(*g, INVALID);
     526      VecNode level_list(n,INVALID);
     527      //List of the nodes in level i<n, set to n.
     528
     529      NodeIt v;
     530      for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
     531      //setting each node to level n
     532     
     533      switch ( fe ) {
     534      case PREFLOW:
     535        {
     536          //counting the excess
     537          NodeIt v;
     538          for(g->first(v); g->valid(v); g->next(v)) {
     539            Num exc=0;
     540         
     541            InEdgeIt e;
     542            for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
     543            OutEdgeIt f;
     544            for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
     545           
     546            excess.set(v,exc);   
     547           
     548            //putting the active nodes into the stack
     549            int lev=level[v];
     550            if ( exc > 0 && lev < n && v != t ) active[lev].push(v);
     551          }
     552          break;
     553        }
     554      case GEN_FLOW:
     555        {
     556          //Counting the excess of t
     557          Num exc=0;
     558         
     559          InEdgeIt e;
     560          for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
     561          OutEdgeIt f;
     562          for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
     563         
     564          excess.set(t,exc);   
     565         
     566          break;
     567        }
     568      default:
     569        break;
     570      }
     571     
     572      preflowPreproc( fe, active, level_list, left, right );
     573      //End of preprocessing
     574     
     575     
     576      //Push/relabel on the highest level active nodes.
     577      while ( true ) {
     578        if ( b == 0 ) {
     579          if ( !what_heur && !end && k > 0 ) {
     580            b=k;
     581            end=true;
     582          } else break;
     583        }
     584       
     585        if ( active[b].empty() ) --b;
     586        else {
     587          end=false; 
     588          Node w=active[b].top();
     589          active[b].pop();
     590          int newlevel=push(w,active);
     591          if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list,
     592                                       left, right, b, k, what_heur);
     593         
     594          ++numrelabel;
     595          if ( numrelabel >= heur ) {
     596            numrelabel=0;
     597            if ( what_heur ) {
     598              what_heur=0;
     599              heur=heur0;
     600              end=false;
     601            } else {
     602              what_heur=1;
     603              heur=heur1;
     604              b=k;
     605            }
     606          }
     607        }
     608      }
     609    }
     610
     611
     612
     613  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
     614  void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase1()
     615  {
     616     
     617      int k=n-2;  //bound on the highest level under n containing a node
     618      int b=k;    //bound on the highest level under n of an active node
     619     
     620      VecStack active(n);
     621      level.set(s,0);
     622      std::queue<Node> bfs_queue;
     623      bfs_queue.push(s);
     624           
     625      while (!bfs_queue.empty()) {
     626       
     627        Node v=bfs_queue.front();       
     628        bfs_queue.pop();
     629        int l=level[v]+1;
     630             
     631        InEdgeIt e;
     632        for(g->first(e,v); g->valid(e); g->next(e)) {
     633          if ( (*capacity)[e] <= (*flow)[e] ) continue;
     634          Node u=g->tail(e);
     635          if ( level[u] >= n ) {
     636            bfs_queue.push(u);
     637            level.set(u, l);
     638            if ( excess[u] > 0 ) active[l].push(u);
     639          }
     640        }
     641       
     642        OutEdgeIt f;
     643        for(g->first(f,v); g->valid(f); g->next(f)) {
     644          if ( 0 >= (*flow)[f] ) continue;
     645          Node u=g->head(f);
     646          if ( level[u] >= n ) {
     647            bfs_queue.push(u);
     648            level.set(u, l);
     649            if ( excess[u] > 0 ) active[l].push(u);
     650          }
     651        }
     652      }
     653      b=n-2;
     654
     655      while ( true ) {
     656       
     657        if ( b == 0 ) break;
     658
     659        if ( active[b].empty() ) --b;
     660        else {
     661          Node w=active[b].top();
     662          active[b].pop();
     663          int newlevel=push(w,active);   
     664
     665          //relabel
     666          if ( excess[w] > 0 ) {
     667            level.set(w,++newlevel);
     668            active[newlevel].push(w);
     669            b=newlevel;
     670          }
     671        }  // if stack[b] is nonempty
     672      } // while(true)
     673    }
     674
     675
     676
     677
     678
     679
     680
     681
     682
     683
     684
     685
    651686} //namespace hugo
    652687
Note: See TracChangeset for help on using the changeset viewer.