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

[Shaozhong SHI]

Imre Samu,

There may be nodes of bifurcation, i.e., forking.

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/16316fe3/attachment.htm>