2

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).
Improve this question
6
  • Have you tried this from the Python prompt outside QGIS? – om_henners Jun 2 '14 at 1:44
  • I wrote a seperate .py file and called these. But same answer – Ramanayake Jun 2 '14 at 2:06
  • Couple of questions then: Which version of networkx are you using? Does the graph that you've created from the shapefile contain any edges (i.e. len(G.edges()))? – om_henners Jun 2 '14 at 2:15
  • I'm using networkx 1.7(I just used sudo pip install networkx). Yes,it shows bunch of nodes and edges when type G.nodes() and G.edges(). – Ramanayake Jun 2 '14 at 2:38
  • Hmm. You could try upgrading networkx to 1.8.1 (I believe the latest version), but really I don't think that will resolve the issue. In theory if there's no path there should be a NetworkXNoPath error. Would it be possible to add your sample .py file to the question as well? And possibly a small subset of sample data? Also, which version of QGIS are you using currently? – om_henners Jun 2 '14 at 2:49
2

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))
    )
Improve this answer
2
  • I tried explode lines using, Vector->Geometry Tools->Single parts to multipart. But then the edges and nodes shows only one.. lyr_1.nodes() [(106.7383696, -6.1091154)] lyr_1.edges() [((106.7383696, -6.1091154), (106.7383696, -6.1091154))] len(lyr_1.nodes()) 1 len(lyr_1.edges()) 1 – Ramanayake Jun 9 '14 at 4:04
  • And also tried to create a separate graph as you said,and got error,Traceback (most recent call last): File "<input>", line 4, in <module> TypeError: 'tuple' object is not callable. And I also installed networkx 1.9.. But same thing happened. Is there anything I have to install with networkx.. – Ramanayake Jun 9 '14 at 4:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.