CODEWITHSUNDEEP
rnodesigraph
Μιχαλης Γογγολιδης
Μιχαλης Γογγολιδης

Reputation: 39

Efficient way of selecting paths from node u to node v igraph R

I have the following problem : In a directed weighted graph i want to compute the paths from a node u to the leaves of the graph and then, based on that list, i need to compute the paths from node u to every node v in order to make some computations. Currently i calculate the paths from u to the leaves using

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

then, i do some (not related to the thread) calculations on those paths,and after that i compute every path from u to v using

for(v in V(g)){ Pspaths<-all_simple_paths(g,from = V(g)[u],to=V(g)[v]) } But in this is not an efficient way because most paths are computed more than once so this way is time wasting. Is there a way to compute the paths from u to v by using the list variable paths? Thanks a lot in advance!

Upvotes: 1

Views: 80

Answers (1)

gfgm
gfgm

Reputation: 3647

You can just turn the calculations around, and first get the paths from u to everywhere, and then extract from those paths the ones which terminate at a leaf (also, all_simple_paths() can compute the paths to many vertices at once so you don't need the for loop):

# 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

First we'll get all the paths from u

# 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

We can see there are six paths, terminating in 6, 8, 3, 14, 7 and 18. We know from our computations above, that 6, 7, and 18 are leaf nodes. We can therefore use our known leaves to create a new list of paths from u that terminate at a leaf:

# 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

Upvotes: 1

Related Questions