नेटवर्कक्स (पायथन)

Question

में एक डिग्राफ की रूट (हेड) प्राप्त करना मैं प्रोजेक्ट में कुछ ग्राफ प्रतिनिधित्व करने के लिए networkx का उपयोग करने का प्रयास कर रहा हूं, और मुझे यकीन नहीं है कि कुछ चीजें कैसे सरल होनी चाहिए। मैंने नोड्स और किनारों के समूह के साथ एक निर्देशित ग्राफ बनाया, जैसे कि इस ग्राफ में केवल एक मूल तत्व है। अब, मैं जो करना चाहता हूं वह रूट पर शुरू होता है, और उसके बाद प्रत्येक तत्व के बच्चों के माध्यम से पुनरावृत्ति करता है और उनसे कुछ जानकारी निकालता है। मैं इस डिग्राफ का मूल तत्व कैसे प्राप्त करूं?

तो यह कुछ इस तरह होगा:

#This is NOT real code, just pseudopython to convey the general intent of what I'd like to do 

    root = myDiGraph.root() 
    for child in root.children(): 
     iterateThroughChildren(child) 

def iterateThroughChildren(parent): 
    if parent.hasNoChildren(): return 
    for child in parent.children(): 
     //do something 
     // 
     iterateThroughChildren(child) 

मैं प्रलेखन कि एक संयुक्ताक्षर की जड़ को पुनः प्राप्त करने का एक आसान तरीका सुझाव में कुछ नहीं देखा - मैं इस मैन्युअल रूप से यह निष्कर्ष निकाल करना चाहिए? : ओ मैंने उम्मीद के साथ iter(myDiGraph) प्राप्त करने की कोशिश की है कि यह रूट पर शुरू हो जाएगा, लेकिन ऑर्डर यादृच्छिक प्रतीत होता है ...: \

सहायता की सराहना की जाएगी, धन्यवाद!

Answer 1

यदि "एक मूल तत्व" होने से आपका मतलब है कि आपका निर्देशित ग्राफ rooted tree है, तो रूट शून्य डिग्री के साथ एकमात्र नोड होगा।

आप के साथ रैखिक समय में उस नोड (नोड की संख्या में) पा सकते हैं:

In [1]: import networkx as nx 

In [2]: G=nx.balanced_tree(2,3,create_using=nx.DiGraph()) # tree rooted at 0 

In [3]: [n for n,d in G.in_degree().items() if d==0] 
Out[3]: [0] 

या आप एक सांस्थितिकीय प्रकार (रूट पहले आइटम है) इस्तेमाल कर सकते हैं:

In [4]: nx.topological_sort(G) 
Out[4]: [0, 1, 3, 8, 7, 4, 9, 10, 2, 5, 11, 12, 6, 13, 14] 

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