Блог

У меня есть ненаправленный список ребер, который выглядит примерно следующим образом (за исключением того, что он содержит сотни тысяч узлов и ребер):

 map <- list(1,1,1,2,6,5,2,3,4,7) %>% matrix(nrow = 5, ncol = 2)
  

Я пытался найти способ разделить эту таблицу на группы узлов, которые могут достигать друг друга. В приведенном выше примере я хотел бы видеть набор c(1,2,3,4,5) и набор c(6,7) как отдельные группы.

Я работал с разными идеями и наткнулся на igraph пакет, который позволил бы мне использовать graph_from_edgelist для создания объекта igrap, а затем я могу использовать dfs его на каждом узле, чтобы найти каждый узел, доступный для этого узла. Я даже зашел так далеко, что исключил посещенные узлы, чтобы не повторять вещи, но это все еще очень медленно.

Это лучшее, что у меня есть, но я надеялся на что-то гораздо более быстрое.

 graph <- graph_from_edgelist(map,firected = F)
all_nodes <- c(map[,1],map[,2]) %>% unlist() %>% unique()
visited <- c()
node_groups <- list()

for(i in 1:length(all_nodes)){
    if(!(i %in% visited)) {
        temp <- dfs(graph,i,neimode = "all", unreachable = F)[[3]]
        temp <- temp[!is.na(temp)]
        node_groups[[length(node_groups)   1 ]] <- temp
        visited <- c(visited, temp)
    }
}
  

Я надеюсь, что я просто где-то упускаю из виду очевидную функцию или что есть простой метод оптимизации, который позволит мне продолжать проводить анализ в R. Спасибо за вашу помощь.