get.shortest.paths in time graph

Asked

Viewed 62 times

1

I’m using the "igraph" library and I’m working with dynamic graphs. I have the following graph:

VertexFrom VertexTo TimeStart TimeStop

to c 1 1

a d 2 2

b d 2 2

c d 3 3

d b 3

That is, v1 is connected to v2 at time x at y.

Example. In the first step [0,1] my graph will be like this

a ----------- c

b (not edge) d

I only have an edge from 'a' to 'c'. And so on...

I’m using the get.shortest.paths function to calculate the shortest time path.

Ex.:

get.shortest.paths(g, 'a 3', 'b 3', mode="all", Weights=E(g)$Hopcost)

It will calculate the path from a to b in the time interval[3.3]. In the range [3.3] this path does not exist, but the function returns me:

a 3 to 2 d 2 b 2 b 3

That is, it goes back in time to find a way. From 'to 3' it went back to 'a 2' it went to’d 2, then 'b 2' and finally 'b 3'. Does anyone know how to modify it so she doesn’t come back? In that case, I want it to calculate, if it exists, only the shortest path in time x to time y, without going back in time. In the example above the result would be zero, because there is no path.

  • How are you importing the graph into the igraph? As far as I know, it is not possible to create dynamic graphs with this library. You would have to create 3 different graphs (3 snapshots) and calculate get.shortest.path for each graph individually.

  • From this library www.benjaminblonder.org/timeorderednetworks/

No answers

Browser other questions tagged

You are not signed in. Login or sign up in order to post.