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