COIN-OR::LEMON - Graph Library

Changeset 901:30d5f950aa5f in lemon-1.2


Ignore:
Timestamp:
02/25/11 21:37:47 (8 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
902:79fab87ee483, 903:8ae2627aba1a
Phase:
public
Message:

Fix wrong initialization in Preflow (#414)

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/preflow.h

    r894 r901  
    526526          _flow->set(e, (*_capacity)[e]);
    527527          (*_excess)[u] += rem;
    528           if (u != _target && !_level->active(u)) {
    529             _level->activate(u);
    530           }
    531528        }
    532529      }
     
    538535          _flow->set(e, 0);
    539536          (*_excess)[v] += rem;
    540           if (v != _target && !_level->active(v)) {
    541             _level->activate(v);
    542           }
    543         }
    544       }
     537        }
     538      }
     539      for (NodeIt n(_graph); n != INVALID; ++n)
     540        if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n]))
     541          _level->activate(n);
     542         
    545543      return true;
    546544    }
  • test/preflow_test.cc

    r585 r901  
    152152}
    153153
     154void initFlowTest()
     155{
     156  DIGRAPH_TYPEDEFS(SmartDigraph);
     157 
     158  SmartDigraph g;
     159  SmartDigraph::ArcMap<int> cap(g),iflow(g);
     160  Node s=g.addNode(); Node t=g.addNode();
     161  Node n1=g.addNode(); Node n2=g.addNode();
     162  Arc a;
     163  a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
     164  a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
     165  a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
     166
     167  Preflow<SmartDigraph> pre(g,cap,s,t);
     168  pre.init(iflow);
     169  pre.startFirstPhase();
     170  check(pre.flowValue() == 10, "The incorrect max flow value.");
     171  check(pre.minCut(s), "Wrong min cut (Node s).");
     172  check(pre.minCut(n1), "Wrong min cut (Node n1).");
     173  check(!pre.minCut(n2), "Wrong min cut (Node n2).");
     174  check(!pre.minCut(t), "Wrong min cut (Node t).");
     175}
     176
     177
    154178int main() {
    155179
     
    242266        "The max flow value or the three min cut values are incorrect.");
    243267
     268  initFlowTest();
     269 
    244270  return 0;
    245271}
Note: See TracChangeset for help on using the changeset viewer.