NetworkXの指示グラフの後継の検索

Question

NetworkXの有向グラフのコードで作業していて、疑わしいプログラミング経験の結果である可能性が高いブロックにヒットしました。私がしようとしていることは、次のとおりです。

私は有向グラフGを持ち、他のすべてのノードが流れる2つの「親ノード」が先頭にあります。このネットワークをグラフ化するとき、「親1」の子孫であるすべてのノードを1色、他のすべてのノードを別の色でグラフ化したいと思います。つまり、親1の後継者のリストが必要です。今

、私が使用して簡単にそれらの最初の層を得ることができます。

descend= G.successors(parent1) 

問題は、これが唯一の私の後継者の第一世代を与えています。私は後継者の後継者、後継者の後継者の後継者などを望むことが望ましい。分析を実行してグラフの作成者が何人いるかを知らなくてもグラフを作成できることは非常に便利なので。

これにどのようにアプローチすればよいですか？

Answer 1

子孫のリストは必要ありません。色を付けるだけです。そのためには、グラフを横断してエッジをカラーリングするアルゴリズムを選択するだけです。 ：

たとえば、あなたが

from networkx.algorithms.traversal.depth_first_search import dfs_edges 

G = DiGraph(...) 
for edge in dfs_edges(G, parent1): 
    color(edge) 

を行うことができますが答えはそれつまずく将来の人々のために見つけるために、ややクリーンかつ容易になるように、ここで私が使用して終了コードだhttp://networkx.lanl.gov/reference/algorithms.traversal.html

Answer 2

さて、後継者の後継者は子孫の後継者ですか？

# First successors 
descend = G.successors(parent1) 
# 2nd level successors 
def allDescendants(d1): 
    d2 = [] 
    for d in d1: 
     d2 += G.successors(d) 
    return d2 

descend2 = allDescendants(descend) 

、レベル3の子孫を得る

編集allDescendants（D2）などを呼び出すために： 問題1： allDescend = descend + descend2は子孫のさらなるレベルのために同じことを行う、あなたに組み合わせた二組を提供します。

Issue2：あなたは、グラフ内のループを持っている場合は、あなたが例えば、最初にあなたが前にその子孫を訪問したかどうかをテストするためのコードを変更する必要があります

def allDescendants(d1, exclude): 
    d2 = [] 
    for d in d1: 
     d2 += filter(lambda s: s not in exclude, G.successors(d)) 
    return d2 

この方法で、あなたのようにallDescendを渡します上記の関数の2番目の引数になります。したがって、それは将来の子孫には含まれません。 allDescandants()が空の配列を返し、グラフ全体を探索したことを知り、停止するまでこれを続けます。

これは宿題のように見え始めているので、私はあなた自身ですべてを一緒にまとめる方法を考えさせます。 ;）

Answer 3

を参照してください。

G = DiGraph() # Creates an empty directed graph G 
infile = open(sys.argv[1]) 
for edge in infile: 
    edge1, edge2 = edge.split() #Splits data on the space 
    node1 = int(edge1) #Creates integer version of the node names 
    node2 = int(edge2) 
    G.add_edge(node1,node2) #Adds an edge between two nodes 

parent1=int(sys.argv[2]) 
parent2=int(sys.argv[3]) 

data_successors = dfs_successors(G,parent1) 
successor_list = data_successors.values() 
allsuccessors = [item for sublist in successor_list for item in sublist] 

pos = graphviz_layout(G,prog='dot') 
plt.figure(dpi=300) 
draw_networkx_nodes(G,pos,node_color="LightCoral") 
draw_networkx_nodes(G,pos,nodelist=allsuccessors, node_color="SkyBlue") 
draw_networkx_edges(G,pos,arrows=False) 
draw_networkx_labels(G,pos,font_size=6,font_family='sans-serif',labels=labels) 

Answer 4

私はNetworkxが数年前@Jochen Ritzelの答えから変わったと信じています。

ここでは、インポートステートメントの変更のみが以下のとおりです。私はあなたの代わりに呼び出す場合に気づい

import networkx as nx 
G = DiGraph(...) 
successors = nx.nodes(nx.dfs_tree(G, your_node)) 

：

import networkx 
from networkx import dfs_edges 

G = DiGraph(...) 
for edge in dfs_edges(G, parent1): 
    color(edge) 

Answer 5

あなたはすべての後続ノードを取得したい場合は、エッジを通過することなく、別の方法は、可能性が

successors = list(nx.dfs_successors(G, your_node) 

ボトムレベルのノードは何らかの形で含まれていません。