<div dir="ltr"><div>Hi David,<br></div><div><br></div>> I am not sure about whether this approach would break endless loop in recursive queries.<div>> ...</div><div>> How about add one column in your examples - a column called count? <br></div><div>> ...</div><div><br></div><div>You should test the idea(s) to see if it works.</div>It is a learning process .. and with learning comes the fact that sometimes it is not easy to understand the processes and the algorithm.<br><div><br><div>and please check the "SEARCH and CYCLE options for common table expressions"<br></div><div>Once you have a good understanding of RECURSIVE CTE, the solution will be simple.<br></div><div><br>Please be patient.<br></div></div><div><br></div><div>regards,</div><div>Imre</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Shaozhong SHI <<a href="mailto:shishaozhong@gmail.com">shishaozhong@gmail.com</a>> ezt írta (időpont: 2022. máj. 11., Sze, 0:43):<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 dir="ltr">I am not sure about whether this approach would break endless loop in recursive queries.<div><br></div><div><a href="https://stackoverflow.com/questions/59445572/how-to-avoid-recursive-endless-cycle-postgresql" target="_blank">sql - How to avoid recursive endless cycle? (postgreSQL) - Stack Overflow</a><br></div><div><br></div><div>Any idea?</div><div><br></div><div>Regards,</div><div><br></div><div>David</div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, 10 May 2022 at 04:48, 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">> Alternatively, can we develop a test to tell whether Walk the Network produces a traversing line, a tree or a loop?<div><br></div><div>PostgreSQL 14 has some enhancements:<br></div><div><b><font color="#0000ff">- "The SQL-standard SEARCH and CYCLE options for common table expressions have been implemented."</font></b></div><div><br></div><div>see<b><font color="#0000ff"> "7.8.2.2. Cycle Detection"</font></b> in the doc ( lot of examples !!!! ) <br></div><div><a href="https://www.postgresql.org/docs/14/queries-with.html#QUERIES-WITH-RECURSIVE" target="_blank">https://www.postgresql.org/docs/14/queries-with.html#QUERIES-WITH-RECURSIVE</a><br></div><div><br></div><div>and <a href="https://www.postgresql.org/docs/14/sql-select.html" target="_blank">https://www.postgresql.org/docs/14/sql-select.html</a></div><div><i>"The optional CYCLE clause is used to detect cycles in recursive queries. The supplied column name list specifies the row key that is to be used for keeping track of visited rows. A column named cycle_mark_col_name will be added to the result column list of the WITH query. This column will be set to cycle_mark_value when a cycle has been detected, else to cycle_mark_default. Furthermore, processing of the recursive union will stop when a cycle has been detected. cycle_mark_value and cycle_mark_default must be constants and they must be coercible to a common data type, and the data type must have an inequality operator. (The SQL standard requires that they be Boolean constants or character strings, but PostgreSQL does not require that.) By default, TRUE and FALSE (of type boolean) are used. Furthermore, a column named cycle_path_col_name will be added to the result column list of the WITH query. This column is used internally for tracking visited rows. See Section 7.8.2.2 for examples."<br></i></div><div><br></div><div>and some examples</div><div><a href="https://www.depesz.com/2021/02/04/waiting-for-postgresql-14-search-and-cycle-clauses/" target="_blank">https://www.depesz.com/2021/02/04/waiting-for-postgresql-14-search-and-cycle-clauses/</a><br></div><div><br></div><div>regards,</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: 2022. máj. 9., H, 20:31):<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">Alternatively, can we develop a test to tell whether Walk the Network produces a traversing line, a tree or a loop?<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, 9 May 2022 at 18:42, <<a href="mailto:ruvenml@beamerbrooks.com" target="_blank">ruvenml@beamerbrooks.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>
<font face="Helvetica, Arial, sans-serif">The Walk the Network
algorithm returns all points reachable from a particular starting
point. The result is a tree. It only appears to be a single
line because the network given as an example has been constructed
without branches.<br>
<br>
Try adding: <br>
insert into network values ('linestring(3 4, 2 3)', 14);<br>
<br>
Note that what is returned is now a tree.<br>
<br>
Now, try adding: <br>
insert into network values ('linestring(0 0, 2 3)', 15);<br>
<br>
If you are patient enough, it will blow up with a memory
allocation error because it creates a loop in the network. <br>
<br>
(Again, my appreciation to Paul Ramsey for constructing such a
focused example.)<br>
<br>
Does a tree structure of paths starting at a designated node and
ending at any node which has no outgoing edges satisfy your
requirements or do you want the minimum cost/distance path? If
so, you have lots of algorithms to choose from and watching some
videos on graph theory might be time well spent.<br>
<br>
Ruven Brooks<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
</font><br>
<div>On 5/9/2022 7:39 AM, Shaozhong SHI
wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">Hi, Imre,
<div><br>
</div>
<div>What happens if more than 1 result from the Walk the
Network?</div>
<div><br>
</div>
<div>Can recursive query return all possible results?</div>
<div><br>
</div>
<div>How to handle such results?</div>
<div><br>
</div>
<div>My guess that memory allocation error occurred because that
more than 1 result is found and the recursive query does not
know what to do.</div>
<div><br>
</div>
<div>What is your thought?</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 Fri, 22 Apr 2022 at 22:14,
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">
<div>> as St_intersects or recursive query used,</div>
<div><br>
</div>
The other alternative ( ~ less efficient ) is using a
“noded” network table ( "edge_table" )
<div>in the recursive query. ( and don't forget to add
indexes to the "source" and "target" columns )</div>
<div>
<div><br>
</div>
<div><font face="monospace">WITH RECURSIVE
walk_network(id, source, target, targetPoint) AS <br>
(SELECT <a href="http://et.id" target="_blank">et.id</a>,et.source,et.target,ST_EndPoint(the_geom)
as targetPoint <br>
FROM edge_table et WHERE <a href="http://et.id" target="_blank">et.id</a> = <b><font color="#0000ff">12</font></b><br>
UNION ALL<br>
SELECT <a href="http://e.id" target="_blank">e.id</a>, e.source, e.target
,ST_EndPoint(the_geom) as targetPoint<br>
FROM edge_table e<br>
, walk_network w<br>
WHERE w.target = e.source<br>
)<br>
SELECT ST_AsText(ST_MakeLine(targetPoint))<br>
FROM walk_network<br>
;<br>
+---------------------------------+<br>
| st_astext |<br>
+---------------------------------+<br>
| LINESTRING(4 2,3 2,2 1,1 1,0 0) |<br>
+---------------------------------+<br>
(1 row)</font><br>
</div>
</div>
<div><font face="monospace"><br>
</font></div>
<div><font face="monospace">regards,</font></div>
<div><font face="monospace"> Imre</font></div>
<div><font face="monospace"><br>
</font></div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">Imre Samu <<a href="mailto:pella.samu@gmail.com" target="_blank">pella.samu@gmail.com</a>>
ezt írta (időpont: 2022. ápr. 22., P, 16:39):<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>> With a large data set,</div>
<div><br>
</div>
<div>:-) </div>
<div>please give more detail:</div>
<div>- How large? </div>
<div>- and what is your real "business problem"? what
type of network? </div>
<div><br>
</div>
<div><br>
</div>
<div>> I tried to use this <a href="http://blog.cleverelephant.ca/2010/07/network-walking-in-postgis.html" target="_blank">http://blog.cleverelephant.ca/2010/07/network-walking-in-postgis.html</a> in
the PostGIS.</div>
<div><br>
</div>
<div>As I see this is a directed "network graph", and I
will try using the pgRouting tool - for a large
graph! <br>
</div>
<div><i>( "pgRouting extends the PostGIS/PostgreSQL
geospatial database to provide geospatial routing <b><font color="#0000ff">and other network analysis
functionality.</font></b>" )</i></div>
<div>The pgRouting project did not exist in 2010/07
when this blogpost was written! </div>
<div><br>
</div>
<div><img src="cid:180aa15543ecb971f161" alt="image.png" width="238" height="210"><br>
</div>
<div><br>
</div>
<div>so I have adapted the example network ( from the
original blogpost ) </div>
<div> to pgRouting and this is my sample result </div>
<div><br>
</div>
<div>---------- ALL "downstream path" from "all
deadends" sorted by descending cost ---------</div>
<div><span style="font-family:monospace">+------------+-----------+---------+-------------------------------------+--------------+</span><br>
</div>
<div><font face="monospace">| route_cost | start_vid |
end_vid | the_geom_text |
edge_ids |<br>
+------------+-----------+---------+-------------------------------------+--------------+<br>
| 6.24 | 3044 | 3000 | LINESTRING(4
4,3 4,2 3,1 2,1 1,0 0) | {13,9,6,3,1} |<br>
| 5.83 | 3043 | 3000 | <b><font color="#0000ff">LINESTRING(4 3,4 2,3 2,2 1,1 1,0
0) | {12,8,5,2,1} |</font></b><br>
| 4.83 | 3024 | 3000 | LINESTRING(2
4,2 3,1 2,1 1,0 0) | {10,6,3,1} |<br>
| 4.41 | 3014 | 3000 | LINESTRING(1
4,1 3,1 2,1 1,0 0) | {11,7,3,1} |<br>
| 3.41 | 3031 | 3000 | LINESTRING(3
1,2 1,1 1,0 0) | {4,2,1} |<br>
+------------+-----------+---------+-------------------------------------+--------------+</font><br>
</div>
<div>
<div>and the second line is same as in the blogpost (
<i>"Downstream(12)" </i>example) , </div>
<div>just with an extra "deadends" points ; the
edges :<b><font color="#0000ff"> {12,8,5,2,1} </font></b></div>
<div><br>
</div>
</div>
<div>start_vid : starting node/vertex id ( "deadends" in
this example )</div>
<div>end_vid : ending node/vertex id constant 3000
(0,0) </div>
<div>node/vertex id = 3000 + X*10+Y coordinate // (
2,1 ) --> 3021 ; (0,0) --> 3000</div>
<div><br>
</div>
<div><br>
</div>
<div>> Whenever geospatial functions such as
St_intersects or recursive query used,<br>
</div>
<div><br>
</div>
<div>IMHO: A good scalable data model is extremely
important.</div>
<div>pgRouting has 2 important (separated) steps.</div>
<div>- creating a routing topology - route optimized
database ( with "start" - and "end" node/vertex )</div>
<div>- fast routing/graph/"network-walking" functions -
without the geometry ( using Boost Graph c++ library
) <br>
</div>
<div> ( in this example I have used <a href="https://docs.pgrouting.org/3.3/en/pgr_dijkstra.html" target="_blank">https://docs.pgrouting.org/3.3/en/pgr_dijkstra.html</a>
)</div>
<div><br>
</div>
<div><br>
</div>
<div>and this is my adapted "routing" topology edge
table : </div>
<div><br>
</div>
<div><font size="1" face="monospace">DROP TABLE IF
EXISTS edge_table CASCADE;<br>
CREATE TABLE edge_table (<br>
id bigint primary key,<br>
source bigint,<br>
target bigint,<br>
cost float,<br>
reverse_cost float,<br>
the_geom geometry<br>
);<br>
-- network example from<br>
-- <a href="http://blog.cleverelephant.ca/2010/07/network-walking-in-postgis.html" target="_blank">http://blog.cleverelephant.ca/2010/07/network-walking-in-postgis.html</a><br>
INSERT INTO edge_table VALUES( 1, 3011, 3000, 1, -1,
'LINESTRING(1 1, 0 0)');<br>
INSERT INTO edge_table VALUES( 2, 3021, 3011, 1, -1,
'LINESTRING(2 1, 1 1)');<br>
INSERT INTO edge_table VALUES( 3, 3012, 3011, 1, -1,
'LINESTRING(1 2, 1 1)');<br>
INSERT INTO edge_table VALUES( 4, 3031, 3021, 1, -1,
'LINESTRING(3 1, 2 1)');<br>
INSERT INTO edge_table VALUES( 5, 3032, 3021, 1, -1,
'LINESTRING(3 2, 2 1)');<br>
INSERT INTO edge_table VALUES( 6, 3023, 3012, 1, -1,
'LINESTRING(2 3, 1 2)');<br>
INSERT INTO edge_table VALUES( 7, 3013, 3012, 1, -1,
'LINESTRING(1 3, 1 2)');<br>
INSERT INTO edge_table VALUES( 8, 3042, 3032, 1, -1,
'LINESTRING(4 2, 3 2)');<br>
INSERT INTO edge_table VALUES( 9, 3034, 3023, 1, -1,
'LINESTRING(3 4, 2 3)');<br>
INSERT INTO edge_table VALUES(10, 3024, 3023, 1, -1,
'LINESTRING(2 4, 2 3)');<br>
INSERT INTO edge_table VALUES(11, 3014, 3013, 1, -1,
'LINESTRING(1 4, 1 3)');<br>
INSERT INTO edge_table VALUES(12, 3043, 3042, 1, -1,
'LINESTRING(4 3, 4 2)');<br>
INSERT INTO edge_table VALUES(13, 3044, 3034, 1, -1,
'LINESTRING(4 4, 3 4)');<br>
</font></div>
<div><br>
</div>
<div>full example code - with data&code: <a href="https://gist.github.com/ImreSamu/efda6093b67391a0edafff39d8056cb5" target="_blank">https://gist.github.com/ImreSamu/efda6093b67391a0edafff39d8056cb5</a> <br>
</div>
<div><br>
</div>
<div>if you are interested in more examples.. check the
pgRouting tutorial</div>
<div>for example: <b>"Pre-processing waterways data"</b><br>
</div>
<div> <a href="https://workshop.pgrouting.org/2.7/en/un_sdg/sdg11-cities.html#pre-processing-waterways-data" target="_blank">https://workshop.pgrouting.org/2.7/en/un_sdg/sdg11-cities.html#pre-processing-waterways-data</a><br>
</div>
<div><br>
</div>
<div>regards,</div>
<div> Imre</div>
<div><br>
</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: 2022. ápr. 22., P, 1: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">
<div dir="ltr">
<div dir="ltr">Whenever geospatial functions such
as St_intersects or recursive query used, the
PostGIS appears to spawn away to many child
queries and just obliterate the CPU. Nothing
finishes.
<div><br>
</div>
<div>That forced me to try out to do the some
tasks on the FME server.</div>
<div><br>
</div>
<div>I tried to use this <a href="http://blog.cleverelephant.ca/2010/07/network-walking-in-postgis.html" target="_blank">http://blog.cleverelephant.ca/2010/07/<span>network</span>-walking-in-postgis.html</a> in
the PostGIS.</div>
<div><br>
</div>
<div>I tried to linecombiner in FME. <a href="https://www.safe.com/transformers/line-combiner/" target="_blank">LineCombiner
| FME (safe.com)</a>.</div>
<div><br>
</div>
<div>With a large data set, the running of
processors were monitored. It was estimated
the PostGIS one would take 16 days to
complete.</div>
<div><br>
</div>
<div>But, it only took a few minute to do the
same thing in FME.</div>
<div><br>
</div>
<div>This suggests that something is not right
with the PostGIS Server.</div>
<div><br>
</div>
<div>Have anyone got experience with
configuration and improving perfomance of
PostGIS Server?</div>
<div><br>
</div>
<div>Regards,</div>
<div><br>
</div>
<div>David</div>
</div>
</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>
<fieldset></fieldset>
<pre>_______________________________________________
postgis-users mailing list
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a>
<a href="https://lists.osgeo.org/mailman/listinfo/postgis-users" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-users</a>
</pre>
</blockquote>
<br>
</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>
_______________________________________________<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>