pgr_KSP ignore results with same vertex collection

[casasvic]

Problem
TL;DR: pgr_KSP function ignores options where vertex collection is the same as another better result. If you can get from point A to point B, traversing exactly the same nodes as another solution, this solution is not considered

To Reproduce
Create a topology, in this example we have already created our tables "noded" and "noded_vertices_pgr" using pgr_nodeNetwork and pgr_createTopology

Then after apply pgr_KSP, only show as possible options edge 7, and edge 9+10.

Edge 8 is missing due to have the same vertex collection as edge 7 (vertex 7 and vertex 8, but through edge 8 instead of edge 7). If edge 8 is split (same as example edge 9+10), then it works and returns 3 path results, just because vertex collection for this result would be different

SQL from node 7 to node 8, we allow reverse as well, and limit to 3 paths, but only 2 will return:

SELECT *
FROM pgr_KSP(
  'SELECT id, source, target, ST_Length(wkb_geometry::geography) as cost, ST_Length(wkb_geometry::geography) as reverse_cost
  FROM mytable_noded',
  7,
  8,
3) as ksp

Result:

Expectation
Get all shortest paths, even if the vertex combination already exists as result, but have a different edges collection. This includes third path, using nodes 7,8 with edge 8 (almost like the first one, but using edge 8 creating a new path_id=3)

Platform/versions

PostgreSQL="14.11"
POSTGIS="3.4.2 c19ce56" 
pgr_version="3.6.2"

[casasvic]

I forgot to say how I'm solving it in the meantime.. I have created my own function that includes missing paths, maybe this can help others.

Using the function would be exactly the same as the original pgr_ksp

CREATE OR REPLACE FUNCTION pgr_ksp_withpararells(
	query_input text,
	vertex_1 bigint,
	vertex_2 bigint,
	max_results integer,
	directed boolean DEFAULT false)
	RETURNS TABLE(seq integer, path_id integer, path_seq integer, start_vid bigint, end_vid bigint, node bigint, edge bigint, cost double precision, agg_cost double precision) 
	LANGUAGE 'plpgsql'
	COST 100
	VOLATILE SECURITY DEFINER PARALLEL UNSAFE
	ROWS 1000

AS $BODY$
DECLARE
	comb_index jsonb;
	comb_length INT;
	pointer INT;

	max_combinations INT;
	path_record RECORD;
	increase boolean;
