3 ms·

Ah, 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

Ah, 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 ago
Aha, 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 ago
  Well, 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.

twic 4y ago

Aha, 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 ago
Well, 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.