मैं Python के साथ NetworkX लाइब्रेरी का उपयोग करने के लिए नया हूं।

मान लीजिए कि मैं पजेक-स्वरूपित फ़ाइल आयात करता हूं:

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

मेरी फ़ाइल की सामग्री हैं (पाजेक में, नोड्स को "वर्टिस" कहा जाता है):

*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

2
elvitaluz 20 नवम्बर 2015, 22:13

2 जवाब

सबसे बढ़िया उत्तर

इस जैसे किसी और के बारे में क्या राय है?

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) लेकिन उपरोक्त विधि थोड़ी अधिक स्पष्ट है यदि आप इससे परिचित नहीं हैं।)

0
Bonlenfum 24 नवम्बर 2015, 15:44

अंत में, मुझे केवल पूरे नेटवर्क के सबसेट के लिए सबसे छोटे पथ की गणना करने की आवश्यकता थी (मेरा वास्तविक नेटवर्क बहुत बड़ा है, 600K नोड्स और 6M किनारों के साथ), इसलिए मैंने एक स्क्रिप्ट लिखी जो एक CSV से स्रोत नोड और लक्ष्य नोड जोड़े को पढ़ता है। फ़ाइल, एक अफीम सरणी में संग्रहीत करता है, फिर उन्हें nx.shortest_path_length के मापदंडों के रूप में पास करता है और प्रत्येक जोड़ी के लिए गणना करता है, और अंत में सीएसवी फ़ाइल के परिणामों को बचाता है।

नीचे कोड है, मैं इसे पोस्ट कर रहा हूं बस अगर यह किसी के लिए उपयोगी हो सकता है:

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!"
1
elvitaluz 5 पद 2015, 05:40