[postgis-users] best finding all paths with recursive query
Shaozhong SHI
shishaozhong at gmail.com
Fri Jul 28 13:45:12 PDT 2023
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> 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], 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/72bdcd6e/attachment.htm>
More information about the postgis-users
mailing list