الحصول على الجذر (رأس) من Digraph في NetworkX (Python)

Question

أحاول استخدام networkx للقيام ببعض تمثيل الرسم البياني في مشروع ، ولست متأكدًا من كيفية القيام ببعض الأشياء التي يجب أن تكون بسيطة. لقد قمت بإنشاء رسم بياني موجه مع مجموعة من العقد والحواف ، بحيث لا يوجد سوى عنصر جذر واحد في هذا الرسم البياني. الآن ، ما أود القيام به هو البدء في الجذر ، ثم التكرار من خلال أطفال كل عنصر واستخراج بعض المعلومات منهم. كيف أحصل على عنصر الجذر لهذا digraph؟

لذلك سيكون شيء من هذا القبيل:

#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)

لم أر أي شيء في الوثائق التي اقترحت طريقة سهلة لاسترداد جذر Digraph - هل من المفترض أن أستنتج هذا يدويًا؟ : يا حاولت الحصول على iter(myDiGraph) على أمل أن يتكرر بدء الجذر ، ولكن يبدو أن الترتيب عشوائي ...:

سيتم تقدير المساعدة ، شكرًا!

Answer 1

إذا كان من خلال وجود "عنصر جذر واحد" يعني أن الرسم البياني الموجه هو شجرة الجذور, ، ثم سيكون الجذر العقدة الوحيدة مع صفر في الدرجة.

يمكنك العثور على تلك العقدة في الوقت الخطي (في عدد العقد) مع:

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() 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]

بدلاً من ذلك ، قد يكون من الأسرع أن نبدأ بعقدة (عشوائية) معينة وتتبع الأسلاك حتى تجد عقدة بدون أسلاف.