ネットワーク（Python）でディグラフのルート（ヘッド）を取得する

Question

私は使用しようとしています networkx プロジェクトでグラフ表現を行うために、シンプルなものをいくつか行う方法がわかりません。このグラフには、ルート要素が1つしかないように、ノードとエッジの束を備えた指示グラフを作成しました。さて、私がしたいのは、ルートから始めてから、各要素の子供たちを繰り返して、そこからいくつかの情報を抽出することです。このジグラフのルート要素を取得するにはどうすればよいですか？

だからそれは次のようなものになるでしょう：

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

ドキュメントには、ディグラフの根を取得する簡単な方法を示唆するものは何も見ませんでした - これを手動で推測することになっていますか？ ：O私は取得しようとしました iter(myDiGraph) ルートから開始することを繰り返すことを願っていますが、順序はランダムであるように見えます...：

助けてくれてありがとう！

Answer 1

「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]

または、トポロジー種を使用することもできます（rootは最初の項目です）：

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

あるいは、特定の（ランダム）ノードから始めて、前身のないノードが見つかるまで前任者を追跡する方が速い場合があります。