दो नोड्स

Question

के बीच सभी पथों के लिए बहुत तेज़ एल्गोरिदम मैं पाइथन कोडिंग के लिए बहुत नया हूं और मैं एक एल्गोरिदम की तलाश में हूं जो एक बहुत बड़े ग्राफ के लिए प्रारंभ नोड और एंड नोड के बीच के सभी पथों को जल्दी से ढूंढ देगा - एक ग्राफ कहें जिसमें लगभग 1000 नोड्स और 10,000 किनारे हैं। प्रारंभिक नोड से अंत नोड तक वास्तव में मौजूद पथों की संख्या छोटी है - दस या उससे कम। प्रश्न को थोड़ा और संदर्भित करने में मदद के लिए, सोशल नेटवर्क पर विचार करें - अगर मेरे पास 1000 दोस्त थे और मैं जानना चाहता था कि कॉलेज से मेरे रूममेट से हाईस्कूल से मेरा सबसे अच्छा दोस्त कितने तरीके से जुड़ता है, तो मुझे इस तथ्य की परवाह नहीं है कि मेरा हाईस्कूल का सबसे अच्छा दोस्त मेरे 200 हाईस्कूल दोस्तों से जुड़ा हुआ है क्योंकि वे पथ कभी मेरे रूममेट तक नहीं जाते हैं। मैं इस पायथन कोड के साथ क्या करना चाहता हूं, जो मेरे दो दोस्तों के बीच मौजूद पथों को जल्दी से सब्सक्राइब करता है और अनिवार्य रूप से इन दो नोड्स के आसपास मौजूद सभी "शोर" से छुटकारा पाता है।

मैंने कोड के कई उदाहरणों को लागू करने का प्रयास किया है, जिनमें से सभी छोटे, सरल ग्राफ पर अच्छी तरह से काम करते हैं। हालांकि, जब मैं उन्हें अपने बड़े ग्राफ विश्लेषण में शामिल करने का प्रयास करता हूं, तो वे सभी उपयोगी होने में बहुत अधिक समय लेते हैं।

क्या आपके पास सभी जांच करने के तरीकों के बारे में कोई सुझाव हैं (यानी, नेटवर्कक्स में पहले से ही बनाया गया है या यहां तक ​​कि एक स्टैक बनाम रिकर्सन आदि का उपयोग करने की जानकारी ...), लागू करने के लिए कोड उदाहरण, या यहां तक ​​कि अन्य मार्ग भी पीछा करने के लिए अजगर? ध्यान रखें, मैं एक अजगर नौसिखिया हूँ।

Answer 1

व्यक्तिगत रूप से मैं इसके लिए ग्राफ डेटाबेस का उपयोग करने की अनुशंसा करता हूं। Neo4j या रेक्सटर वसंत दिमाग में।

जब अजगर से इन तक पहुंचने में कोई कुछ पुस्तकालयों में उपलब्ध हैं:

• http://bulbflow.com/overview/
• http://py2neo.org/

हालांकि यह असंभव इनमें से एक तेजी से/स्केलेबल अजगर संस्करण लिखने के लिए नहीं होगा, जहां तक ​​मुझे पता है, अभी तक कोई भी नहीं है।

Answer 2

शायद आप दो नोड्स के बीच सभी सरल (कोई दोहराया नोड्स) पथ चाहते हैं? नेटवर्कएक्स के लिए एक फ़ंक्शन है जो गहराई-पहली खोज पर आधारित है। http://networkx.github.com/documentation/development/reference/generated/networkx.algorithms.simple_paths.all_simple_paths.html

उदाहरण देखें वहाँ से पता चलता है कि सरल रास्तों की संख्या अधिक हो सकती हैं:

>>> import networkx as nx 
>>> G = nx.complete_graph(4) 
>>> for path in nx.all_simple_paths(G, source=0, target=3): 
...  print(path) 
... 
[0, 1, 2, 3] 
[0, 1, 3] 
[0, 2, 1, 3] 
[0, 2, 3] 
[0, 3]