Início / coding / Perguntas / 79182778
Accepted
farrow90
Asked: 2024-11-13 05:35:23 +0800 CST

Calculando a menor distância entre vários pontos em um gráfico?

  • 772

Tenho um gráfico aleatório em R:

library(igraph)
library(tidyr)

set.seed(123)
g <- sample_gnm(n = 20, m = 20, directed = FALSE)

insira a descrição da imagem aqui

Estou tentando descobrir a menor distância entre cada nó.

Encontrei esta função no igraph chamada distances() e tentei implementá-la:

dist_df <- as.data.frame(distances(g)) %>%
    mutate(node_i = 1:nrow(.)) %>%
    pivot_longer(cols = -node_i,
                 names_to = "node_j",
                 values_to = "distance") %>%
    mutate(node_j = as.numeric(gsub("V", "", node_j))) %>%
    select(node_i, node_j, distance)

Verificando manualmente os resultados, eles parecem estar corretos:

# A tibble: 400 × 3
   node_i node_j distance
    <int>  <dbl>    <dbl>
 1      1      1        0
 2      1      2        2
 3      1      3        3
 4      1      4        4
 5      1      5        4
 6      1      6        3
 7      1      7      Inf
 8      1      8        3
 9      1      9      Inf
10      1     10      Inf

Aqui está minha pergunta: Como a função distance() consegue funcionar tão rápido? Eu pensei que descobrir o caminho mais curto em gráficos é um processo computacionalmente intensivo - como essa função faz isso tão rápido? Essa é a função correta para esse problema?

1 respostas

  1. Best Answer

    Se você estiver curioso sobre " Por que ", sugiro que consulte o código-fonte digitando ?distances(não sou especialista em teoria dos grafos, mas espero que o código abaixo possa lhe dar algumas pistas)

    > distances
function (graph, v = V(graph), to = V(graph), mode = c("all", 
    "out", "in"), weights = NULL, algorithm = c("automatic", 
    "unweighted", "dijkstra", "bellman-ford", "johnson", "floyd-warshall")) 
{
    ensure_igraph(graph)
    if (!is_directed(graph)) {
        mode <- "out"
    }
    v <- as_igraph_vs(graph, v)
    to <- as_igraph_vs(graph, to)
    mode <- igraph.match.arg(mode)
    mode <- switch(mode, out = 1, `in` = 2, all = 3)
    algorithm <- igraph.match.arg(algorithm)
    algorithm <- switch(algorithm, automatic = 0, unweighted = 1,
        dijkstra = 2, `bellman-ford` = 3, johnson = 4, `floyd-warshall` = 5)
    if (is.null(weights)) {
        if ("weight" %in% edge_attr_names(graph)) {
            weights <- as.numeric(E(graph)$weight)
        }
    }
    else {
        if (length(weights) == 1 && is.na(weights)) {
            weights <- NULL
        }
        else {
            weights <- as.numeric(weights)
        }
    }
    if (!is.null(weights) && algorithm == 1) {
        weights <- NULL
        warning("Unweighted algorithm chosen, weights ignored")
    }
    on.exit(.Call(R_igraph_finalizer))
    res <- .Call(R_igraph_shortest_paths, graph, v - 1, to -
        1, as.numeric(mode), weights, as.numeric(algorithm))
    if (igraph_opt("add.vertex.names") && is_named(graph)) {
        rownames(res) <- V(graph)$name[v]
        colnames(res) <- V(graph)$name[to]
    }
    res
}

    onde você pode ver que há várias opções de algoritmos, e seu código-fonte pode ser encontrado https://github.com/igraph/igraph/tree/master/src/paths

    Talvez você devesse ler sobre esses arquivos e acredito que você mesmo chegaria a essa conclusão.

    • 1

relate perguntas