Optimizing shortest_path_length in networkx

Summary

As of networkx version 2.4rc1 [1], the helper function
networkx.algorithms.shortest_path.unweighted._single_shortest_path_length
can be optimized.

Current implementation: add neighbours of visited nodes to "nextlevel" set. Later, iterate through "nextlevel" set to expand their unseen neighbours. Iterate until "nextlevel" is empty.

Suggested optimization 1: keep track of nodes to be expanded in a queue (collections.deque) that remains sorted by distance from source node. Do not add already visited nodes to any set.

Suggested optimization 2: terminate immediately if all nodes have been visited. This saves a lot of work for dense, strongly connected graphs.

Investigation and analysis shows the effectiveness of the optimization. Measured speedup is at least a factor of 2. For dense strongly connected graphs, the speedup can be up to O(n), where n is the number of nodes.

Code

Current implementation

Suggested implementation

Results

Both algorithms were run on a set of test graphs. This included random graphs of varying sizes. It also included a large tree, a complete graph, and a couple of other special structure graphs. Both versions received exactly the same random graphs. The output was verified to be identical. The benchmarks were re-run with the two algorithms in reversed order, to check that cached variables did not play a role. 

Random + structured graphs, single iteration all_pairs_shortest_paths

time / ms                    current         optimized           
n=1e1, m=1e1                    0.15              0.14             
n=1e1, m=3e1                    0.34              0.18            
n=1e2, m=1e2                    2.04              1.35           
n=1e3, m=1e3                   56.76             31.89         
n=1e3, m=1e5                27857.46            612.96        
caveman(100,10)              3373.64           1168.82       
windmill(10, 10)               32.08              4.09          
nary_tree(3, 1000)           1886.88            810.51       
complete(100)                 205.25              3.48           
mlp(10, 10)                    15.09              5.70          
amnesia(100)                  261.17             41.43         

Small random graphs, total all_pairs_shortest_paths, 1000 iterations

time / ms        current   optimized     
n=1e1, m=1e1       63.69       56.82    
n=1e1, m=3e1      213.32       87.55   
n=1e2, m=1e2     2035.69     1296.77  

Empirical conclusions

For all graphs that were tested, the optimized algorithm was faster. The speedup for a tree is a factor of 2, which is in the lower end. For the very smallest graph, the speedup is "only" on the scale of 10%. However, these functions execute so fast that function calls and other Python overhead probably plays a large role. For the largest dense strongly connected graph, the observed speedup is a factor of 50. It is argued below that the speedup for such graphs can be up to O(n).

Analysis

Optimization 1 (use queue, not sets):
The current implementation keeps a set "thislevel" of unexpanded nodes that it goes through. All neighbours of "thislevel" are added to another set "nextlevel", whether they have been expanded or not. In the below graph, that means that all the bottom nodes will get added to "nextlevel" n times.

Current implementation will add bottom nodes to a set 'n' times, as well as do a set lookup 'n' for each bottom node. Suggested implementation will only do a set lookup for bottom nodes 'n' times.

In the suggest optimization, it is checked whether a node has been expanded before it is added to the queue. The above graph is the one referred to as "amnesia(n)" in the results table. The empiric speedup is about a factor of 6, independent of n. 

Optimization 2 (early termination):
In the current implementation, we check all neighbours of the nodes in "thislevel" until no new unvisited nodes are found. In the suggested optimization, we count the number of unvisited nodes using just an integer counter. Whenever an unvisited node is found, we decrement. If the counter reaches zero, search can terminate. This can make a big difference for dense, strongly connected graphs.

In the extreme case, we have the complete graph, which requires checking (n-1)^2 edges in the current implementation, but only (n-1) edges in the suggested optimization. That is to say, an O(n) reduction of the required work. The measured speedup for the complete graph with 100 nodes is a factor of 60. For a large dense graph with 1000 nodes and approx. 100,000 random (directed) edges, the measured speedup is a factor of 50.

A risk case is if the graph changes during the search. This can cause incorrect results. This can also happen with the current implementation. However, the optimized algorithm will still terminate (unless new nodes and edges are added faster than the algorithm can process them), because it also terminates when the queue runs out.

Impact

The function _single_shortest_path_length is directly used by

• single_source_shortest_path_length 
• single_target_shortest_path_length
• all_pairs_shortest_path_length

Indirectly, references were found to these functions in:

• algorithms.distance_measures
• algorithms.distance_regular
• algorithms.efficiency_measures
• algorithms.bipartite.centrality
• algorithms.centrality.closeness
• algorithms.connectivity.stoerwagner
• generators.ego

It may be used by other functions within networkx, but it's hard to determine since functions can be passed as arguments by another name.

Details, discussion

Currently, the function accepts a dict "firstlevel", where the values are not used, only the keys. In all functions that call _single_shortest_path_length directly (which is just 2), "firstlevel" is either {source: 1} or {target: 1}. 

It may be a desirable use case to "seed" the shortest_path_length with different nodes predetermined to be at different levels. This is not supported by the current implementation, however. It is not supported by this optimization either.

Further suggestion

Either: make the argument "firstlevel" a set, so that shortest distance is counted from a number of source nodes. This use case is currently supported, although it is obfuscated by the fact that a dict is expected. So basically, just change the docstring. 

Or: replace "firstlevel" with a single "source" node. The function is, after all, called _single_shortest_path_length.

Update 2019-10-24

This pull request led to a merge, see the rest of the conversation here:
https://github.com/networkx/networkx/pull/3647

References

[1] Hagberg, Aric, et al. "NetworkX." URL http://networkx. github. io/index. html (2013).