графический инструмент быстрого расчета кратчайшего пути - PullRequest
Новая
       35

графический инструмент быстрого расчета кратчайшего пути

0 голосов
/ 19 марта 2020

Я использую Graph-Tool и хотел бы рассчитать кратчайший путь (/ все кратчайшие пути) между списком исходных узлов и списком целевых узлов, которые являются подмножеством полной сети. Вот воспроизводимый пример кода: 

import graph_tool.all as gt

data = {'source': [0, 1, 2, 3, 4, 5, 6], 'target': [1, 5, 3, 4, 6, 2, 2]}
df_network = pd.DataFrame.from_dict(data)

# Initialise network
gt_net = Graph(directed=False)
gt_net.add_edge_list(df_network.values)

# List of nodes I want to calculate the shortest path
list_nodes = [0,2,1]

# Calculate all possible combinations between nodes
all_combinations = combinations(list_nodes , 2)

# Calculate all possible shortest paths
nlist = []   # Initialise list of nodes

for left, right in all_combinations:
    vlist, _ = gt.shortest_path(gt_net, gt_net.vertex(left), gt_net.vertex(right))  
    nlist.extend([str(v) if vlist != [] else [str(left), str(right)] for v in vlist])

    nlist = list(dict.fromkeys(nlist))   # remove duplicates

Код, который выполняет работу. Тем не менее, он использует python для l oop, и я понимаю, что это может быть не лучшим способом сделать это (то есть это замедляет работу). Действительно, вычисление кратчайшего пути занимает довольно много времени, когда сети очень большие.

Есть предложения о том, как ускорить расчет? Может быть, передав полный список исходных узлов и список целевых узлов в одном go?

Спасибо

...