I am working with large weighted undirected graphs and need to calculate a form of betweenness and closeness up to a certain maximum distance.
What is the most efficient way to go about this with graph-tool? I basically need all-pairs shortest paths up to a certain maximum distance, after which I can use the property arrays to deduce the information I need.
For example:
- Using the provided betweenness and closeness methods will search all pairs of nodes, whereas I only need to search up to a certain distance.
- Topology.shortest_distance() lets me search to a maximum distance, but only if source is not set to None. So what I am currently trying is to iterate all nodes as source ‘i’. For each ‘i’, the remaining ‘j-vertices’ are provided to the target parameter as an iterable. To avoid duplication, I pop each ‘i’ from ‘j-vertices’ as the loop progresses, so that if it has already searched from ‘i’ to ‘j’ it doesn’t later also search from ‘j’ to ‘i’.
For each ‘i’ source the method therefore returns the distances to all ‘j’ as well as the predecessor map. I then use the predecessor map to generate the shortest path for each ‘i’-‘j’ pair by using the topology.shortest_path() method (with predecessor map provided so that it doesn’t recalculate the shortest paths.)
There is quite a bit of looping going on and I’m wondering if there is a simpler way to calculate all-pairs shortest paths to a maximum distance while minimising duplication of shortest path searches?
Thanks,
Gareth