Acyclic graph - Smallest weight of each path between vertices

0
votes

I am new to R and IGraph.

I want to obtain the smallest weight of all edges (can also be the label of the edge) from a node to another. But My actual goal is to perform the same for each node, which will provide me with all smallest weight in each path from each node to each other node. Edited(graph is cyclic) My graph is cyclic and undirected.

Example of my goal:

Edges

NODE1 > NODE2

NODE2 > NODE3

NODE2 > NODE4

NODE3 > NODE4

Weight of edges

EDGE1 - 2

EDGE2 - 1

EDGE3 - 0.5

EDGE4 - 0.2

I want to get

1 as result from NODE1 to NODE3

0.5 from NODE1 to NODE4 (one path)

0.2 from NODE1 to NODE4 (another path)

Is it possible to do that?

1
rigraph

1 Answers

1
votes

get.shortest.paths(..., output="epath") will give you the indices of the edges involved in each of the shortest paths that it finds in the $epath component of the result items. You can then use min(E(g)$weight[some.path$epath]) to get the minimum weight in the path (where some.path is one of the paths returned by get.shortest.paths).

Update: okay, if your graph is not acyclic, there can be more than one path between any two vertices, and as far as I know igraph has no function for enumerating all the simple paths (i.e. paths without vertex repetitions) yet. The next major release (igraph 0.8) will have a function named get.all.simple.paths, which will probably do what you need, but it is not released yet so you'll have to compile it yourself from the development tree if you want to try it. Also, the API is probably not stable yet.