Find best paths sorted by length with graph tools

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Find best paths sorted by length with graph tools

Ruhm
Hello,

I'm a beginner in graph algorithm, and I have trouble to find an efficient
solution for my issue.

My goal is to find X best paths between two vertices. Not only the shortest
paths, but sub optimals path, ordered by length.
My graph is relatively small (10k vertices, 20k edges) and is not directed.
I don't use weight or vertices/edges attributes.

My current prototype:
I use first all_shortest_paths to find the best paths.
Then I use all_paths with a cutoff = length of shortest_path + K . K is an
arbitrary value set as an argument of my function.
Finally, I sort the return of all_paths by path length and select the X
shortest.

It works fine when the vertices are close to each other, but when my cutoff
is over 20ish, the all_paths function take forever and my CPU usage
skyrockets. I can't even iterate with next() over the result. I understand
that all_paths is not very effective in my case, but at the moment this is
my best guess.

I'm reading the documentation of graph tools, but I cant find any other
function fitting my needs. I 'm considering using the function bfs_search
with a custom BFSVisitor, but I'm afraid i will encounter performance issues
too.

Am i missing something?

Anyways, thanks for this library, its impressive.
Sorry for my poor English.

Regards



--
Sent from: https://nabble.skewed.de/
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Find best paths sorted by length with graph tools

Tiago Peixoto
Administrator
Am 15.12.20 um 16:22 schrieb Ruhm:
> My goal is to find X best paths between two vertices. Not only the shortest
> paths, but sub optimals path, ordered by length.

Finding the k-shortest paths is not yet implemented in graph-tool. You
can see a simple version of the algorithm here:

    https://en.wikipedia.org/wiki/K_shortest_path_routing

If you open an issue in the website with a feature request, I will
implement it when I find the time.

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

OpenPGP_signature (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>