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 <[email protected]> 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 <[email protected]> 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 -- [email protected] > To unsubscribe send an email to [email protected] _______________________________________________ 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]
