| 470 | |
| 471 | template <typename captype, typename tcaptype, typename flowtype> |
| 472 | flowtype Graph<captype,tcaptype,flowtype>::maxflow(bool reuse_trees, Block<node_id>* _changed_list) |
| 473 | { |
| 474 | node *i, *j, *current_node = NULL; |
| 475 | arc *a; |
| 476 | nodeptr *np, *np_next; |
| 477 | |
| 478 | if (!nodeptr_block) |
| 479 | { |
| 480 | nodeptr_block = new DBlock<nodeptr>(NODEPTR_BLOCK_SIZE, error_function); |
| 481 | } |
| 482 | |
| 483 | changed_list = _changed_list; |
| 484 | if (maxflow_iteration == 0 && reuse_trees) { if (error_function) (*error_function)("reuse_trees cannot be used in the first call to maxflow()!"); exit(1); } |
| 485 | if (changed_list && !reuse_trees) { if (error_function) (*error_function)("changed_list cannot be used without reuse_trees!"); exit(1); } |
| 486 | |
| 487 | if (reuse_trees) maxflow_reuse_trees_init(); |
| 488 | else maxflow_init(); |
| 489 | |
| 490 | // main loop |
| 491 | while ( 1 ) |
| 492 | { |
| 493 | // test_consistency(current_node); |
| 494 | |
| 495 | if ((i=current_node)) |
| 496 | { |
| 497 | i -> next = NULL; /* remove active flag */ |
| 498 | if (!i->parent) i = NULL; |
| 499 | } |
| 500 | if (!i) |
| 501 | { |
| 502 | if (!(i = next_active())) break; |
| 503 | } |
| 504 | |
| 505 | /* growth */ |
| 506 | if (!i->is_sink) |
| 507 | { |
| 508 | /* grow source tree */ |
| 509 | for (a=i->first; a; a=a->next) |
| 510 | if (a->r_cap) |
| 511 | { |
| 512 | j = a -> head; |
| 513 | if (!j->parent) |
| 514 | { |
| 515 | j -> is_sink = 0; |
| 516 | j -> parent = a -> sister; |
| 517 | j -> TS = i -> TS; |
| 518 | j -> DIST = i -> DIST + 1; |
| 519 | set_active(j); |
| 520 | add_to_changed_list(j); |
| 521 | } |
| 522 | else if (j->is_sink) break; |
| 523 | else if (j->TS <= i->TS && |
| 524 | j->DIST > i->DIST) |
| 525 | { |
| 526 | /* heuristic - trying to make the distance from j to the source shorter */ |
| 527 | j -> parent = a -> sister; |
| 528 | j -> TS = i -> TS; |
| 529 | j -> DIST = i -> DIST + 1; |
no test coverage detected