CODEWITHSUNDEEP
rsubsetigraphshortest-path
R.Hanovre
R.Hanovre

Reputation: 27

R igraph: calculate shortest path only for a subset of all pairs of vertices

I have a very large igraph object so that calculation of shortest paths takes a long time. I am only interested in the length of the shortest path between a very small set of pairs of vertices. Let's say the (undirected) graph consists of 10,000 vertices and has 500,000 edges, there are shortest paths for 10,000 * 10,000 / 2 pairs of vertices, but I only need the paths between 10,000 pairs of vertices.

Is there any possibility to define not only vertices, but pairs of vertices (meaning: start and end point of the path to be calculated)?

Upvotes: 1

Views: 286

Answers (1)

ThomasIsCoding
ThomasIsCoding

Reputation: 101247

Since you have even number of vertices to make pairs, you can divide all vertices into two groups, i.e., even or odd, like below

v_even <- subset(V(g), !V(g) %% 2)
v_odd <- subset(V(g), !!V(g) %% 2)

and then you run shortest_paht with mapply to produce the shortest paths

> mapply(function(x, y) shortest_paths(g, x, y)$vpath, v_even, v_odd)
[[1]]
+ 3/10 vertices, from 7125d30:
[1] 2 6 1

[[2]]
+ 2/10 vertices, from 7125d30:
[1] 4 3

[[3]]
+ 2/10 vertices, from 7125d30:
[1] 6 5

[[4]]
+ 5/10 vertices, from 7125d30:
[1] 8 5 6 2 7

[[5]]
+ 3/10 vertice

Data

set.seed(1)
g <- sample_gnm(10, 15)

Upvotes: 2

Related Questions