在NetworkX中寻找有向图中后继关系的后继关系

Question

我正在为NetworkX中的有向图编写一些代码，并且遇到了一个可能是我编程经验有问题的结果的块。我要做的是：

我有一个有向图G，顶部有两个“父节点”，所有其他节点都从中流动。在绘制此网络时，我想将“Parent 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

因此，对于那些偶然发现这个问题的未来人来说，答案更清晰、更容易找到，下面是我最终使用的代码：

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 3

好吧，继承人的继承人就是继承人的继承人对吧？

# 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的子体，请调用AllDescents（d2）等

编辑： 问题1： allDescend = descend + descend2将这两个集合组合在一起，对后代的进一步级别执行相同的操作。

问题2：如果图中有循环，则需要首先修改代码以测试以前是否访问过该子体，例如：

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

这样，就可以将allDescend作为第二个参数传递给上面的函数，这样它就不会包含在将来的后代中。一直这样做，直到allDescandants()返回一个空数组，在这种情况下，您知道您已经浏览了整个图，然后停止。

既然这看起来像是家庭作业，我就让你自己想办法把这些拼凑起来。；）