Efficiently sorting through a generator of paths in order to find the longest one

Question

I am trying to write a function that calculates the maximum number of unexplored cells in a grid that is reachable within a given fuel limit. For example I have a 10x10 grid, and each cell in the grid is connected to each other and their weight is the Manhattan distance between them. From this grid I create an adjacency matrix whose dimensions are then 100x100, and create a graph from the adjacency matrix using the networkx library. I then use the all_simple_paths function which returns a generator that contains all the paths from a source to a target node.

Now comes the problem, when trying to sort through this generator in order to find the path that contains the most unexplored cells (in this case just equal to the path length), my program either runs out of memory, or it takes a really long time to execute.

I have tried to convert the generator into a list, and then sort the list from longest to shortest path length, but this just causes the python script to keep growing in memory size until it takes all available memory on my PC (16GB). I have also tried using the sorted function to sort the generator as below, but this just takes too long to execute, and eventually runs out of memory as well.

G = nx.from_numpy_array(A)
sorted_paths = sorted(nx.all_simple_paths(G, source=current_node, target=target_node), key=len, reverse=True)

If anybody has any suggestions as to how I can tackle my problem, it would be greatly appreciated. Whether it be sorting the generator, or maybe another function inside networkx/another python library that could help me find the max number of unexplored cells in a grid.

Answer 1

As I said in my comments above, I would search on the grid graph itself instead of searching on the graph of Manhattan distances.

1. The grid-graph is much smaller than the graph of Manhattan distances, and hence the search space of possible paths is smaller.

2. Paths with increments of 1 grid position will always be at least as optimal as paths that "jump" over a grid position.

3. Using the grid-graph, further optimisations become apparent. For example, iff the Manhattan distance between A and B is even, one need only consider paths of even maximum length. Say the distance between A and B is 10, and the maximum path length is 15. Then one only needs to look at paths of maximum length 14, as there will be no path of length 15 between A and B. This easily translates to another speedup of factor 2.

import networkx as nx
import time

g = nx.grid_2d_graph(10, 10)

for maximum_distance in range(17, 21):
    tic = time.time()
    paths = list(nx.all_simple_paths(g, (0, 0), (9, 9), maximum_distance))
    toc = time.time()
    print(f"Maximum distance: {maximum_distance}; total paths: {len(paths)}; time elapsed: {toc-tic:.1f} seconds")

# Maximum distance: 17; total paths: 0; time elapsed: 25.8 seconds
# Maximum distance: 18; total paths: 48620; time elapsed: 62.9 seconds
# Maximum distance: 19; total paths: 48620; time elapsed: 178.0 seconds
# Maximum distance: 20; total paths: 621452; time elapsed: 462.2 seconds