Yen's algorithm implementation for Python2 / iGraph, adapted from ALenfant's work (https://gist.github.com/ALenfant/5491853) I had to modify it to make it run on Python 2 with the corresponding iGraph library. I added the possibility to deal with loops in undirected graphs and the possibility to detect that all possible pathes were discovered in…

yen.py

def path_cost(graph, path, weights=None):

    pathcost = 0
    if weights is None:
        pathcost = len(path)-1
    else:
        for i in range(len(path)):
            if i > 0:
                edge = graph.es.find(_source=min(path[i-1], path[i]),
                                     _target=max(path[i-1], path[i]))
                pathcost += edge[weights]

    return pathcost


def in_lists(list1, list2):

    result = False
    node_result = -1

    if len(list1) < len(list2):
        toIter = list1
        toRefer = list2
    else:
        toIter = list2
        toRefer = list1

    for element in toIter:
        result = element in toRefer
        if result:
            node_result = element
            break

    return result, node_result


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=min(path[i], path[i+1]),
                                           _target=max(path[i], path[i+1]))
                    if len(edge) == 0:
                        continue
                    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
            while True:
                spurPath = graph.get_shortest_paths(spurNode,
                                                    to=target,
                                                    weights=weights,
                                                    output="vpath")[0]
                [is_loop, loop_element] = in_lists(spurPath, rootPath)

                if not is_loop:
                    break
                else:
                    loop_index = spurPath.index(loop_element)
                    edge = graph.es.select(_source=min(spurPath[loop_index],
                                                       spurPath[loop_index-1]),
                                           _target=max(spurPath[loop_index],
                                                       spurPath[loop_index-1]))

                    if len(edge) == 0:
                        continue

                    edge = edge[0]
                    removed_edges.append((spurPath[loop_index],
                                         spurPath[loop_index-1],
                                         edge.attributes()))
                    edge.delete()

            #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=min(node_start, node_end),
                                       _target=max(node_start, node_end))[0]
                edge.update_attributes(cost)

            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))

        #Sort the potential k-shortest paths by cost
        #B is already sorted
        #Add the lowest cost path becomes the k-shortest path.
        while True:
            if B.qsize() == 0:
                break
            cost_, path_ = B.get()
            if path_ not in A:
                #We found a new path to add
                A.append(path_)
                A_costs.append(cost_)
                break

        if not len(A) > k:
            break

    return A, A_costs

Thanks for sharing! I have a doubt though, just a heads up that I'm pretty new to igraph. I called yen_igraph function from another file by the statement
p, co = yen_igraph(g, 0, 5, 5, weights=[3,2,4,1,2,3,2,1,2]) #where each entry in weights is link weight of respective edges defined in g
but I keep getting this error,
Traceback (most recent call last):
File "sample.py", line 29, in
main()
File "sample.py", line 21, in main
p, co = yen_igraph(g, 0, 5, 5, weights=[3,2,4,1,2,3,2,1,2])
File "/home/pox/Documents/yen_igraphnew.py", line 45, in yen_igraph
A_costs = [path_cost(graph, A[0], weights)]
File "/home/pox/Documents/yen_igraphnew.py", line 11, in path_cost
pathcost += edge[weights]
KeyError: 'Attribute does not exist'

So is the format of weights attribute wrong? If so what should be the right way to pass weights?

The actual file from which I'm calling yen_igraph:

from igraph import *
from yen_igraphnew import *
from multiprocessing import *

def main():

Create the graph

vertices = [i for i in range(6)]
edges = [(0,1),(0,2),(1,3),(2,1),(2,3),(2,4),(3,4),(3,5),(4,5)]

weight=[3,2,4,1,2,3,2,1,2]

g = Graph(vertex_attrs={"label":vertices}, edges=edges, directed=True)
g.es["weight"] = [3,2,4,1,2,3,2,1,2]

print g.is_weighted()

print g.es["weight"]

g.es["weight"] = range(10)

print(g)
plot(g)
print('hey')

p, co = yen_igraph(g, 0, 5, 5, weights=g.es[“weight”])

p, co = yen_igraph(g, 0, 5, 5, weights=[3,2,4,1,2,3,2,1,2])
print('success')
'''
for path in p:
print "Cost:%s\t%s" % (path['cost'], "->".join(path['path']))
return 0
'''

if name == "main":
main()

I wonder where is the function "get_shortest_paths" defined?