Networkx - Как получить кратчайшую длину пути между узлами, отображающими идентификатор узла вместо метки

Question

Я новичок в использовании библиотеки NetworkX с Python.

Допустим, что я импортировать Pajek отформатированный файл:

import networkx as nx 
G=nx.read_pajek("pajek_network_file.net") 
G=nx.Graph(G) 

Содержимое моего файла являются (В Pajek, узлы называются "Вершины"):

*Network 
*Vertices 6 
123 Author1 
456 Author2 
789 Author3 
111 Author4 
222 Author5 
333 Author6 
*Edges 
123 333 
333 789 
789 222 
222 111 
111 456 

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

path = nx.all_pairs_shortest_path_length(G) 

Возвраты: длины - Словарь кратчайших путей длины, заданных по источнику и цели.

Возвращение я получаю:

print path 
{u'Author4': {u'Author4': 0, u'Author5': 1, u'Author6': 3, u'Author1': 4, u'Author2': 1, u'Author3': 2}, u'Author5': {u'Author4': 1, u'Author5': 0, u'Author6': 2, u'Author1': 3, u'Author2': 2, u'Author3': 1}, u'Author6': {u'Author4': 3, u'Author5': 2, u'Author6': 0, u'Author1': 1, u'Author2': 4, u'Author3': 1}, u'Author1': {u'Author4': 4, u'Author5': 3, u'Author6': 1, u'Author1': 0, u'Author2': 5, u'Author3': 2}, u'Author2': {u'Author4': 1, u'Author5': 2, u'Author6': 4, u'Author1': 5, u'Author2': 0, u'Author3': 3}, u'Author3': {u'Author4': 2, u'Author5': 1, u'Author6': 1, u'Author1': 2, u'Author2': 3, u'Author3': 0}} 

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

В идеале, что бы я хотел возврат с форматом похож на ниже:

source_node_id, target_node_id, path_length 
123, 456, 5 
123, 789, 2 
123, 111, 4 

Короче говоря, мне нужно, чтобы получить отдачу, используя только (или, по крайней мере, в том числе) в узлах идентификаторами, а не только с указанием узлов метки. И, чтобы получить каждую возможную пару в одной строке с их соответствующим самым коротким путем ...

Возможно ли это в NetworkX?

Справочник по функциям: https://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.shortest_paths.unweighted.all_pairs_shortest_path_length.html

Answer 1

Как о чем-то вроде этого?

import networkx as nx                
G=nx.read_pajek("pajek_network_file.net")           
G=nx.Graph(G) 
# first get all the lengths  
path_lengths = nx.all_pairs_shortest_path_length(G)        

# now iterate over all pairs of nodes  
for src in G.nodes(): 
    # look up the id as desired       
    id_src = G.node[src].get('id') 
    for dest in G.nodes():              
     if src != dest: # ignore self-self paths 
      id_dest = G.node[dest].get('id')          
      l = path_lengths.get(src).get(dest)         
      print "{}, {}, {}".format(id_src, id_dest, l) 

Это дает выходной сигнал

111, 222, 1 
111, 333, 3 
111, 123, 4 
111, 456, 1 
111, 789, 2 
... 

Если вам нужно сделать дальнейшей обработки (например, сортировка), а затем хранить l ценности, а не только их печати.

(вы можете перебрать пар более чисто с чем-то вроде itertools.combinations(G.nodes(), 2) но выше метод является немного более явным в случае, если вы не знакомы с ним.)

Answer 2

В конце концов, я только необходимые для расчета кратчайший путь для подмножества всей сети (моя реальная сеть огромна, с 600K узлами и 6M ребрами), поэтому я написал скрипт, который считывает исходный узел и пары целевых узлов из файла CSV, сохраняет в массив numpy, затем передает их как параметры в nx.shortest_path_length и вычисляет для каждой пары и, наконец, сохраняет результаты в файл CSV.

код ниже, я отправляю это только в случае, если это может быть полезным для кого-то там:

print "Importing libraries..." 

import networkx as nx 
import csv 
import numpy as np 

#Import network in Pajek format .net 
myG=nx.read_pajek("MyNetwork_0711_onlylabel.net") 

print "Finished importing Network Pajek file" 

#Simplify graph into networkx format 
G=nx.Graph(myG) 

print "Finished converting to Networkx format" 

#Network info 
print "Nodes found: ",G.number_of_nodes() 
print "Edges found: ",G.number_of_edges() 


#Reading file and storing to array 
with open('paired_nodes.csv','rb') as csvfile: 
    reader = csv.reader(csvfile, delimiter = ',', quoting=csv.QUOTE_MINIMAL)#, quotechar = '"') 
    data = [data for data in reader] 
paired_nodes = np.asarray(data) 
paired_nodes.astype(int) 

print "Finished reading paired nodes file" 

#Add extra column in array to store shortest path value 
paired_nodes = np.append(paired_nodes,np.zeros([len(paired_nodes),1],dtype=np.int),1) 

print "Just appended new column to paired nodes array" 

#Get shortest path for every pair of nodes 

for index in range(len(paired_nodes)): 
    try: 
    shortest=nx.shortest_path_length(G,paired_nodes[index,0],paired_nodes[index,1]) 
     #print shortest 
     paired_nodes[index,2] = shortest 
    except nx.NetworkXNoPath: 
     #print '99999' #Value to print when no path is found 
     paired_nodes[index,2] = 99999 

print "Finished calculating shortest path for paired nodes" 

#Store results to csv file  
f = open('shortest_path_results.csv','w') 

for item in paired_nodes: 
    f.write(','.join(map(str,item))) 
    f.write('\n') 
f.close() 

print "Done writing file with results, bye!"