cwida / duckpgq-extension

DuckDB extension that adds support for SQL/PGQ
https://duckpgq.notion.site/b8ac652667964f958bfada1c3e53f1bb?v=3b47a8d44bdf4e0c8b503bf23f1b76f2
MIT License
73 stars 7 forks source link

Support path-finding on undirected edges #136

Closed Dtenwolde closed 2 months ago

Dtenwolde commented 2 months ago

Fixes #87

This PR adds support for path-finding on undirected edges. Building an undirected CSR and then performing MS-BFS over this CSR. It can be done both inside named subpaths and outside.

Example query:

CREATE TABLE Student(id BIGINT, name VARCHAR);INSERT INTO Student VALUES (0, 'Daniel'), (1, 'Tavneet'), (2, 'Gabor'), (3, 'Peter'), (4, 'David');
CREATE TABLE know(src BIGINT, dst BIGINT, id BIGINT);INSERT INTO know VALUES (0,1, 10), (0,2, 11), (0,3, 12), (3,0, 13), (1,2, 14), (1,3, 15), (2,3, 16), (4,3, 17), (2, 4, 18);
FROM GRAPH_TABLE (pg
    MATCH
    o = ANY SHORTEST (a:Student WHERE a.id = 0)-[e:know]-{0,2}(b:Student)
    COLUMNS (a.id as a_id, b.id as b_id, path_length(o))
    )
    ORDER BY a_id, b_id;