How to ignore paths of equal length in Yen's shortest path algorithm (python networkx)

Question

I am using a code to implement Yen's algorithm in order to find the k shortest paths. However I would like it to produce the k shortest paths of different lengths, i.e. if multiple paths have the same length it just chooses one of those and returns the length.

The code of Yen's algorithm is as follows (credits to https://github.com/nextgis/metro4all/wiki/Yen%27s-algorithm-for-networkx):

import networkx as nx 
import Queue


def path_cost(graph, path, weight=None):
    pathcost = 0
    for i in range(len(path)):
        if i > 0:
            edge = (path[i-1], path[i])
            if weight != None:
                pathcost += graph.get_edge_data(*edge)[weight]
            else:
                #just count the number of edges
                pathcost += 1
    return pathcost


def ksp(graph, source, target, num_k, weight):
    # Shortest path from the source to the target
    A = [nx.shortest_path(graph, source, target, weight=weight)]
    A_costs = [path_cost(graph, A[0], weight)]#[nx.shortest_path_length(graph, source, target, weight=weight)]

    # 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
        try:
            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 = (path[i], path[i+1])
                        if not graph.has_edge(*edge):
                            continue
                        removed_edges.append((edge, graph.get_edge_data(*edge)))
                        graph.remove_edge(*edge)

                # Calculate the spur path from the spur node to the sink
                try:
                    spurPath = nx.shortest_path(graph, spurNode, target, weight=weight)

                    # Entire path is made up of the root path and spur path
                    totalPath = rootPath + spurPath
                    totalPathCost = path_cost(graph, totalPath, weight)
                    # Add the potential k-shortest path to the heap
                    B.put((totalPathCost, totalPath))

                except nx.NetworkXNoPath:
                    pass

                #Add back the edges that were removed from the graph
                for removed_edge in removed_edges:
                    graph.add_edge(
                        *removed_edge[0],
                        **removed_edge[1]
                    )

            # Sort the potential k-shortest paths by cost
            # B is already sorted
            # Add the lowest cost path becomes the k-shortest path.
            while True:
                try:
                    cost_, path_ = B.get(False)
                    if path_ not in A:
                        A.append(path_)
                        A_costs.append(cost_)
                        break
                except Empty:
                    break
        except Queue.IndexError:
            pass

    return A_costs

I tried to change the line at the end if path_ not in A: to if (path_ not in A) and (cost_ not in A_costs):, but that returns the error

AttributeError                            Traceback (most recent call last)
<ipython-input-58-038c80524d5d> in <module>()
----> 1 ksp(G,'source','target',100,"weight")

<ipython-input-54-7b3d0aa42558> in ksp(graph, source, target, num_k, weight)
     77                 except Empty:
     78                     break
---> 79         except Queue.IndexError:
     80             pass
     81 

AttributeError: 'module' object has no attribute 'IndexError'

What would be a better way?

EDIT: My test graph is the following:

G = nx.DiGraph()

G.add_node("source")
G.add_node("target")

for i in range(16):
    G.add_node(i+1)

for i in range(4):
    G.add_edge("source",i+1,weight=0)
    G.add_edge(16-i,"target",weight=0)

W=np.empty([3,4,4])

W[0::]=np.array([[3,9,7,16],
                 [21,2,18,29],
                 [37,32,41,17],
                 [42,12,19,26]])
W[1::]=np.array([[9,12,10,22],
                 [24,5,11,28],
                 [40,35,38,19],
                 [45,6,43,27]])
W[2::]=np.array([[1,2,3,4],
                 [5,6,7,8],
                 [9,10,11,12],
                 [13,14,15,16]])

for i in range(4):
    for j in range(4):
        G.add_edge(i+1,j+5,weight=W[0,i,j])
        G.add_edge(i+5,j+9,weight=W[1,i,j])
        G.add_edge(i+9,j+13,weight=W[2,i,j])

If I do

print newnewksp(G,'source','target',8,"weight")
print newksp(G,'source','target',35,"weight")
print ksp(G,'source','target',35,"weight")

