नेटवर्कएक्स ग्राफ में कुछ पथ कैसे प्रतिबंधित करें?

Question

मैं डिजस्ट्रा और ए स्टार एल्गोरिदम (निर्देशित नेटवर्कएक्स ग्राफ में) का उपयोग करके 2 बिंदुओं के बीच सबसे कम पथ की गणना करने की कोशिश कर रहा हूं।

फिलहाल यह ठीक काम करता है और मैं गणना पथ देख सकते हैं, लेकिन मैं कुछ रास्तों सीमित का एक तरीका खोजने के लिए चाहते हैं।

उदाहरण के लिए अगर हम निम्नलिखित है नोड्स:

नोड्स = [1,2,3,4]

इन किनारों के साथ

:

किनारों = ((1,2), (2 > 2 - -> 3 लेकिन अभी भी अनुमति देते हैं 2 -> 3 & 1 -> 2, 3), (3,4))

वहाँ 1 अवरुद्ध/सीमित करने का एक तरीका है।

यह है कि मतलब होगा:

• कर सकते हैं यात्रा से 1 करने के लिए 2

• कर सकते हैं यात्रा से 2 3

• नहीं कर सकते यात्रा 1 से 3 को .. प्रत्यक्ष या अप्रत्यक्ष रूप से (यानी प्रतिबंधित 1-> 2-> 3 पथ)।

क्या यह नेटवर्कएक्स में हासिल किया जा सकता है .. यदि पाइथन में कोई और ग्राफ लाइब्रेरी नहीं है तो यह अनुमति देगी?

धन्यवाद।

Answer 1

दिलचस्प सवाल, मैंने इस समस्या के बारे में कभी नहीं सुना, शायद इसलिए कि मेरे पास इस विषय में ज्यादा पृष्ठभूमि नहीं है, न ही नेटवर्कएक्स के साथ बहुत अधिक अनुभव है। हालांकि, मेरे पास एल्गोरिदम के लिए एक विचार है। यह करने के लिए यह सबसे बेवकूफ तरीका हो सकता है और मुझे एक चतुर एल्गोरिदम के बारे में सुनकर खुशी होगी।

विचार यह है कि आप ग्राफ को नए ग्राफ में बदलने के लिए अपने प्रतिबंध नियमों का उपयोग कर सकते हैं जहां सभी किनारों को निम्नलिखित एल्गोरिदम का उपयोग करके मान्य किया जाता है। (1,2) तो हटाने (2,3)

• तुम पर आता है तो आप छोड़ देते हैं:

  पथ (1,2,3) के प्रतिबंध दो नियमों में विभाजित किया जा सकता ओवर (2,3) फिर हटाएं (1,2)

ग्राफ में इसे रखने के लिए आप प्रत्येक मामले के लिए नोड 2 की प्रतियां डाल सकते हैं। संबंधित मामले में वैध किनारे के बाद मैं नए नोड 1_2 और 2_3 पर कॉल करूंगा। दोनों नोड्स के लिए, आप सभी आने वाले और आउटगोइंग किनारों को प्रतिबंधित किनारे से कम करते हैं।

उदाहरण के लिए:

Nodes = [1,2,3,4] 
Edges = [(1,2),(2,3),(4,2)] 

मान्य पथ केवल 4> 2-> 3 नहीं 1-> 2-> 3 होगा। तो हम ग्राफ का विस्तार करते हैं:

Nodes = [1,1_2,2_3,3,4] # insert the two states of 2 
Edges = [ # first case: no (1_2,3) because of the restriction 
      (1,1_2), (4, 1_2) 
      # 2nd case, no (1,2_3) 
      (2_3,3), (4,2_3)] 

इस ग्राफ में एकमात्र वैध पथ 4-> 2_3-> 3 है। यह मूल ग्राफ में 4-> 2-> 3 के लिए मानचित्र करता है।

मुझे आशा है कि यदि आप कोई मौजूदा समाधान नहीं पाते हैं तो यह उत्तर कम से कम आपकी सहायता कर सकता है। लंबे प्रतिबंध नियम ग्राउंड को राज्य नोड्स की तेजी से बढ़ती संख्या के साथ उड़ा देंगे, इसलिए या तो यह एल्गोरिदम बहुत आसान है, या समस्या कठिन है ;-)

Answer 2

आप अपना नोड डेटा {color = ['blue' सेट कर सकते हैं ]} नोड 1 के लिए, नोड 2 में {color = ['red', 'blue']} है और नोड 3 में {color = ['red']} है। फिर networkx.algorithms का उपयोग करें। astar_path() दृष्टिकोण

• अनुमानी की स्थापना एक समारोह है जो एक might_as_well_be_infinity लौटाता है जब यह एक ही रंग आप के लिए
• वजन खोज रहे हैं = less_than_infinity के बिना एक नोड का सामना करना पड़ा को तैयार है।