COIN-OR::LEMON - Graph Library

Changeset 745:d976ba609099 in lemon-0.x


Ignore:
Timestamp:
07/29/04 19:18:49 (15 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1005
Message:

jacint javitgatott.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/max_flow.h

    r735 r745  
    141141    ///
    142142    MaxFlow(const Graph& _G, Node _s, Node _t,
    143                    const CapMap& _capacity, FlowMap& _flow) :
     143            const CapMap& _capacity, FlowMap& _flow) :
    144144      g(&_G), s(_s), t(_t), capacity(&_capacity),
    145145      flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0),
     
    218218      VecFirst first(n, INVALID);
    219219      NNMap next(*g, INVALID); //maybe INVALID is not needed
    220       //    VecStack active(n);
    221220
    222221      NNMap left(*g, INVALID);
     
    255254                first[lev]=v;
    256255              }
    257             //    active[lev].push(v);
    258256          }
    259257          break;
     
    281279      }
    282280
    283       preflowPreproc(fe, next, first,/*active*/ level_list, left, right);
     281      preflowPreproc(fe, next, first, level_list, left, right);
    284282      //End of preprocessing
    285283
     
    294292        }
    295293
    296         if ( !g->valid(first[b])/*active[b].empty()*/ ) --b;
     294        if ( !g->valid(first[b]) ) --b;
    297295        else {
    298296          end=false;
    299297          Node w=first[b];
    300298          first[b]=next[w];
    301           /*    Node w=active[b].top();
    302                 active[b].pop();*/
    303           int newlevel=push(w,/*active*/next, first);
    304           if ( excess[w] > 0 ) relabel(w, newlevel, /*active*/next, first, level_list,
     299          int newlevel=push(w, next, first);
     300          if ( excess[w] > 0 ) relabel(w, newlevel, next, first, level_list,
    305301                                       left, right, b, k, what_heur);
    306302
     
    341337      VecFirst first(n, INVALID);
    342338      NNMap next(*g, INVALID); //maybe INVALID is not needed
    343       //    VecStack active(n);
    344339      level.set(s,0);
    345340      std::queue<Node> bfs_queue;
     
    362357              next.set(u,first[l]);
    363358              first[l]=u;
    364               //active[l].push(u);
    365359            }
    366360          }
     
    377371              next.set(u,first[l]);
    378372              first[l]=u;
    379               //active[l].push(u);
    380373            }
    381374          }
     
    388381        if ( b == 0 ) break;
    389382
    390         if ( !g->valid(first[b])/*active[b].empty()*/ ) --b;
     383        if ( !g->valid(first[b]) ) --b;
    391384        else {
    392385
    393386          Node w=first[b];
    394387          first[b]=next[w];
    395           /*    Node w=active[b].top();
    396                 active[b].pop();*/
    397388          int newlevel=push(w,next, first/*active*/);
    398389
     
    402393            next.set(w,first[newlevel]);
    403394            first[newlevel]=w;
    404             //active[newlevel].push(w);
    405395            b=newlevel;
    406396          }
     
    421411      for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
    422412      for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
    423 
     413      return a;
    424414      //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan   
     415    }
     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     
    425424    }
    426425
     
    452451      case AFTER_PRE_FLOW_PHASE_2:
    453452      case AFTER_NOTHING:
     453      case AFTER_AUGMENTING:
     454      case AFTER_FAST_AUGMENTING:
    454455        minMinCut(M);
    455456        break;
     
    592593            next.set(v,first[level[v]]);
    593594            first[level[v]]=v;
    594             //      int lev_v=level[v];
    595             //active[lev_v].push(v);
    596595          }
    597596
     
    627626              next.set(v,first[level[v]]);
    628627              first[level[v]]=v;
    629               //int lev_v=level[v];
    630               //active[lev_v].push(v);
    631628            }
    632629
     
    701698                    next.set(w,first[level[w]]);
    702699                    first[level[w]]=w;
    703                     //active[level[w]].push(w);
    704700                  }
    705701                flow->set(e, c);
     
    766762                    next.set(w,first[level[w]]);
    767763                    first[level[w]]=w;
    768                     //active[level[w]].push(w);
    769764                  }   
    770765                flow->set(e, (*capacity)[e]);
     
    783778                    next.set(w,first[level[w]]);
    784779                    first[level[w]]=w;
    785                     //active[level[w]].push(w);
    786780                  }   
    787781                excess.set(w, excess[w]+(*flow)[f]);
     
    835829          level_list[i]=INVALID;
    836830          if ( !what_heur ) first[i]=INVALID;
    837           /*{
    838             while ( !active[i].empty() ) {
    839             active[i].pop();    //FIXME: ezt szebben kene
    840             }
    841             }*/
    842831        }
    843832
     
    854843          next.set(w,first[newlevel]);
    855844          first[newlevel]=w;
    856           //      active[newlevel].push(w);
    857845          if ( what_heur ) b=newlevel;
    858846          if ( k < newlevel ) ++k;      //now k=newlevel
Note: See TracChangeset for help on using the changeset viewer.