Fast Connected Component Identifikation in ungerichteten Graphen in R

Question

Gegeben ein Knoten x in einem ungerichteten Graphen, von dem bekannt ist, dass er Teil einer verbundenen Komponente ist, suche ich nach allen Knoten, die zu der Komponente von x gehören.

Meine aktuelle Implementierung identifiziert alle Komponenten im ungerichteten Graphen und ist daher für große Graphen nicht geeignet. Ich verwende derzeit connectedComp aus der ggm-Bibliothek, um dies zu tun, würde aber lieber ein BFS von RBGL beginnend am Knoten x ausführen und beenden, sobald seine Komponente vollständig erkundet ist. Irgendwelche Vorschläge, wie man das macht? Außerdem würden alle Informationen zu parallelen Graphalgorithmus-Implementierungen, die von R aufgerufen werden können, geschätzt werden.

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

Meiner Meinung nach Vorverarbeitung Graph mit Union-find Wir geben Ihnen beste Ergebnisse.
Es wäre schneller, wenn Sie Graph als Liste der Kanten statt Adjazenzmatrix speichern.

Wenn Sie parallel Lösung benötigen, dann sollten Sie über bfs in hadoop