Pattern

Walking a graph without looping

A recursive query over links that can loop must carry its path and refuse to revisit a node.

A hierarchy has no loops, a graph of links (shared cards, referrals, friendships) does. Carry the path as text (',1,', then path || next || ',') and add WHERE path NOT LIKE '%,' || next || ',%' to the recursive step: a node already on the path is not visited again. The commas around each id keep 1 from matching 12. This works on every engine; arrays do the same where they exist (<> ALL(path) on Postgres, NOT IN UNNEST(path) on BigQuery). Cap the depth on real data, since the number of paths grows fast, and keep the smallest distance per node at the end.

WITH RECURSIVE links(a, b) AS (VALUES (1, 2), (2, 1), (2, 3), (3, 2), (3, 1), (1, 3), (3, 4), (4, 3)),
walk AS (
  SELECT 1 AS node, 0 AS distance, CAST(',1,' AS VARCHAR) AS path
  UNION ALL
  SELECT l.b, w.distance + 1, w.path || CAST(l.b AS VARCHAR) || ','
  FROM walk w
  JOIN links l ON l.a = w.node
  WHERE w.path NOT LIKE '%,' || CAST(l.b AS VARCHAR) || ',%'
)
SELECT node, MIN(distance) AS distance
FROM walk
WHERE node <> 1
GROUP BY node
ORDER BY node;

node	distance
2	1
3	1
4	2

Try it in Randori

Practise:Linked through a shared card