Good day, I can give some feedback on this since I've also used graph-tool for getting paths. In my case it was slightly different because (1) I wanted to sample paths without bias, (2) I used a weight on the arcs, (3) my arcs were directed and (4) the number of nodes and edges was really big . Sadly, (1) and (2) made it not very easy to do it via graph tool.
As far as I understand, graph tool uses a DFS to obtain `all_paths`. When the number of potential paths is large for a given cutoff but the remaining number of valid paths is small, it will iterate a long time (at each `next()`) until it proves there are no more paths that have a length equal or smaller to the cutoff. You could choose to stop the iteration once it starts taking longer than certain time to find a path, but even this is no guarantee. There may be many paths still remaining to be found. You can also play with the number of paths to return... Another thing you should take into account if you want to stop `all_paths` at a limit number of paths is that since it does a DFS, two paths that are close in the returned list will be "close" in structure (i.e., similar). So "sampling" paths this way is not great. Sorry I cannot be of more help. If you find a better way to do it with graph-tool, please share it over here! Good luck! Franco On Wed, Dec 16, 2020 at 12:00 PM <[email protected]> wrote: > Send graph-tool mailing list submissions to > [email protected] > > To subscribe or unsubscribe via the World Wide Web, visit > https://lists.skewed.de/mailman/listinfo/graph-tool > or, via email, send a message with subject or body 'help' to > [email protected] > > You can reach the person managing the list at > [email protected] > > When replying, please edit your Subject line so it is more specific > than "Re: Contents of graph-tool digest..." > > > Today's Topics: > > 1. Find best paths sorted by length with graph tools (Ruhm) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Tue, 15 Dec 2020 08:22:24 -0700 (MST) > From: Ruhm <[email protected]> > To: [email protected] > Subject: [graph-tool] Find best paths sorted by length with graph > tools > Message-ID: <[email protected]> > Content-Type: text/plain; charset=us-ascii > > 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/ > > > ------------------------------ > > Subject: Digest Footer > > _______________________________________________ > graph-tool mailing list > [email protected] > https://lists.skewed.de/mailman/listinfo/graph-tool > > > ------------------------------ > > End of graph-tool Digest, Vol 155, Issue 4 > ****************************************** >
_______________________________________________ graph-tool mailing list [email protected] https://lists.skewed.de/mailman/listinfo/graph-tool
