How do i find all connected nodes?

Question

Lets say I have a table with Nodes and one table with Links that lets you create a link between two Nodes. How do I get the whole "web" of Nodes from just one Node ID? I have tried to visualize my problem like this:

As you can see, the Links don't form a chain like a linked list so a normal recursive query does not return all the Nodes in this web. If I start with ID 1, it will only return: 1, 2 and 3.

UPDATE: example with simple recursive query and sample data

WITH RECURSIVE links AS (
    SELECT 1 AS id_from, 2 AS id_to 
    UNION
    SELECT 2 AS id_from, 3 AS id_to 
    UNION
    SELECT 4 AS id_from, 3 AS id_to 
), web AS (
    SELECT
        l.id_from,
        l.id_to
    FROM
        links AS l
    WHERe
        id_from = 1

    UNION ALL

    SELECT
        l.id_from,
        l.id_to
    FROM
        links AS l
        jOIN web ON l.id_from = web.id_to
)

SELECT
    *
FROM
    web

OUTPUT:

id_from  |id_to
________________
      1  |     2
      2  |     3

What I would like is for the link between 4 and 3 to be included in the result.

UPDATE 2: what I am trying to achieve:

I am creating a web app without user registration. Each device is given a unique ID, but I want to make it possible to recognize a user across several devices/browsers. For this to be possible the user must be able to link their devices together. Each user will have their own cluster of device IDs like in the image above. The reason I need this query is so that I can retrieve all the devices in the cluster using any of the linked devices IDs.

Cyclic vs acyclic: I will not allow links between two nodes that are aleary apart of the cluster, will this make the graph acyclic?

Please show your recursive query and sample input data as CTE. To your question: it seems you don't need edge orientation. Before invoking recursive query, prepare helper CTE with edges reversed. You will also need to memoize traversed edges. This answer could be inspiration for you https://stackoverflow.com/a/44802524/653539 (note it is for Oracle). — Tomáš Záluský, Jun 09 '20 at 09:39
@wildplasser Yes, you should be able to link between any nodes in any direction — Pådne, Jun 09 '20 at 10:09
@wildplasser, if OP doesn't need edge orientation, the graph is cyclic all the way. — Serg, Jun 09 '20 at 10:31
The drawing has arrowheads, and the names are id_from , id_to, so the graph is directed. But it could be made cyclic, by adding some more arrows. (the example data is acyclic, it is a plain tree) To the OP: (cyclic vs acyclic) you are looking for a (minimal) spanning tree. (undirected) — wildplasser, Jun 09 '20 at 12:30
Extra question: can a device *ever* be used by two different users? — wildplasser, Jun 09 '20 at 12:36
I don't imagine one device being used by several users. The drawing has arrow heads and the names are suffixed with to/from because it made sense to me since one device is being linked from another device. But I will present the linked devices to the user as a list, because it doesn't matter to them how the devices has been linked. Is there a better/more logical way of storing the linked devices? — Pådne, Jun 09 '20 at 16:46

score 1 · Answer 1 · answered Jun 09 '20 at 11:41

Try this. I didn't test it so much, take it as a starting point:

WITH RECURSIVE links0 AS (
    SELECT 1 AS id_from, 2 AS id_to 
    UNION
    SELECT 2 AS id_from, 3 AS id_to 
    UNION
    SELECT 4 AS id_from, 3 AS id_to 
), links as (
  select id_from, id_to from links0 union select id_to, id_from from links0
), web (id_from,id_to,seen) AS (
    SELECT
        l.id_from,
        l.id_to,
        array[least(l.id_from,l.id_to)||'-'||greatest(l.id_from,l.id_to)]
    FROM
        links AS l
    WHERe
        id_from = 1

    UNION ALL

    SELECT
        l.id_from,
        l.id_to,
        web.seen || (least(l.id_from,l.id_to)||'-'||greatest(l.id_from,l.id_to))
    FROM
        links AS l
        jOIN web ON l.id_from = web.id_to
        and not (least(l.id_from,l.id_to)||'-'||greatest(l.id_from,l.id_to) = any(web.seen))
)

SELECT
    *
FROM
    web

The links CTE has edges reversed, then the seen array keeps visited edges in canonical form.

Db fiddle.

How do i find all connected nodes?

1 Answers1