Риграф: найти общее количество кратчайших путей между узлами u и v, которые проходят через узел g - PullRequest
Новая
       12

Риграф: найти общее количество кратчайших путей между узлами u и v, которые проходят через узел g

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

У меня есть следующая матрица, которая генерирует ненаправленную сетевую диаграмму: 

  a b c d e f g h i j
a 0 1 1 0 0 0 0 0 0 0
b 1 0 1 0 0 0 0 0 0 0
c 1 1 0 1 1 0 1 0 0 0
d 0 0 1 0 1 0 0 0 0 0
e 0 0 1 1 0 1 0 0 0 0
f 0 0 0 0 1 0 1 0 0 0
g 0 0 1 0 0 1 0 1 0 0
h 0 0 0 0 0 0 1 0 1 1
i 0 0 0 0 0 0 0 1 0 0
j 0 0 0 0 0 0 0 1 0 0

m <- structure(c(0L, 1L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 1L, 
0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 1L, 0L, 1L, 1L, 0L, 1L, 0L, 0L, 
0L, 0L, 0L, 1L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 1L, 0L, 
1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 1L, 0L, 0L, 0L, 0L, 
0L, 1L, 0L, 0L, 1L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 
0L, 1L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 
0L, 0L, 0L, 0L, 1L, 0L, 0L), .Dim = c(10L, 10L), .Dimnames = list(
    c("a", "b", "c", "d", "e", "f", "g", "h", "i", "j"), c("a", 
    "b", "c", "d", "e", "f", "g", "h", "i", "j")))

library(igraph)
g3n <- graph.adjacency(m)

Меня интересует ручное вычисление промежуточности узла 'g', которое требует нахождения кратчайших путей среди всех возможных узловв качестве знаменателя и числителя в качестве числа кратчайших путей содержится узел 'g'.

Я использовал следующий код для генерации длин кратчайших путей среди всех узлов: 

shortest.paths(g3n, v=V(g3n), to=V(g3n))

КратчайшийМатрица пути: 

  a b c d e f g h i j
a 0 1 1 2 2 3 2 3 4 4
b 1 0 1 2 2 3 2 3 4 4
c 1 1 0 1 1 2 1 2 3 3
d 2 2 1 0 1 2 2 3 4 4
e 2 2 1 1 0 1 2 3 4 4
f 3 3 2 2 1 0 1 2 3 3
g 2 2 1 2 2 1 0 1 2 2
h 3 3 2 3 3 2 1 0 1 1
i 4 4 3 4 4 3 2 1 0 2
j 4 4 3 4 4 3 2 1 2 0

Есть ли способ подсчитать, сколько раз кратчайший путь между двумя узлами содержит узел 'g' в качестве матрицы или просто любым другим способом в R?

1 Ответ

0 голосов
/ 03 октября 2018

Итак, я не уверен, насколько элегантно это решение, но следующее должно работать: 

#initialize a list to populate with all the shortest paths in the graphy
allpaths <- list()


#Assuming this is an undirected graph, we don't want to calculate both a %--% b and b %--% a  
for(x in V(g3n)$name){
  for(y in V(g3n)$name){
    if(x < y){
      shortest_path_options <- all_shortest_paths(g3n, x, y)$res

      #sometimes there are multiple shortest paths, we will include them all
      for(z in shortest_path_options){
        allpaths[[length(allpaths)+1]] <- z$name
      }
    }
}

#create a boolean of whether a shortest path contains 'g' or not
allpaths_bool <- sapply(allpaths, function(x){
  ('g' %in% x) & (head(x, 1) != 'g') & (tail(x, 1) != 'g')
  })

#Show all the paths that contain 'g'
allpaths[allpaths_bool]

Вы можете вычислить это для каждой вершины, упаковав все в функцию sapply. 

sapply(V(g3n)$name, function(x){
  temp_bool <- sapply(allpaths, function(y){
    (x %in% y) & (head(y, 1) != x) & (tail(y, 1) != x)
  })
  length(allpaths[temp_bool])
})

}

Должен быть более простой способ, но я не совсем уверен в этом.Может быть способ вывести эту информацию с помощью функции betweeness, которая обеспечивает измерения центральности между объектами, но я не очень хорошо разбираюсь в теории графов.

...