Networkx graph_from_place: нет пути между парой точек, как решить?

Question

Когда я создаю график networkx из OSM (Турин, Италия), и я пытаюсь запустить кратчайший путь между различными парами узлов. Там сказано, что пути нет. Я проверил и среди большинства пар точек нет путей. Как это возможно, поскольку я загрузил график из OSM, а узел является соединением между двумя ребрами?

G = ox.graph_from_place('Torino, Italy')
nodi=[]
for i in G.nodes():
   nodi.append(i)

print(len(nodi))
print(len(G.edges()))

false=0
true=0
for i in nodi:
  for j in nodi:
    if i!=j:
      a=G.has_edge(i, j)
      if a==False:
        false+=1
      if a==True:
        true+=1

print(false)
print(true)


24976
62072

623714119
61481

Когда я запускаю кратчайший путь, это ошибка. В приведенном ниже примере я выбрал источник и пункт назначения в Excel.

df=pd.read_excel('Ori_Ex.xlsx')
origin=[]

for index, row in df.iterrows():

   lat=row['lat']
   lon=row['lon']
   origin_point=(lat,lon)
   origin_node = ox.get_nearest_node(G, origin_point) 
   origin.append(origin_node)

done=[]

for i in origin: 
    orig=i
    for j in origin:
        if orig!=j:
            check = j+orig
            if check not in done:
               done.append(check)
               dest=j
               path=nx.shortest_path(G, source = orig, target=dest, weight = 'length')

               print('ok')

ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok

---------------------------------------------------------------------------

KeyError                                  Traceback (most recent call last)

/usr/local/lib/python3.6/dist-packages/networkx/algorithms/shortest_paths/weighted.py in multi_source_dijkstra(G, sources, target, cutoff, weight)
    743     try:
--> 744         return (dist[target], paths[target])
    745     except KeyError:

KeyError: 262294804


During handling of the above exception, another exception occurred:

NetworkXNoPath                            Traceback (most recent call last)

4 frames

/usr/local/lib/python3.6/dist-packages/networkx/algorithms/shortest_paths/weighted.py in multi_source_dijkstra(G, sources, target, cutoff, weight)
    744         return (dist[target], paths[target])
    745     except KeyError:
--> 746         raise nx.NetworkXNoPath("No path to {}.".format(target))
    747 
    748 

NetworkXNoPath: No path to 262294804.

Answer 1

Ваш код показывает, что большинство мест не связаны напрямую друг с другом. has_edge проверяет, имеет ли граф их непосредственное соединение, а не путь.

Попробуйте G.has_path(i,j)

---

Как примечание, в вашем коде:

a=G.has_edge(i, j)
      if a==False:
        false+=1
      if a==True:
        true+=1

можно переписать более четко как:

if G.has_edge(i,j):
    true += 1
else:
    false += 1