[Python] Creating a Adjecency matrix fast for use in path finding to calculate gird distance...

Goal


I'm working on a project that requires me visualize how far a given budget can reach on a map with different price zones.

Example with 3 price zones, water, countryside, and city, each having different costs per meter traveled:



Red point is the origin, green point is just a sample point, it has no bearing on the result. Gradient goes from yellow (cheap) to purple (max budget)

Issue


Time complexity is currently really bad, causing time to grow very fast as I increase the resolution (decreasing size in meters of each cell). This is most likely due to the iterative creation of the scipy.sparse.lil_array when creating a array adjacency graph.

Details


My current processes to achieve this is by following 6 major steps (time added to show bottlenecks):

1. 
   Create a Python list of shapely.geometry.Point which represents all points in a 2d grid which we will sample the prices from the geopandas geometry. The list is initialized with empty values before modifications. I iteratively set each index (one at a time) to a point created depending on the grid cell size. And lastly I convert the python list into a pandas dataFrame to later intersect with the geopandas regions. (13.6s)
   
   
2. 
   I now use the dataFrame with points and convert it into a GeoDataFrame and the use gpd.sjoin against my diffrent price areas to receive in this case 3 geoDataFrame's each containing only the points which intersected with the given price area. (0.7s)
   
   
3. 
   After mapping each point with their price, I want to combine it back into a 2d array with the value being the price to do this I use a Python 2d List and index and replace values using a conversion from point coordinates to index coordinates. (14.9s)
   
   
4. 
   We now have a 2d array that contains the cost/weight for each cell. Now I want to convert it into a graph (matrix adjacency graph). To do this I use an iterative procces and inserts each edge into a scipy.sparse.lil_array and then after each element has been connected convert the array into a scipy.sparse.csr_array (136.7s)
   
   
5. 
   I now call scipy.sparse.csgraph.dijkstra and use the distance array created. (0.4s)
   
   
6. 
   Due to a fixed price needed for each node I once again iteratively loop through the array adding the fixed cost. (0.2s)
   

In addition to step 4 I should mention that I use more than 4 edges per node. Namely using a 5x5 centered on the node (but ignoring duplicate cardinal and diagonal paths), but this introduces a bit of a error margin as it is possible to avoid cost of a cell by jumping diagonal over it, but the error margin should be small enough that it can be ignored. This is due to the otherwise square result:



Question


Is this a good approach to this problem? (even if it has blocky unnatural edges due to it using graph with limited amount of edges for each node)
If so how can I more efficiently create my adjacency graph (Reduce time spent in step 4)?

What I have tried

1. I have tried drawing lines from origin in a circle and saving how long the line can get before the budget runs out. this gave me poor runtime (probably a coding issue) but also can not handle finding a cheaper route by going further thru cheaper areas.
2. Using a list adjacency graph. whilst this reduced creation time by a lot, it also increased path finding time by a larger margin (needed to use a self implemented version of Dijkstra based on Wikipedia using a heap and early exit using budget) in total the total time of creating and path finding is around 2x slowdown compared to the adjacency matrix method mentioned above.

Continue reading...