| 610 | } |
| 611 | |
| 612 | bool simple_mcf(const tal_t *ctx, const struct graph *graph, |
| 613 | const struct node source, const struct node destination, |
| 614 | s64 *capacity, s64 amount, const s64 *cost) |
| 615 | { |
| 616 | const tal_t *this_ctx = tal(ctx, tal_t); |
| 617 | |
| 618 | assert(graph); |
| 619 | const size_t max_num_arcs = graph_max_num_arcs(graph); |
| 620 | const size_t max_num_nodes = graph_max_num_nodes(graph); |
| 621 | |
| 622 | /* check preconditions */ |
| 623 | assert(amount > 0); |
| 624 | assert(source.idx < max_num_nodes); |
| 625 | assert(destination.idx < max_num_nodes); |
| 626 | assert(capacity); |
| 627 | assert(cost); |
| 628 | assert(tal_count(capacity) == max_num_arcs); |
| 629 | assert(tal_count(cost) == max_num_arcs); |
| 630 | |
| 631 | s64 *potential = tal_arrz(this_ctx, s64, max_num_nodes); |
| 632 | s64 *excess = tal_arrz(this_ctx, s64, max_num_nodes); |
| 633 | |
| 634 | excess[source.idx] = amount; |
| 635 | excess[destination.idx] = -amount; |
| 636 | |
| 637 | if (!mcf_refinement(this_ctx, graph, excess, capacity, cost, potential)) |
| 638 | goto fail; |
| 639 | |
| 640 | tal_free(this_ctx); |
| 641 | return true; |
| 642 | |
| 643 | fail: |
| 644 | tal_free(this_ctx); |
| 645 | return false; |
| 646 | } |
| 647 | |
| 648 | s64 flow_cost(const struct graph *graph, const s64 *capacity, const s64 *cost) |
| 649 | { |