igraph-help
[Top][All Lists]

## [igraph] Direction of edges along shortest path

 From: Johannes Radinger Subject: [igraph] Direction of edges along shortest path Date: Sat, 5 Dec 2015 14:05:02 +0100

Hi all,

I have a directed graph (dendritic network, e.g. river) where the directions represent flow directions. I'd like to calculate shortest distances between vertices within the network. Therefore I am using shortest_paths with the length of each edges as a weighing factor. Is their an easy way to get the direction of each edge that is passed along the shortest way? In other words, if we consider following graph (in Python-igraph):

e=[(0,1),(1,2),(1,3),(2,4),(4,5),(4,6)]
v=range(7)
g=Graph(directed=True)
g.es["length"]=[15,5,10,10,5,5]

to calculate the distance matrix is straight forward:
g.shortest_paths(weights="length",mode="ALL")

But how can I get the directions of the edges that are passed along the way for each path?
For a single starting vertex I can get a list of edges that are passed to each target vertex:

g.get_shortest_paths(v=0,weights="length",output="epath")

Is it possible to get a list of the directions of each path (1="in direction", 0="against direction"),
or a full matrix (source/target) similar to the output of shortest_paths but with the direction of how
the first/last edge is traversed along the way between each vertex?

For example, moving from vertex 0 to vertex 6 is traversing 4 times against the direction = [0,0,0,0].
Moving from vertex 5 to 6 is moving first in direction and afterwards against = [1,0].

Is there an easy and fast way to calculate this for a large number of vertices/paths in a network in Python?

cheers,
Johannes