The first 10 shortest paths in a graph - Igraph 0.6 - Python 2.7

Question

I was wondering about this ever since I've started to successfully implement Igraph into my coding: Can you retrieve with get_all_shortest_paths as many shortest paths as you like. Let's say first 10.

I've understood so far that retrieving ALL shortest paths in a undirected graph is non-sense since in most cases you have infinite amount of them.

But can I simply retrieve first 10 shortest paths?

I've tried to achieve this with an undirected g = Graph() :

list = []
list.append(g.get_all_shortest_paths(index1,index2, "distance")[0])   # shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[1])   # second shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[2])   # third shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[3])   # forth shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[4])   # fifth shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[5])   # sixth shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[6])   # seventh shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[7])   # eigth shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[8])   # ninth shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[9])   # tenth shortest path

#"distance" is from g.es["distance"]

It would alway give me error that list index is out of range. Actually I can't even get list.append(g.get_all_shortest_paths(index1,index2, "distance")[1]), though I know there are more then 10 paths there.

There is nothing special about the graph. thousands of vertexes, all connected somehow, I mean various vertex degrees.

Finally I would like to have a wx.spin or wx.ComboBox to choose between the paths (i.e. the shortest path which is a national highway in real life has ice on it during winter so I would like to take the second shortest road between City1 and City2... then oh no.. that has kangoroos jumping all over it so I take the third, or better forth path because there I know a McDonalds and I really like to eat junk food bla bla)

I know shortest != short, though I need something like: if shortest no good then ignore that, go to second and so on. I've searched Google but it is not clear for me how can I do this.

Thank you in advance!

Edit: I might mention that list.append(g.get_all_shortest_paths(index1,index2, "distance")[1]) of course is working when there are exactly 2 shortest paths with naturally the exact same distances.

Important Update:

Since I've ingloriously misunderstood g.get_all_shortest_paths this part will change in my code to g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath") and I also mention that the graph is weighted, but that bit is obvious anyway:

list = []
g.es["weight"] = distance
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[0])   # shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[1])   # second shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[2])   # third shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[3])   # forth shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[4])   # fifth shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[5])   # sixth shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[6])   # seventh shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[7])   # eigth shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[8])   # ninth shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[9])   # tenth shortest path

#"distance" is a list containing the weights
# graph is TRUE-ly weighted now

How to get the first 10 or all short paths between two vertex's?

This question is still looking for its answer to be accepted. Thank you.

(P.S. I've kept the wrong approach in the first part of the question since might be other enormous idiobooms out there like me who try the same thing)

Answer 1

Okay, I'm still unsure what you mean by the "first 10 shortest paths", but here is what I think you might want to achieve. You have a graph where the edges are labeled by the actual (say, Euclidean) distance of the two endpoints. You are given two points, and you wish to find a few alternate paths between them while trying to keep these paths as short as possible. Note that since your graph is weighted, it is very unlikely that you will have many shortest paths between two points - in order for all of the paths to be the shortest, they must have exactly the same total weight. If your weights measure actual distances "as the crow flies", it is very unlikely that such a co-occurrence ever happens - the ten paths you would be looking for would have slightly different lengths. So, get_all_shortest_paths is not useful to you, not only because it does not use weights, but also because even if it did, you are unlikely find multiple paths between two points that have exactly the same length.

An alternative is get_shortest_paths, which can consider weights, but it will return only one path between a pair of vertices. (The reason why it is called get_shortest_paths is because it returns multiple paths if you specify multiple target vertices - more precisely, it gives you one path for each target vertex). So, you cannot use get_shortest_paths to obtain the ten paths you are looking for.

After some googling, I have found an implementation of the k-shortest-paths algorithm that might be useful for you. It is not part of igraph, but you can save your graph from igraph, call out to the compiled executable of the k-shortest-paths algorithm using os.system or the subprocess module in Python and then parse the result somehow.