<div dir="ltr">Imre Samu,<div><br></div><div>Very interesting. I will read and review.</div><div><br></div><div>I am interested in exploring new concepts. Something like connectivity tests.</div><div><br></div><div>Different network have different connectivity or known as topological relationships between objects. For instance, water network and road network.</div><div><br></div><div>Certain types are expected to be valid in water network whilst other types are expected to be valid in road network.</div><div><br></div><div>Regards,</div><div><br></div><div>David</div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, 28 Jul 2023 at 02:16, Imre Samu <<a href="mailto:pella.samu@gmail.com">pella.samu@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Hi David,</div><div><br></div>I have created<div>an extended source data ( 20 edges ; with pgrouting create topology ) </div><div>Therefore, the pgrouting extension is essential! It's also crucial to grasp the fundamental PGRouting concepts.<br><div>- <a href="https://docs.pgrouting.org/3.5/en/pgRouting-concepts.html" target="_blank">https://docs.pgrouting.org/3.5/en/pgRouting-concepts.html</a> </div><div><br></div><div>As I understand, your example represents a 'directed' network. </div><div>In response, I have developed two solutions:<br>- A Common Table Expressions (CTE) recursive pure SQL version, and<br>- A version utilizing pgr_ksp.<br></div><div><div><div><br></div><div>CTE SQL - result ( for my extended test data ~ 20 edges )<br><font face="monospace" color="#38761d">+-------------------+<br>| path |<br>+-------------------+<br>| {6,3,14,20} |<br>| {6,3,1,18,19} |<br>| {6,3,14,16,18,19} |<br>| {6,3,15,17,18,19} |<br>+-------------------+</font></div><div><br></div><div>and a pgr_ksp version result:</div><div><font face="monospace" color="#741b47">+---------+--------+--------+---------+-------------------+--------------------+<br>| edge_id | source | target | path_id | edges | nodes |<br>+---------+--------+--------+---------+-------------------+--------------------+<br>| 6 | 7 | 18 | 1 | {6,3,1,18,19} | {7,4,1,2,17,18} |<br>| 6 | 7 | 18 | 2 | {6,3,14,16,18,19} | {7,4,1,15,2,17,18} |<br>| 6 | 7 | 18 | 3 | {6,3,15,17,18,19} | {7,4,1,16,2,17,18} |<br>| 6 | 7 | 19 | 1 | {6,3,14,20} | {7,4,1,15,19} |<br>+---------+--------+--------+---------+-------------------+--------------------+</font><br></div><div><br><br>And this is the Data + Code:</div><div><br></div><div><font face="monospace">--------------------------------<br><font color="#351c75">DROP TABLE IF EXISTS network;</font><br><font color="#351c75">BEGIN;</font><br><font color="#351c75">CREATE TABLE network ( segment geometry, id integer primary key);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 1 1, 0 0)', 1);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 2 1, 1 1)', 2);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 1 2, 1 1)', 3);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 3 1, 2 1)', 4);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 3 2, 2 1)', 5);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 2 3, 1 2)', 6);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 1 3, 1 2)', 7);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 4 2, 3 2)', 8);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 3 4, 2 3)', 9);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 2 4, 2 3)', 10);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 1 4, 1 3)', 11);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 4 3, 4 2)', 12);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 4 4, 3 4)', 13);</font><br><br><font color="#351c75">-- add some extra edges to make it interesting</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 1 1, 1 0)', 14);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 1 1, 0 1)', 15);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 1 0, 0 0)', 16);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 0 1, 0 0)', 17);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 0 0, -1 -1)', 18);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING(-1 -1, -2 -2)', 19);</font><br><font color="#351c75">INSERT INTO network VALUES ('LINESTRING( 1 0, 5 0)', 20);</font><br><br><font color="#351c75">ALTER TABLE network ADD COLUMN "source" integer;</font><br><font color="#351c75">ALTER TABLE network ADD COLUMN "target" integer;</font><br><font color="#351c75">ALTER TABLE network ADD COLUMN cost float;</font><br><font color="#351c75">UPDATE network SET cost = ST_Length(segment);</font><br><font color="#351c75">CREATE INDEX network_gix ON network USING GIST (segment);</font><br><font color="#351c75">COMMIT;</font><br><br><font color="#351c75">VACUUM FULL ANALYZE network;</font><br><br><font color="#351c75">-- enable pgrouting : <a href="https://pgrouting.org/" target="_blank">https://pgrouting.org/</a></font><br><font color="#351c75">CREATE EXTENSION IF NOT EXISTS PGROUTING ;</font><br><font color="#351c75">-- Builds a network topology based on the geometry information.</font><br><font color="#351c75">-- <a href="https://docs.pgrouting.org/latest/en/pgr_createTopology.html" target="_blank">https://docs.pgrouting.org/latest/en/pgr_createTopology.html</a></font><br><font color="#351c75">SELECT pgr_createTopology('network', 0.000001, 'segment', 'id');</font><br><font color="#351c75">-- Vertices table for table public.network is: public.network_vertices_pgr</font><br><br><font color="#351c75">-- analyze the network table</font><br><font color="#351c75">SELECT pgr_analyzeGraph('network', 0.000001, the_geom := 'segment', id := 'id');</font><br><br><font color="#351c75">-- the new network table</font><br><font color="#351c75">\d+ network</font><br><font color="#351c75">select * from network;</font><br><br><font color="#351c75">-- the new vertices table</font><br><font color="#351c75">\d+ network_vertices_pgr</font><br><font color="#351c75">select * from network_vertices_pgr;</font><br><br><font color="#38761d">-----------------------------------<br>-- This code essentially finds all paths in the network <br>-- that start from the edge with id = 6 and end at a node that has no outgoing edges (end node). <br>-- It avoids cycles by not including an edge in a path if it is already in the path. <br>-- This code uses a recursive common table expression (CTE) to perform the path search. <br>-- The recursion is done by joining the paths generated <br>-- so far with the edges in the network based on the end node of the path <br>-- and the start node of the edge.<br>-----------------------------------<br>--<br>-- Start a recursive CTE (Common Table Expression) <br>WITH RECURSIVE paths(path, last_node) AS (<br><br> -- Initial selection for the recursive CTE ------<br> -- The initial path is an array with a single element, the start node's id<br> -- The last_node is the end node of the edge with the start node's id <br> SELECT ARRAY[id] AS path, target AS last_node<br> FROM network<br> WHERE id = 6 -- Select the edge with id = 6 as the start edge<br><br> UNION ALL -- Union to append following results to the initial selection<br><br> -- Recursive part of the CTE -------<br> -- Build the path by appending the current edge id to the existing path,<br> -- and update the last node to the end node of the current edge <br> SELECT p.path || ARRAY[<a href="http://e.id" target="_blank">e.id</a>], e.target<br> FROM network e<br> INNER JOIN paths p ON e.source = p.last_node -- Join with the previous paths based on the last_node<br> WHERE NOT <a href="http://e.id" target="_blank">e.id</a> = any( p.path ) -- Prevent cycles: Do not select an edge if its id is already in the path<br>)<br>-- Finally, select the paths<br>SELECT path<br>FROM paths<br>WHERE NOT EXISTS (<br> -- For each path, check if there exists an edge in the network starting from the path's last node<br> -- If such an edge exists, the path is not selected, because the path has not reached the end<br> SELECT 1<br> FROM network e<br> WHERE e.source = paths.last_node<br>);<br></font><br><font color="#351c75">----------------------------------</font><br><br><font color="#741b47"><br>---------------------------------------------------------<br>-- (pgrouting) pgr_KSP - K Shortest Path solution;<br>-- This script first creates a "ksp" table<br>-- to fetch the K shortest paths from a specific source to all other targets<br>-- in the "network" that are not "sources". <br>-- From the "ksp": It then extracts each path, organizes the sequence of edges and nodes, <br>-- and presents the result in a structured way.<br>------------------------------------------------<br><br>-- Creating a 'ksp' table (K Shortest Paths)<br>drop table if exists ksp;<br>create table ksp as<br> -- Selects the edge_id and source from the network table where id = 6,<br> -- and selects all targets from the network that are not sources <br> SELECT <br> tsource.edge_id as edge_id -- This is the id of the selected edge<br> , tsource.source as source -- This is the source node of the selected edge<br> , tx.target as target -- These are the target nodes which are not sources<br> , (pgr_KSP ( -- This is a pgRouting function to get the K shortest paths from source to target.<br> -- <a href="https://docs.pgrouting.org/latest/en/pgr_KSP.html" target="_blank">https://docs.pgrouting.org/latest/en/pgr_KSP.html</a><br> 'SELECT id, source, target, cost FROM network' -- This is the SQL to generate the network graph<br> ,tsource.source -- This is the source node of the selected edge<br> ,tx.target -- These are the target nodes which are not sources<br> ,999999999 -- This is the maximum number of paths to return<br> ,directed:=true -- This is a pgRouting function to indicate that the graph is directed<br> )).* <br> FROM <br> ( <br> -- This subquery selects the edge with id = 6 as the source edge<br> select id as edge_id, source from network where id = 6 ) as tsource<br> ,( <br> -- This subquery selects all targets that are not sources<br> SELECT target <br> FROM network<br> EXCEPT <br> SELECT source <br> FROM network<br> ) tx<br>;<br><br>-- examine ksp<br>select * from ksp;<br><br>-- Now the final edges and nodes :<br>select edge_id -- Selects edge_id<br> ,source -- Selects source<br> ,target -- Selects target<br> ,path_id -- Selects path_id <br> -- Aggregates all edges from 'ksp' in the order of their sequence, excluding edge = -1 <br> ,array_agg(edge order by path_seq ) FILTER (Where edge != -1 ) as edges <br> -- Aggregates all nodes from 'ksp' in the order of their sequence<br> ,array_agg(node order by path_seq ) as nodes <br> from ksp <br> group by edge_id,source,target, path_id<br> order by edge_id,source,target, path_id</font><br><font color="#351c75">; </font><br></font><br>-----------------------------------<br>in gist ( SQL + Log ) : <a href="https://gist.github.com/ImreSamu/cdd9afed6106366296622b10c0d44be2" target="_blank">https://gist.github.com/ImreSamu/cdd9afed6106366296622b10c0d44be2</a> </div><div>------------------</div><div><br></div><div>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.<br></div><div>And I think it's definitely worth spending a few weeks on pgrouting and completing the basic workshop.<br></div><div>( <a href="https://workshop.pgrouting.org/2.8/en/index.html" target="_blank">https://workshop.pgrouting.org/2.8/en/index.html</a> )<br></div><div>And if you have any more questions about pgrouting, there is also a dedicated mailing list.<br></div><div>( <a href="https://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">https://lists.osgeo.org/mailman/listinfo/pgrouting-users</a> )<br></div><div><br></div><div>I hope you can use something from the solution I suggested.<br></div><div> Imre<br></div><div><div><br></div></div></div></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Shaozhong SHI <<a href="mailto:shishaozhong@gmail.com" target="_blank">shishaozhong@gmail.com</a>> ezt írta (időpont: 2023. júl. 19., Sze, 11:22):<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Imre Samu,<div><br></div><div>With the example: the output the path is </div><div>6</div><div>3</div><div>1</div><div><br></div><div>When extra added:</div><div>the output is:</div><div>6</div><div>3</div><div>1</div><div>14</div><div><br></div><div>Regards,</div><div><br></div><div>David</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, 17 Jul 2023 at 23:12, Imre Samu <<a href="mailto:pella.samu@gmail.com" target="_blank">pella.samu@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">> How about finding out all possible route paths.?<div><br><div>I'm sorry, I don't fully understand your question as it could be interpreted in several ways.<br>Could you provide a small set of test data and specify the kind of output you're looking for?<br></div></div><div><br></div><div>Thanks,</div><div> Imre</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Shaozhong SHI <<a href="mailto:shishaozhong@gmail.com" target="_blank">shishaozhong@gmail.com</a>> ezt írta (időpont: 2023. júl. 17., H, 21:24):<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">How about finding out all possible route paths.?<div>Regards, david<br><br>On Monday, 17 July 2023, Imre Samu <<a href="mailto:pella.samu@gmail.com" target="_blank">pella.samu@gmail.com</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>> Which one is the best example for finding all paths with recursive query?</div><div><br></div><div>What type of graph are you working with?<br></div><div><br></div><div>1.) <br></div>You can check Yugabyte (PostgreSQL compatible) documentation for pure SQL recursive-graph solutions for :<div>- Undirected cyclic graph<br>- Directed cyclic graph<br>- Directed acyclic graph<br>- Rooted tree<br>- Unique containing paths<br><div><a href="https://docs.yugabyte.com/preview/api/ysql/the-sql-language/with-clause/traversing-general-graphs/common-code/" target="_blank">https://docs.yugabyte.com/preview/api/ysql/the-sql-language/with-clause/traversing-general-graphs/common-code/</a><br></div></div><div>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...<br></div><div><br></div><div>2.) </div><div>Or use pgr_KSP - if you're only interested in the final result and you're not attached to the purely recursive SQL solution. <br></div><div>And it's much more optimal for large graphs as well. </div><div>Here, you just need to provide a large enough K value (e.g., ~ maximum (integer/bigint) value) and then you get all possible paths. </div><div>Or if you're only interested in the top 2, then set K=2.<br></div><div><br></div><div><a href="https://docs.pgrouting.org/latest/en/pgr_KSP.html" target="_blank">https://docs.pgrouting.org/latest/en/pgr_KSP.html</a><br></div><div><span style="font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:14px"><font color="#0000ff">"The K shortest path routing algorithm based on Yen’s algorithm<b>. “K” is the number of shortest paths desired.</b>"</font></span><br></div><div><a href="https://en.wikipedia.org/wiki/K_shortest_path_routing" target="_blank">https://en.wikipedia.org/wiki/K_shortest_path_routing</a><br></div><div><br></div><div><span style="color:rgb(51,51,51);font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:14px">regards,</span></div><div><span style="color:rgb(51,51,51);font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:14px"> Imre</span></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Shaozhong SHI <<a href="mailto:shishaozhong@gmail.com" target="_blank">shishaozhong@gmail.com</a>> ezt írta (időpont: 2023. júl. 17., H, 9:01):<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Which one is the best example for finding all paths with recursive query?<div><br></div><div>Regards,</div><div><br></div><div>David</div></div>
_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/postgis-users" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-users</a><br>
</blockquote></div>
</blockquote></div>
_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/postgis-users" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-users</a><br>
</blockquote></div>
_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/postgis-users" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-users</a><br>
</blockquote></div>
_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/postgis-users" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-users</a><br>
</blockquote></div>
</blockquote></div>