This works like a charm! With it, I'm down to 228 ms ± 1.31 ms from 3.6 s ( 82.9 ms ± 2.45 ms for shortest_distance(G) ).
It's still very very expensive as it's 2.75 times APSP but approaching reasonability. The costly remaining part is the manual B x B.* I tried to speed it up by the approximation to limit G to B since I know that B is connected but graph-tool segfaults right away (I wrote another ticket for that). :/ If anyone else has any ideas on how to speed this up, I'd be very grateful! Cheers, Stephan - - - o - - - *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\B) x (V\B) = [ (V x V) \ [ (V x B) + (B x V) ] ] U (B x B). Or in graph-tool terms: - (V x V): shortest_distance(G) - (B x V): shortest_distance(G, b, _) for b in B - (V x B): shortest_distance(GraphView(G, reversed=True), b, _) for b in B - (B x B): shortest_distance(G, u, v) for u,v in B x B Von: Stephan Monecke <[email protected]> Gesendet: Mittwoch, 17. November 2021 20:24 An: Main discussion list for the graph-tool project Betreff: [graph-tool] Re: All Pairs Shortest Path with limitations 🥳 I didn't know that existed! Thanks a ton, I'm really looking forward to test it out tomorrow! Cheers, Stephan -- Sent from my mobile device. Please excuse my brevity. Am 17. November 2021 19:27:37 MEZ schrieb Tiago de Paula Peixoto <[email protected]>: >Am 17.11.21 um 19:22 schrieb Monecke, Stephan: >> 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". >> > >Of course it does. Just reverse the graph with: > > GraphView(g, reversed=True) > > _______________________________________________ graph-tool mailing list -- [email protected] To unsubscribe send an email to [email protected] _______________________________________________ graph-tool mailing list -- [email protected] To unsubscribe send an email to [email protected]
