401 _flow->set(e, (*_lo)[e]); |
401 _flow->set(e, (*_lo)[e]); |
402 _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]); |
402 _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]); |
403 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]); |
403 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]); |
404 } |
404 } |
405 |
405 |
406 typename Graph::template NodeMap<bool> reached(_g, false); |
|
407 |
|
408 |
|
409 // global relabeling tested, but in general case it provides |
406 // global relabeling tested, but in general case it provides |
410 // worse performance for random graphs |
407 // worse performance for random graphs |
411 _level->initStart(); |
408 _level->initStart(); |
412 for(NodeIt n(_g);n!=INVALID;++n) |
409 for(NodeIt n(_g);n!=INVALID;++n) |
413 _level->initAddItem(n); |
410 _level->initAddItem(n); |
434 _flow->set(e, (*_up)[e]); |
431 _flow->set(e, (*_up)[e]); |
435 _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]); |
432 _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]); |
436 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]); |
433 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]); |
437 } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) { |
434 } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) { |
438 _flow->set(e, (*_lo)[e]); |
435 _flow->set(e, (*_lo)[e]); |
439 _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]); |
436 _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]); |
440 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]); |
437 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]); |
441 } else { |
438 } else { |
442 Value fc = -(*_excess)[_g.target(e)]; |
439 Value fc = -(*_excess)[_g.target(e)]; |
443 _flow->set(e, fc); |
440 _flow->set(e, fc); |
444 _excess->set(_g.target(e), 0); |
441 _excess->set(_g.target(e), 0); |
445 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc); |
442 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc); |
469 Node last_activated=INVALID; |
466 Node last_activated=INVALID; |
470 while((act=_level->highestActive())!=INVALID) { |
467 while((act=_level->highestActive())!=INVALID) { |
471 int actlevel=(*_level)[act]; |
468 int actlevel=(*_level)[act]; |
472 int mlevel=_node_num; |
469 int mlevel=_node_num; |
473 Value exc=(*_excess)[act]; |
470 Value exc=(*_excess)[act]; |
474 |
471 |
475 for(OutEdgeIt e(_g,act);e!=INVALID; ++e) { |
472 for(OutEdgeIt e(_g,act);e!=INVALID; ++e) { |
476 Node v = _g.target(e); |
473 Node v = _g.target(e); |
477 Value fc=(*_up)[e]-(*_flow)[e]; |
474 Value fc=(*_up)[e]-(*_flow)[e]; |
478 if(!_tol.positive(fc)) continue; |
475 if(!_tol.positive(fc)) continue; |
479 if((*_level)[v]<actlevel) { |
476 if((*_level)[v]<actlevel) { |