Computing K number of shortest paths for a single end-node
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! -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
Am 26.02.19 um 02:12 schrieb sergzz:
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?
It's just called all_paths(): https://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.al... -- Tiago de Paula Peixoto <tiago@skewed.de>
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? -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
Am 01.03.19 um 00:23 schrieb sergzz:
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?
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 -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (2)
-
sergzz -
Tiago de Paula Peixoto