Problem: find a potential and capacity redistribution such that: * excess[all nodes] = 0 * capacity[all arcs] >= 0 * cost/potential [i,j] < 0 implies capacity[i,j] = 0 * * Q. Is this a feasible solution? * * A. If we use flow conserving function sendflow, then * if for all nodes excess[i] = 0 and capacity[i,j] >= 0 for all arcs * then we have reached a feasible flow. * * Q. Is this flow
| 492 | * to find the MCF every time. |
| 493 | * */ |
| 494 | bool mcf_refinement(const tal_t *ctx, |
| 495 | const struct graph *graph, |
| 496 | s64 *excess, |
| 497 | s64 *capacity, |
| 498 | const s64 *cost, |
| 499 | s64 *potential) |
| 500 | { |
| 501 | bool solved = false; |
| 502 | const tal_t *this_ctx = tal(ctx, tal_t); |
| 503 | |
| 504 | assert(graph); |
| 505 | assert(excess); |
| 506 | assert(capacity); |
| 507 | assert(cost); |
| 508 | assert(potential); |
| 509 | |
| 510 | const size_t max_num_arcs = graph_max_num_arcs(graph); |
| 511 | const size_t max_num_nodes = graph_max_num_nodes(graph); |
| 512 | |
| 513 | assert(tal_count(excess) == max_num_nodes); |
| 514 | assert(tal_count(capacity) == max_num_arcs); |
| 515 | assert(tal_count(cost) == max_num_arcs); |
| 516 | assert(tal_count(potential) == max_num_nodes); |
| 517 | |
| 518 | s64 total_excess = 0; |
| 519 | for (u32 i = 0; i < max_num_nodes; i++) |
| 520 | total_excess += excess[i]; |
| 521 | |
| 522 | if (total_excess) |
| 523 | /* there is no way to satisfy the constraints if supply does not |
| 524 | * match demand */ |
| 525 | goto finish; |
| 526 | |
| 527 | /* Enforce the complementary slackness condition, rolls back |
| 528 | * constraints. */ |
| 529 | for (u32 arc_id = 0; arc_id < max_num_arcs; arc_id++) { |
| 530 | struct arc arc = {.idx = arc_id}; |
| 531 | if(!arc_enabled(graph, arc)) |
| 532 | continue; |
| 533 | const s64 r = capacity[arc.idx]; |
| 534 | if (reduced_cost(graph, arc, cost, potential) < 0 && r > 0) { |
| 535 | /* This arc's reduced cost is negative and non |
| 536 | * saturated. */ |
| 537 | sendflow(graph, arc, r, capacity, excess); |
| 538 | } |
| 539 | } |
| 540 | |
| 541 | struct arc *prev = tal_arr(this_ctx, struct arc, max_num_nodes); |
| 542 | s64 *distance = tal_arrz(this_ctx, s64, max_num_nodes); |
| 543 | if (!prev || !distance) |
| 544 | goto finish; |
| 545 | |
| 546 | /* Now build back constraints again keeping the complementary slackness |
| 547 | * condition. */ |
| 548 | for (u32 node_id = 0; node_id < max_num_nodes; node_id++) { |
| 549 | struct node src = {.idx = node_id}; |
| 550 | |
| 551 | /* is this node a source */ |
no test coverage detected