[GIS] Does not show shortest path in networkx (in QGIS)

astarnetworkxpythonqgis

I used the following commands (in qgis console) to get the shortest path with astar algorithm. But the result shows 'NetworkXNoPath' every time. Why was that? Please help me to find a solution to this problem.

>>>import networkx as nx
>>>G = nx.read_shp(str(iface.mapCanvas().currentLayer().source()))
>>>len(G.edges())
18562
>>>route = nx.shortest_path(G, G.nodes()[1], G.nodes()[10])
Traceback (most recent call last):
  File "<input>", line 1, in <module>
  File "/usr/local/lib/python2.7/dist-packages/networkx/algorithms/shortest_paths/generic.py", line 136, in shortest_path
  File "/usr/local/lib/python2.7/dist-packages/networkx/algorithms/shortest_paths/unweighted.py", line 138, in bidirectional_shortest_path
  File "/usr/local/lib/python2.7/dist-packages/networkx/algorithms/shortest_paths/unweighted.py", line 203, in _bidirectional_pred_succ
NetworkXNoPath: No path between (106.8249296, -6.2047544) and (106.7920071, -6.2245956).

Best Answer

Given that the graph is loading successfully and no paths are being found there are two possibilities that might cause this:

  1. NetworkX does not split lines when loading into the system as it simplifies edges to their start and end points and only where those points overlap are edges created. To fix this you will need to explode your lines, using something like the Explode tool from the Processing toolbox to split the lines.
  2. Points at the ends of lines may not be 100% coincident, meaning no join will be created between the edges at those points. I don't believe that NetworkX has a way of reducing the decimal accuracy when importing shapefiles so your best bet is to create a new graph from the old with something like the below snippet. NetworkX interprets nodes with the same key as the same, and rounding floats will give the same signature.
lower_point_accuracy_G = nx.Graph()

for (start_x, start_y), (end_x, end_y) in G.edges_iter():
    lower_point_accuracy_G.add_edge(
        (round(start_x, 4), round(start_y, 4))
        (round(end_x, 4), round(end_y, 4))
    )
Related Question