I'm using igraph
to generate a matrix of shortest path distances between pairs of vertices but I can't figure out how to return the vertices. So far I have:
path_length_matrix = ig_graph.shortest_paths_dijkstra(None,None,"distance", "ALL")
I'm looking for a function which returns a matrix of paths like the matrix of distances but I can't see anything in the igraph documentation which shows how to get the paths.
The idea is to use Dijkstra's algorithm. In order to find the shortest distance from all vertex to a given destination vertex we reverse all the edges of the directed graph and use the destination vertex as the source vertex in dijkstra's algorithm.
Dijkstra's Algorithm finds the shortest path between a given node (which is called the "source node") and all other nodes in a graph. This algorithm uses the weights of the edges to find the path that minimizes the total distance (weight) between the source node and all other nodes.
Depth-First Search (DFS) Your graph needs to be a tree or polytree. If this condition is met, you can use a slightly modified DFS to find your shortest path: If there does not exist a path between startNode and stopNode , the shortest path will have a length of -1.
The function you need is get_shortest_paths
I believe. See https://igraph.org/python/doc/igraph.GraphBase-class.html#get_shortest_paths
You need to call it individually for each source vertex, and it will give you only a single (arbitrary) shortest path for each pair of nodes. If you need all shortest paths, then see get_all_shortest_paths
: https://igraph.org/python/doc/igraph.GraphBase-class.html#get_all_shortest_paths
I do this
from igraph import *
g = Graph([(0,1), (0,2), (2,3), (3,4), (4,2), (2,5), (5,0), (6,3), (5,6)])
g.vs["name"] = ["Alice", "Bob", "Claire", "Dennis", "Esther", "Frank", "George"]
#You could create Vertexes like g.add_vertex(name="Bill")
path=g.get_shortest_paths("Alice",to="Frank",mode=OUT,output='vpath')
for n in path[0]:
print("{}".format(g.vs[n]['name']))
Hope this helps
This is the way to find shortest path for weighted directed graph (DAG). So this what I figured out:
import igraph
from igraph import *
g = Graph(directed=True)
g.add_vertices(3)
g.vs["name"]=["GO:1234567","GO:6789056","GO:5674321"]
g.es["weight"]=1
g['GO:1234567','GO:6789056']=1
g['GO:6789056','GO:5674321']=5
weight=g.es["weight"]
print weight
print g.degree(mode="in")
print g.shortest_paths_dijkstra(source="GO:1234567", target="GO:5674321",
weights=weight, mode=OUT)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With