Function find_admissible_path

plugins/renepay/mcf.c:818–878

TODO(eduardo): unit test this Finds an admissible path from source to target, traversing arcs in the * residual network with capacity greater than 0. * The path is encoded into prev, which contains the idx of the arcs that are * traversed. */

 * The path is encoded into prev, which contains the idx of the arcs that are
 * traversed. */
static bool
find_admissible_path(const tal_t *ctx,
		     const struct linear_network *linear_network,
		     const struct residual_network *residual_network,
		     const u32 source, const u32 target, struct arc *prev)
{
	tal_t *this_ctx = tal(ctx,tal_t);

	bool target_found = false;

	for(size_t i=0;i<tal_count(prev);++i)
		prev[i].idx=INVALID_INDEX;

	// The graph is dense, and the farthest node is just a few hops away,
	// hence let's BFS search.
	LQUEUE(struct queue_data,ql) myqueue = LQUEUE_INIT;
	struct queue_data *qdata;

	qdata = tal(this_ctx,struct queue_data);
	qdata->idx = source;
	lqueue_enqueue(&myqueue,qdata);

	while(!lqueue_empty(&myqueue))
	{
		qdata = lqueue_dequeue(&myqueue);
		u32 cur = qdata->idx;

		tal_free(qdata);

		if(cur==target)
		{
			target_found = true;
			break;
		}

		for(struct arc arc = node_adjacency_begin(linear_network,cur);
		        !node_adjacency_end(arc);
			arc = node_adjacency_next(linear_network,arc))
		{
			// check if this arc is traversable
			if(residual_network->cap[arc.idx] <= 0)
				continue;

			u32 next = arc_head(linear_network,arc);

			assert(next < tal_count(prev));

			// if that node has been seen previously
			if(prev[next].idx!=INVALID_INDEX)
				continue;

			prev[next] = arc;

			qdata = tal(this_ctx,struct queue_data);
			qdata->idx = next;
			lqueue_enqueue(&myqueue,qdata);
		}
	}