(where newksp is my suggestion, and newnewksp @H4kim 's), I get

[12.0, 13.0, 22.0, 27.0, 31.0, 40.0, 43.0, 50.0]
[12.0, 13.0, 14.0, 15.0, 16.0, 19.0, 20.0, 21.0, 22.0, 23.0, 27.0, 28.0, 29.0, 30.0, 31.0, 32.0, 34.0, 35.0, 36.0, 37.0, 39.0, 40.0, 41.0, 42.0, 47.0, 48.0, 49.0, 50.0, 51.0, 52.0, 53.0, 54.0, 55.0, 56.0, 57.0]
[12.0, 13.0, 13.0, 14.0, 14.0, 15.0, 15.0, 16.0, 19.0, 20.0, 20.0, 21.0, 21.0, 22.0, 22.0, 22.0, 22.0, 22.0, 23.0, 23.0, 23.0, 23.0, 24.0, 24.0, 24.0, 25.0, 25.0, 25.0, 27.0, 27.0, 28.0, 28.0, 28.0, 29.0, 29.0]

Answer 1

I think your change is ok but Queue.IndexError should be replaced by IndexError since it is a python built-in exception. At the opposite Empty is not a built-in exception so it should be Queue.Empty.

I suppose we shouldn't change A in the main loop because is critical for the algorithm. Instead we could try to change the end condition by tracking the different costs values in a set :

import networkx as nx 
import Queue


def path_cost(graph, path, weight=None):
    pathcost = 0
    for i in range(len(path)):
        if i > 0:
            edge = (path[i-1], path[i])
            if weight != None:
                pathcost += graph.get_edge_data(*edge)[weight]
            else:
                #just count the number of edges
                pathcost += 1
    return pathcost


def ksp(graph, source, target, num_k, weight):
    # Shortest path from the source to the target
    A = [nx.shortest_path(graph, source, target, weight=weight)]
    A_costs = [path_cost(graph, A[0], weight)]

    unique_costs = set(A_costs)

    # Initialize the heap to store the potential kth shortest path
    B = Queue.PriorityQueue()

    k = 1
    while len(unique_costs) < num_k:
        # The spur node ranges from the first node to the next to last node in the shortest path
        try:
            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 = (path[i], path[i+1])
                        if not graph.has_edge(*edge):
                            continue
                        removed_edges.append((edge, graph.get_edge_data(*edge)))
                        graph.remove_edge(*edge)

                # Calculate the spur path from the spur node to the sink
                try:
                    spurPath = nx.shortest_path(graph, spurNode, target, weight=weight)

                    # Entire path is made up of the root path and spur path
                    totalPath = rootPath + spurPath
                    totalPathCost = path_cost(graph, totalPath, weight)
                    # Add the potential k-shortest path to the heap
                    B.put((totalPathCost, totalPath))

                except nx.NetworkXNoPath:
                    pass

                #Add back the edges that were removed from the graph
                for removed_edge in removed_edges:
                    graph.add_edge(
                        *removed_edge[0],
                        **removed_edge[1]
                    )

            # Sort the potential k-shortest paths by cost
            # B is already sorted
            # Add the lowest cost path becomes the k-shortest path.
            while True:
                try:
                    cost_, path_ = B.get(False)
                    if path_ not in A:
                        A.append(path_)
                        A_costs.append(cost_)
                        unique_costs.add(cost_)
                        break
                except Queue.Empty:
                    break
        except IndexError:
            pass

        k += 1

    return list(unique_costs)

It returns the following with your example :

>>> print ksp(G,'source','target',35,"weight")
[12.0, 13.0, 14.0, 15.0, 16.0, 19.0, 20.0, 21.0, 22.0, 23.0, 24.0, 25.0, 27.0, 28.0, 29.0, 30.0, 31.0, 32.0, 33.0, 34.0, 35.0, 36.0, 37.0, 38.0, 39.0, 40.0, 41.0, 42.0, 43.0, 44.0, 45.0, 46.0, 47.0, 48.0, 49.0]