[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
>
> 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> 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
>>>> 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> 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>
More information about the postgis-users
mailing list