Как получить все кратчайшие пути длины диаметра для объекта iGraph?

Question

Я хочу получить все самые длинные кратчайшие пути для объекта iGraph. Есть эта функция

get.diameter (graph, directed = TRUE, unconnected = TRUE) 

Но он возвращает только один путь. Таким образом, если есть много кратчайших путей длины диаметра, то он возвращает первый найденный

Answer 1

Вы можете легко извлечь, какие узлы и с какой длиной соединены, используя матрицу кратчайшего расстояния, возвращаемую shorttest.paths(graph). В R вы можете использовать which() а также arr.ind=TRUE вот так:

longest.shortest.paths <- function(graph){
    # Return edgelist of all node-pairs between which the shortest path
    # in a graph are the longest shortest path observed in that graph.

    # Get all the shortest paths of a graph
    shortest.paths = shortest.paths(graph)

    # Make sure that there are no Inf-values caused by isolates in the graph
    shortest.paths[shortest.paths == Inf] <- 0

    # What nodes in the distance matrix are linked by longest shortest paths?
    el <- which(shortest.paths==max(shortest.paths), arr.ind=TRUE)
    colnames(el) <- c("i","j")
    (el)
}

graph <- erdos.renyi.game(100, 140, "gnm", directed=FALSE)
longest.shortest.paths(graph)