Rの無向グラフの高速接続されたコンポーネントの識別R

Question

接続されたコンポーネントの一部であることが知られている無向グラフのノードxを考えると、私はxのコンポーネントに属するすべてのノードを探します。

私の現在の実装では、無向グラフのすべてのコンポーネントを識別しているため、大きなグラフでは不十分です。私は現在、ggmライブラリのconnectedCompを使ってこれを行っていますが、ノードxからRBGLからBFSを実行し、コンポーネントが完全に探索されると終了します。これを行う方法に関する提案はありますか？また、Rから呼び出すことができる並列グラフアルゴリズムの実装についての情報は高く評価されます。 Union-findと私の意見の前処理グラフで

library("ggm") 
x <- 2 

> graph 
    1 2 3 4 5 6 7 8 9 10 
1 0 0 0 0 0 0 0 0 0 0 
2 0 0 1 0 0 1 0 0 0 0 
3 0 1 0 0 0 1 1 1 0 0 
4 0 0 0 0 0 0 0 0 0 0 
5 0 0 0 0 0 0 0 0 0 0 
6 0 1 1 0 0 0 0 0 0 0 
7 0 0 1 0 0 0 0 0 0 0 
8 0 0 1 0 0 0 0 0 0 0 
9 0 0 0 0 0 0 0 0 0 0 
10 0 0 0 0 0 0 0 0 0 0 

graph_object <- as(graph, "graphNEL") 

# All connected components of graph using connectedComp function: 
comp_list <- connectedComp(graph_object) 
> comp_list 
$`1` 
[1] "1" 

$`2` 
[1] "2" "3" "6" "7" "8" 

$`3` 
[1] "4" 

$`4` 
[1] "5" 

$`5` 
[1] "9" 

$`6` 
[1] "10" 

# Extract adjacency matrix of component containing x: 

comp_x <- seq_along(comp_list)[sapply(comp_list, FUN=function(list) x %in% list)] 
> comp_x 
[1] 2 

comp_x_list <- comp_list[[comp_x]] 
> comp_x_list 
[1] "2" "3" "6" "7" "8" 

comp_x <- graph[comp_x_list, comp_x_list] 
> comp_x 
    2 3 6 7 8 
2 0 1 1 0 0 
3 1 0 1 1 1 
6 1 1 0 0 0 
7 0 1 0 0 0 
8 0 1 0 0 0 

Answer 1

あなたに最高の結果が得られます。
隣接行列の代わりにエッジのリストとしてグラフを保存する方が速いでしょう。

あなたはパラレルソリューションが必要な場合は、ノードでおよそbfs in hadoop