Hi Aleks! I thank you for your answer! If already tried that but have not been successful speed-wise. A full APSP of a very small test graph already takes around 200 ms. The fastest I could get as described below runs in about 3.6 s. :/ The main reason is that shortest_distance() has a "single source, all targets" mode but no "single target, all sources" mode (the reverse) - as soon as "source" is empty, it defaults to APSP, neglecting "target". Hence I have to do this part manually using shortest_distance(G, u, v).* My bottleneck is the APSP calculation. Cheers, Stephan *Since the graph is directed, we have the following: Say V is the set of all vertices and B a subset of V I want to exclude as sources / targets from APSP. Then the set of points is [ (V x V) \ [ (V x B) + (B x V) ] ] + (B x B). Or in graph-tool terms: - (V x V): shortest_distance(G) - (V x B): shortest_distance(G, v, b) for b in B for v in V (horrible run-time) - (B x V): shortest_distance(G, b, _) for b in B - (B x B): shortest_distance(G, u, v) for u,v in B x B ________________________________ Von: Aleksandar Trifunovic <akstrfn@gmail.com> Gesendet: Mittwoch, 17. November 2021 17:54 An: Main discussion list for the graph-tool project Betreff: [graph-tool] Re: All Pairs Shortest Path with limitations Hi Stephan, If the number of start-end pairs is not high you could compute all shortest paths and then remove the ones you are not interested in. Best, Aleks On Wed, Nov 17, 2021 at 3:55 PM Monecke, Stephan <stephan.monecke@ds.mpg.de> wrote:
Hi together,
I have a question on how you would tackle the following:
I have a graph and want to calculate all possible shortest paths but exclude a few nodes as starting / stopping positions.
I can not filter out those vertices, since paths should be allowed to pass them - just not start or terminate there.
Calculating all possible shortest paths manually is computationally infeasible.
Thanks a lot!
Stephan
_______________________________________________ graph-tool mailing list -- graph-tool@skewed.de To unsubscribe send an email to graph-tool-leave@skewed.de
_______________________________________________ graph-tool mailing list -- graph-tool@skewed.de To unsubscribe send an email to graph-tool-leave@skewed.de _______________________________________________ graph-tool mailing list -- graph-tool@skewed.de To unsubscribe send an email to graph-tool-leave@skewed.de