如何使用NetworkX的DiGraph从特定节点开始查找单个输入叶节点？

Question

以下是所需翻译内容：

看下面的图表：

G = nx.DiGraph()

G.add_edge(1,2)
G.add_edge(3,2)
G.add_edge(1,4)
G.add_edge(2,5)

将其可视化为:

我想找到只有来自于从1开始的“子图”内部的入边的叶节点。

在我的示例中，它必须找到4但不能是5。5是2的子级，2的第二个输入为3。

我认为应该使用后继者和入度来查找正确的算法，但我对NetworkX非常新手，因此很难找到正确的算法。

另一个例子:

G = nx.DiGraph()

G.add_edge(1,2)
G.add_edge(3,2)
G.add_edge(1,4)
G.add_edge(2,5)
G.add_edge(4,6)
G.add_edge(1,7)
G.add_edge(7,6)

G.add_edge(1,8)
G.add_edge(8,7)
G.add_edge(8,6)
G.add_edge(4,9)
G.add_edge(4,10)
G.add_edge(5,10)

这里应该会找到 9 和 6，但不会找到 10（因为 3 是 2 的父节点，而 2 又是 5 的父节点）。

- Patrick B.

---

如果您能创建一个样本DiGraph，那么我可以提供帮助，这样我们就可以创建可重现的代码。 - Scott Boston

@ScottBoston，我更新了我的问题。 - Patrick B.

现在这是一个有趣的问题。已点赞并标记为我的最爱。我认为我们需要遍历后代节点，以查看它是否分支到另一个头节点。 - Scott Boston

Answer 1

下面的代码比其他答案更紧凑，速度更快。

roots = [v for v, d in G.in_degree() if d == 0]
leaves = [v for v, d in G.out_degree() if d == 0]

- jalil jabari

---

欢迎来到 Stack Overflow。当回答一个已有被接受答案的旧问题（查找绿色 ✓）时，请确保您的答案添加了新的内容或者是有帮助的。此外，虽然这段代码片段可能解决了问题，但它并没有解释为什么或者如何回答这个问题。请包含您代码的解释，因为这有助于提高您的帖子质量。请参阅导览以了解 Stack Overflow，并参考贡献指南。 - Ivo Mori

Answer 2

让我们尝试这段逻辑：

def find_leafnodes(G):
    leafnode = []

    for i in G.nodes:
        head =  []
        if nx.descendants(G, i) == set(): #find all leaf nodes
            for a in nx.ancestors(G, i):  #get all ancestors for leaf node
                if nx.ancestors(G, a) == set():  #Determine if ancestor is a head node
                    head.append(a)
        if len(head) == 1: #if this leaf had only one head then append to leafnode
            leafnode.append(i)
    return leafnode   

输入：

G = nx.DiGraph()

G.add_edge(1,2)
G.add_edge(3,2)
G.add_edge(1,4)
G.add_edge(2,5)

find_leafnodes(G)
# [4]

G = nx.DiGraph()

G.add_edge(1,2)
G.add_edge(3,2)
G.add_edge(1,4)
G.add_edge(2,5)
G.add_edge(4,6)
G.add_edge(1,7)
G.add_edge(7,6)

G.add_edge(1,8)
G.add_edge(8,7)
G.add_edge(8,6)
G.add_edge(4,9)
G.add_edge(4,10)
G.add_edge(5,10)

find_leafnodes(G)
# [6, 9]

- Scott Boston

---

谢谢你迄今为止的帮助，它有效。然而 find_leavenodes() 缺少“起始节点”参数。想象一下添加边 [3, 11]。如果我正在寻找 1 的基因纯正后代，我不想找到 11。 - Patrick B.

我在 if len(head) == 1 条件中添加了 root == head[0]，现在它可以正常工作了。 - Patrick B.