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 ed…

yen_igraph.py

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.

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.

Hello,

Thanks a lot for this piece of code. Yet, I had to modify it to make in 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 case k is large.

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 created a iGraph graph called MyG and tried to call your function but got the following error:
(Please note that my MyG is weighted (MyG.es['weight'] = [123, 456, 678, ...]; should I pass 'weights' argument to the function?)

YenKSP.yen_igraph(MyG,'BBA','01A',3,'')

Traceback (most recent call last):

File "", line 1, in
YenKSP.yen_igraph(MyG,'BBA','01A',3,'')

File "C:\Users\3626416\Documents\NKA-OPT\src\YenKSP.py", line 17, in yen_igraph
A = [graph.get_shortest_paths(source, to=target, weights=weights, output="vpath")[0]]

InternalError: Error at src\attributes.c:1420: No such attribute, Invalid value

good work

how is graph defined?

When calling yen_igraph(graph, source, target, num_k, weights), what am I supposed to pass as weights? A list with edges' weights?

If you got the answer let me know too Please....I am stack :(

If you got the answer let me know too Please....I am stack :(

Just use the string you used to define the weights... In my case I have used 'weight' when creating the graph.

If you got the answer let me know too Please....I am stack :(

Just use the string you used to define the weights... In my case I have used 'weight' when creating the graph.

I am using adjacency matrix...and i need the program to find the weight bcz it won't work if i put the weight manually

hi, could you please give me an example about how to define a igraph between use the code you provided? thanks

Do lines 47-52 need to be after lines 54-59? Otherwise, path_cost() generates errors because some edges are removed from the graph.

hi, could you please give me an example about how to define a igraph between use the code you provided? thanks

hey, have you got how to define igraph..??
I'm also stuck here

igraph is just a Python lib: https://igraph.org/python/
I can't answer other questions as it's been ages since I coded this, sorry

Do lines 47-52 need to be after lines 54-59? Otherwise, path_cost() generates errors because some edges are removed from the graph.

Yes, I believe this is true (at least this fixes my bug when num_k is large)