Function get_flow_paths

plugins/askrene/child/mcf.c:817–894

Given a flow in the residual network, build a set of payment flows in the * gossmap that corresponds to this flow. */

/* Given a flow in the residual network, build a set of payment flows in the
 * gossmap that corresponds to this flow. */
static struct flow **
get_flow_paths(const tal_t *ctx,
	       const tal_t *working_ctx,
	       const struct pay_parameters *params,
	       const struct graph *graph,
	       const s64 *arc_residual_capacity)
{
	struct flow **flows = tal_arr(ctx,struct flow*,0);

	const size_t max_num_chans = gossmap_max_chan_idx(params->rq->gossmap);
	struct chan_flow *chan_flow = tal_arrz(working_ctx,struct chan_flow,max_num_chans);

	const size_t max_num_nodes = gossmap_max_node_idx(params->rq->gossmap);
	s64 *balance = tal_arrz(working_ctx,s64,max_num_nodes);

	const struct gossmap_chan **prev_chan
		= tal_arr(working_ctx,const struct gossmap_chan *,max_num_nodes);


	int *prev_dir = tal_arr(working_ctx,int,max_num_nodes);
	u32 *prev_idx = tal_arr(working_ctx, u32, max_num_nodes);

	for (u32 node_idx = 0; node_idx < max_num_nodes; node_idx++)
		prev_idx[node_idx] = INVALID_INDEX;

	// Convert the arc based residual network flow into a flow in the
	// directed channel network.
	// Compute balance on the nodes.
	for (struct node n = {.idx = 0}; n.idx < max_num_nodes; n.idx++) {
		for(struct arc arc = node_adjacency_begin(graph,n);
		        !node_adjacency_end(arc);
			arc = node_adjacency_next(graph,arc))
		{
			if(arc_is_dual(graph, arc))
				continue;
			struct node m = arc_head(graph,arc);
			s64 flow = get_arc_flow(arc_residual_capacity,
						graph, arc);
			u32 chanidx;
			int chandir;

			balance[n.idx] -= flow;
			balance[m.idx] += flow;

			arc_to_parts(arc, &chanidx, &chandir, NULL, NULL);
			chan_flow[chanidx].half[chandir] +=flow;
		}
	}

	// Select all nodes with negative balance and find a flow that reaches a
	// positive balance node.
	for (struct node source = {.idx = 0}; source.idx < max_num_nodes;
	     source.idx++) {
		// this node has negative balance, flows leaves from here
		while (balance[source.idx] < 0) {
			prev_chan[source.idx] = NULL;
			struct node sink = find_path_or_cycle(
			    working_ctx, params->rq, chan_flow, source,