Ağda (Python)

Question

bir DiGraph kök (kafa) alma Bir projede grafik temsili yapmak için networkx kullanmaya çalışıyorum ve basit olması gereken birkaç şeyi nasıl yapacağınızdan emin değilim. Bu grafikte sadece bir kök eleman olacak şekilde bir dizi düğüm ve kenar ile yönlendirilmiş bir grafik oluşturdum. Şimdi, yapmak istediğim şey kökten başlayıp, her bir öğenin çocukları boyunca yinelemek ve onlardan bazı bilgileri çıkarmak. Bu DiGraph'ın kök öğesini nasıl alabilirim?

Yani böyle bir şey olurdu: Bir digraf kök almak için kolay bir yol önerdi belgelerinde şey görmedik

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

- Ben elle sonucuna gerekiyor? : iter(myDiGraph)'u kökü kullanarak yinelemeyi umuduyla denedim, ancak sipariş rastgele görünüyor ...: \

Yardımı takdir edeceksiniz, teşekkürler!

Answer 1

"Tek bir kök öğesi" alarak, yönettiğiniz grafiğin bir rooted tree olduğu anlamına gelirse, o zaman kök sıfır derece olan tek düğüm olacaktır.

Sen ile (düğüm sayısı olarak) doğrusal zamanda bu düğümü bulabilirsiniz

:

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] 

Yoksa topolojik sıralama (kök ilk öğedir) de kullanabilir: Alternatif

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

Belirli bir (rastgele) düğümle başlamak daha hızlı olabilir ve öncülleri olmayan bir düğüm bulana kadar öncülleri izleyin.