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).
6
  • Have you tried this from the Python prompt outside QGIS?
    – om_henners
    Jun 2, 2014 at 1:44
  • I wrote a seperate .py file and called these. But same answer
    – Ramanayake
    Jun 2, 2014 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, 2014 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, 2014 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, 2014 at 2:49

1 Answer 1

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))
    )
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, 2014 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, 2014 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.