एक निर्देशित पेड़ (igraph)

Question

में एक नोड से दूसरे में सभी संभावित पथ एक निर्देशित पेड़ का प्रतिनिधित्व करने के लिए python binding से igraph का उपयोग करते हैं। मैं उस ग्राफ में किसी नोड से सभी संभावित पथों को दूसरे में ढूंढना चाहता हूं। दुर्भाग्यवश, मुझे इस कार्य को करने वाले igraph में फ़ंक्शन का उपयोग करने के लिए तैयार नहीं मिला?

संपादित

रास्तों

की अनंत संख्या पर चिंताओं ग्राफ के बारे में मैं बात कर रहा हूँ वास्तव में एक निर्देशित अचक्रीय ग्राफ (DAG) एकल रूट के साथ है। यह घटनाओं के एक unidirectional कैस्केड का प्रतिनिधित्व करता है कि, कैस्केड के विभिन्न स्तरों पर, या तो विभाजित या एक साथ शामिल हो सकते हैं। जैसा कि मैंने कहा, यह एक unidirectional ग्राफ है। यह भी प्रदान किया जाता है कि ग्राफ में कोई चक्र नहीं है। इन दो कारणों से, पथों की अनंत सूची असंभव है।

मैं क्या करने की कोशिश कर रहा हूं?

मेरा लक्ष्य ग्राफ़ (रूट) के शीर्ष से दिए गए नोड तक के सभी संभावित पथों को ढूंढना है।

Answer 1

आप एक निर्देशित विश्वकोश ग्राफ (डीएजी) में एक नोड और दूसरे के बीच सभी पथों की तलाश में हैं।

एक पेड़ हमेशा एक डीएजी होता है, लेकिन एक डीएजी हमेशा एक पेड़ नहीं होता है। अंतर यह है कि एक पेड़ की शाखाओं में शामिल होने की अनुमति नहीं है, केवल विभाजित करें, जबकि एक डीएजी की शाखाएं एक साथ बहती हैं, जब तक कोई चक्र पेश नहीं किया जाता है।

आपका समाधान find_all_paths()"Python Patterns - Implementing Graphs." में पाया जा सकता है इसके लिए igraph के साथ उपयोग करने के लिए थोड़ा अनुकूलन की आवश्यकता है। मैं igraph स्थापित नहीं है, लेकिन mocks का उपयोग कर, यह काम करने के लिए लगता है:

def adjlist_find_paths(a, n, m, path=[]): 
    "Find paths from node index n to m using adjacency list a." 
    path = path + [n] 
    if n == m: 
    return [path] 
    paths = [] 
    for child in a[n]: 
    if child not in path: 
     child_paths = adjlist_find_paths(a, child, m, path) 
     for child_path in child_paths: 
     paths.append(child_path) 
    return paths 

def paths_from_to(graph, source, dest): 
    "Find paths in graph from vertex source to vertex dest." 
    a = graph.get_adjlist() 
    n = source.index 
    m = dest.index 
    return adjlist_find_paths(a, n, m) 

यह दस्तावेज़ से स्पष्ट नहीं है कि adjlist या शिखर सूचकांकों की सूचियों की एक सूची सूची की एक सूची शिखर खुद को वस्तुओं की है था । मैंने माना कि सूचियों में सूचीबद्ध सूची का उपयोग करके सरलीकृत करने के लिए सूचकांक शामिल हैं। नतीजतन, लौटा पथ वर्टेक्स सूचकांक के मामले में हैं। आपको इन्हें वर्टेक्स ऑब्जेक्ट्स पर मैप करना होगा यदि आपको इसके बजाय इसकी आवश्यकता है, या कोड को इसके इंडेक्स की बजाय वर्टेक्स को जोड़ने के लिए अनुकूलित करना होगा।