Function SPpaths_next

src/procedures/proc_sp_paths.c:430–503

use DFS to find all paths from src to dst tracking cost and weight

// use DFS to find all paths from src to dst tracking cost and weight
static void SPpaths_next
(
	SinglePairCtx *ctx,
	WeightedPath *p,
	double max_weight
) {
	// as long as path is not empty OR there are neighbors to traverse.
	while(Path_NodeCount(ctx->path) || _SinglePairCtx_LevelNotEmpty(ctx, 0)) {
		uint32_t depth = Path_NodeCount(ctx->path);

		// can we advance?
		if(_SinglePairCtx_LevelNotEmpty(ctx, depth)) {
			// get a new frontier.
			LevelConnection frontierConnection = array_pop(ctx->levels[depth]);
			Node frontierNode = frontierConnection.node;

			bool frontierAlreadyOnPath = Path_ContainsNode(ctx->path, &frontierNode);

			// don't allow cycles
			if(frontierAlreadyOnPath) continue;

			// add frontier to path.
			Path_AppendNode(ctx->path, frontierNode);

			// if depth is 0 this is the source node, there is no leading edge to it.
			// For depth > 0 for each frontier node, there is a leading edge.
			if(depth > 0) {
				SIValue c = _get_value_or_defualt((GraphEntity *)&frontierConnection.edge, ctx->cost_prop, SI_LongVal(1));
				SIValue w = _get_value_or_defualt((GraphEntity *)&frontierConnection.edge, ctx->weight_prop, SI_LongVal(1));
				if(p->cost + SI_GET_NUMERIC(c) <= ctx->max_cost && p->weight + SI_GET_NUMERIC(w) <= max_weight) {
					p->cost += SI_GET_NUMERIC(c);
					p->weight += SI_GET_NUMERIC(w);
					Path_AppendEdge(ctx->path, frontierConnection.edge);
				} else {
					Path_PopNode(ctx->path);
					continue;
				}
			}

			// update path depth.
			depth++;

			// introduce neighbors only if path depth < maximum path length.
			// and frontier wasn't already expanded.
			if(depth < ctx->maxLen) {
				addNeighbors(ctx, &frontierConnection, depth, ctx->dir);
			}

			// see if we can return path.
			if(depth >= ctx->minLen && depth <= ctx->maxLen) {
				Node dst = Path_Head(ctx->path);
				if(ENTITY_GET_ID(ctx->dst) != ENTITY_GET_ID(&dst)) {
					continue;
				}
				p->path = ctx->path;
				return;
			}
		} else {