[postgis-users] best finding all paths with recursive query

[Shaozhong SHI]

The data is here.

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);
CREATE INDEX network_gix ON network USING GIST (segment);


Add insert into network values ('linestring(1 1, 1 0)', 14);

or insert into network values ('linestring(1 1, 0 1)', 15);
Source:
Network Walking in PostGIS · Paul Ramsey (cleverelephant.ca)
<http://blog.cleverelephant.ca/2010/07/network-walking-in-postgis.html>


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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20230718/88df8fed/attachment.htm>