How to count all the connected nodes (rows) in a graph on Postgres?

Question

My table has account_id and device_id. One account_id could have multiple device_ids and vice versa. I am trying to count the depth of each connected many-to-many relationship.

Ex:

account_id | device_id
1 | 10
1 | 11
1 | 12
2 | 10
3 | 11
3 | 13
3 | 14
4 | 15
5 | 15
6 | 16

How do I construct a query that knows to combine accounts 1-3 together, 4-5 together, and leave 6 by itself? All 7 entries of accounts 1-3 should be grouped together because they all touched the same account_id or device_id at some point. I am trying to group them together and output the count.

Account 1 was used on device's 10, 11, 12. Those devices used other accounts too so we want to include them in the group. They used additional accounts 2 and 3. But account 3 was further used by 2 more devices so we will include them as well. The expansion of the group brings in any other account or device that also "touched" an account or device already in the group.

A diagram is shown below:

Answer 1

You can use a recursive cte:

with recursive t(account_id, device_id) as (
       select 1, 10 union all
       select 1, 11 union all
       select 1, 12 union all
       select 2, 10 union all
       select 3, 11 union all
       select 3, 13 union all
       select 3, 14 union all
       select 4, 15 union all
       select 5, 15 union all
       select 6, 16
     ),
     a as (
      select distinct t.account_id as a, t2.account_id as a2
      from t join
           t t2
           on t2.device_id = t.device_id and t.account_id >= t2.account_id
     ),
     cte as (
      select a.a, a.a2 as mina
      from a
      union all
      select a.a, cte.a
      from cte join
           a
           on a.a2 = cte.a and a.a > cte.a
     )
select grp, array_agg(a)
from (select a, min(mina) as grp
      from cte
      group by a
     ) a
group by grp;

Here is a SQL Fiddle.