COIN-OR::LEMON - Graph Library

Changeset 84:56e879edcca6 in lemon-0.x for src


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

after debugging

File:
1 edited

Legend:

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

    r83 r84  
    6666    void run() {
    6767 
    68       int i=0;//DELME
    69 
    7068      typename Graph::NodeMap<int> level(G);     
    71       typename Graph::NodeMap<T> excess(G);     
     69      typename Graph::NodeMap<T> excess(G);
     70      std::cout <<"excess s:"<<excess.get(s);      //delme
    7271           
    73       int n=G.nodeNum();    
     72      int n=G.nodeNum();
    7473      int b=n-2;
    7574      /*
     
    9089        }
    9190
    92       std::cout << "the level of t is " << bfs.dist(t);//delme
    93 
    9491      level.set(s,n);
    9592
     
    10097          if ( capacity.get(e) > 0 ) {
    10198            NodeIt w=G.head(e);
     99            if ( excess.get(w) == 0 && w!=t && w!=s ) stack[level.get(w)].push(w);
    102100            flow.set(e, capacity.get(e));
    103             stack[level.get(w)].push(w);
    104101            excess.set(w, excess.get(w)+capacity.get(e));
    105102          }
    106103        }
    107104
    108 
    109105      /*
    110106         End of preprocessing
     
    114110
    115111      /*
    116         Push/relabel on the highest level active Nodes.
     112        Push/relabel on the highest level active nodes.
    117113      */
    118114       
    119       /*While there exists active Node.*/
     115      /*While there exists active node.*/
    120116      while (b) {
    121117
     
    125121        } else {
    126122
    127           NodeIt w=stack[b].top();    //w is the highest label active Node.
    128           stack[b].pop();                    //We delete w from the stack.
     123          NodeIt w=stack[b].top();        //w is a highest label active node.
     124          stack[b].pop();           
    129125       
    130           int newlevel=2*n-2;                   //In newlevel we maintain the next level of w.
     126          int newlevel=2*n-2;             //In newlevel we bound the next level of w.
    131127       
    132128          for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
    133             NodeIt v=G.head(e);
    134             /*e is the Edge wv.*/
    135 
    136             if (flow.get(e)<capacity.get(e)) {             
    137               /*e is an Edge of the residual graph */
    138 
    139               if(level.get(w)==level.get(v)+1) {     
     129           
     130            if ( flow.get(e) < capacity.get(e) ) {             
     131              /*e is an edge of the residual graph */
     132
     133              NodeIt v=G.head(e);               /*e is the edge wv.*/
     134
     135              if( level.get(w) > level.get(v)+1 ) { std::cout<<"HIBA1!";} //delme     
     136
     137              if( level.get(w) == level.get(v)+1 ) {     
    140138                /*Push is allowed now*/
    141139
     
    143141                  /*A nonsaturating push.*/
    144142                 
    145                   if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
     143                  if (excess.get(v)==0 && v != s && v !=t) stack[level.get(v)].push(v);
    146144                  /*v becomes active.*/
    147145
    148                   //std::cout<<++i;
    149                  
    150146                  flow.set(e, flow.get(e)+excess.get(w));
    151147                  excess.set(v, excess.get(v)+excess.get(w));
     
    156152                  /*A saturating push.*/
    157153
    158                   if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
     154                  if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v);
    159155                  /*v becomes active.*/
    160156
     
    194190                  /*A nonsaturating push.*/
    195191                 
    196                   if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
     192                  if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v);
    197193                  /*v becomes active.*/
    198194
     
    205201                  /*A saturating push.*/
    206202                 
    207                   if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
     203                  if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v);
    208204                  /*v becomes active.*/
    209205                 
Note: See TracChangeset for help on using the changeset viewer.