नेटवर्कक्स: कुशलतापूर्वक डिग्राफ

Question

में पूर्णतम पथ पाएं, मैं चाहता हूं कि नेटवर्क निर्देश मेरे निर्देशित, विश्वकोश ग्राफ में पूर्णतम पथ पाएं।

मुझे बेलमैन-फोर्ड के बारे में पता है, इसलिए मैंने अपनी ग्राफ लंबाई को अस्वीकार कर दिया। समस्या: नेटवर्कक्स के bellman_ford() को एक स्रोत नोड की आवश्यकता है। मैं पूर्ण सबसे लंबा पथ (या अस्वीकृति के बाद सबसे छोटा रास्ता) खोजना चाहता हूं, किसी दिए गए नोड से सबसे लंबा रास्ता नहीं।

बेशक, मैं ग्राफ में प्रत्येक नोड पर bellman_ford() चला सकता हूं और सॉर्ट कर सकता हूं, लेकिन क्या एक और अधिक कुशल विधि है?

से मैं क्या पढ़ा है (जैसे, http://en.wikipedia.org/wiki/Longest_path_problem) मुझे पता है वहाँ वास्तव में एक अधिक कुशल विधि नहीं हो सकता है, लेकिन अगर किसी को भी किसी भी विचार था (और/या पी ने साबित कर दिया सोच रहा था = एनपी (मुस्कराहट))।

संपादित करें: मेरे ग्राफ में सभी किनारों की लंबाई +1 (या अस्वीकरण के बाद -1) है, इसलिए एक विधि जो बस अधिकांश नोड्स पर जाती है, भी काम करेगी। सामान्य रूप से, पाठ्यक्रम के सभी नोड्स पर जाना संभव नहीं होगा।

संपादित करें: ठीक है, मुझे अभी एहसास हुआ है कि मैं एक अतिरिक्त नोड जोड़ सकता हूं जो ग्राफ में हर दूसरे नोड से कनेक्ट होता है, और उसके बाद उस नोड से bellman_ford चलाता है। कोई अन्य सुझाव?

Answer 1

एक रेखीय समय एल्गोरिथ्म http://en.wikipedia.org/wiki/Longest_path_problem

यहाँ पर उल्लेख नहीं है एक (बहुत हल्के से परीक्षण किया) कार्यान्वयन

संपादित है, यह स्पष्ट रूप से गलत है, नीचे देखें। भविष्य के लिए +1

import networkx as nx 

def longest_path(G): 
    dist = {} # stores [node, distance] pair 
    for node in nx.topological_sort(G): 
     pairs = [[dist[v][0]+1,v] for v in G.pred[node]] # incoming pairs 
     if pairs: 
      dist[node] = max(pairs) 
     else: 
      dist[node] = (0, node) 
    node, max_dist = max(dist.items()) 
    path = [node] 
    while node in dist: 
     node, length = dist[node] 
     path.append(node) 
    return list(reversed(path)) 

if __name__=='__main__': 
    G = nx.DiGraph() 
    G.add_path([1,2,3,4]) 
    print longest_path(G) 

संपादित पोस्ट करने से पहले हल्के से अधिक से अधिक परीक्षण: सही किया संस्करण (अपने जोखिम पर उपयोग करें और कृपया बग की रिपोर्ट)

def longest_path(G): 
    dist = {} # stores [node, distance] pair 
    for node in nx.topological_sort(G): 
     # pairs of dist,node for all incoming edges 
     pairs = [(dist[v][0]+1,v) for v in G.pred[node]] 
     if pairs: 
      dist[node] = max(pairs) 
     else: 
      dist[node] = (0, node) 
    node,(length,_) = max(dist.items(), key=lambda x:x[1]) 
    path = [] 
    while length > 0: 
     path.append(node) 
     length,node = dist[node] 
    return list(reversed(path)) 

if __name__=='__main__': 
    G = nx.DiGraph() 
    G.add_path([1,2,3,4]) 
    G.add_path([1,20,30,31,32,4]) 
# G.add_path([20,2,200,31]) 
    print longest_path(G) 

Answer 2

Aric की संशोधित जवाब एक अच्छा एक है और मुझे मिल गया नेटवर्कक्स लाइब्रेरी link

द्वारा अपनाया गया था, हालांकि, मुझे इस विधि में थोड़ा दोष मिला।

if pairs: 
    dist[node] = max(pairs) 
else: 
    dist[node] = (0, node) 

क्योंकि जोड़े (int, nodetype) के tuples की एक सूची है। ट्यूपल्स की तुलना करते समय, पायथन पहले तत्व की तुलना करता है और यदि वे समान हैं, तो दूसरे तत्व की तुलना करने की प्रक्रिया होगी, जो कि नोडटाइप है। हालांकि, मेरे मामले में nodetype एक कस्टम वर्ग है जो तुलनात्मक विधि परिभाषित नहीं है। अजगर इसलिए की तरह एक त्रुटि बाहर फेंक ': unorderable प्रकार: लेखन त्रुटि() xxx> xxx()'

एक संभव सुधार लाने के लिए, मैं कहता हूँ लाइन

dist[node] = max(pairs) 

dist[node] = max(pairs,key=lambda x:x[0]) 

द्वारा बदला जा सकता है

स्वरूपण के बारे में खेद है क्योंकि यह मेरी पहली बार पोस्टिंग है। काश मैं सिर्फ एक टिप्पणी के रूप में एरिक के जवाब से नीचे पोस्ट कर सकता हूं लेकिन वेबसाइट मुझे ऐसा करने के लिए मना करती है कि मेरे पास पर्याप्त प्रतिष्ठा नहीं है (ठीक है ...)