<div dir="ltr">Hello, Ruven Brooks,<div><br></div><div>Thank you for sharing the insight. That is very interesting for advancing out understanding.</div><div><br></div><div>What do you think about the following strategy for conducting traversing test?</div><div><br></div><div>Step 1. Find all circular loops formed by lines in a data set. </div><div><br></div><div>Step 2. Remove all such loops in the data set.</div><div><br></div><div>Step 3. Apply Walk the Network to carry out traversing test.</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, 9 May 2022 at 18:42, <<a href="mailto:ruvenml@beamerbrooks.com">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:180aa04d217cb971f161" 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>