| 259 | } |
| 260 | |
| 261 | bool simple_feasibleflow(const tal_t *ctx, |
| 262 | const struct graph *graph, |
| 263 | const struct node source, |
| 264 | const struct node destination, |
| 265 | s64 *capacity, |
| 266 | s64 amount) |
| 267 | { |
| 268 | const tal_t *this_ctx = tal(ctx, tal_t); |
| 269 | assert(graph); |
| 270 | const size_t max_num_arcs = graph_max_num_arcs(graph); |
| 271 | const size_t max_num_nodes = graph_max_num_nodes(graph); |
| 272 | |
| 273 | /* check preconditions */ |
| 274 | assert(amount > 0); |
| 275 | assert(source.idx < max_num_nodes); |
| 276 | assert(destination.idx < max_num_nodes); |
| 277 | assert(capacity); |
| 278 | assert(tal_count(capacity) == max_num_arcs); |
| 279 | |
| 280 | /* path information |
| 281 | * prev: is the id of the arc that lead to the node. */ |
| 282 | struct arc *prev = tal_arr(this_ctx, struct arc, max_num_nodes); |
| 283 | if (!prev) |
| 284 | goto finish; |
| 285 | |
| 286 | while (amount > 0) { |
| 287 | /* find a path from source to target */ |
| 288 | if (!BFS_path(this_ctx, graph, source, destination, capacity, 1, |
| 289 | prev)) |
| 290 | goto finish; |
| 291 | |
| 292 | /* traverse the path and see how much flow we can send */ |
| 293 | s64 delta = get_augmenting_flow(graph, source, destination, |
| 294 | capacity, prev); |
| 295 | |
| 296 | /* commit that flow to the path */ |
| 297 | delta = MIN(amount, delta); |
| 298 | assert(delta > 0 && delta <= amount); |
| 299 | |
| 300 | augment_flow(graph, source, destination, prev, NULL, capacity, |
| 301 | delta); |
| 302 | amount -= delta; |
| 303 | } |
| 304 | finish: |
| 305 | tal_free(this_ctx); |
| 306 | return amount == 0; |
| 307 | } |
| 308 | |
| 309 | s64 node_balance(const struct graph *graph, |
| 310 | const struct node node, |