Computing K number of shortest paths for a single end-node

graph-tool
1

Hello,

I have just discovered graph-tool and read through a bunch of documentation.
I am fairly new to python and graphs. The speed comparison to networkx
really impressed me!

I was utilizing networkx for a project to find K number of weighted shortest
paths from a source to a target node.
It has 'all_simple_path' function - outputting a generator that generates
all paths starting from shortest to longest. I would simply cut the
generator to the K number of paths that I needed.

I can't find a similar function in graph-tool, but I am sure this could be
implemented. The only thing I found was the all_shortest_paths function, but
that only returns the shortest path(s), in most cases only 1. Could you
point me in the right direction how to efficiently generate and store K
number of shortest paths for a specified node?

I know I could just generate all paths and then cut down based on order, but
that's not a real solution since I am running into memory issues with a
small amount of nodes.

Thanks!

2

It's just called all_paths():

https://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.all_paths

3

Thank you very much for your reply!!

Just to confirm, the all_paths function will return all paths starting from
the shortest to the longest in that order? Meaning that if I generate 100
paths, the first one will be the shortest, 100th will be the longest, and
15th path will be the 15th shortest?

4

No, in this function the paths are not sorted by length, as it uses
depth-first search. But note that the all_simple_paths() function from
networkx does not sort them either.

Best,
Tiago