Извлечение информации из `all_shortest_paths` функций от` igraph` пакета в R

Question

В данном примере граф:

set.seed(1) 
g <- make_chordal_ring(15, matrix(c(3, 12, 4, 7, 8, 11), nr = 2)) 
k <- Vectorize(all_shortest_paths, "from", F)(g, V(g), 7) 

Мы имеем все кратчайшие пути, начиная любой заданный узел в графе и заканчивая узлом 7 (ссылка узел). Я хочу, чтобы подсчитать количество раз, когда узел Y присутствует в кратчайшем пути от узла X до узла 7.

Если я обозначаю количество кратчайших путей от узла 1 до узла 7, проходящего через узел 2, п (1,2,7), а общее количество кратчайших путей от узла 1 к узлу 7, п (1,7) Я хочу способ создать таблицу, которая выглядит примерно так:

Я действительно застрял в этом, например, если посмотреть на выход k:

> k[[1]][1] 
$res 
$res[[1]] 
+ 3/15 vertices: 
[1] 1 4 7 

я не знаю, как изолировать путь 1,4,7 и считать это в направлении п (1,4,7)

Answer 1

Я бы для простого цикла:

# initialize your matrix with all zeros 
m <- matrix(0,nrow=vcount(g),ncol=vcount(g)+1) 

# iterate over elements of k 
for(fromVertex in 1:length(k)){ 

    # iterate over res entry of each element of k 
    for(path in k[[fromVertex]]$res){ 

    # path is a vertex sequence, same type as V(g), 
    # calling as.integer we get the vertices indexes inside the sequence 
    verticesOfPath <- as.integer(path) 

    # we exclude the first and the last vertex (from,to) 
    innerVertices <- verticesOfPath[c(-1,-length(verticesOfPath))] 

    if(length(innerVertices) > 0){ 
     # this is not a direct path 
     m[verticesOfPath[1],innerVertices] <- m[verticesOfPath[1],innerVertices] + 1 
    } 
    # add 1 to the last column 
    m[verticesOfPath[1],ncol(m)] <- m[verticesOfPath[1],ncol(m)] + 1 
    } 
} 

Результат:

> m 
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] 
[1,] 0 0 0 1 0 0 0 0 0  0  0  0  0  0  0  1 
[2,] 0 0 0 0 0 1 0 0 0  0  0  0  0  0  0  1 
[3,] 0 0 0 1 0 0 0 0 0  0  0  0  0  0  0  1 
[4,] 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  1 
[5,] 0 0 0 1 0 1 0 0 0  0  0  0  0  0  0  2 
[6,] 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  1 
[7,] 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  1 
[8,] 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  1 
[9,] 0 0 0 0 0 0 0 1 0  1  0  0  0  0  0  2 
[10,] 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  1 
[11,] 0 0 0 0 0 0 0 0 0  1  0  0  0  0  0  1 
[12,] 0 0 0 0 0 0 0 1 0  0  0  0  0  0  0  1 
[13,] 0 0 0 0 0 0 0 0 0  1  0  0  0  0  0  1 
[14,] 0 0 0 0 0 1 0 0 0  0  0  0  0  0  0  1 
[15,] 0 0 0 0 0 0 0 1 0  0  0  0  0  0  0  1 

Если вершины имеют атрибуты имен, вы можете установить их в качестве строки и Col имена матрицы:

rownames(m) <- V(g)$name 
colnames(m) <- c(V(g)$name,'TOT') 

> m 
    A B C D E F G H I J K L M N O TOT 
A 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 
B 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 
C 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 
D 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
E 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 2 
F 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
H 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
I 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 2 
J 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
K 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 
L 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 
M 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 
N 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 
O 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1