# [postgis-users] best finding all paths with recursive query

Imre Samu pella.samu at gmail.com
Thu Jul 27 18:16:08 PDT 2023

```Hi David,

I have created
an extended source data  ( 20 edges ;  with pgrouting create topology )
Therefore, the pgrouting extension is essential! It's also crucial to grasp
the fundamental PGRouting concepts.
- https://docs.pgrouting.org/3.5/en/pgRouting-concepts.html

As I understand, your example represents a 'directed' network.
In response, I have developed two solutions:
-  A Common Table Expressions (CTE) recursive pure SQL version, and
-  A version utilizing pgr_ksp.

CTE SQL  - result  ( for my extended test data ~ 20 edges )
+-------------------+
|       path        |
+-------------------+
| {6,3,14,20}       |
| {6,3,1,18,19}     |
| {6,3,14,16,18,19} |
| {6,3,15,17,18,19} |
+-------------------+

and a pgr_ksp version result:
+---------+--------+--------+---------+-------------------+--------------------+
| edge_id | source | target | path_id |       edges       |       nodes
|
+---------+--------+--------+---------+-------------------+--------------------+
|       6 |      7 |     18 |       1 | {6,3,1,18,19}     | {7,4,1,2,17,18}
|
|       6 |      7 |     18 |       2 | {6,3,14,16,18,19} |
{7,4,1,15,2,17,18} |
|       6 |      7 |     18 |       3 | {6,3,15,17,18,19} |
{7,4,1,16,2,17,18} |
|       6 |      7 |     19 |       1 | {6,3,14,20}       | {7,4,1,15,19}
|
+---------+--------+--------+---------+-------------------+--------------------+

And this is the Data + Code:

--------------------------------
DROP TABLE IF EXISTS network;
BEGIN;
CREATE TABLE network ( segment geometry, id integer primary key);
INSERT INTO network VALUES ('LINESTRING( 1  1,  0  0)',  1);
INSERT INTO network VALUES ('LINESTRING( 2  1,  1  1)',  2);
INSERT INTO network VALUES ('LINESTRING( 1  2,  1  1)',  3);
INSERT INTO network VALUES ('LINESTRING( 3  1,  2  1)',  4);
INSERT INTO network VALUES ('LINESTRING( 3  2,  2  1)',  5);
INSERT INTO network VALUES ('LINESTRING( 2  3,  1  2)',  6);
INSERT INTO network VALUES ('LINESTRING( 1  3,  1  2)',  7);
INSERT INTO network VALUES ('LINESTRING( 4  2,  3  2)',  8);
INSERT INTO network VALUES ('LINESTRING( 3  4,  2  3)',  9);
INSERT INTO network VALUES ('LINESTRING( 2  4,  2  3)', 10);
INSERT INTO network VALUES ('LINESTRING( 1  4,  1  3)', 11);
INSERT INTO network VALUES ('LINESTRING( 4  3,  4  2)', 12);
INSERT INTO network VALUES ('LINESTRING( 4  4,  3  4)', 13);

-- add some extra edges to make it interesting
INSERT INTO network VALUES ('LINESTRING( 1  1,  1  0)', 14);
INSERT INTO network VALUES ('LINESTRING( 1  1,  0  1)', 15);
INSERT INTO network VALUES ('LINESTRING( 1  0,  0  0)', 16);
INSERT INTO network VALUES ('LINESTRING( 0  1,  0  0)', 17);
INSERT INTO network VALUES ('LINESTRING( 0  0, -1 -1)', 18);
INSERT INTO network VALUES ('LINESTRING(-1 -1, -2 -2)', 19);
INSERT INTO network VALUES ('LINESTRING( 1  0,  5  0)', 20);

ALTER TABLE network ADD COLUMN "source" integer;
ALTER TABLE network ADD COLUMN "target" integer;
ALTER TABLE network ADD COLUMN cost float;
UPDATE network SET cost = ST_Length(segment);
CREATE INDEX network_gix    ON network USING GIST (segment);
COMMIT;

VACUUM FULL ANALYZE network;

-- enable pgrouting : https://pgrouting.org/
CREATE EXTENSION IF NOT EXISTS PGROUTING ;
--  Builds a network topology based on the geometry information.
--  https://docs.pgrouting.org/latest/en/pgr_createTopology.html
SELECT pgr_createTopology('network', 0.000001, 'segment', 'id');
-- Vertices table for table public.network is: public.network_vertices_pgr

--  analyze the network table
SELECT pgr_analyzeGraph('network',   0.000001, the_geom := 'segment', id :=
'id');

-- the new network table
\d+ network
select * from network;

-- the new vertices table
\d+ network_vertices_pgr
select * from network_vertices_pgr;

-----------------------------------
-- This code essentially finds all paths in the network
-- that start from the edge with id = 6 and end at a node that has no
outgoing edges (end node).
-- It avoids cycles by not including an edge in a path if it is already in
the path.
-- This code uses a recursive common table expression (CTE) to perform the
path search.
-- The recursion is done by joining the paths generated
-- so far with the edges in the network based on the end node of the path
-- and the start node of the edge.
-----------------------------------
--
-- Start a recursive CTE (Common Table Expression)
WITH RECURSIVE paths(path, last_node) AS (

-- Initial selection for the recursive CTE ------
-- The initial path is an array with a single element, the start node's id
-- The last_node is the end node of the edge with the start node's id
SELECT ARRAY[id] AS path, target AS last_node
FROM network
WHERE id = 6  -- Select the edge with id = 6 as the start edge

UNION ALL -- Union to append following results to the initial selection

-- Recursive part of the CTE -------
-- Build the path by appending the current edge id to the existing path,
-- and update the last node to the end node of the current edge
SELECT p.path || ARRAY[e.id], e.target
FROM network e
INNER JOIN paths p ON e.source = p.last_node -- Join with the previous
paths based on the last_node
WHERE NOT e.id  = any( p.path )  -- Prevent cycles: Do not select an edge
if its id is already in the path
)
-- Finally, select the paths
SELECT path
FROM paths
WHERE NOT EXISTS (
-- For each path, check if there exists an edge in the network starting
from the path's last node
-- If such an edge exists, the path is not selected, because the path has
not reached the end
SELECT 1
FROM network e
WHERE e.source = paths.last_node
);

----------------------------------

---------------------------------------------------------
-- (pgrouting) pgr_KSP - K Shortest Path solution;
-- This script first creates a  "ksp" table
--    to fetch the K shortest paths from a specific source to all other
targets
--    in the "network" that are not "sources".
-- From the "ksp":  It then extracts each path, organizes the sequence of
edges and nodes,
-- and presents the result in a structured way.
------------------------------------------------

-- Creating a 'ksp' table (K Shortest Paths)
drop table if exists ksp;
create table ksp as
-- Selects the edge_id and source from the network table where id = 6,
-- and selects all targets from the network that are not sources
SELECT
tsource.edge_id as edge_id  -- This is the id of the selected edge
, tsource.source  as source   -- This is the source node of the
selected edge
, tx.target       as target   -- These are the target nodes which are
not sources
, (pgr_KSP (  -- This is a pgRouting function to get the K shortest
paths from source to target.
-- https://docs.pgrouting.org/latest/en/pgr_KSP.html
'SELECT id, source, target, cost FROM network' -- This is the SQL
to generate the network graph
,tsource.source -- This is the source node of the selected edge
,tx.target      -- These are the target nodes which are not sources
,999999999      -- This is the maximum number of paths to return
,directed:=true -- This is a pgRouting function to indicate that
the graph is directed
)).*
FROM
(
-- This subquery selects the edge with id = 6 as the source edge
select id as edge_id, source from network where id = 6 ) as tsource
,(
-- This subquery selects all targets that are not sources
SELECT target
FROM network
EXCEPT
SELECT source
FROM network
) tx
;

-- examine ksp
select * from ksp;

-- Now the final edges and nodes :
select edge_id  -- Selects edge_id
,source   -- Selects source
,target   -- Selects target
,path_id  -- Selects path_id
-- Aggregates all edges from 'ksp' in the order of their sequence,
excluding edge = -1
,array_agg(edge order by path_seq ) FILTER (Where edge != -1 ) as
edges
-- Aggregates all nodes from 'ksp' in the order of their sequence
,array_agg(node order by path_seq ) as nodes
from ksp
group by edge_id,source,target, path_id
order by edge_id,source,target, path_id
;

-----------------------------------
in gist ( SQL + Log ) :
https://gist.github.com/ImreSamu/cdd9afed6106366296622b10c0d44be2
------------------

I assume it's not easy to understand the code, especially the pgrouting
concepts, but I think it's inevitable if you want to deal with similar
networks.
And I think it's definitely worth spending a few weeks on pgrouting and
completing the basic workshop.
(  https://workshop.pgrouting.org/2.8/en/index.html )
And if you have any more questions about pgrouting, there is also a
dedicated mailing list.
( https://lists.osgeo.org/mailman/listinfo/pgrouting-users )

I hope you can use something from the solution I suggested.
Imre

Shaozhong SHI <shishaozhong at gmail.com> ezt írta (időpont: 2023. júl. 19.,
Sze, 11:22):

> Imre Samu,
>
> With the example:  the output the path is
> 6
> 3
> 1
>
> the output is:
> 6
> 3
> 1
> 14
>
> Regards,
>
> David
>
> On Mon, 17 Jul 2023 at 23:12, Imre Samu <pella.samu at gmail.com> wrote:
>
>> > How about finding out all possible route paths.?
>>
>> I'm sorry, I don't fully understand your question as it could be
>> interpreted in several ways.
>> Could you provide a small set of test data and specify the kind of output
>> you're looking for?
>>
>> Thanks,
>>   Imre
>>
>> Shaozhong SHI <shishaozhong at gmail.com> ezt írta (időpont: 2023. júl.
>> 17., H, 21:24):
>>
>>> How about finding out all possible route paths.?
>>> Regards, david
>>>
>>> On Monday, 17 July 2023, Imre Samu <pella.samu at gmail.com> wrote:
>>>
>>>> > Which one is the best example for finding all paths with recursive
>>>> query?
>>>>
>>>> What type of graph are you working with?
>>>>
>>>> 1.)
>>>> You can check Yugabyte (PostgreSQL compatible) documentation for pure
>>>> SQL recursive-graph solutions for :
>>>> - Undirected cyclic graph
>>>> - Directed cyclic graph
>>>> - Directed acyclic graph
>>>> - Rooted tree
>>>> - Unique containing paths
>>>>
>>>> https://docs.yugabyte.com/preview/api/ysql/the-sql-language/with-clause/traversing-general-graphs/common-code/
>>>> I think there's a pretty good summary for solving basic graph problems
>>>> and find a solution for it...
>>>>
>>>> 2.)
>>>> Or use pgr_KSP - if you're only interested in the final result and
>>>> you're not attached to the purely recursive SQL solution.
>>>> And it's much more optimal for large graphs as well.
>>>> Here, you just need to provide a large enough K value (e.g., ~ maximum
>>>> (integer/bigint) value) and then you get all possible paths.
>>>> Or if you're only interested in the top 2, then set K=2.
>>>>
>>>> https://docs.pgrouting.org/latest/en/pgr_KSP.html
>>>> "The K shortest path routing algorithm based on Yen’s algorithm*. “K”
>>>> is the number of shortest paths desired.*"
>>>> https://en.wikipedia.org/wiki/K_shortest_path_routing
>>>>
>>>> regards,
>>>>  Imre
>>>>
>>>> Shaozhong SHI <shishaozhong at gmail.com> ezt írta (időpont: 2023. júl.
>>>> 17., H, 9:01):
>>>>
>>>>> Which one is the best example for finding all paths with recursive
>>>>> query?
>>>>>
>>>>> Regards,
>>>>>
>>>>> David
>>>>> _______________________________________________
>>>>> postgis-users mailing list
>>>>> postgis-users at lists.osgeo.org
>>>>> https://lists.osgeo.org/mailman/listinfo/postgis-users
>>>>>
>>>> _______________________________________________
>>> postgis-users mailing list
>>> postgis-users at lists.osgeo.org
>>> https://lists.osgeo.org/mailman/listinfo/postgis-users
>>>
>> _______________________________________________
>> postgis-users mailing list
>> postgis-users at lists.osgeo.org
>> https://lists.osgeo.org/mailman/listinfo/postgis-users
>>
> _______________________________________________
> postgis-users mailing list
> postgis-users at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/postgis-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20230728/fc3ae946/attachment.htm>
```