451 void init() |
451 void init() |
452 { |
452 { |
453 createStructures(); |
453 createStructures(); |
454 |
454 |
455 for(NodeIt n(_g);n!=INVALID;++n) { |
455 for(NodeIt n(_g);n!=INVALID;++n) { |
456 _excess->set(n, (*_delta)[n]); |
456 (*_excess)[n] = (*_delta)[n]; |
457 } |
457 } |
458 |
458 |
459 for (ArcIt e(_g);e!=INVALID;++e) { |
459 for (ArcIt e(_g);e!=INVALID;++e) { |
460 _flow->set(e, (*_lo)[e]); |
460 _flow->set(e, (*_lo)[e]); |
461 _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]); |
461 (*_excess)[_g.target(e)] += (*_flow)[e]; |
462 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]); |
462 (*_excess)[_g.source(e)] -= (*_flow)[e]; |
463 } |
463 } |
464 |
464 |
465 // global relabeling tested, but in general case it provides |
465 // global relabeling tested, but in general case it provides |
466 // worse performance for random digraphs |
466 // worse performance for random digraphs |
467 _level->initStart(); |
467 _level->initStart(); |
480 void greedyInit() |
480 void greedyInit() |
481 { |
481 { |
482 createStructures(); |
482 createStructures(); |
483 |
483 |
484 for(NodeIt n(_g);n!=INVALID;++n) { |
484 for(NodeIt n(_g);n!=INVALID;++n) { |
485 _excess->set(n, (*_delta)[n]); |
485 (*_excess)[n] = (*_delta)[n]; |
486 } |
486 } |
487 |
487 |
488 for (ArcIt e(_g);e!=INVALID;++e) { |
488 for (ArcIt e(_g);e!=INVALID;++e) { |
489 if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) { |
489 if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) { |
490 _flow->set(e, (*_up)[e]); |
490 _flow->set(e, (*_up)[e]); |
491 _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]); |
491 (*_excess)[_g.target(e)] += (*_up)[e]; |
492 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]); |
492 (*_excess)[_g.source(e)] -= (*_up)[e]; |
493 } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) { |
493 } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) { |
494 _flow->set(e, (*_lo)[e]); |
494 _flow->set(e, (*_lo)[e]); |
495 _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]); |
495 (*_excess)[_g.target(e)] += (*_lo)[e]; |
496 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]); |
496 (*_excess)[_g.source(e)] -= (*_lo)[e]; |
497 } else { |
497 } else { |
498 Value fc = -(*_excess)[_g.target(e)]; |
498 Value fc = -(*_excess)[_g.target(e)]; |
499 _flow->set(e, fc); |
499 _flow->set(e, fc); |
500 _excess->set(_g.target(e), 0); |
500 (*_excess)[_g.target(e)] = 0; |
501 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc); |
501 (*_excess)[_g.source(e)] -= fc; |
502 } |
502 } |
503 } |
503 } |
504 |
504 |
505 _level->initStart(); |
505 _level->initStart(); |
506 for(NodeIt n(_g);n!=INVALID;++n) |
506 for(NodeIt n(_g);n!=INVALID;++n) |
535 Value fc=(*_up)[e]-(*_flow)[e]; |
535 Value fc=(*_up)[e]-(*_flow)[e]; |
536 if(!_tol.positive(fc)) continue; |
536 if(!_tol.positive(fc)) continue; |
537 if((*_level)[v]<actlevel) { |
537 if((*_level)[v]<actlevel) { |
538 if(!_tol.less(fc, exc)) { |
538 if(!_tol.less(fc, exc)) { |
539 _flow->set(e, (*_flow)[e] + exc); |
539 _flow->set(e, (*_flow)[e] + exc); |
540 _excess->set(v, (*_excess)[v] + exc); |
540 (*_excess)[v] += exc; |
541 if(!_level->active(v) && _tol.positive((*_excess)[v])) |
541 if(!_level->active(v) && _tol.positive((*_excess)[v])) |
542 _level->activate(v); |
542 _level->activate(v); |
543 _excess->set(act,0); |
543 (*_excess)[act] = 0; |
544 _level->deactivate(act); |
544 _level->deactivate(act); |
545 goto next_l; |
545 goto next_l; |
546 } |
546 } |
547 else { |
547 else { |
548 _flow->set(e, (*_up)[e]); |
548 _flow->set(e, (*_up)[e]); |
549 _excess->set(v, (*_excess)[v] + fc); |
549 (*_excess)[v] += fc; |
550 if(!_level->active(v) && _tol.positive((*_excess)[v])) |
550 if(!_level->active(v) && _tol.positive((*_excess)[v])) |
551 _level->activate(v); |
551 _level->activate(v); |
552 exc-=fc; |
552 exc-=fc; |
553 } |
553 } |
554 } |
554 } |
559 Value fc=(*_flow)[e]-(*_lo)[e]; |
559 Value fc=(*_flow)[e]-(*_lo)[e]; |
560 if(!_tol.positive(fc)) continue; |
560 if(!_tol.positive(fc)) continue; |
561 if((*_level)[v]<actlevel) { |
561 if((*_level)[v]<actlevel) { |
562 if(!_tol.less(fc, exc)) { |
562 if(!_tol.less(fc, exc)) { |
563 _flow->set(e, (*_flow)[e] - exc); |
563 _flow->set(e, (*_flow)[e] - exc); |
564 _excess->set(v, (*_excess)[v] + exc); |
564 (*_excess)[v] += exc; |
565 if(!_level->active(v) && _tol.positive((*_excess)[v])) |
565 if(!_level->active(v) && _tol.positive((*_excess)[v])) |
566 _level->activate(v); |
566 _level->activate(v); |
567 _excess->set(act,0); |
567 (*_excess)[act] = 0; |
568 _level->deactivate(act); |
568 _level->deactivate(act); |
569 goto next_l; |
569 goto next_l; |
570 } |
570 } |
571 else { |
571 else { |
572 _flow->set(e, (*_lo)[e]); |
572 _flow->set(e, (*_lo)[e]); |
573 _excess->set(v, (*_excess)[v] + fc); |
573 (*_excess)[v] += fc; |
574 if(!_level->active(v) && _tol.positive((*_excess)[v])) |
574 if(!_level->active(v) && _tol.positive((*_excess)[v])) |
575 _level->activate(v); |
575 _level->activate(v); |
576 exc-=fc; |
576 exc-=fc; |
577 } |
577 } |
578 } |
578 } |
579 else if((*_level)[v]<mlevel) mlevel=(*_level)[v]; |
579 else if((*_level)[v]<mlevel) mlevel=(*_level)[v]; |
580 } |
580 } |
581 |
581 |
582 _excess->set(act, exc); |
582 (*_excess)[act] = exc; |
583 if(!_tol.positive(exc)) _level->deactivate(act); |
583 if(!_tol.positive(exc)) _level->deactivate(act); |
584 else if(mlevel==_node_num) { |
584 else if(mlevel==_node_num) { |
585 _level->liftHighestActiveToTop(); |
585 _level->liftHighestActiveToTop(); |
586 _el = _node_num; |
586 _el = _node_num; |
587 return false; |
587 return false; |