Create support for SHORTEST path

[Dtenwolde]

This query will return a list of rowids alternating between the vertex rowid and the edge rowid between a source and destination We will only support (ANY) SHORTEST path for now, there is also opportunity for ALL

[tomkom]

Did you oconsider emulating the output format of pg_routing (spatial graph extension to Postgres)? https://docs.pgrouting.org/latest/en/pgr_dijkstra.html The format avoids alternating, thus creating a heterogeneous collection. It is a simple edge list.

[Dtenwolde]

Hi Tom,

Thanks for the suggestion! What do you mean by that this format avoids alternating?

So far I have been following the SQL/PGQ specification which says the result of the PATH should be a list of alternating vertexIDs and edgeIDs ([v0, e1, v1, ..., ek, vk]). However, I do have plans to work on the path-finding functions, and then I'll keep this in mind.

[tomkom]

-- its Martin :)

What I meant is that you do not need a return table of format

V0... attribs E0...attribs V1 E1 ...

As each edge is defined bybstart/end vertex. So E0 E1 ... You can then join the vertices in... but you need to indicate if the edge is traverse in reverse.

Or, with redundancy, but easier to work with,

E0,v0,v1 E1, v1,v2 E2,v2,v3

Where you may possibly already indicate in this manner which is the direction of the edge traversed...

Hope I understood well what you do. This is if the result is a relation (table), as I would assume. See the pg routing docs.

[Dtenwolde]

Apologies Martin, that's the last time I'm guessing a first name based on their Github name :)

I sort of see what you mean, but I don't think it'll apply to how the path-finding will look like in our case. Take for example the following query:

    MATCH ANY SHORTEST p = (a WHERE a.id=1)-[e]->{0,3}(b WHERE b.id=3)
    COLUMNS(a.id, b.id, path_length(p), p)

For the following graph:

vertex

id

1

2

3

edges

edgeid	source	target
12	1	2
23	2	3

Would return 1 row:

a.id	b.id	path_length	p
1	2	2	[1, 12, 2, 23, 3]

So all the attributes of the vertices and edges that match would result in 1 row, with the actual path being represented as a list. I hope that clears up what we do :)

[tomkom]

Yes, understood. Just a bit hard to reconcile with the rest of the duckdb ecosystem operating on tables. Returning a table with a a rownum and edge id would be better, no?

On Fri, 27 Oct 2023, 3:39 pm Daniël ten Wolde, @.***> wrote:

Apologies Martin, that's the last time I'm guessing a first name based on their Github name :)

I sort of see what you mean, but I don't think it'll apply to how the path-finding will look like in our case. Take for example the following query:

MATCH ANY SHORTEST p = (a WHERE a.id=1)-[e]->{0,3}(b WHERE b.id=3) COLUMNS(a.id, b.id, path_length(p), p)

For the following graph: vertex id 1 2 3 edges edgeid source target 12 1 2 23 2 3

Would return 1 row: a.id b.id path_length p 1 2 2 [1, 12, 2, 23, 3] So all the attributes of the vertices and edges that match would result in 1 row, with the actual path being represented as a list. I hope that clears up what we do :)

— Reply to this email directly, view it on GitHub https://github.com/cwida/duckpgq-extension/issues/17#issuecomment-1782280713, or unsubscribe https://github.com/notifications/unsubscribe-auth/AALLGHQJZTJB5PTVXKRM4TTYBM3J7AVCNFSM6AAAAAAZUBPHOGVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTOOBSGI4DANZRGM . You are receiving this because you commented.Message ID: @.***>

[github-actions[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.