Last active

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

Yen's algorithm for igraph, adapted from Wikipedia's pseudocode. The arguments are: graph: your igraph graph object (warning: the edge's id will change by using this function, so make a copy with gcopy if you want to keep them intact); source: source vertex; target: target vertex; num_k: number of shortest paths you want; weights: name of the edge attribute that contain each edge's weight (this parameter is a string)

View yen_igraph.py
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
def path_cost(graph, path, weights=None):
pathcost = 0
for i in range(len(path)):
if i > 0:
edge=graph.es.find(_source=path[i-1], _target=path[i])
if weights != None:
pathcost += edge[weights]
else:
#just count the number of edges
pathcost += 1
return pathcost
 
def yen_igraph(graph, source, target, num_k, weights):
import queue
 
#Shortest path from the source to the target
A = [graph.get_shortest_paths(source, to=target, weights=weights, output="vpath")[0]]
A_costs = [path_cost(graph, A[0], weights)]
 
#Initialize the heap to store the potential kth shortest path
B = queue.PriorityQueue()
 
for k in range(1, num_k):
#The spur node ranges from the first node to the next to last node in the shortest path
for i in range(len(A[k-1])-1):
#Spur node is retrieved from the previous k-shortest path, k − 1
spurNode = A[k-1][i]
#The sequence of nodes from the source to the spur node of the previous k-shortest path
rootPath = A[k-1][:i]
 
#We store the removed edges
removed_edges = []
 
for path in A:
if len(path) - 1 > i and rootPath == path[:i]:
#Remove the links that are part of the previous shortest paths which share the same root path
edge = graph.es.select(_source=path[i], _target=path[i+1])
if len(edge) == 0:
continue #edge already deleted
edge = edge[0]
removed_edges.append((path[i], path[i+1], edge.attributes()))
edge.delete()
 
#Calculate the spur path from the spur node to the sink
spurPath = graph.get_shortest_paths(spurNode, to=target, weights=weights, output="vpath")[0]
 
if len(spurPath) > 0:
#Entire path is made up of the root path and spur path
totalPath = rootPath + spurPath
totalPathCost = path_cost(graph, totalPath, weights)
#Add the potential k-shortest path to the heap
B.put((totalPathCost, totalPath))
 
#Add back the edges that were removed from the graph
for removed_edge in removed_edges:
node_start, node_end, cost = removed_edge
graph.add_edge(node_start, node_end)
edge = graph.es.select(_source=node_start, _target=node_end)[0]
edge.update_attributes(cost)
 
#Sort the potential k-shortest paths by cost
#B is already sorted
#Add the lowest cost path becomes the k-shortest path.
while True:
cost_, path_ = B.get()
if path_ not in A:
#We found a new path to add
A.append(path_)
A_costs.append(cost_)
break
 
return A, A_costs

Thanks for sharing. You forgot to include your path_cost() function, so I just wrote my own.

Owner

Hey, sorry for forgetting it, just added it!

Perhaps a note to anyone who might start hunting for infinite loops, B.get() blocks if B is empty, which happens if num_k is greater than the total number of paths in the graph.
Thanks a lot, this was very helpful.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.