[postgis-users] best finding all paths with recursive query
Regina Obe
lr at pcorp.us
Fri Jul 28 15:02:17 PDT 2023
I’m cc’ing pgRouting users list since some people might have some more ideas there.
@Shaozhong – you should join the pgRouting Users mailing list if you more pointed questions about it’s capabilities.
Thanks,
Regina
From: postgis-users [mailto:postgis-users-bounces at lists.osgeo.org] On Behalf Of Shaozhong SHI
Sent: Friday, July 28, 2023 4:45 PM
To: Imre Samu <pella.samu at gmail.com>
Cc: PostGIS Users Discussion <postgis-users at lists.osgeo.org>
Subject: Re: [postgis-users] best finding all paths with recursive query
Imre Samu,
Very interesting. I will read and review.
I am interested in exploring new concepts. Something like connectivity tests.
Different network have different connectivity or known as topological relationships between objects. For instance, water network and road network.
Certain types are expected to be valid in water network whilst other types are expected to be valid in road network.
Regards,
David
On Fri, 28 Jul 2023 at 02:16, Imre Samu <pella.samu at gmail.com <mailto:pella.samu at gmail.com> > wrote:
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 <http://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 <http://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 <mailto: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
When extra added:
the output is:
6
3
1
14
Regards,
David
On Mon, 17 Jul 2023 at 23:12, Imre Samu <pella.samu at gmail.com <mailto: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 <mailto: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 <mailto: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 with SQL, which could potentially help you understand your problem as well 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 <mailto: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 <mailto:postgis-users at lists.osgeo.org>
https://lists.osgeo.org/mailman/listinfo/postgis-users
_______________________________________________
postgis-users mailing list
postgis-users at lists.osgeo.org <mailto:postgis-users at lists.osgeo.org>
https://lists.osgeo.org/mailman/listinfo/postgis-users
_______________________________________________
postgis-users mailing list
postgis-users at lists.osgeo.org <mailto:postgis-users at lists.osgeo.org>
https://lists.osgeo.org/mailman/listinfo/postgis-users
_______________________________________________
postgis-users mailing list
postgis-users at lists.osgeo.org <mailto: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/4f54c4a5/attachment.htm>
More information about the postgis-users
mailing list