Панды: Наименьшая длина пути между большими парами узлов - PullRequest
Новая
       27

Панды: Наименьшая длина пути между большими парами узлов

4 голосов
/ 17 марта 2019

У меня есть фрейм данных, содержащий orgin_nodes и Distination_nodes следующим образом: enter image description here

Мне нужно вычислить short_path_length между этими узлами, используя библиотеку networkx, применив следующую функцию: 

def short_path_length (node1,node2):
    return nx.shortest_path_length(G, node1, nod2,weight='length')

df['short_path_length']=np.vectorize(short_length_nodes)(df['Orgin_nodes'],df['Destination_nodes'])

Где G - сетевой график, полученный из библиотеки osmnx: Я применил этот код к образцу Dataframes, получив в результате следующее:

enter image description here

Когда я применил его для оригинального фрейма данных с 3000000 строками, это заняло больше времени?

Есть ли способ сделать бег быстрее?

update1:

Я следовал @gboeing ответу и преобразовал networkx graph в igraph следующим образом (https://github.com/gboeing/osmnx-examples/blob/master/notebooks/18-osmnx-to-igraph.ipynb):

ox.config(use_cache=True, log_console=True)
weight = 'length'
G_nx = nx.relabel.convert_node_labels_to_integers(G)
# convert networkx graph to igraph
G_ig = ig.Graph(directed=True)
G_ig.add_vertices(list(G_nx.nodes()))
G_ig.add_edges(list(G_nx.edges()))
G_ig.vs['osmid'] = list(nx.get_node_attributes(G_nx, 'osmid').values())
G_ig.es[weight] = list(nx.get_edge_attributes(G_nx, weight).values())



def short_path_length(node1,node2):
        return G_ig.shortest_paths(source=node1,target=node2, weights=weight)[0][0]


df['short_path_length'] = df.apply(short_path_length(df['Orgin_nodes'],df['Destination_nodes']), axis=1)

Я получил эту ошибку: 

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<timed exec> in <module>()

<timed exec> in short_path_length(node1, node2)

ValueError: vertex IDs must be positive, got: -1

причина этой ошибки в том, что номер узла в df['Orgin_nodes'],df['Destination_nodes'] не совпадает с G_ig именами вершин. Что я должен сделать, чтобы решить это?

Update2

Я решил вышеупомянутую проблему Создавая массив данных, содержащий G_nx.nodes и соответствующие ему значения OSMid, и заменил Orgin_nodes и Destination_nodes на G_nx.nodes следующим образом: 

df_indices_osmid_Orgin=pd.DataFrame.from_dict({'Orgin_nodes':list(nx.get_node_attributes(G_nx, 'osmid').values()),'Indecise_Nodes_Orgin':list(G_nx.nodes())})
df=pd.merge(df,df_indices_osmid_Orgin,how='inner',on='Orgin_nodes')
df_indices_osmid_Dest=pd.DataFrame.from_dict({'Destination_nodes':list(nx.get_node_attributes(G_nx, 'osmid').values()),'Indecise_Nodes_Dest':list(G_nx.nodes())})
df=pd.merge(df,df_indices_osmid_Dest,how='inner',on='Destination_nodes')

и примените следующую функциональную выборку df для измерения кратчайшего расстояния: 

sampl_df=df.head()
def short_path_length(row):
    return G_ig.shortest_paths(source=row['Indecise_Nodes_Orgin'], target=row['Indecise_Nodes_Dest'], weights=weight)[0][0]
sampl_df['short_path_length_1'] = sampl_df.apply(short_path_length, axis=1)

Хотя он работает без ошибок , это заняло больше времени по сравнению с предыдущей пробной версией: 

sampl_df=df.head()
%%time
    def short_path_length(row):
        return G_ig.shortest_paths(source=row['Indecise_Nodes_Orgin'], target=row['Indecise_Nodes_Dest'], weights=weight)[0][0]
sampl_df['short_path_length_1'] = sampl_df.apply(short_path_length, axis=1)

Время стены: 2,89 с

2,88 с ± 66,3 мс на цикл (среднее ± стандартное отклонение из 7 циклов, по 1 циклу каждый) 

%%time
def short_path_length(row):
    return nx.shortest_path_length(G, row['Orgin_nodes'], row['Destination_nodes'], weight='length')
sampl_df['short_path_length_2'] = sampl_df.apply(short_path_length, axis=1)

Время стены: 1,24 с

1,2 с ± 15,7 мс на цикл (среднее ± стандартное отклонение из 7 циклов, по 1 циклу каждый) 

%%time
def short_path_length (node1,node2):
     return nx.shortest_path_length(G, node1, node2,weight='length')

sampl_df['short_path_length_intr3']=np.vectorize(short_path_length)(sampl_df['Orgin_nodes'],sampl_df['Destination_nodes'])

Время стены: 1,2 с

1,21 с ± 12 мс на цикл (среднее ± стандартное отклонение из 7 циклов, по 1 циклу каждый)

Таким образом, можно отметить, что третий является лучшим или это , а не шкала для определения, какой из них работает быстрее .

1 Ответ

1 голос
/ 17 марта 2019

Это по сути не векторизованная проблема, поскольку вы передаете метки узлов и вычисляете кратчайшие пути между ними алгоритмически с графическим объектом.Вы можете получить небольшое ускорение, упростив свой код: 

def short_path_length(row):
    return nx.shortest_path_length(G, row['Orgin_nodes'], row['Destination_nodes'], weight='length')
df['short_path_length'] = df.apply(short_path_length, axis=1)

Для большего ускорения экспортируйте свой график OSMnx в igraph для быстрого вычисления кратчайших путей в C, как показано в блокноте 18 в Примеры OSMnx .

...