Преобразование переходных соединений элементов в группы в R или SQL

Question

В следующей таблице каждая строка представляет собой соединение между парами элементов.

Например: А соединен с В, В к С, С, D и G, G подключен к H.

Таким образом, все соединенные элементы совместно используют ту же самую группу, например, под названием «1».

e1 e2 group 
A B 1 
B C 1 
C D 1 
C G 1 
E F 2 
I E 2 
H G 1 
J K 3 
K L 3 

Как написать эффективный алгоритм в R (или возможно SQL) для вычисления неизвестных «группы» имея только таблицу со связями между e1, e2?

Answer 1

Данные являются графиком, определяемым списком его ребер, , и вы хотите, чтобы его компоненты были подключены. Это то, что делает clusters функция в пакете igraph.

# Sample data 
d <- structure(c("A", "B", "C", "C", "E", "I", "H", "J", "K", "B", 
"C", "D", "G", "F", "E", "G", "K", "L"), .Dim = c(9L, 2L), .Dimnames = list(
    NULL, c("e1", "e2"))) 

library(igraph) 
g <- graph.edgelist(as.matrix(d)) 
clusters(d) 
# $membership 
# [1] 1 1 1 1 1 2 2 2 1 3 3 3 

Answer 2

Рекурсивный CTE (это для Postgres, будут необходимы незначительные изменения для Oracle) Примечание: без контрмер, некоторые петли не избежать, что приводит к бесконечной рекурсии.

CREATE TABLE pairs 
     (e1 varchar NOT NULL 
     , e2 varchar NOT NULL 
     , PRIMARY KEY (e1,e2) 
     ); 

INSERT INTO pairs(e1,e2) VALUES 
('A' , 'B') 
, ('B','C') 
, ('C','D') 
, ('C','G') 
, ('E','F') 
, ('I','E') 
, ('H','G') 
, ('J','K') 
, ('K','L') 
     ; 
WITH RECURSIVE tree AS (
     WITH dpairs AS (
     SELECT e1 AS one, e2 AS two FROM pairs WHERE e1 < e2 
     UNION ALL 
     SELECT e2 AS one, e1 AS two FROM pairs WHERE e1 > e2 
     ) 
     SELECT dp.one AS opa 
       , dp.one AS one 
       , dp.two AS two 
     FROM dpairs dp 
     WHERE NOT EXISTS (SELECT * 
       FROM dpairs nx 
       WHERE nx.two = dp.one 
       AND nx.one < dp.one 
       ) 
     UNION ALL 
     SELECT tr.opa AS opa 
       , dp.one AS one 
       , dp.two AS two 
     FROM tree tr 
     JOIN dpairs dp ON dp.one = tr.two AND dp.two <> tr.opa AND dp.two <> tr.one 
     ) 
SELECT opa,one,two 
     , dense_rank() OVER (ORDER BY opa) AS rnk 
FROM tree 
ORDER BY opa, one,two 
     ; 

Результат:

opa | one | two | rnk 
-----+-----+-----+----- 
A | A | B | 1 
A | B | C | 1 
A | C | D | 1 
A | C | G | 1 
A | G | H | 1 
E | E | F | 2 
E | E | I | 2 
J | J | K | 3 
J | K | L | 3 
(9 rows)