Эффективный способ выбора путей от узла u к узлу v igraph R - PullRequest
Новая
       19

Эффективный способ выбора путей от узла u к узлу v igraph R

0 голосов
/ 26 апреля 2018

У меня следующая проблема: В ориентированном взвешенном графе я хочу вычислить пути от узла u до листьев графа, а затем, основываясь на этом списке, мне нужно вычислить пути от узла u к каждому узлу v, чтобы сделать некоторые вычисления. В настоящее время я рассчитываю пути от вас до листьев, используя

leaves<- which(degree(g, v = V(g), mode = "out")==0, useNames = T) paths<-all_simple_paths(g, from = V(g)[u], to = leaves)

Затем я делаю некоторые (не связанные с потоком) вычисления для этих путей, и после этого я вычисляю каждый путь от u до v, используя

for(v in V(g)){ Pspaths<-all_simple_paths(g,from = V(g)[u],to=V(g)[v]) } Но это неэффективный способ, потому что большинство путей вычисляются более одного раза, поэтому этот способ тратит время. Есть ли способ вычислить пути от u до v, используя переменную списка paths? Большое спасибо заранее!

1 Ответ

0 голосов
/ 27 апреля 2018

Вы можете просто перевернуть вычисления и сначала получить пути от u везде, а затем извлечь из этих путей те, которые заканчиваются на листе (также, all_simple_paths() может вычислить пути ко многим вершинам в один раз, поэтому вам не нужен цикл for): 

# Generate some data
set.seed(123)
library(igraph)

g <- random.graph.game(20, .05, directed = T)

leaves <- which(degree(g, mode = 'out')==0, useNames = T)
leaves
#>  [1]  6  7  9 10 11 12 15 16 17 18

# lets say u = 4
u <- 4
V(g)[u]
#> + 1/20 vertex, from f1ba243:
#> [1] 4

Сначала мы получим все пути от вас 

# Get all the paths from u to all other nodes
all_paths_from_u <- all_simple_paths(g, from = V(g)[u])
all_paths_from_u
#> [[1]]
#> + 2/20 vertices, from f1ba243:
#> [1] 4 6
#> 
#> [[2]]
#> + 2/20 vertices, from f1ba243:
#> [1] 4 8
#> 
#> [[3]]
#> + 3/20 vertices, from f1ba243:
#> [1] 4 8 3
#> 
#> [[4]]
#> + 4/20 vertices, from f1ba243:
#> [1]  4  8  3 14
#> 
#> [[5]]
#> + 5/20 vertices, from f1ba243:
#> [1]  4  8  3 14  7
#> 
#> [[6]]
#> + 2/20 vertices, from f1ba243:
#> [1]  4 18

Мы можем видеть, что существует шесть путей, оканчивающихся на 6, 8, 3, 14, 7 и 18. Из наших вычислений выше мы знаем, что 6, 7 и 18 являются листовыми узлами. Поэтому мы можем использовать наши известные листья, чтобы создать новый список путей от вас, которые заканчиваются на листе: 

# now we extract from these paths the ones that terminate at a leaf
# this means we extract the last element of the path and compare it
# to the known leaves. 
leaf_paths <- all_paths_from_u[unlist(lapply(all_paths_from_u, function(p){p[length(p)] %in% leaves}))]
leaf_paths
#> [[1]]
#> + 2/20 vertices, from f1ba243:
#> [1] 4 6
#> 
#> [[2]]
#> + 5/20 vertices, from f1ba243:
#> [1]  4  8  3 14  7
#> 
#> [[3]]
#> + 2/20 vertices, from f1ba243:
#> [1]  4 18
...