COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 466:cd40ecf4d2a9 in lemon-0.x for src/work/jacint/preflow.h


Ignore:
Timestamp:
04/29/04 12:16:46 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@617
Message:

preflow, maxflow comp

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/work/jacint/preflow.h

    r465 r466  
    6060    typedef typename std::vector<Node> VecNode;
    6161
    62     const Graph& G;
     62    const Graph* g;
    6363    Node s;
    6464    Node t;
    … …  
    8080    Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
    8181            FlowMap& _flow) :
    82       G(_G), s(_s), t(_t), capacity(&_capacity),
     82      g(&_G), s(_s), t(_t), capacity(&_capacity),
    8383      flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
    8484
    … …  
    110110      VecStack active(n);
    111111     
    112       NNMap left(G,INVALID);
    113       NNMap right(G,INVALID);
     112      NNMap left(*g, INVALID);
     113      NNMap right(*g, INVALID);
    114114      VecNode level_list(n,INVALID);
    115115      //List of the nodes in level i<n, set to n.
    116116
    117117      NodeIt v;
    118       for(G.first(v); G.valid(v); G.next(v)) level.set(v,n);
     118      for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
    119119      //setting each node to level n
    120120     
    … …  
    124124          //counting the excess
    125125          NodeIt v;
    126           for(G.first(v); G.valid(v); G.next(v)) {
     126          for(g->first(v); g->valid(v); g->next(v)) {
    127127            T exc=0;
    128128         
    129129            InEdgeIt e;
    130             for(G.first(e,v); G.valid(e); G.next(e)) exc+=(*flow)[e];
     130            for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
    131131            OutEdgeIt f;
    132             for(G.first(f,v); G.valid(f); G.next(f)) exc-=(*flow)[f];
     132            for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
    133133           
    134134            excess.set(v,exc);   
    … …  
    146146         
    147147          InEdgeIt e;
    148           for(G.first(e,t); G.valid(e); G.next(e)) exc+=(*flow)[e];
     148          for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
    149149          OutEdgeIt f;
    150           for(G.first(f,t); G.valid(f); G.next(f)) exc-=(*flow)[f];
     150          for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
    151151         
    152152          excess.set(t,exc);   
    … …  
    217217             
    218218        InEdgeIt e;
    219         for(G.first(e,v); G.valid(e); G.next(e)) {
     219        for(g->first(e,v); g->valid(e); g->next(e)) {
    220220          if ( (*capacity)[e] == (*flow)[e] ) continue;
    221           Node u=G.tail(e);
     221          Node u=g->tail(e);
    222222          if ( level[u] >= n ) {
    223223            bfs_queue.push(u);
    … …  
    228228       
    229229        OutEdgeIt f;
    230         for(G.first(f,v); G.valid(f); G.next(f)) {
     230        for(g->first(f,v); g->valid(f); g->next(f)) {
    231231          if ( 0 == (*flow)[f] ) continue;
    232           Node u=G.head(f);
     232          Node u=g->head(f);
    233233          if ( level[u] >= n ) {
    234234            bfs_queue.push(u);
    … …  
    270270    void actMinCut(_CutMap& M) {
    271271      NodeIt v;
    272       for(G.first(v); G.valid(v); G.next(v))
    273         if ( level[v] < n ) M.set(v,false);
    274         else M.set(v,true);
     272      for(g->first(v); g->valid(v); g->next(v))
     273      if ( level[v] < n ) {
     274        M.set(v,false);
     275      } else {
     276        M.set(v,true);
     277      }
    275278    }
    276279
    … …  
    293296
    294297        OutEdgeIt e;
    295         for(G.first(e,w) ; G.valid(e); G.next(e)) {
    296           Node v=G.head(e);
     298        for(g->first(e,w) ; g->valid(e); g->next(e)) {
     299          Node v=g->head(e);
    297300          if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
    298301            queue.push(v);
    … …  
    302305
    303306        InEdgeIt f;
    304         for(G.first(f,w) ; G.valid(f); G.next(f)) {
    305           Node v=G.tail(f);
     307        for(g->first(f,w) ; g->valid(f); g->next(f)) {
     308          Node v=g->tail(f);
    306309          if (!M[v] && (*flow)[f] > 0 ) {
    307310            queue.push(v);
    … …  
    323326
    324327      NodeIt v;
    325       for(G.first(v) ; G.valid(v); G.next(v)) {
     328      for(g->first(v) ; g->valid(v); g->next(v)) {
    326329        M.set(v, true);
    327330      }
    … …  
    338341
    339342        InEdgeIt e;
    340         for(G.first(e,w) ; G.valid(e); G.next(e)) {
    341           Node v=G.tail(e);
     343        for(g->first(e,w) ; g->valid(e); g->next(e)) {
     344          Node v=g->tail(e);
    342345          if (M[v] && (*flow)[e] < (*capacity)[e] ) {
    343346            queue.push(v);
    … …  
    347350       
    348351        OutEdgeIt f;
    349         for(G.first(f,w) ; G.valid(f); G.next(f)) {
    350           Node v=G.head(f);
     352        for(g->first(f,w) ; g->valid(f); g->next(f)) {
     353          Node v=g->head(f);
    351354          if (M[v] && (*flow)[f] > 0 ) {
    352355            queue.push(v);
    … …  
    386389         
    387390      OutEdgeIt e;
    388       for(G.first(e,w); G.valid(e); G.next(e)) {
     391      for(g->first(e,w); g->valid(e); g->next(e)) {
    389392           
    390393        if ( (*flow)[e] == (*capacity)[e] ) continue;
    391         Node v=G.head(e);           
     394        Node v=g->head(e);           
    392395           
    393396        if( lev > level[v] ) { //Push is allowed now
    … …  
    419422      if ( exc > 0 ) { 
    420423        InEdgeIt e;
    421         for(G.first(e,w); G.valid(e); G.next(e)) {
     424        for(g->first(e,w); g->valid(e); g->next(e)) {
    422425         
    423426          if( (*flow)[e] == 0 ) continue;
    424           Node v=G.tail(e);
     427          Node v=g->tail(e);
    425428         
    426429          if( lev > level[v] ) { //Push is allowed now
    … …  
    475478           
    476479            InEdgeIt e;
    477             for(G.first(e,v); G.valid(e); G.next(e)) {
    478               Node w=G.tail(e);
     480            for(g->first(e,v); g->valid(e); g->next(e)) {
     481              Node w=g->tail(e);
    479482              if ( level[w] == n && w != s ) {
    480483                bfs_queue.push(w);
    481484                Node first=level_list[l];
    482                 if ( G.valid(first) ) left.set(first,w);
     485                if ( g->valid(first) ) left.set(first,w);
    483486                right.set(w,first);
    484487                level_list[l]=w;
    … …  
    490493          //the starting flow
    491494          OutEdgeIt e;
    492           for(G.first(e,s); G.valid(e); G.next(e))
     495          for(g->first(e,s); g->valid(e); g->next(e))
    493496            {
    494497              T c=(*capacity)[e];
    495498              if ( c == 0 ) continue;
    496               Node w=G.head(e);
     499              Node w=g->head(e);
    497500              if ( level[w] < n ) {       
    498501                if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
    … …  
    519522           
    520523            InEdgeIt e;
    521             for(G.first(e,v); G.valid(e); G.next(e)) {
     524            for(g->first(e,v); g->valid(e); g->next(e)) {
    522525              if ( (*capacity)[e] == (*flow)[e] ) continue;
    523               Node w=G.tail(e);
     526              Node w=g->tail(e);
    524527              if ( level[w] == n && w != s ) {
    525528                bfs_queue.push(w);
    526529                Node first=level_list[l];
    527                 if ( G.valid(first) ) left.set(first,w);
     530                if ( g->valid(first) ) left.set(first,w);
    528531                right.set(w,first);
    529532                level_list[l]=w;
    … …  
    533536           
    534537            OutEdgeIt f;
    535             for(G.first(f,v); G.valid(f); G.next(f)) {
     538            for(g->first(f,v); g->valid(f); g->next(f)) {
    536539              if ( 0 == (*flow)[f] ) continue;
    537               Node w=G.head(f);
     540              Node w=g->head(f);
    538541              if ( level[w] == n && w != s ) {
    539542                bfs_queue.push(w);
    540543                Node first=level_list[l];
    541                 if ( G.valid(first) ) left.set(first,w);
     544                if ( g->valid(first) ) left.set(first,w);
    542545                right.set(w,first);
    543546                level_list[l]=w;
    … …  
    550553          //the starting flow
    551554          OutEdgeIt e;
    552           for(G.first(e,s); G.valid(e); G.next(e))
     555          for(g->first(e,s); g->valid(e); g->next(e))
    553556            {
    554557              T rem=(*capacity)[e]-(*flow)[e];
    555558              if ( rem == 0 ) continue;
    556               Node w=G.head(e);
     559              Node w=g->head(e);
    557560              if ( level[w] < n ) {       
    558561                if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
    … …  
    563566         
    564567          InEdgeIt f;
    565           for(G.first(f,s); G.valid(f); G.next(f))
     568          for(g->first(f,s); g->valid(f); g->next(f))
    566569            {
    567570              if ( (*flow)[f] == 0 ) continue;
    568               Node w=G.tail(f);
     571              Node w=g->tail(f);
    569572              if ( level[w] < n ) {       
    570573                if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
    … …  
    590593     
    591594      //unlacing starts
    592       if ( G.valid(right_n) ) {
    593         if ( G.valid(left_n) ) {
     595      if ( g->valid(right_n) ) {
     596        if ( g->valid(left_n) ) {
    594597          right.set(left_n, right_n);
    595598          left.set(right_n, left_n);
    … …  
    599602        }
    600603      } else {
    601         if ( G.valid(left_n) ) {
     604        if ( g->valid(left_n) ) {
    602605          right.set(left_n, INVALID);
    603606        } else {
    … …  
    607610      //unlacing ends
    608611               
    609       if ( !G.valid(level_list[lev]) ) {
     612      if ( !g->valid(level_list[lev]) ) {
    610613             
    611614        //gapping starts
    612615        for (int i=lev; i!=k ; ) {
    613616          Node v=level_list[++i];
    614           while ( G.valid(v) ) {
     617          while ( g->valid(v) ) {
    615618            level.set(v,n);
    616619            v=right[v];
    … …  
    638641          if ( k < newlevel ) ++k;      //now k=newlevel
    639642          Node first=level_list[newlevel];
    640           if ( G.valid(first) ) left.set(first,w);
     643          if ( g->valid(first) ) left.set(first,w);
    641644          right.set(w,first);
    642645          left.set(w,INVALID);
Note: See TracChangeset for help on using the changeset viewer.