COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 774:4297098d9677 in lemon-0.x for src/hugo/max_flow.h


Ignore:
Timestamp:
08/30/04 14:01:47 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1066
Message:

Merge back the whole branches/hugo++ to trunk.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/hugo/max_flow.h

    r773 r774  
    66#include <queue>
    77
    8 #include <hugo/graph_wrapper.h>
     8//#include <hugo/graph_wrapper.h>
    99#include <hugo/invalid.h>
    1010#include <hugo/maps.h>
    … …  
    6363    FlowMap* flow;
    6464    int n;      //the number of nodes of G
    65     typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;   
     65    //    typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;   
    6666    //typedef ExpResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
    67     typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
    68     typedef typename ResGW::Edge ResGWEdge;
     67    //    typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
     68    //    typedef typename ResGW::Edge ResGWEdge;
    6969    typedef typename Graph::template NodeMap<int> ReachedMap;
    7070
    … …  
    113113    StatusEnum status;
    114114
    115 //     int number_of_augmentations;
    116 
    117 
    118 //     template<typename IntMap>
    119 //     class TrickyReachedMap {
    120 //     protected:
    121 //       IntMap* map;
    122 //       int* number_of_augmentations;
    123 //     public:
    124 //       TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) :
    125 //      map(&_map), number_of_augmentations(&_number_of_augmentations) { }
    126 //       void set(const Node& n, bool b) {
    127 //      if (b)
    128 //        map->set(n, *number_of_augmentations);
    129 //      else
    130 //        map->set(n, *number_of_augmentations-1);
    131 //       }
    132 //       bool operator[](const Node& n) const {
    133 //      return (*map)[n]==*number_of_augmentations;
    134 //       }
    135 //     };
     115    //     int number_of_augmentations;
     116
     117
     118    //     template<typename IntMap>
     119    //     class TrickyReachedMap {
     120    //     protected:
     121    //       IntMap* map;
     122    //       int* number_of_augmentations;
     123    //     public:
     124    //       TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) :
     125    //  map(&_map), number_of_augmentations(&_number_of_augmentations) { }
     126    //       void set(const Node& n, bool b) {
     127    //  if (b)
     128    //    map->set(n, *number_of_augmentations);
     129    //  else
     130    //    map->set(n, *number_of_augmentations-1);
     131    //       }
     132    //       bool operator[](const Node& n) const {
     133    //  return (*map)[n]==*number_of_augmentations;
     134    //       }
     135    //     };
    136136   
    137137    ///Constructor
    … …  
    235235        }
    236236
    237         if ( !g->valid(first[b]) ) --b;
     237        if ( first[b]==INVALID ) --b;
    238238        else {
    239239          end=false;
    … …  
    290290        int l=level[v]+1;
    291291
    292         InEdgeIt e;
    293         for(g->first(e,v); g->valid(e); g->next(e)) {
     292        for(InEdgeIt e(*g,v); e!=INVALID; ++e) {
    294293          if ( (*capacity)[e] <= (*flow)[e] ) continue;
    295294          Node u=g->tail(e);
    … …  
    304303        }
    305304
    306         OutEdgeIt f;
    307         for(g->first(f,v); g->valid(f); g->next(f)) {
    308           if ( 0 >= (*flow)[f] ) continue;
    309           Node u=g->head(f);
     305        for(OutEdgeIt e(*g,v); e!=INVALID; ++e) {
     306          if ( 0 >= (*flow)[e] ) continue;
     307          Node u=g->head(e);
    310308          if ( level[u] >= n ) {
    311309            bfs_queue.push(u);
    … …  
    324322        if ( b == 0 ) break;
    325323
    326         if ( !g->valid(first[b]) ) --b;
     324        if ( first[b]==INVALID ) --b;
    327325        else {
    328326
    … …  
    352350    /// It can be called already after running \ref preflowPhase1.
    353351    Num flowValue() const {
    354 //       Num a=0;
    355 //       for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
    356 //       for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
    357 //       return a;
     352      //       Num a=0;
     353      //       for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
     354      //       for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
     355      //       return a;
    358356      return excess[t];
    359357      //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan   
    … …  
    375373    template<typename _CutMap>
    376374    void actMinCut(_CutMap& M) const {
    377       NodeIt v;
    378375      switch (status) {
    379       case AFTER_PRE_FLOW_PHASE_1:
    380         for(g->first(v); g->valid(v); g->next(v)) {
     376        case AFTER_PRE_FLOW_PHASE_1:
     377        for(NodeIt v(*g); v!=INVALID; ++v) {
    381378          if (level[v] < n) {
    382379            M.set(v, false);
    … …  
    386383        }
    387384        break;
    388       case AFTER_PRE_FLOW_PHASE_2:
    389       case AFTER_NOTHING:
    390       case AFTER_AUGMENTING:
    391       case AFTER_FAST_AUGMENTING:
     385        case AFTER_PRE_FLOW_PHASE_2:
     386        case AFTER_NOTHING:
     387        case AFTER_AUGMENTING:
     388        case AFTER_FAST_AUGMENTING:
    392389        minMinCut(M);
    393390        break;
    … …  
    413410        queue.pop();
    414411
    415         OutEdgeIt e;
    416         for(g->first(e,w) ; g->valid(e); g->next(e)) {
     412        for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
    417413          Node v=g->head(e);
    418414          if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
    … …  
    422418        }
    423419
    424         InEdgeIt f;
    425         for(g->first(f,w) ; g->valid(f); g->next(f)) {
    426           Node v=g->tail(f);
    427           if (!M[v] && (*flow)[f] > 0 ) {
     420        for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
     421          Node v=g->tail(e);
     422          if (!M[v] && (*flow)[e] > 0 ) {
    428423            queue.push(v);
    429424            M.set(v, true);
    … …  
    443438    void maxMinCut(_CutMap& M) const {
    444439
    445       NodeIt v;
    446       for(g->first(v) ; g->valid(v); g->next(v)) {
    447         M.set(v, true);
    448       }
     440      for(NodeIt v(*g) ; v!=INVALID; ++v) M.set(v, true);
    449441
    450442      std::queue<Node> queue;
    … …  
    457449        queue.pop();
    458450
    459         InEdgeIt e;
    460         for(g->first(e,w) ; g->valid(e); g->next(e)) {
     451        for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
    461452          Node v=g->tail(e);
    462453          if (M[v] && (*flow)[e] < (*capacity)[e] ) {
    … …  
    466457        }
    467458
    468         OutEdgeIt f;
    469         for(g->first(f,w) ; g->valid(f); g->next(f)) {
    470           Node v=g->head(f);
    471           if (M[v] && (*flow)[f] > 0 ) {
     459        for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
     460          Node v=g->head(e);
     461          if (M[v] && (*flow)[e] > 0 ) {
    472462            queue.push(v);
    473463            M.set(v, false);
    … …  
    519509      int newlevel=n;       //bound on the next level of w
    520510
    521       OutEdgeIt e;
    522       for(g->first(e,w); g->valid(e); g->next(e)) {
    523 
     511      for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
    524512        if ( (*flow)[e] >= (*capacity)[e] ) continue;
    525513        Node v=g->head(e);
    526514
    527515        if( lev > level[v] ) { //Push is allowed now
    528 
     516         
    529517          if ( excess[v]<=0 && v!=t && v!=s ) {
    530518            next.set(v,first[level[v]]);
    … …  
    535523          Num flo=(*flow)[e];
    536524          Num remcap=cap-flo;
    537 
     525         
    538526          if ( remcap >= exc ) { //A nonsaturating push.
    539 
     527           
    540528            flow->set(e, flo+exc);
    541529            excess.set(v, excess[v]+exc);
    … …  
    552540
    553541      if ( exc > 0 ) {
    554         InEdgeIt e;
    555         for(g->first(e,w); g->valid(e); g->next(e)) {
    556 
     542        for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
     543         
    557544          if( (*flow)[e] <= 0 ) continue;
    558545          Node v=g->tail(e);
    … …  
    585572
    586573      excess.set(w, exc);
    587 
     574     
    588575      return newlevel;
    589576    }
    590 
    591 
    592 
     577   
     578   
     579   
    593580    void preflowPreproc(FlowEnum fe, NNMap& next, VecFirst& first,
    594581                        VecNode& level_list, NNMap& left, NNMap& right)
    595582    {
    596       switch (fe) { //setting excess
     583      switch (fe) {  //setting excess
    597584        case NO_FLOW:
     585        for(EdgeIt e(*g); e!=INVALID; ++e) flow->set(e,0);
     586        for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
     587        break;
     588        case ZERO_FLOW:
     589        for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
     590        break;
     591        case GEN_FLOW:
     592        for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
    598593        {
    599           EdgeIt e;
    600           for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0);
    601          
    602           NodeIt v;
    603           for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
    604           break;
    605         }
    606         case ZERO_FLOW:
    607         {
    608           NodeIt v;
    609           for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
    610           break;
    611         }
    612         case GEN_FLOW:
    613         {
    614           NodeIt v;
    615           for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
    616 
    617594          Num exc=0;
    618           InEdgeIt e;
    619           for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
    620           OutEdgeIt f;
    621           for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
     595          for(InEdgeIt e(*g,t) ; e!=INVALID; ++e) exc+=(*flow)[e];
     596          for(OutEdgeIt e(*g,t) ; e!=INVALID; ++e) exc-=(*flow)[e];
    622597          excess.set(t,exc);
    623           break;
    624         }
    625         default: break;
    626       }
    627 
    628       NodeIt v;
    629       for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
     598        }
     599        break;
     600        default:
     601        break;
     602      }
     603     
     604      for(NodeIt v(*g); v!=INVALID; ++v) level.set(v,n);
    630605      //setting each node to level n
    631606     
    … …  
    636611      case NO_FLOW:   //flow is already set to const zero
    637612      case ZERO_FLOW:
    638         {
    639           //Reverse_bfs from t, to find the starting level.
    640           level.set(t,0);
    641           bfs_queue.push(t);
    642 
    643           while (!bfs_queue.empty()) {
    644 
    645             Node v=bfs_queue.front();
    646             bfs_queue.pop();
    647             int l=level[v]+1;
    648 
    649             InEdgeIt e;
    650             for(g->first(e,v); g->valid(e); g->next(e)) {
    651               Node w=g->tail(e);
    652               if ( level[w] == n && w != s ) {
    653                 bfs_queue.push(w);
    654                 Node z=level_list[l];
    655                 if ( g->valid(z) ) left.set(z,w);
    656                 right.set(w,z);
    657                 level_list[l]=w;
    658                 level.set(w, l);
    659               }
    660             }
    661           }
    662 
    663           //the starting flow
    664           OutEdgeIt e;
    665           for(g->first(e,s); g->valid(e); g->next(e))
     613        //Reverse_bfs from t, to find the starting level.
     614        level.set(t,0);
     615        bfs_queue.push(t);
     616       
     617        while (!bfs_queue.empty()) {
     618         
     619          Node v=bfs_queue.front();
     620          bfs_queue.pop();
     621          int l=level[v]+1;
     622         
     623          for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
     624            Node w=g->tail(e);
     625            if ( level[w] == n && w != s ) {
     626              bfs_queue.push(w);
     627              Node z=level_list[l];
     628              if ( z!=INVALID ) left.set(z,w);
     629              right.set(w,z);
     630              level_list[l]=w;
     631              level.set(w, l);
     632            }
     633          }
     634        }
     635       
     636        //the starting flow
     637        for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e)
     638          {
     639            Num c=(*capacity)[e];
     640            if ( c <= 0 ) continue;
     641            Node w=g->head(e);
     642            if ( level[w] < n ) {
     643              if ( excess[w] <= 0 && w!=t ) //putting into the stack
     644                {
     645                  next.set(w,first[level[w]]);
     646                  first[level[w]]=w;
     647                }
     648              flow->set(e, c);
     649              excess.set(w, excess[w]+c);
     650            }
     651          }
     652        break;
     653      case GEN_FLOW:
     654        //Reverse_bfs from t in the residual graph,
     655        //to find the starting level.
     656        level.set(t,0);
     657        bfs_queue.push(t);
     658       
     659        while (!bfs_queue.empty()) {
     660         
     661          Node v=bfs_queue.front();
     662          bfs_queue.pop();
     663          int l=level[v]+1;
     664         
     665          for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
     666            if ( (*capacity)[e] <= (*flow)[e] ) continue;
     667            Node w=g->tail(e);
     668            if ( level[w] == n && w != s ) {
     669              bfs_queue.push(w);
     670              Node z=level_list[l];
     671              if ( z!=INVALID ) left.set(z,w);
     672              right.set(w,z);
     673              level_list[l]=w;
     674              level.set(w, l);
     675            }
     676          }
     677         
     678          for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) {
     679            if ( 0 >= (*flow)[e] ) continue;
     680            Node w=g->head(e);
     681            if ( level[w] == n && w != s ) {
     682              bfs_queue.push(w);
     683              Node z=level_list[l];
     684              if ( z!=INVALID ) left.set(z,w);
     685              right.set(w,z);
     686              level_list[l]=w;
     687              level.set(w, l);
     688            }
     689          }
     690        }
     691       
     692        //the starting flow
     693        for(OutEdgeIt e(*g,s); e!=INVALID; ++e)
     694          {
     695            Num rem=(*capacity)[e]-(*flow)[e];
     696            if ( rem <= 0 ) continue;
     697            Node w=g->head(e);
     698            if ( level[w] < n ) {
     699              if ( excess[w] <= 0 && w!=t ) //putting into the stack
     700                {
     701                  next.set(w,first[level[w]]);
     702                  first[level[w]]=w;
     703                }   
     704              flow->set(e, (*capacity)[e]);
     705              excess.set(w, excess[w]+rem);
     706            }
     707          }
     708       
     709        for(InEdgeIt e(*g,s); e!=INVALID; ++e)
     710          {
     711            if ( (*flow)[e] <= 0 ) continue;
     712            Node w=g->tail(e);
     713            if ( level[w] < n ) {
     714              if ( excess[w] <= 0 && w!=t )
     715                {
     716                  next.set(w,first[level[w]]);
     717                  first[level[w]]=w;
     718                } 
     719              excess.set(w, excess[w]+(*flow)[e]);
     720              flow->set(e, 0);
     721            }
     722          }
     723        break;
     724      case PRE_FLOW:
     725        //Reverse_bfs from t in the residual graph,
     726        //to find the starting level.
     727        level.set(t,0);
     728        bfs_queue.push(t);
     729       
     730        while (!bfs_queue.empty()) {
     731         
     732          Node v=bfs_queue.front();
     733          bfs_queue.pop();
     734          int l=level[v]+1;
     735         
     736          for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
     737            if ( (*capacity)[e] <= (*flow)[e] ) continue;
     738            Node w=g->tail(e);
     739            if ( level[w] == n && w != s ) {
     740              bfs_queue.push(w);
     741              Node z=level_list[l];
     742              if ( z!=INVALID ) left.set(z,w);
     743              right.set(w,z);
     744              level_list[l]=w;
     745              level.set(w, l);
     746            }
     747          }
     748         
     749          for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) {
     750            if ( 0 >= (*flow)[e] ) continue;
     751            Node w=g->head(e);
     752            if ( level[w] == n && w != s ) {
     753              bfs_queue.push(w);
     754              Node z=level_list[l];
     755              if ( z!=INVALID ) left.set(z,w);
     756              right.set(w,z);
     757              level_list[l]=w;
     758              level.set(w, l);
     759            }
     760          }
     761        }
     762       
     763       
     764        //the starting flow
     765        for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) {
     766          Num rem=(*capacity)[e]-(*flow)[e];
     767          if ( rem <= 0 ) continue;
     768          Node w=g->head(e);
     769          if ( level[w] < n ) {
     770            flow->set(e, (*capacity)[e]);
     771            excess.set(w, excess[w]+rem);
     772          }
     773        }
     774       
     775        for(InEdgeIt e(*g,s) ; e!=INVALID; ++e) {
     776          if ( (*flow)[e] <= 0 ) continue;
     777          Node w=g->tail(e);
     778          if ( level[w] < n ) {
     779            excess.set(w, excess[w]+(*flow)[e]);
     780            flow->set(e, 0);
     781          }
     782        }
     783       
     784        //computing the excess
     785        for(NodeIt w(*g); w!=INVALID; ++w) {
     786          Num exc=0;
     787         
     788          for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) exc+=(*flow)[e];
     789          for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) exc-=(*flow)[e];
     790         
     791          excess.set(w,exc);
     792         
     793          //putting the active nodes into the stack
     794          int lev=level[w];
     795            if ( exc > 0 && lev < n && Node(w) != t )
     796              ///\bug       if ( exc > 0 && lev < n && w != t ) temporarily for working with wrappers.
    666797            {
    667               Num c=(*capacity)[e];
    668               if ( c <= 0 ) continue;
    669               Node w=g->head(e);
    670               if ( level[w] < n ) {
    671                 if ( excess[w] <= 0 && w!=t ) //putting into the stack
    672                   {
    673                     next.set(w,first[level[w]]);
    674                     first[level[w]]=w;
    675                   }
    676                 flow->set(e, c);
    677                 excess.set(w, excess[w]+c);
    678               }
    679             }
    680           break;
    681         }
    682 
    683       case GEN_FLOW:
    684         {
    685           //Reverse_bfs from t in the residual graph,
    686           //to find the starting level.
    687           level.set(t,0);
    688           bfs_queue.push(t);
    689 
    690           while (!bfs_queue.empty()) {
    691 
    692             Node v=bfs_queue.front();
    693             bfs_queue.pop();
    694             int l=level[v]+1;
    695 
    696             InEdgeIt e;
    697             for(g->first(e,v); g->valid(e); g->next(e)) {
    698               if ( (*capacity)[e] <= (*flow)[e] ) continue;
    699               Node w=g->tail(e);
    700               if ( level[w] == n && w != s ) {
    701                 bfs_queue.push(w);
    702                 Node z=level_list[l];
    703                 if ( g->valid(z) ) left.set(z,w);
    704                 right.set(w,z);
    705                 level_list[l]=w;
    706                 level.set(w, l);
    707               }
    708             }
    709 
    710             OutEdgeIt f;
    711             for(g->first(f,v); g->valid(f); g->next(f)) {
    712               if ( 0 >= (*flow)[f] ) continue;
    713               Node w=g->head(f);
    714               if ( level[w] == n && w != s ) {
    715                 bfs_queue.push(w);
    716                 Node z=level_list[l];
    717                 if ( g->valid(z) ) left.set(z,w);
    718                 right.set(w,z);
    719                 level_list[l]=w;
    720                 level.set(w, l);
    721               }
    722             }
    723           }
    724 
    725           //the starting flow
    726           OutEdgeIt e;
    727           for(g->first(e,s); g->valid(e); g->next(e))
    728             {
    729               Num rem=(*capacity)[e]-(*flow)[e];
    730               if ( rem <= 0 ) continue;
    731               Node w=g->head(e);
    732               if ( level[w] < n ) {
    733                 if ( excess[w] <= 0 && w!=t ) //putting into the stack
    734                   {
    735                     next.set(w,first[level[w]]);
    736                     first[level[w]]=w;
    737                   }   
    738                 flow->set(e, (*capacity)[e]);
    739                 excess.set(w, excess[w]+rem);
    740               }
    741             }
    742 
    743           InEdgeIt f;
    744           for(g->first(f,s); g->valid(f); g->next(f))
    745             {
    746               if ( (*flow)[f] <= 0 ) continue;
    747               Node w=g->tail(f);
    748               if ( level[w] < n ) {
    749                 if ( excess[w] <= 0 && w!=t )
    750                   {
    751                     next.set(w,first[level[w]]);
    752                     first[level[w]]=w;
    753                   } 
    754                 excess.set(w, excess[w]+(*flow)[f]);
    755                 flow->set(f, 0);
    756               }
    757             }
    758           break;
    759         } //case GEN_FLOW
    760    
    761       case PRE_FLOW:
    762         {
    763           //Reverse_bfs from t in the residual graph,
    764           //to find the starting level.
    765           level.set(t,0);
    766           bfs_queue.push(t);
    767 
    768           while (!bfs_queue.empty()) {
    769 
    770             Node v=bfs_queue.front();
    771             bfs_queue.pop();
    772             int l=level[v]+1;
    773 
    774             InEdgeIt e;
    775             for(g->first(e,v); g->valid(e); g->next(e)) {
    776               if ( (*capacity)[e] <= (*flow)[e] ) continue;
    777               Node w=g->tail(e);
    778               if ( level[w] == n && w != s ) {
    779                 bfs_queue.push(w);
    780                 Node z=level_list[l];
    781                 if ( g->valid(z) ) left.set(z,w);
    782                 right.set(w,z);
    783                 level_list[l]=w;
    784                 level.set(w, l);
    785               }
    786             }
    787 
    788             OutEdgeIt f;
    789             for(g->first(f,v); g->valid(f); g->next(f)) {
    790               if ( 0 >= (*flow)[f] ) continue;
    791               Node w=g->head(f);
    792               if ( level[w] == n && w != s ) {
    793                 bfs_queue.push(w);
    794                 Node z=level_list[l];
    795                 if ( g->valid(z) ) left.set(z,w);
    796                 right.set(w,z);
    797                 level_list[l]=w;
    798                 level.set(w, l);
    799               }
    800             }
    801           }
    802 
    803 
    804           //the starting flow
    805           OutEdgeIt e;
    806           for(g->first(e,s); g->valid(e); g->next(e))
    807             {
    808               Num rem=(*capacity)[e]-(*flow)[e];
    809               if ( rem <= 0 ) continue;
    810               Node w=g->head(e);
    811               if ( level[w] < n ) {
    812                 flow->set(e, (*capacity)[e]);
    813                 excess.set(w, excess[w]+rem);
    814               }
    815             }
    816 
    817           InEdgeIt f;
    818           for(g->first(f,s); g->valid(f); g->next(f))
    819             {
    820               if ( (*flow)[f] <= 0 ) continue;
    821               Node w=g->tail(f);
    822               if ( level[w] < n ) {
    823                 excess.set(w, excess[w]+(*flow)[f]);
    824                 flow->set(f, 0);
    825               }
    826             }
    827          
    828           NodeIt w; //computing the excess
    829           for(g->first(w); g->valid(w); g->next(w)) {
    830             Num exc=0;
    831 
    832             InEdgeIt e;
    833             for(g->first(e,w); g->valid(e); g->next(e)) exc+=(*flow)[e];
    834             OutEdgeIt f;
    835             for(g->first(f,w); g->valid(f); g->next(f)) exc-=(*flow)[f];
    836 
    837             excess.set(w,exc);
    838 
    839             //putting the active nodes into the stack
    840             int lev=level[w];
    841             if ( exc > 0 && lev < n && Node(w) != t )
    842 ///\bug     if ( exc > 0 && lev < n && w != t ) tempararily for working with wrappers. in hugo 0.2 it will work. Amugy mukodik sage_graph-fal, de smart_graph-fal nem, azt hozzatennem.
    843               {
    844                 next.set(w,first[lev]);
    845                 first[lev]=w;
    846               }
    847           }
    848           break;
    849         } //case PRE_FLOW
    850       }
     798              next.set(w,first[lev]);
     799              first[lev]=w;
     800            }
     801        }
     802        break;
     803      } //switch
    851804    } //preflowPreproc
    852805
    … …  
    863816
    864817      //unlacing starts
    865       if ( g->valid(right_n) ) {
    866         if ( g->valid(left_n) ) {
     818      if ( right_n!=INVALID ) {
     819        if ( left_n!=INVALID ) {
    867820          right.set(left_n, right_n);
    868821          left.set(right_n, left_n);
    … …  
    872825        }
    873826      } else {
    874         if ( g->valid(left_n) ) {
     827        if ( left_n!=INVALID ) {
    875828          right.set(left_n, INVALID);
    876829        } else {
    … …  
    880833      //unlacing ends
    881834
    882       if ( !g->valid(level_list[lev]) ) {
     835      if ( level_list[lev]==INVALID ) {
    883836
    884837        //gapping starts
    885838        for (int i=lev; i!=k ; ) {
    886839          Node v=level_list[++i];
    887           while ( g->valid(v) ) {
     840          while ( v!=INVALID ) {
    888841            level.set(v,n);
    889842            v=right[v];
    … …  
    908861          if ( k < newlevel ) ++k;      //now k=newlevel
    909862          Node z=level_list[newlevel];
    910           if ( g->valid(z) ) left.set(z,w);
     863          if ( z!=INVALID ) left.set(z,w);
    911864          right.set(w,z);
    912865          left.set(w,INVALID);
    … …  
    919872      std::cout << "Excesses:" <<std::endl;
    920873
    921       NodeIt v;
    922       for(g->first(v); g->valid(v); g->next(v)) {
     874      for(NodeIt v(*g); v!=INVALID ; ++v) {
    923875        std::cout << 1+(g->id(v)) << ":" << excess[v]<<std::endl;
    924876      }
    925877    }
    926878
    927  void printlevel() {////
     879    void printlevel() {////
    928880      std::cout << "Levels:" <<std::endl;
    929881
    930       NodeIt v;
    931       for(g->first(v); g->valid(v); g->next(v)) {
     882      for(NodeIt v(*g); v!=INVALID ; ++v) {
    932883        std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl;
    933884      }
    934885    }
    935886
    936 void printactive() {////
     887    void printactive() {////
    937888      std::cout << "Levels:" <<std::endl;
    938889
    939       NodeIt v;
    940       for(g->first(v); g->valid(v); g->next(v)) {
     890      for(NodeIt v(*g); v!=INVALID ; ++v) {
    941891        std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl;
    942892      }
Note: See TracChangeset for help on using the changeset viewer.