COIN-OR::LEMON - Graph Library

Changeset 749:8e933219691e in lemon-0.x for src/hugo/max_flow.h


Ignore:
Timestamp:
07/30/04 12:24:05 (20 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1009
Message:

bug fixing

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/max_flow.h

    r745 r749  
    11// -*- C++ -*-
    2 #ifndef HUGO_MAX_FLOW_NO_STACK_H
    3 #define HUGO_MAX_FLOW_NO_STACK_H
     2#ifndef HUGO_MAX_FLOW_H
     3#define HUGO_MAX_FLOW_H
    44
    55#include <vector>
    66#include <queue>
    7 //#include <stack>
    87
    98#include <hugo/graph_wrapper.h>
     
    1211
    1312/// \file
    14 /// \brief The same as max_flow.h, but without using stl stack for the active nodes. Only for test.
    1513/// \ingroup galgs
    1614
     
    5250    typedef typename Graph::InEdgeIt InEdgeIt;
    5351
    54     //    typedef typename std::vector<std::stack<Node> > VecStack;
    5552    typedef typename std::vector<Node> VecFirst;
    5653    typedef typename Graph::template NodeMap<Node> NNMap;
     
    6764    typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
    6865    typedef typename ResGW::Edge ResGWEdge;
    69     //typedef typename ResGW::template NodeMap<bool> ReachedMap;
    7066    typedef typename Graph::template NodeMap<int> ReachedMap;
    7167
     
    111107    };
    112108
    113     /// Don not needle this flag only if necessary.
     109    /// Do not needle this flag only if necessary.
    114110    StatusEnum status;
    115111
     
    189185    ///first phase. After the first phase the maximum flow value and a
    190186    ///minimum value cut can already be computed, though a maximum flow
    191     ///is net yet obtained. So after calling this method \ref flowValue
     187    ///is not yet obtained. So after calling this method \ref flowValue
    192188    ///and \ref actMinCut gives proper results.
    193189    ///\warning: \ref minCut, \ref minMinCut and \ref maxMinCut do not
     
    224220      //List of the nodes in level i<n, set to n.
    225221
    226       NodeIt v;
    227       for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
    228       //setting each node to level n
    229 
    230       if ( fe == NO_FLOW ) {
    231         EdgeIt e;
    232         for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0);
    233       }
    234 
    235       switch (fe) { //computing the excess
    236       case PRE_FLOW:
    237         {
    238           NodeIt v;
    239           for(g->first(v); g->valid(v); g->next(v)) {
    240             Num exc=0;
    241 
    242             InEdgeIt e;
    243             for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
    244             OutEdgeIt f;
    245             for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
    246 
    247             excess.set(v,exc);
    248 
    249             //putting the active nodes into the stack
    250             int lev=level[v];
    251             if ( exc > 0 && lev < n && v != t )
    252               {
    253                 next.set(v,first[lev]);
    254                 first[lev]=v;
    255               }
    256           }
    257           break;
    258         }
    259       case GEN_FLOW:
    260         {
    261           NodeIt v;
    262           for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
    263 
    264           Num exc=0;
    265           InEdgeIt e;
    266           for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
    267           OutEdgeIt f;
    268           for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
    269           excess.set(t,exc);
    270           break;
    271         }
    272       case ZERO_FLOW:
    273       case NO_FLOW:
    274         {
    275           NodeIt v;
    276           for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
    277           break;
    278         }
    279       }
    280 
    281222      preflowPreproc(fe, next, first, level_list, left, right);
    282223      //End of preprocessing
    283 
    284224
    285225      //Push/relabel on the highest level active nodes.
     
    395335            b=newlevel;
    396336          }
    397         }  // if stack[b] is nonempty
     337        }
    398338      } // while(true)
    399339
     
    414354      //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan   
    415355    }
    416     Num flowValue2() const {
    417       return excess[t];
    418 //       Num a=0;
    419 //       for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
    420 //       for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
    421 //       return a;
    422 //       //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan 
    423      
    424     }
     356
    425357
    426358    ///Returns a minimum value cut after calling \ref preflowPhase1.
     
    653585
    654586
     587
    655588    void preflowPreproc(FlowEnum fe, NNMap& next, VecFirst& first,
    656589                        VecNode& level_list, NNMap& left, NNMap& right)
    657590    {
     591      switch (fe) { //setting excess
     592        case NO_FLOW:
     593        {
     594          EdgeIt e;
     595          for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0);
     596         
     597          NodeIt v;
     598          for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
     599          break;
     600        }
     601        case ZERO_FLOW:
     602        {
     603          NodeIt v;
     604          for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
     605          break;
     606        }
     607        case GEN_FLOW:
     608        {
     609          NodeIt v;
     610          for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
     611
     612          Num exc=0;
     613          InEdgeIt e;
     614          for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
     615          OutEdgeIt f;
     616          for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
     617          excess.set(t,exc);
     618          break;
     619        }
     620        default: break;
     621      }
     622
     623      NodeIt v;
     624      for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
     625      //setting each node to level n
     626     
    658627      std::queue<Node> bfs_queue;
    659628
     629
    660630      switch (fe) {
    661       case NO_FLOW:   //flow is already set to const zero in this case
     631      case NO_FLOW:   //flow is already set to const zero
    662632      case ZERO_FLOW:
    663633        {
     
    694664              Node w=g->head(e);
    695665              if ( level[w] < n ) {
    696                 if ( excess[w] <= 0 && w!=t )
    697                   {
     666                if ( excess[w] <= 0 && w!=t ) //putting into the stack
     667                  { 
    698668                    next.set(w,first[level[w]]);
    699669                    first[level[w]]=w;
     
    707677
    708678      case GEN_FLOW:
    709       case PRE_FLOW:
    710679        {
    711680          //Reverse_bfs from t in the residual graph,
     
    749718          }
    750719
    751 
    752720          //the starting flow
    753721          OutEdgeIt e;
     
    758726              Node w=g->head(e);
    759727              if ( level[w] < n ) {
    760                 if ( excess[w] <= 0 && w!=t )
     728                if ( excess[w] <= 0 && w!=t ) //putting into the stack
    761729                  {
    762730                    next.set(w,first[level[w]]);
     
    778746                    next.set(w,first[level[w]]);
    779747                    first[level[w]]=w;
    780                   }   
     748                  } 
    781749                excess.set(w, excess[w]+(*flow)[f]);
    782750                flow->set(f, 0);
     
    784752            }
    785753          break;
     754        } //case GEN_FLOW
     755   
     756      case PRE_FLOW:
     757        {
     758          //Reverse_bfs from t in the residual graph,
     759          //to find the starting level.
     760          level.set(t,0);
     761          bfs_queue.push(t);
     762
     763          while (!bfs_queue.empty()) {
     764
     765            Node v=bfs_queue.front();
     766            bfs_queue.pop();
     767            int l=level[v]+1;
     768
     769            InEdgeIt e;
     770            for(g->first(e,v); g->valid(e); g->next(e)) {
     771              if ( (*capacity)[e] <= (*flow)[e] ) continue;
     772              Node w=g->tail(e);
     773              if ( level[w] == n && w != s ) {
     774                bfs_queue.push(w);
     775                Node z=level_list[l];
     776                if ( g->valid(z) ) left.set(z,w);
     777                right.set(w,z);
     778                level_list[l]=w;
     779                level.set(w, l);
     780              }
     781            }
     782
     783            OutEdgeIt f;
     784            for(g->first(f,v); g->valid(f); g->next(f)) {
     785              if ( 0 >= (*flow)[f] ) continue;
     786              Node w=g->head(f);
     787              if ( level[w] == n && w != s ) {
     788                bfs_queue.push(w);
     789                Node z=level_list[l];
     790                if ( g->valid(z) ) left.set(z,w);
     791                right.set(w,z);
     792                level_list[l]=w;
     793                level.set(w, l);
     794              }
     795            }
     796          }
     797
     798
     799          //the starting flow
     800          OutEdgeIt e;
     801          for(g->first(e,s); g->valid(e); g->next(e))
     802            {
     803              Num rem=(*capacity)[e]-(*flow)[e];
     804              if ( rem <= 0 ) continue;
     805              Node w=g->head(e);
     806              if ( level[w] < n ) {
     807                flow->set(e, (*capacity)[e]);
     808                excess.set(w, excess[w]+rem);
     809              }
     810            }
     811
     812          InEdgeIt f;
     813          for(g->first(f,s); g->valid(f); g->next(f))
     814            {
     815              if ( (*flow)[f] <= 0 ) continue;
     816              Node w=g->tail(f);
     817              if ( level[w] < n ) {
     818                excess.set(w, excess[w]+(*flow)[f]);
     819                flow->set(f, 0);
     820              }
     821            }
     822         
     823          NodeIt w; //computing the excess
     824          for(g->first(w); g->valid(w); g->next(w)) {
     825            Num exc=0;
     826
     827            InEdgeIt e;
     828            for(g->first(e,w); g->valid(e); g->next(e)) exc+=(*flow)[e];
     829            OutEdgeIt f;
     830            for(g->first(f,w); g->valid(f); g->next(f)) exc-=(*flow)[f];
     831
     832            excess.set(w,exc);
     833
     834            //putting the active nodes into the stack
     835            int lev=level[w];
     836            if ( exc > 0 && lev < n && w != t )
     837              {
     838                next.set(w,first[lev]);
     839                first[lev]=w;
     840              }
     841          }
     842          break;
    786843        } //case PRE_FLOW
    787844      }
    788845    } //preflowPreproc
    789 
    790846
    791847
     
    853909      }
    854910    } //relabel
     911
     912    void printexcess() {////
     913      std::cout << "Excesses:" <<std::endl;
     914
     915      NodeIt v;
     916      for(g->first(v); g->valid(v); g->next(v)) {
     917        std::cout << 1+(g->id(v)) << ":" << excess[v]<<std::endl;
     918      }
     919    }
     920
     921 void printlevel() {////
     922      std::cout << "Levels:" <<std::endl;
     923
     924      NodeIt v;
     925      for(g->first(v); g->valid(v); g->next(v)) {
     926        std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl;
     927      }
     928    }
     929
     930void printactive() {////
     931      std::cout << "Levels:" <<std::endl;
     932
     933      NodeIt v;
     934      for(g->first(v); g->valid(v); g->next(v)) {
     935        std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl;
     936      }
     937    }
     938
     939
    855940  };  //class MaxFlow
    856941} //namespace hugo
Note: See TracChangeset for help on using the changeset viewer.