0

以下の表で、各行は要素のペア間の接続を表します。

例: A は B に接続され、B は C に接続され、C は D に接続され、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

e1、e2間の接続を持つテーブルのみを持つ未知の「グループ」を計算するために、R（またはおそらくSQL）で効率的なアルゴリズムを作成する方法は?

4

2 に答える 2

2

データはグラフであり、そのエッジのリストによって定義され、その連結成分が必要です。これは、パッケージ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
于 2013-09-22T22:23:28.983 に答える
1

再帰的 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)
于 2013-09-22T22:58:09.840 に答える