CODEWITHSUNDEEP
rnetwork-programmingigraphshortest-pathdijkstra
copamundial
copamundial

Reputation: 213

Export path sequence of all shortest path in a network

I have two networks in igraph where I'd like to extract the path sequences (not just the length) of all shortest path from the first network in the second one. The idea behind that is: I have stored the information of an origin-destination dataframe in net2. So I have the start and end node of trips. What I don't have is the nodes visited between start and end node. I assume that the agents will choose the shortest_path for traveling.

In net (first network) I have a whole network with nodes and edges attributed with travel times. Now I would like to see how the agents in the origin-destination dataframe (net2) travel from the start to the end node while choosing shortest paths.

This means: I need to combine both networks. One has the information of the origin-destination relation,the other has the sequence of connecting nodes. Or in other words: Which vertices use the agents from net2 in net to get to their desired node.

To get the shortest path sequence of my network net I used igraph::shortest_paths. This gives me an igraph.vs object with the desired information. Now I would like to store this information in dataframe but I don't know how to access it.

I tried: df<-unlist(shortest_paths(net,from =od$from,to=od$to)

where od is the origin-destination df

Now I want to store the multidimensional list as a dataframe.

results <- unlist(df, recursive = F)
results <- sapply(results, as_ids)

result_df <- as.data.frame(matrix(results))

When I'm doing this I get the error: Error in UseMethod("as_ids") : no applicable method for 'as_ids' applied to an object of class "c('integer', 'numeric')"

Upvotes: 0

Views: 551

Answers (2)

Lukas JLU
Lukas JLU

Reputation: 1

I converted my o-d-matrix to a graph as I assume this will run faster. I still get the error: Error in UseMethod("as_ids") : no applicable method for 'as_ids' applied to an object of class "c('integer', 'numeric')"

Might this be due to the class of my edgelist? I have vertices with IDs like: U1309? When I call str(links) it is a character. Do I need to convert the class of my edgelist? Or is there another command to turn the vertex sequence into an ordninary vector?

Upvotes: 0

Newl
Newl

Reputation: 330

I don't know if it's a misspell or you are using a different version, but I can't find the shortest_path() function, only the one you have mentioned later: shortest_paths().

If I understand clearly, you want to extract the exact shortest path sequences in a list of vertices (list of lists containing vertices), and convert it to a DF.

Here's my solution:

library('igraph')

set.seed(24)

g <- as.undirected(barabasi.game(20, power = 0.5, m = 4))

results <- sapply(V(g), function(x){ all_shortest_paths(g, from = x, to = V(g)[-x])$res})
results <- unlist(results, recursive = F)
results <- sapply(results, as_ids)

result_df <- as.data.frame(matrix(results))

I extracted the shortest paths by calling the all_short all_shortest_paths on each vertex, where the from parameter is the current vertex, and the to parameter is the list of the other vertices, minus the current one. Only the res attribute is needed from the given structure.

This gave me a multidimensional list: lists of vertex lists (every shortest path from the given vertex) for every node.

...
[[15]]
[[15]][[1]]
+ 3/20 vertices, from 84297ee:
[1] 15 14  1

[[15]][[2]]
+ 3/20 vertices, from 84297ee:
[1] 15  7  1

[[15]][[3]]
+ 3/20 vertices, from 84297ee:
[1] 15  5  1

[[15]][[4]]
+ 3/20 vertices, from 84297ee:
[1] 15  8  2
...

Once I have unlisted one layer of it, I got the inner list of vertices. This is an igraph.vs structure, and you have to convert it with the sapply(,as_ids) function as it is mentioned here.

After this step, you can work further with your simple list of vertex name lists, converting them to a data.frame

Upvotes: 1

Related Questions