Function minflow

plugins/askrene/child/mcf.c:948–1055

TODO(eduardo): choose some default values for the minflow parameters eduardo: I think it should be clear that this module deals with linear * flows, ie. base fees are not considered. Hence a flow along a path is * described with a sequence of directed channels and one amount. * In the `pay_flow` module there are dedicated routes to compute the actual * amount to be forward on each hop. * * T

// TODO(eduardo): we should LOG_DBG the process of finding the MCF while
// adjusting the frugality factor.
static struct flow **minflow(const tal_t *ctx,
			     const struct route_query *rq,
			     const struct gossmap_node *source,
			     const struct gossmap_node *target,
			     struct amount_msat amount,
			     u32 mu,
			     double delay_feefactor)
{
	struct flow **flow_paths;
	/* We allocate everything off this, and free it at the end,
	 * as we can be called multiple times without cleaning tmpctx! */
	tal_t *working_ctx = tal(NULL, char);
	struct pay_parameters *params = tal(working_ctx, struct pay_parameters);

	params->rq = rq;
	params->source = source;
	params->target = target;
	params->amount = amount;
	/* -> We reduce the granularity of the flow by limiting the subdivision
	 * of the payment amount into 1000 units of flow. That reduces the
	 * computational burden for algorithms that depend on it, eg. "capacity
	 * scaling" and "successive shortest path".
	 * -> Using Ceil operation instead of Floor so that
	 *      accuracy x 1000 >= amount
	 * */
	params->accuracy =
	    amount_msat_max(AMOUNT_MSAT(1), amount_msat_div_ceil(amount, 1000));

	// template the channel partition into linear arcs
	params->cap_fraction[0]=0;
	params->cost_fraction[0]=0;
	for(size_t i =1;i<CHANNEL_PARTS;++i)
	{
		params->cap_fraction[i]=CHANNEL_PIVOTS[i]-CHANNEL_PIVOTS[i-1];
		params->cost_fraction[i]=
			log((1-CHANNEL_PIVOTS[i-1])/(1-CHANNEL_PIVOTS[i]))
			/params->cap_fraction[i];
	}

	params->delay_feefactor = delay_feefactor;
	params->base_fee_penalty = base_fee_penalty_estimate(amount);

	// build the uncertainty network with linearization and residual arcs
	struct graph *graph;
	double *arc_prob_cost;
	s64 *arc_fee_cost;
	s64 *arc_capacity;
	init_linear_network(working_ctx, params, &graph, &arc_prob_cost,
			    &arc_fee_cost, &arc_capacity);

	const size_t max_num_arcs = graph_max_num_arcs(graph);
	const size_t max_num_nodes = graph_max_num_nodes(graph);
	s64 *arc_cost;
	s64 *node_potential;
	s64 *node_excess;
	arc_cost = tal_arrz(working_ctx, s64, max_num_arcs);
	node_potential = tal_arrz(working_ctx, s64, max_num_nodes);
	node_excess = tal_arrz(working_ctx, s64, max_num_nodes);