5 ms·
I think the only way to build the path up is to do it as you're traversing, though. Here's a small example: create table node ( name varchar primary key
by twic 4y ago
I think the only way to build the path up is to do it as you're traversing, though.
Here's a small example:
create table node (
name varchar primary key
);
create table edge (
from_name varchar not null references node (name),
to_name varchar not null references node (name)
);
insert into node values
('Hawaii'),
('San Francisco'),
('New York'),
('Houston');
insert into edge values
('Hawaii', 'San Francisco'),
('San Francisco', 'New York'),
('San Francisco', 'Houston'),
('Houston', 'New York');
with recursive route (destination_name, path) as (
values ('Hawaii', 'Hawaii')
union
select to_name, route.path || ' -> ' || to_name
from route
join edge on route.destination_name = edge.from_name
)
select * from route;
That works as long as the graph is acyclic. If you add an edge from New York to Houston, say, then the query goes into an infinite loop.
How would you do this after computing the transitive closure? And how would that avoid an infinite loop?
- cryptonector 4y agoAh, yes, I flubbed -- this one requires aggregation as you go. It's tricky. Ideally you could have a decent aggregation data structure for the path that lets you select a distinct sequence (path) of middle points. One could write such an aggregation function, I think. Lacking that you have to limit the length of all paths between any pair of points to the longest possible path (which is the number of points minus one), which is annoying, and then you still have to fix up each resulting path to remove any repeating suffix. sqlite> .schema CREATE TABLE edge (src text, dst text); sqlite> with recursive paths (src, dst, len, path) as ( ...> select src, dst, 0, src || '->' || dst from edge ...> union ...> select p.src, e.dst, p.len + 1, p.path || '->' || e.src from paths p join edge e on p.dst = e.src where p.len < (select count(*) from (select src from edge union select dst from edge))) select * from paths; Hawaii|San Francisco|0|Hawaii->San Francisco San Francisco|New York|0|San Francisco->New York San Francisco|Houston|0|San Francisco->Houston Houston|New York|0|Houston->New York Houston|Hawaii|0|Houston->Hawaii Hawaii|Houston|1|Hawaii->San Francisco->San Francisco Hawaii|New York|1|Hawaii->San Francisco->San Francisco San Francisco|Hawaii|1|San Francisco->Houston->Houston San Francisco|New York|1|San Francisco->Houston->Houston Houston|San Francisco|1|Houston->Hawaii->Hawaii Hawaii|Hawaii|2|Hawaii->San Francisco->San Francisco->Houston Hawaii|New York|2|Hawaii->San Francisco->San Francisco->Houston San Francisco|San Francisco|2|San Francisco->Houston->Houston->Hawaii Houston|Houston|2|Houston->Hawaii->Hawaii->San Francisco Houston|New York|2|Houston->Hawaii->Hawaii->San Francisco Hawaii|San Francisco|3|Hawaii->San Francisco->San Francisco->Houston->Hawaii San Francisco|Houston|3|San Francisco->Houston->Houston->Hawaii->San Francisco San Francisco|New York|3|San Francisco->Houston->Houston->Hawaii->San Francisco Houston|Hawaii|3|Houston->Hawaii->Hawaii->San Francisco->Houston Houston|New York|3|Houston->Hawaii->Hawaii->San Francisco->Houston Hawaii|Houston|4|Hawaii->San Francisco->San Francisco->Houston->Hawaii->San Francisco Hawaii|New York|4|Hawaii->San Francisco->San Francisco->Houston->Hawaii->San Francisco San Francisco|Hawaii|4|San Francisco->Houston->Houston->Hawaii->San Francisco->Houston San Francisco|New York|4|San Francisco->Houston->Houston->Hawaii->San Francisco->Houston Houston|San Francisco|4|Houston->Hawaii->Hawaii->San Francisco->Houston->Hawaii sqlite>
- twic 4y agoAha, nice, i didn't think of just limiting it that way! The need to postprocess this is annoying but only very mildly; i think it takes a fairly simple window function. I had a go at changing my query to only produce one route to each node, by excluding rows in the recursive step which go to a node for which we already have a destination, but i couldn't find a way to do it which PostgreSQL would accept, because you can't use the recursive table in an outer join or a subquery. The PostgreSQL has some advice about dealing with cycles, but i haven't worked up the mental energy to absorb it: https://www.postgresql.org/docs/14/queries-with.html#QUERIES-WITH-CYCLE https://www.postgresql.org/docs/14/queries-with.html#QUERIES...
- cryptonector 4y agoWell, it's a nice trick but it's O(N^2) in terms of output size because you have N items and paths up to N-1 long, so you have up to N ~N-length paths. If your data is guaranteed to have loops then this could be annoying. The PG thing works trivially because you can use an array for the path and inspect the array in each iteration. That's harder to do in SQLite3, but... you could: just format a string like '%->' || src || '->%' then use it with `like()` to check if the path you're adding `src` to already has it.