TODO(eduardo): unit test this Starting from a feasible flow (satisfies the balance and capacity * constraints), find a solution that minimizes the network->cost function. * * TODO(eduardo) The MCF must be called several times until we get a good * compromise between fees and probabilities. Instead of re-computing the MCF at * each step, we might use the previous flow result, which is not opti
| 1110 | * current iteration but I might be not too far from the truth. |
| 1111 | * It comes to mind to use cycle cancelling. */ |
| 1112 | static bool optimize_mcf(const tal_t *ctx, struct dijkstra *dijkstra, |
| 1113 | const struct linear_network *linear_network, |
| 1114 | struct residual_network *residual_network, |
| 1115 | const u32 source, const u32 target, const s64 amount, |
| 1116 | char **fail) |
| 1117 | { |
| 1118 | assert(amount>=0); |
| 1119 | tal_t *this_ctx = tal(ctx,tal_t); |
| 1120 | char *errmsg; |
| 1121 | |
| 1122 | zero_flow(linear_network,residual_network); |
| 1123 | struct arc *prev = tal_arr(this_ctx,struct arc,linear_network->max_num_nodes); |
| 1124 | |
| 1125 | const s64 *const distance = dijkstra_distance_data(dijkstra); |
| 1126 | |
| 1127 | s64 remaining_amount = amount; |
| 1128 | |
| 1129 | while(remaining_amount>0) |
| 1130 | { |
| 1131 | if (!find_optimal_path(this_ctx, dijkstra, linear_network, |
| 1132 | residual_network, source, target, prev, |
| 1133 | &errmsg)) { |
| 1134 | if (fail) |
| 1135 | *fail = |
| 1136 | tal_fmt(ctx, "find_optimal_path failed: %s", |
| 1137 | errmsg); |
| 1138 | goto function_fail; |
| 1139 | } |
| 1140 | |
| 1141 | // traverse the path and see how much flow we can send |
| 1142 | s64 delta = get_augmenting_flow(linear_network,residual_network,source,target,prev); |
| 1143 | |
| 1144 | // commit that flow to the path |
| 1145 | delta = MIN(remaining_amount,delta); |
| 1146 | assert(delta>0 && delta<=remaining_amount); |
| 1147 | |
| 1148 | augment_flow(linear_network,residual_network,source,target,prev,delta); |
| 1149 | remaining_amount -= delta; |
| 1150 | |
| 1151 | // update potentials |
| 1152 | for(u32 n=0;n<linear_network->max_num_nodes;++n) |
| 1153 | { |
| 1154 | // see page 323 of Ahuja-Magnanti-Orlin |
| 1155 | residual_network->potential[n] -= MIN(distance[target],distance[n]); |
| 1156 | |
| 1157 | /* Notice: |
| 1158 | * if node i is permanently labeled we have |
| 1159 | * d_i<=d_t |
| 1160 | * which implies |
| 1161 | * MIN(d_i,d_t) = d_i |
| 1162 | * if node i is temporarily labeled we have |
| 1163 | * d_i>=d_t |
| 1164 | * which implies |
| 1165 | * MIN(d_i,d_t) = d_t |
| 1166 | * */ |
| 1167 | } |
| 1168 | } |
| 1169 | tal_free(this_ctx); |
no test coverage detected