Function reduce_num_flows

plugins/askrene/child/refine.c:691–731

}

const char *reduce_num_flows(const tal_t *ctx,
			     const struct route_query *rq,
			     struct flow ***flows,
			     struct amount_msat deliver,
			     size_t num_parts)
{
	/* Keep the largest flows (not as I originally implemented, the largest
	 * capacity flows).  Here's Lagrang3's analysis:
	 *
	 * I think it is better to keep the largest-deliver flows.  If we only
	 * go for the highest capacity we may throw away the low cost benefits
	 * of the MCF.

	 * Hypothetical scenario: MCF finds 3 flows but maxparts=2,
	 * flow 1: deliver=10, cost=0, capacity=0
	 * flow 2: deliver=7, cost=1, capacity=5
	 * flow 3: deliver=1, cost=10, capacity=100
	 *
	 * It is better to keep flows 1 and 2 by accomodating 1 more unit of
	 * flow in flow2 at 1 value expense (per flow), than to keep flows 2 and
	 * 3 by accomodating 5 more units of flow in flow2 at cost 1 and 5 in
	 * flow3 at cost 100.
	 *
	 * The trade-off is: if we prioritize the delivery value already
	 * computed by MCF then we find better solutions, but we might fail to
	 * find feasible solutions sometimes. If we prioritize capacity then we
	 * generally find bad solutions though we find feasibility more often
	 * than the alternative.
	 */
	size_t orig_num_flows = tal_count(*flows);
	asort(*flows, orig_num_flows, revcmp_flows, NULL);
	while (tal_count(*flows) > num_parts)
		del_flow_from_arr(flows, tal_count(*flows) - 1);

	if (!increase_flows(rq, *flows, deliver, -1.0))
		return child_log(ctx, LOG_INFORM,
				 "Failed to reduce %zu flows down to maxparts (%zu)",
				 orig_num_flows, num_parts);

	return NULL;
}