COIN-OR::LEMON - Graph Library

Changeset 85:15362fafaf1a in lemon-0.x for src/work


Ignore:
Timestamp:
02/17/04 12:16:39 (20 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@112
Message:

* empty log message *

Location:
src/work/jacint
Files:
2 edited

Legend:

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

    r84 r85  
    2626#define PREFLOW_PUSH_HL_H
    2727
    28 #include <algorithm>
     28//#include <algorithm>
    2929#include <vector>
    3030#include <stack>
    3131
    32 #include <list_graph.hh>
    3332#include <reverse_bfs.h>
    3433
     
    6867      typename Graph::NodeMap<int> level(G);     
    6968      typename Graph::NodeMap<T> excess(G);
    70       std::cout <<"excess s:"<<excess.get(s);      //delme
    71            
     69
    7270      int n=G.nodeNum();
    7371      int b=n-2;
     
    7775      */
    7876
     77      std::vector<int> numb(n);     //The number of nodes on level i < n.
    7978      std::vector<std::stack<NodeIt> > stack(2*n-1);   
    8079      //Stack of the active nodes in level i.
     
    8685      for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v)
    8786        {
    88           level.set(v, bfs.dist(v));
     87          int dist=bfs.dist(v);
     88          level.set(v, dist);
     89          ++numb[dist];
    8990        }
    9091
     
    9798          if ( capacity.get(e) > 0 ) {
    9899            NodeIt w=G.head(e);
    99             if ( excess.get(w) == 0 && w!=t && w!=s ) stack[level.get(w)].push(w);
    100             flow.set(e, capacity.get(e));
    101             excess.set(w, excess.get(w)+capacity.get(e));
     100            if ( w!=s ) {         
     101              if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w);
     102              flow.set(e, capacity.get(e));
     103              excess.set(w, excess.get(w)+capacity.get(e));
     104            }
    102105          }
    103106        }
     
    113116      */
    114117       
    115       /*While there exists active node.*/
     118      /*While there exists an active node.*/
    116119      while (b) {
    117120
    118         /*We decrease the bound if there is no active Node of level b.*/
     121        /*We decrease the bound if there is no active node of level b.*/
    119122        if (stack[b].empty()) {
    120123          --b;
     
    133136              NodeIt v=G.head(e);               /*e is the edge wv.*/
    134137
    135               if( level.get(w) > level.get(v)+1 ) { std::cout<<"HIBA1!";} //delme     
    136 
    137138              if( level.get(w) == level.get(v)+1 ) {     
    138139                /*Push is allowed now*/
    139140
    140                 if (capacity.get(e)-flow.get(e) > excess.get(w)) {       
     141                if ( excess.get(v)==0 && v != s && v !=t ) stack[level.get(v)].push(v);
     142                /*v becomes active.*/
     143
     144                if ( capacity.get(e)-flow.get(e) > excess.get(w) ) {       
    141145                  /*A nonsaturating push.*/
    142146                 
    143                   if (excess.get(v)==0 && v != s && v !=t) stack[level.get(v)].push(v);
    144                   /*v becomes active.*/
    145 
    146147                  flow.set(e, flow.get(e)+excess.get(w));
    147148                  excess.set(v, excess.get(v)+excess.get(w));
    148149                  excess.set(w,0);
    149                   //std::cout << w << " " << v <<" elore elen nonsat pump "  << std::endl;
    150150                  break;
     151
    151152                } else {
    152153                  /*A saturating push.*/
    153 
    154                   if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v);
    155                   /*v becomes active.*/
    156154
    157155                  excess.set(v, excess.get(v)+capacity.get(e)-flow.get(e));
    158156                  excess.set(w, excess.get(w)-capacity.get(e)+flow.get(e));
    159157                  flow.set(e, capacity.get(e));
    160                   //std::cout << w<<" " <<v<<" elore elen sat pump "   << std::endl;
    161                   if (excess.get(w)==0) break;
    162                   /*If w is not active any more, then we go on to the next Node.*/
     158                  if ( excess.get(w)==0 ) break;
     159                  /*If w is not active any more, then we go on to the next node.*/
    163160                 
    164                   //std::cout<<++i;
     161                }
     162              } else {
     163                newlevel = newlevel < level.get(v) ? newlevel : level.get(v);
     164              }
     165           
     166            } //if the out edge wv is in the res graph
     167         
     168          } //for out edges wv
     169         
     170
     171          if ( excess.get(w) > 0 ) {   
     172           
     173            for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
     174              NodeIt v=G.tail(e);  /*e is the edge vw.*/
     175
     176              if( flow.get(e) > 0 ) {             
     177                /*e is an edge of the residual graph */
     178
     179                if( level.get(w)==level.get(v)+1 ) { 
     180                  /*Push is allowed now*/
     181               
     182                  if ( excess.get(v)==0 && v != s && v !=t) stack[level.get(v)].push(v);
     183                  /*v becomes active.*/
     184
     185                  if ( flow.get(e) > excess.get(w) ) {
     186                    /*A nonsaturating push.*/
    165187                 
    166                 } // if (capacity.get(e)-flow.get(e) > excess.get(w))
    167               } // if(level.get(w)==level.get(v)+1)
    168            
    169               else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
    170            
    171             } //if (flow.get(e)<capacity.get(e))
    172          
    173           } //for(OutEdgeIt e=G.first_OutEdge(w); e.valid(); ++e)
     188                    flow.set(e, flow.get(e)-excess.get(w));
     189                    excess.set(v, excess.get(v)+excess.get(w));
     190                    excess.set(w,0);
     191                    break;
     192                  } else {                                               
     193                    /*A saturating push.*/
     194                   
     195                    excess.set(v, excess.get(v)+flow.get(e));
     196                    excess.set(w, excess.get(w)-flow.get(e));
     197                    flow.set(e,0);
     198                    if ( excess.get(w)==0 ) break;
     199                  } 
     200                } else {
     201                  newlevel = newlevel < level.get(v) ? newlevel : level.get(v);
     202                }
     203               
     204              } //if in edge vw is in the res graph
     205
     206            } //for in edges vw
     207
     208          } // if w still has excess after the out edge for cycle
     209
     210
     211          /*
     212            Relabel
     213          */
    174214         
    175 
    176 
    177           for(InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
    178             NodeIt v=G.tail(e);
    179             /*e is the Edge vw.*/
    180 
    181             if (excess.get(w)==0) break;
    182             /*It may happen, that w became inactive in the first for cycle.*/           
    183             if(flow.get(e)>0) {             
    184               /*e is an Edge of the residual graph */
    185 
    186               if(level.get(w)==level.get(v)+1) { 
    187                 /*Push is allowed now*/
     215          if ( excess.get(w) > 0 ) {
     216           
     217            int oldlevel=level.get(w);     
     218            level.set(w,++newlevel);
     219
     220            if ( oldlevel < n ) {
     221              --numb[oldlevel];
     222
     223              if ( !numb[oldlevel] ) {  //If the level of w gets empty.
    188224               
    189                 if (flow.get(e) > excess.get(w)) {
    190                   /*A nonsaturating push.*/
    191                  
    192                   if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v);
    193                   /*v becomes active.*/
    194 
    195                   flow.set(e, flow.get(e)-excess.get(w));
    196                   excess.set(v, excess.get(v)+excess.get(w));
    197                   excess.set(w,0);
    198                   //std::cout << v << " " << w << " vissza elen nonsat pump "     << std::endl;
    199                   break;
    200                 } else {                                               
    201                   /*A saturating push.*/
    202                  
    203                   if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v);
    204                   /*v becomes active.*/
    205                  
    206                   excess.set(v, excess.get(v)+flow.get(e));
    207                   excess.set(w, excess.get(w)-flow.get(e));
    208                   flow.set(e,0);
    209                   //std::cout << v <<" " << w << " vissza elen sat pump "     << std::endl;
    210                   if (excess.get(w)==0) { break;}
    211                 } //if (flow.get(e) > excess.get(v))
    212               } //if(level.get(w)==level.get(v)+1)
    213              
    214               else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
    215              
    216 
    217             } //if (flow.get(e)>0)
    218 
    219           } //for
    220 
    221 
    222           if (excess.get(w)>0) {
    223             level.set(w,++newlevel);
     225                for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
     226                  if (level.get(v) > oldlevel && level.get(v) < n ) level.set(v,n); 
     227                }
     228                for (int i=oldlevel+1 ; i!=n ; ++i) numb[i]=0;
     229                if ( newlevel < n ) newlevel=n;
     230              } else {
     231                if ( newlevel < n ) ++numb[newlevel];
     232              }
     233            } else {
     234            if ( newlevel < n ) ++numb[newlevel];
     235            }
     236           
    224237            stack[newlevel].push(w);
    225238            b=newlevel;
    226             //std::cout << "The new level of " << w << " is "<< newlevel <<std::endl;
     239
    227240          }
    228241
    229 
    230         } //else
    231        
    232       } //while(b)
     242        } // if stack[b] is nonempty
     243
     244      } // while(b)
     245
    233246
    234247      value = excess.get(t);
    235248      /*Max flow value.*/
    236 
    237 
    238249
    239250
  • src/work/jacint/preflow_push_max_flow.h

    r83 r85  
    2727#include <stack>
    2828
    29 #include <list_graph.hh>
    3029#include <reverse_bfs.h>
    3130
Note: See TracChangeset for help on using the changeset viewer.