NetworkXは、私はそのようなことをネットワークXに有向グラフGがあると有向グラフ

Question

内の特定のノードのためてroot_nodeを見つける：GはGの各ノードNが正確に1を有し、それ

で複数のツリーを有する

1. をまたは0 親のもの。

特定のノードN1については、そのノードが存在するツリーの祖先（度0の祖先）を探したいと思います。ネットワークxでこれを行う簡単な方法はありますか？

私は見ました： Getting the root (head) of a DiGraph in networkx (Python) しかし、グラフには複数のルートノードがあります。 N1と同じツリーに存在するルートノードは1つだけです。

Answer 1

編集11月2017これはnetworkx 2.0がリリースされる前に書かれていたことに注意してください。 2.0コードに1.xのコードを更新するためのmigration guideは

---

は、ここで簡単な再帰アルゴリズムです（特に両方のために、それは互換性のある作り）があります。多くても1つの親が存在することを前提としています。何かに親がない場合は、それがルートです。それ以外の場合は、親のルートを返します。

def find_root(G,node): 
    if G.predecessors(node): #True if there is a predecessor, False otherwise 
     root = find_root(G,G.predecessors(node)[0]) 
    else: 
     root = node 
    return root 

グラフは非循環有向グラフであれば、それはrootのみ、または指定されたノードのだけでもルート祖先ではないかもしれませんけれども、これはまだ、ルートを見つけるでしょう。

Answer 2

私は@ Joelのスクリプトを更新する自由を取った。彼の元の投稿は私にとってはうまくいかなかった。ここで

def find_root(G,child): 
    parent = list(G.predecessors(child)) 
    if len(parent) == 0: 
     print(f"found root: {child}") 
     return child 
    else: 
     return find_root(G, parent[0]) 

がテストだ：

G = nx.DiGraph(data = [('glu', 'skin'), ('glu', 'bmi'), ('glu', 'bp'), ('glu', 'age'), ('npreg', 'glu')]) 
test = find_root(G, "age") 
age 
glu 
npreg 
found root: npreg