Convert transitive connections of elements into groups in R or SQL

Question

In table below, each row represents connection between pair of elements.

For example: A is connected to B, B to C, C to D and G, G is connected to H.

So all connected elements share the same group, for example named '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

How to write efficient algorithm in R (or maybe SQL) to calculate unknown 'group' having only table with connections between e1, e2 ?

In SQL this would need recursive CTEs. Which SQL do you intend to use? — wildplasser, Sep 22 '13 at 22:17
I prefer Oracle 10. (11g has some additional extentions regarding CTEs, so may be easier) — ipj, Sep 22 '13 at 22:22

score 2 · Accepted Answer · answered Sep 22 '13 at 22:23

2

You data is a graph, defined by the list of its edges, and you want its connected components. This is what the clusters function in the igraph package computes.

# 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

answered Sep 22 '13 at 22:23

Vincent Zoonekynd

31,893
5
69
78

1

Though you will have to merge the `$membership` data back to `d` using `names(g[1])` as the corresponding `e1` variable. Notice that the `$membership` is length 12, while the original data is length 9. – thelatemail Sep 22 '13 at 22:49

score 1 · Answer 2 · answered Sep 22 '13 at 22:58

Recursive CTE (this is for Postgres, minor changes will be needed for Oracle) Note: without counter-measures, some loops will not be avoided, leading to infinite recursion.

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
        ;

Result:

 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)

Convert transitive connections of elements into groups in R or SQL

2 Answers2