Reachability graph

given a graph G I want to compute a corresponding reachability graph; that
is, for a given distance r, if the distance between two vertices is less
than r they are joined by an edge.

The shortest_distance function with the Johnson algorithm works fine but
returns the distances between all pairs of vertices's and not just those
with a distance less than r. Iterating through all distances and finding
those with distance less than r is one solution but this is incredibly slow
due to the size of my graph.

Have you any suggestions? I’m considering using the breath first search
functionality but I don’t think there is an option to terminate the search
on parts the search tree with distance greater than r.
thanks in advance

Take a look at the shortest_distance() function:

It accepts a "max_dist" parameter that does what you want.