BEGIN
	-- Create a new temp table, to be able to sort later
	CREATE TEMP TABLE temp_result (
		seq integer primary key,
		path_id integer,
		path_seq integer,
		start_vid bigint,
		end_vid bigint,
		node bigint,
		edge bigint,
		cost double precision,
		agg_cost double precision
	);
	
	-- Start a BEGIN ... EXCEPTION ... END block, to make sure that if there is an error the temporary table is deleted in the same session
	BEGIN
		-- Initialize the ids
		path_id := 1;
		seq := 1;

		-- Run the pgr_KSP query and go through the results of each path
		-- Since postgresql does not allow to group arrays of different dimensions, we do it using jsonb
		-- Group each sequence, and then each path, to be very clear about the combinations
		FOR path_record IN EXECUTE '
			SELECT path_id, start_vid, end_vid,
					jsonb_agg(nodes order by seq) AS nodes_array,
					jsonb_agg(edges order by seq) AS edges_array, 
					jsonb_agg(costs order by seq) as costs_array 
			FROM (
				SELECT distinct seq, path_id, start_vid, end_vid,

					-- Get the nodes also for convenience, I do it as json to not modify anything, but I know that all the elements in the sequence have the same value
					jsonb_agg(node order by seq) as nodes,

					-- Group the parallel ids (edge) as json, or -1 if it does not cross
					jsonb_agg(COALESCE(nd2.id, -1) order by 

							  -- Sort by cost, which we then set aside as another field as well
							  COALESCE(CASE 
										WHEN ksp.edge = nd2.id THEN ksp.cost 
										WHEN ksp.edge <> nd2.id and nd.source = nd2.source THEN nd2.cost
										WHEN ksp.edge <> nd2.id and nd.source = nd2.target THEN nd2.reverse_cost
									   END, 0)
							 ) as edges,

					-- Group costs, taking into account whether it is the original result, whether it is parallel in the same direction, or parallel in reverse
					jsonb_agg(COALESCE(CASE 
										WHEN ksp.edge = nd2.id THEN ksp.cost 
										WHEN ksp.edge <> nd2.id and nd.source = nd2.source THEN nd2.cost
										WHEN ksp.edge <> nd2.id and nd.source = nd2.target THEN nd2.reverse_cost
									   END, 0) order by nd2.cost) as costs
				FROM pgr_KSP(''' || query_input || ''', ' || vertex_1 || ', ' || vertex_2 || ', ' || max_results || ') as ksp
				left join ('|| query_input ||') as nd
					on ksp.edge = nd.id
				left join ('|| query_input ||') as nd2
					on (nd.source = nd2.source and nd.target = nd2.target)

						-- If it is not directed, it also crosses if the source->target relationship is inverse
						or (nd.source = nd2.target and nd.target = nd2.source and (' || directed || ' = False))
						
				group by seq, path_id,  start_vid, end_vid
				order by seq, path_id
			) as sub GROUP BY path_id, start_vid, end_vid order by path_id'
		LOOP
			-- Initialize a list to use as position pointers
			comb_length := jsonb_array_length(path_record.edges_array);
			comb_index := jsonb_agg(0::INTEGER) FROM generate_series(1, comb_length);
			max_combinations := 1;

			-- Calculate the possible combinations, multiplying by the length of the lists
			FOR i IN 0..(comb_length - 1) LOOP
				max_combinations := max_combinations * jsonb_array_length(path_record.edges_array[i]);
			END LOOP;

			-- Start without incrementing, to get all the values from the 0 positions first
			increase = FALSE;

			-- Get start_vid and end_vid values
			start_vid := path_record.start_vid;
			end_vid := path_record.end_vid;

			-- Loop as many times as we have calculated
			FOR i IN 1..max_combinations LOOP
				-- Initialize the path variables
				path_seq := 1;
				cost := 0;
				agg_cost := 0;

				-- In each iteration go through the lists (and increase only once)
				FOR idx IN 0..(comb_length - 1) LOOP
					IF increase THEN
						IF jsonb_array_length(path_record.edges_array[idx]) > ((comb_index[idx])::INTEGER + 1) THEN
							increase = FALSE;
							comb_index[idx] = (comb_index[idx])::INTEGER + 1;
						ELSE
							comb_index[idx] = 0;
						END IF;
					END IF;

					pointer = (comb_index[idx])::INTEGER;

					agg_cost := agg_cost + cost;
					edge := (path_record.edges_array[idx][pointer])::bigint;
					node := (path_record.nodes_array[idx][pointer])::bigint;
					cost := (path_record.costs_array[idx][pointer])::float;

					-- Save the current combination in the table
					INSERT INTO temp_result
					VALUES(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost);

					seq := seq + 1;
					path_seq := path_seq + 1;
				END LOOP;

				-- Set the flag for the next iteration
				increase = TRUE;
				path_id := path_id + 1;
			END LOOP;		
		END LOOP;
		
		-- Return the data from the temporary table, but this time sorted, and limited to max_results
		RETURN QUERY
		SELECT
			row_number () over (order by op.new_path_id, ksp.seq)::INTEGER as seq,
			op.new_path_id as path_id,
			ksp.path_seq,
			ksp.start_vid,
			ksp.end_vid,
			ksp.node,
			ksp.edge,
			ksp.cost,
			ksp.agg_cost
		FROM temp_result as ksp
		inner join (
			SELECT row_number() over(order by SUM(ksp2.cost))::INTEGER as new_path_id, ksp2.path_id
			FROM temp_result as ksp2
			GROUP BY ksp2.path_id
		) as op on ksp.path_id = op.path_id
		WHERE op.new_path_id <= max_results;
		
	EXCEPTION
		-- Catch any exceptions that occur
		WHEN OTHERS THEN
			RAISE EXCEPTION 'An error has occurred: %', SQLERRM;
	END;
	
	-- Delete the temporary table (regardless of whether there was an error or not)
	DROP TABLE IF EXISTS temp_result;	
	
END;
$BODY$;

Use this function as the original one

SELECT *
FROM pgr_ksp_withpararells(
  'SELECT id, source, target, ST_Length(wkb_geometry::geography) as cost, ST_Length(wkb_geometry::geography) as reverse_cost
  FROM mytable_noded',
  7,
  8,
3) as ksp

Then we have all 3 results

[cvvergara]

@casasvic
the way to go forward on this one is that you send an sql script that includes:

• creating the table
• creating the data
• use the function

please send to vicky at erosion.dev