Блог

Главная - Вопросы по программированию - Найдите самый дальний узел в сети с помощью R igraph

Найдите самый дальний узел в сети с помощью R igraph

#r #igraph

#r #igraph

Вопрос:

Как я могу найти узел, который находится дальше всего к другому узлу в направленной сети?

Например, в следующем коде:

 g <- graph( c('A',1,'A',2,'2','B','B',4,'B',5,5,'C','C',7,'C',8,'D',7,8,'D'))

Как я могу получить самый дальний узел от B, равный «7» (B> 5> 8> D> 7) или C, также равный «7» (C> 8> D> 7)

Спасибо

Комментарии:

1. igraph имеет функцию для определения расстояний: например distances(g, 7) .

2. Возможно ли получить максимальное значение, я думаю. Звучит неплохо. Спасибо

3. Да, например plot(g);V(g)[4];d <- distances(g, 4, mode = "out");d <- d[1, !is.infinite(d)];d[d==max(d)] , дает вам узел (ы) с максимальным расстоянием от 4-го узла на вашем графике.

4. Да!!! Это потрясающе!! Спасибо. Спасибо.

Ответ №1:

Вы могли бы использовать простое умножение матрицы. Например, следующий код показывает пути от C (7-го узла) длиной 1,2,3,4. По длине 4 их нет.

 ga <- get.adjacency(g, sparse = F)
for (i in 1:4) {
print(i)
print(matrix.power(ga,i)[7,])
}

Хотя это может быть непрактично, если ваш график очень большой.

Комментарии:

1. Спасибо jac. Какую библиотеку вы используете для matrix.power?

2. Это из пакета matrixcalc . Но вы также можете использовать что-то вроде Reduce("%*%", rep(list(ga), i))

3. Спасибо lukeA. Очень полезно.