pgr_ksp doesn't give all correct shortest path

[luisfernandos1]

Problem

To Reproduce

In order to reproduce the problem just create a graph like a square, where all point are connected, let's say
A,B,C,D
you want to find path from A to D
There are the paths it is returning
AD
ABD
ACD
ABCD

Expectation

Should bring all paths including ACBD, which is not happening, not that this route is different from ABCD

Sample Data

select id, idvertexfrom as source, idvertexto as target, distance::double precision as cost from fiber
"id","source","target","cost"
1,1,2,10.0
2,2,4,10.0
3,1,3,10.0
4,3,4,10.0
5,2,3,10.0
6,1,4,10.0

select * from pgr_KSP('select id, idvertexfrom as source, idvertexto as target, distance::double precision as cost from fiber',1, 4, 10, false, false);
"seq","path_id","path_seq","node","edge","cost","agg_cost"
1,1,1,1,6,10.0,0.0
2,1,2,4,-1,0.0,10.0
3,2,1,1,1,10.0,0.0
4,2,2,2,2,10.0,10.0
5,2,3,4,-1,0.0,20.0
6,3,1,1,3,10.0,0.0
7,3,2,3,4,10.0,10.0
8,3,3,4,-1,0.0,20.0
9,4,1,1,1,10.0,0.0
10,4,2,2,5,10.0,10.0
11,4,3,3,4,10.0,20.0
12,4,4,4,-1,0.0,30.0

ONLY 4 path are returned !!!

Platform/versions

SELECT version();
PostgreSQL 12.7 (Debian 12.7-1.pgdg100+1) on x86_64-pc-linux-gnu, compiled by gcc (Debian 8.3.0-6) 8.3.0, 64-bit

SELECT postgis_full_version();
POSTGIS="3.1.2 cbe925d" [EXTENSION] PGSQL="120" GEOS="3.7.1-CAPI-1.11.1 27a5e771" PROJ="Rel. 5.2.0, September 15th, 2018" LIBXML="2.9.4" LIBJSON="0.12.1" LIBPROTOBUF="1.3.1" WAGYU="0.5.0 (Internal)"
SELECT pgr_version();
3.2.0

[cvvergara]

@luisfernandos1
Thanks for reporting.

Reproduction:

CREATE TABLE fiber (id SERIAL, source INT, target INT, cost FLOAT) ;

INSERT INTO FIBER (source, target, cost) VALUES
1,2,10),(2,4,10),(1,3,10),(3,4,10),(2,3,10),(1,4,10);

SELECT * FROM pgr_ksp('SELECT * FROM fiber', 1, 4, 10, false, false);
 seq | path_id | path_seq | node | edge | cost | agg_cost 
-----+---------+----------+------+------+------+----------
   1 |       1 |        1 |    1 |    6 |   10 |        0
   2 |       1 |        2 |    4 |   -1 |    0 |       10
   3 |       2 |        1 |    1 |    1 |   10 |        0
   4 |       2 |        2 |    2 |    2 |   10 |       10
   5 |       2 |        3 |    4 |   -1 |    0 |       20
   6 |       3 |        1 |    1 |    3 |   10 |        0
   7 |       3 |        2 |    3 |    4 |   10 |       10
   8 |       3 |        3 |    4 |   -1 |    0 |       20
   9 |       4 |        1 |    1 |    1 |   10 |        0
  10 |       4 |        2 |    2 |    5 |   10 |       10
  11 |       4 |        3 |    3 |    4 |   10 |       20
  12 |       4 |        4 |    4 |   -1 |    0 |       30
(12 rows)
-- showing the heap_paths:
SELECT * FROM pgr_ksp('SELECT * FROM fiber', 1, 4, 10, directed => false, heap_paths => true);
 seq | path_id | path_seq | node | edge | cost | agg_cost 
-----+---------+----------+------+------+------+----------
   1 |       1 |        1 |    1 |    6 |   10 |        0
   2 |       1 |        2 |    4 |   -1 |    0 |       10
   3 |       2 |        1 |    1 |    1 |   10 |        0
   4 |       2 |        2 |    2 |    2 |   10 |       10
   5 |       2 |        3 |    4 |   -1 |    0 |       20
   6 |       3 |        1 |    1 |    3 |   10 |        0
   7 |       3 |        2 |    3 |    4 |   10 |       10
   8 |       3 |        3 |    4 |   -1 |    0 |       20
   9 |       4 |        1 |    1 |    1 |   10 |        0
  10 |       4 |        2 |    2 |    5 |   10 |       10
  11 |       4 |        3 |    3 |    4 |   10 |       20
  12 |       4 |        4 |    4 |   -1 |    0 |       30
(12 rows)

Indeed it returns only 4 paths, I deduce that 5 paths are expected on the solution. which can visually be seen on the following visual representation of the graph and of the paths found

color	path_seq
Blue	1
Yellow	2
Purple	3
Green	4
red	missing

[luisfernandos1]

Is there any knews about this problem ?

[cvvergara]

@luisfernandos1
working on it

[cvvergara]

Checking again
Viewing the graph here (all costs are the same 10):
https://dreampuf.github.io/GraphvizOnline/

graph G {
  1 -- 2;
  2 -- 4;
  1 -- 3;
  3 -- 4;
  2 -- 3;
  1 -- 4;
}

working the results by hand on next comment

[cvvergara]

Expected path results:

1 -> 4
1 -> 3 -> 4
1 -> 2 -> 4
1-> 2 -> 3 -> 4
1 -> 3 -> 2 -> 4