特定の比較基準に従ってリストをソートします。R

Question

Rで、リストをハッシュテーブルに変換し、特定の基準に従って類似した要素をグループ化する方法を探しています。

詳細は、以下で説明するように「グラフ理論」に特有ですが、答えはいくつかの特定の基準に基づいてハッシュする一般的な手順だと思います。

リストは、（igraphパッケージの）「グラフ」オブジェクトで構成されています。

library(igraph) 

#Creating the list of graphs 
edgeList <- data.frame(
    idA=c(008, 001, 001, 010, 047, 002, 005, 005), 
    idB=c(100, 010, 020, 030, 030, 001, 011, 111) 
) 
edgeList$idB= edgeList$idB+0.1 
g <- graph_from_data_frame(edgeList, directed = TRUE) 
g_list <- decompose(g, mode = "weak") 

#from the 8 edges we obtain 5 graphs (connected components of the original graph) 

類似性基準は、グラフは同型でなければならないということです。

isomorphic(g_list[[1]],g_list[[4]]) 

私はハッシュテーブルにg_list内の要素のインデックスをハッシュするにはどうすればよいですか？

この玩具例えば予想される結果は次のようになります

g_inded_hash 
[[1]] 
[1] 1 4 

[[2]] 
[1] 2 5 

[[3]] 
[1] 3 

（必ずしもリストが、いくつかのデータ構造グループグラフ（1,4）及び（2,5）に類似している）

実際には、私は同形にしたがってグループ化する必要がある4000万（小さな）のグラフを持っています。

検索の結果、答えがパッケージまたはenvironmentに関連している必要があることが判明しましたが、その解決策には対応できませんでした。

EDIT：directed = TRUEをgraph_from_data_frame()に変更しました。

Answer 1

同型性は推移的であるため、i < jのようなすべてのコンポーネントのペア（i、j）を見てから、ノードがコンポーネントであり、エッジが同形プロパティによって定義されるグラフを作成できます。この新しいグラフの接続されたコンポーネントからハッシュテーブルを抽出することができます。

# all pairs (i,j) such that i < j 
combinations <- unlist(sapply(seq_along(g_list), 
           function(j) lapply(seq_len(j-1), 
              function(i) c(i,j))), 
         recursive = FALSE) 
# filter the isomorphic pairs 
iso <- Filter(function(pair) isomorphic(g_list[[pair[1]]],g_list[[pair[2]]]), 
       combinations) 
# convert to data frame 
df <- data.frame(matrix(unlist(iso), ncol = 2, byrow = TRUE)) 
# build graph where the vertices are the components 
# and the edges indicate the isomorphic property 
g_iso <- graph_from_data_frame(df, directed = FALSE) 
# identify groups that share the same property 
groups <- clusters(g_iso)$membership 
# the names are the indices of g_list 
g_hash <- lapply(unique(groups), 
       function(i) as.integer(names(which(groups == i)))) 

結果：

> g_hash 
[[1]] 
[1] 2 3 5 

[[2]] 
[1] 1 4 

これが問題の予想される結果と一致していませんが、isomorphic(g_list[[2]],g_list[[3]])とisomorphic(g_list[[3]],g_list[[5]])がtrueあります。

おそらくこれを行う最も簡単な方法ではありませんが、それは思い浮かぶものです。

Answer 2

私は自分の問題の解決方法を書くことができました。それはおそらく非常に効率的ではない、非常に "リッシュ"ではない、すべてのループでは、私はそれが動作すると思います。これを行うより良い方法を教えてください。

gl_hash <- list() 
gl_hash[1] <- 1 
j <- 1 
for(i in 2:length(gl)) { 
    m <- 0 
    for(k in 1:j){ 
    if(isomorphic(gl[[ gl_hash[[k]][1] ]], gl[[i]])) { 
     gl_hash[[k]] <- c(gl_hash[[1]],i) 
     m <- 1 
     break 
    } 
    } 
    if(m==0) { 
    j <- j+ 1 
    gl_hash[j] <- i 
    } 
}