указать корень в igraph минимальное связующее дерево - PullRequest
Новая
       40

указать корень в igraph минимальное связующее дерево

0 голосов
/ 14 сентября 2018

У меня есть взвешенная матрица смежности, и мне нужно создать направленный MST.Проблема в том, что я знаю вес ребер и корень, поэтому я могу сгенерировать MST на неориентированном графе, но не могу найти способ указать корень.Если бы я мог указать корень, это автоматически привело бы к указанию на всех краях MST, завершив задачу. 

my_graph <- igraph::graph_from_adjacency_matrix(adjmatrix = cluster_adj_matrix, mode = "upper", weighted = TRUE)
my_mst <- igraph::mst(my_graph)

1 Ответ

0 голосов
/ 15 сентября 2018

Две основные функции, которые меня интересовали: длина пути к корню и предшественник ориентированного графа могут быть сгенерированы следующим образом:

Для получения предшественников: 

GetPredecessors <- function(minspantree, root){
  pathdata <- igraph::get.shortest.paths(graph = minspantree, from = root)
  pathlist <- prelist <- lapply(paths$vpath, function(x){
    y = as.vector(x)
    y[(length(y)-1)]
  })
  prelist[[root]] <- 0
  return(unlist(prelist))
}

Дляполучить длину пути к корню: 

igraph::shortest.paths(graph = minspantree, v = root)
...