Function AllShortestPaths_NextPath

src/algorithms/all_shortest_paths.c:105–167

find paths from src to dest by traversing from dest to src using DFS inspecting nodes which where discovered by the previous call to `AllShortestPaths_FindMinimumLength`

// inspecting nodes which where discovered by
// the previous call to `AllShortestPaths_FindMinimumLength`
Path *AllShortestPaths_NextPath
(
	AllPathsCtx *ctx
) {
	ASSERT(ctx != NULL);

	uint32_t depth = Path_NodeCount(ctx->path);
	if(depth > 0) {
		// a full path already returned
		// advance to next path by backtracking
		depth--;
	} else {
		if(array_len(ctx->levels[0]) == 0) return NULL;

		Path_EnsureLen(ctx->path, ctx->minLen);
		LevelConnection frontierConnection = array_pop(ctx->levels[0]);
		Node frontierNode = frontierConnection.node;
		Path_SetNode(ctx->path, ctx->minLen - depth - 1, frontierNode);
		depth++;
		addNeighbors(ctx, &frontierConnection, depth, ctx->dir);
	}

	// as long as we didn't found a full path from src to dest
	while (depth < ctx->maxLen) {
		if (array_len(ctx->levels[depth]) > 0) {
			// get a new node from the frontier
			bool is_visited;
			LevelConnection frontierConnection = array_pop(ctx->levels[depth]);
			Node frontierNode = frontierConnection.node;
			NodeID frontierID = ENTITY_GET_ID(&frontierNode);
			GrB_Info info = GrB_Vector_extractElement_BOOL(&is_visited,
					ctx->visited, frontierID);

			// consider only previously discovered nodes
			if(info == GrB_NO_VALUE) continue;

			// if we reached to the end of the path and this node is not the
			// dst node continue
			if(depth == ctx->maxLen - 1 &&
			   frontierID != ENTITY_GET_ID(ctx->dst)) {
				continue;
			}

			Path_SetNode(ctx->path, ctx->minLen - depth - 1, frontierNode);
			Path_SetEdge(ctx->path, ctx->minLen - depth - 1, frontierConnection.edge);

			if(depth == ctx->maxLen - 1) break;

			depth++;
			addNeighbors(ctx, &frontierConnection, depth, ctx->dir);
		} else {
			depth--;
			if(depth == 0) {
				Path_Clear(ctx->path);
				// first level fully consumed
				// there are no more paths leading from src to dest, we're done
				return NULL;
			}