34

プロジェクトでグラフ表現を行うために を使用しようとしnetworkxていますが、単純にする必要があるいくつかのことを行う方法がわかりません。このグラフにはルート要素が 1 つしかないように、多数のノードとエッジを持つ有向グラフを作成しました。ここで、私がやりたいことは、ルートから始めて、各要素の子を繰り返し処理し、それらからいくつかの情報を抽出することです。この 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 のルートを取得する簡単な方法を示唆するものは何もありませんでした。これを手動で推測する必要がありますか? :Oiter(myDiGraph)ルートから反復することを期待して取得しようとしましたが、順序はランダムなようです... :\

助けていただければ幸いです、ありがとう！

4

1 に答える 1

61

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

または、特定の (ランダムな) ノードから開始し、先行ノードがないノードが見つかるまで先行ノードをたどる方が高速な場合があります。

于 2010-11-08T10:54:30.703 に答える