Thanks. This does explain why.
Regards, David On Tue, 10 May 2022 at 04:48, Imre Samu <[email protected]> wrote: > > Alternatively, can we develop a test to tell whether Walk the Network > produces a traversing line, a tree or a loop? > > PostgreSQL 14 has some enhancements: > *- "The SQL-standard SEARCH and CYCLE options for common table > expressions have been implemented."* > > see* "7.8.2.2. Cycle Detection"* in the doc ( lot of examples !!!! ) > https://www.postgresql.org/docs/14/queries-with.html#QUERIES-WITH-RECURSIVE > > and https://www.postgresql.org/docs/14/sql-select.html > > *"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."* > > and some examples > > https://www.depesz.com/2021/02/04/waiting-for-postgresql-14-search-and-cycle-clauses/ > > regards, > Imre > > Shaozhong SHI <[email protected]> ezt írta (időpont: 2022. máj. 9., > H, 20:31): > >> Alternatively, can we develop a test to tell whether Walk the Network >> produces a traversing line, a tree or a loop? >> >> Regards, >> >> David >> >> On Mon, 9 May 2022 at 18:42, <[email protected]> wrote: >> >>> 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. >>> >>> Try adding: >>> insert into network values ('linestring(3 4, 2 3)', 14); >>> >>> Note that what is returned is now a tree. >>> >>> Now, try adding: >>> insert into network values ('linestring(0 0, 2 3)', 15); >>> >>> If you are patient enough, it will blow up with a memory allocation >>> error because it creates a loop in the network. >>> >>> (Again, my appreciation to Paul Ramsey for constructing such a focused >>> example.) >>> >>> 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. >>> >>> Ruven Brooks >>> >>> >>> >>> >>> >>> >>> >>> >>> On 5/9/2022 7:39 AM, Shaozhong SHI wrote: >>> >>> Hi, Imre, >>> >>> What happens if more than 1 result from the Walk the Network? >>> >>> Can recursive query return all possible results? >>> >>> How to handle such results? >>> >>> 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. >>> >>> What is your thought? >>> >>> Regards, >>> >>> David >>> >>> On Fri, 22 Apr 2022 at 22:14, Imre Samu <[email protected]> wrote: >>> >>>> > as St_intersects or recursive query used, >>>> >>>> The other alternative ( ~ less efficient ) is using a “noded” >>>> network table ( "edge_table" ) >>>> in the recursive query. ( and don't forget to add indexes to the >>>> "source" and "target" columns ) >>>> >>>> WITH RECURSIVE walk_network(id, source, target, targetPoint) AS >>>> (SELECT et.id,et.source,et.target,ST_EndPoint(the_geom) as >>>> targetPoint >>>> FROM edge_table et WHERE et.id = *12* >>>> UNION ALL >>>> SELECT e.id, e.source, e.target ,ST_EndPoint(the_geom) as >>>> targetPoint >>>> FROM edge_table e >>>> , walk_network w >>>> WHERE w.target = e.source >>>> ) >>>> SELECT ST_AsText(ST_MakeLine(targetPoint)) >>>> FROM walk_network >>>> ; >>>> +---------------------------------+ >>>> | st_astext | >>>> +---------------------------------+ >>>> | LINESTRING(4 2,3 2,2 1,1 1,0 0) | >>>> +---------------------------------+ >>>> (1 row) >>>> >>>> regards, >>>> Imre >>>> >>>> >>>> Imre Samu <[email protected]> ezt írta (időpont: 2022. ápr. 22., P, >>>> 16:39): >>>> >>>>> > With a large data set, >>>>> >>>>> :-) >>>>> please give more detail: >>>>> - How large? >>>>> - and what is your real "business problem"? what type of network? >>>>> >>>>> >>>>> > I tried to use this >>>>> http://blog.cleverelephant.ca/2010/07/network-walking-in-postgis.html in >>>>> the PostGIS. >>>>> >>>>> As I see this is a directed "network graph", and I will try using the >>>>> pgRouting tool - for a large graph! >>>>> *( "pgRouting extends the PostGIS/PostgreSQL geospatial database to >>>>> provide geospatial routing and other network analysis functionality." )* >>>>> The pgRouting project did not exist in 2010/07 when this blogpost >>>>> was written! >>>>> >>>>> [image: image.png] >>>>> >>>>> so I have adapted the example network ( from the original blogpost ) >>>>> to pgRouting and this is my sample result >>>>> >>>>> ---------- ALL "downstream path" from "all deadends" sorted by >>>>> descending cost --------- >>>>> >>>>> +------------+-----------+---------+-------------------------------------+--------------+ >>>>> | route_cost | start_vid | end_vid | the_geom_text >>>>> | edge_ids | >>>>> >>>>> +------------+-----------+---------+-------------------------------------+--------------+ >>>>> | 6.24 | 3044 | 3000 | LINESTRING(4 4,3 4,2 3,1 2,1 1,0 >>>>> 0) | {13,9,6,3,1} | >>>>> | 5.83 | 3043 | 3000 | *LINESTRING(4 3,4 2,3 2,2 1,1 >>>>> 1,0 0) | {12,8,5,2,1} |* >>>>> | 4.83 | 3024 | 3000 | LINESTRING(2 4,2 3,1 2,1 1,0 0) >>>>> | {10,6,3,1} | >>>>> | 4.41 | 3014 | 3000 | LINESTRING(1 4,1 3,1 2,1 1,0 0) >>>>> | {11,7,3,1} | >>>>> | 3.41 | 3031 | 3000 | LINESTRING(3 1,2 1,1 1,0 0) >>>>> | {4,2,1} | >>>>> >>>>> +------------+-----------+---------+-------------------------------------+--------------+ >>>>> and the second line is same as in the blogpost ( *"Downstream(12)" >>>>> *example) >>>>> , >>>>> just with an extra "deadends" points ; the edges :* >>>>> {12,8,5,2,1} * >>>>> >>>>> start_vid : starting node/vertex id ( "deadends" in this example ) >>>>> end_vid : ending node/vertex id constant 3000 (0,0) >>>>> node/vertex id = 3000 + X*10+Y coordinate // ( 2,1 ) --> 3021 ; >>>>> (0,0) --> 3000 >>>>> >>>>> >>>>> > Whenever geospatial functions such as St_intersects or recursive >>>>> query used, >>>>> >>>>> IMHO: A good scalable data model is extremely important. >>>>> pgRouting has 2 important (separated) steps. >>>>> - creating a routing topology - route optimized database ( with >>>>> "start" - and "end" node/vertex ) >>>>> - fast routing/graph/"network-walking" functions - without the >>>>> geometry ( using Boost Graph c++ library ) >>>>> ( in this example I have used >>>>> https://docs.pgrouting.org/3.3/en/pgr_dijkstra.html ) >>>>> >>>>> >>>>> and this is my adapted "routing" topology edge table : >>>>> >>>>> DROP TABLE IF EXISTS edge_table CASCADE; >>>>> CREATE TABLE edge_table ( >>>>> id bigint primary key, >>>>> source bigint, >>>>> target bigint, >>>>> cost float, >>>>> reverse_cost float, >>>>> the_geom geometry >>>>> ); >>>>> -- network example from >>>>> -- >>>>> http://blog.cleverelephant.ca/2010/07/network-walking-in-postgis.html >>>>> INSERT INTO edge_table VALUES( 1, 3011, 3000, 1, -1, 'LINESTRING(1 1, >>>>> 0 0)'); >>>>> INSERT INTO edge_table VALUES( 2, 3021, 3011, 1, -1, 'LINESTRING(2 1, >>>>> 1 1)'); >>>>> INSERT INTO edge_table VALUES( 3, 3012, 3011, 1, -1, 'LINESTRING(1 2, >>>>> 1 1)'); >>>>> INSERT INTO edge_table VALUES( 4, 3031, 3021, 1, -1, 'LINESTRING(3 1, >>>>> 2 1)'); >>>>> INSERT INTO edge_table VALUES( 5, 3032, 3021, 1, -1, 'LINESTRING(3 2, >>>>> 2 1)'); >>>>> INSERT INTO edge_table VALUES( 6, 3023, 3012, 1, -1, 'LINESTRING(2 3, >>>>> 1 2)'); >>>>> INSERT INTO edge_table VALUES( 7, 3013, 3012, 1, -1, 'LINESTRING(1 3, >>>>> 1 2)'); >>>>> INSERT INTO edge_table VALUES( 8, 3042, 3032, 1, -1, 'LINESTRING(4 2, >>>>> 3 2)'); >>>>> INSERT INTO edge_table VALUES( 9, 3034, 3023, 1, -1, 'LINESTRING(3 4, >>>>> 2 3)'); >>>>> INSERT INTO edge_table VALUES(10, 3024, 3023, 1, -1, 'LINESTRING(2 4, >>>>> 2 3)'); >>>>> INSERT INTO edge_table VALUES(11, 3014, 3013, 1, -1, 'LINESTRING(1 4, >>>>> 1 3)'); >>>>> INSERT INTO edge_table VALUES(12, 3043, 3042, 1, -1, 'LINESTRING(4 3, >>>>> 4 2)'); >>>>> INSERT INTO edge_table VALUES(13, 3044, 3034, 1, -1, 'LINESTRING(4 4, >>>>> 3 4)'); >>>>> >>>>> full example code - with data&code: >>>>> https://gist.github.com/ImreSamu/efda6093b67391a0edafff39d8056cb5 >>>>> >>>>> if you are interested in more examples.. check the pgRouting tutorial >>>>> for example: *"Pre-processing waterways data"* >>>>> >>>>> https://workshop.pgrouting.org/2.7/en/un_sdg/sdg11-cities.html#pre-processing-waterways-data >>>>> >>>>> regards, >>>>> Imre >>>>> >>>>> >>>>> Shaozhong SHI <[email protected]> ezt írta (időpont: 2022. ápr. >>>>> 22., P, 1:22): >>>>> >>>>>> 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. >>>>>> >>>>>> That forced me to try out to do the some tasks on the FME server. >>>>>> >>>>>> I tried to use this http://blog.cleverelephant.ca/2010/07/network >>>>>> -walking-in-postgis.html in the PostGIS. >>>>>> >>>>>> I tried to linecombiner in FME. LineCombiner | FME (safe.com) >>>>>> <https://www.safe.com/transformers/line-combiner/>. >>>>>> >>>>>> With a large data set, the running of processors were monitored. It >>>>>> was estimated the PostGIS one would take 16 days to complete. >>>>>> >>>>>> But, it only took a few minute to do the same thing in FME. >>>>>> >>>>>> This suggests that something is not right with the PostGIS Server. >>>>>> >>>>>> Have anyone got experience with configuration and improving >>>>>> perfomance of PostGIS Server? >>>>>> >>>>>> Regards, >>>>>> >>>>>> David >>>>>> _______________________________________________ >>>>>> postgis-users mailing list >>>>>> [email protected] >>>>>> https://lists.osgeo.org/mailman/listinfo/postgis-users >>>>>> >>>>> _______________________________________________ >>>> postgis-users mailing list >>>> [email protected] >>>> https://lists.osgeo.org/mailman/listinfo/postgis-users >>>> >>> >>> _______________________________________________ >>> postgis-users mailing >>> [email protected]https://lists.osgeo.org/mailman/listinfo/postgis-users >>> >>> >>> _______________________________________________ >>> postgis-users mailing list >>> [email protected] >>> https://lists.osgeo.org/mailman/listinfo/postgis-users >>> >> _______________________________________________ >> postgis-users mailing list >> [email protected] >> https://lists.osgeo.org/mailman/listinfo/postgis-users >> > _______________________________________________ > postgis-users mailing list > [email protected] > https://lists.osgeo.org/mailman/listinfo/postgis-users >
_______________________________________________ postgis-users mailing list [email protected] https://lists.osgeo.org/mailman/listinfo/postgis-users
