* API for min cost single path. * @ctx: context to allocate returned flows from * @rq: the route_query we're processing (for logging) * @source: the source to start from * @target: the target to pay * @amount: the amount we want to reach @target * @mu: 0 = corresponds to only probabilities, 100 corresponds to only fee. * @delay_feefactor: convert 1 block delay into msat. * * @delay_feefac
| 1161 | * Returns an array with one flow which deliver amount to target, or NULL. |
| 1162 | */ |
| 1163 | static struct flow **single_path_flow(const tal_t *ctx, const struct route_query *rq, |
| 1164 | const struct gossmap_node *source, |
| 1165 | const struct gossmap_node *target, |
| 1166 | struct amount_msat amount, u32 mu, |
| 1167 | double delay_feefactor) |
| 1168 | { |
| 1169 | struct flow **flow_paths; |
| 1170 | /* We allocate everything off this, and free it at the end, |
| 1171 | * as we can be called multiple times without cleaning tmpctx! */ |
| 1172 | tal_t *working_ctx = tal(NULL, char); |
| 1173 | struct pay_parameters *params = tal(working_ctx, struct pay_parameters); |
| 1174 | |
| 1175 | params->rq = rq; |
| 1176 | params->source = source; |
| 1177 | params->target = target; |
| 1178 | params->amount = amount; |
| 1179 | /* for the single-path solver the accuracy does not detriment |
| 1180 | * performance */ |
| 1181 | params->accuracy = amount; |
| 1182 | params->delay_feefactor = delay_feefactor; |
| 1183 | params->base_fee_penalty = base_fee_penalty_estimate(amount); |
| 1184 | |
| 1185 | struct graph *graph; |
| 1186 | double *arc_prob_cost; |
| 1187 | s64 *arc_fee_cost; |
| 1188 | s64 *arc_capacity; |
| 1189 | |
| 1190 | init_linear_network_single_path(working_ctx, params, &graph, |
| 1191 | &arc_prob_cost, &arc_fee_cost, |
| 1192 | &arc_capacity); |
| 1193 | |
| 1194 | const struct node dst = {.idx = gossmap_node_idx(rq->gossmap, target)}; |
| 1195 | const struct node src = {.idx = gossmap_node_idx(rq->gossmap, source)}; |
| 1196 | |
| 1197 | const size_t max_num_nodes = graph_max_num_nodes(graph); |
| 1198 | const size_t max_num_arcs = graph_max_num_arcs(graph); |
| 1199 | |
| 1200 | s64 *potential = tal_arrz(working_ctx, s64, max_num_nodes); |
| 1201 | s64 *distance = tal_arrz(working_ctx, s64, max_num_nodes); |
| 1202 | s64 *arc_cost = tal_arrz(working_ctx, s64, max_num_arcs); |
| 1203 | struct arc *prev = tal_arrz(working_ctx, struct arc, max_num_nodes); |
| 1204 | |
| 1205 | combine_cost_function(working_ctx, graph, arc_prob_cost, arc_fee_cost, |
| 1206 | rq->biases, mu, arc_cost); |
| 1207 | |
| 1208 | /* We solve a linear cost flow problem. */ |
| 1209 | if (!dijkstra_path(working_ctx, graph, src, dst, |
| 1210 | /* prune = */ true, arc_capacity, |
| 1211 | /*threshold = */ 1, arc_cost, potential, prev, |
| 1212 | distance)) { |
| 1213 | /* This might fail if we are unable to find a suitable route, it |
| 1214 | * doesn't mean the plugin is broken, that's why we LOG_INFORM. */ |
| 1215 | child_log(tmpctx, LOG_INFORM, |
| 1216 | "%s: could not find a feasible single path", __func__); |
| 1217 | goto fail; |
| 1218 | } |
| 1219 | const u64 pay_amount = |
| 1220 | amount_msat_ratio_ceil(params->amount, params->accuracy); |
no test coverage detected