NetworkX 为有向图中的特定节点找到 root_node

Question

假设我在网络 X 中有一个有向图 G 使得：

G 中有多棵树
G中的每个节点N恰好有1或0 parent的。

对于特定节点 N1，我想找到它所在的树的根节点（它的度为 0 的祖先）。有没有在网络 x 中执行此操作的简单方法？

我看了： Getting the root (head) of a DiGraph in networkx (Python) 但是我的图中有多个根节点。只有一个根节点恰好与 N1 在同一棵树中。

Answer 1

编辑 2017 年 11 月 请注意，这是在 networkx 2.0 发布之前编写的。有一个 migration guide 用于将 1.x 代码更新为 2.0 代码（特别是使其与两者兼容）

这是一个简单的递归算法。它假设最多只有一个 parent。如果某物没有 parent，它就是根。否则，它 returns 其 parent 的根。

def find_root(G,node):
    if G.predecessors(node):  #True if there is a predecessor, False otherwise
        root = find_root(G,G.predecessors(node)[0])
    else:
        root = node
    return root

如果图是有向无环图，这仍然会找到一个根，尽管它可能不是唯一的根，甚至可能不是给定节点的唯一根祖先。

Answer 2

我冒昧地更新了@Joel 的脚本。他原来的post不适合我。

def find_root(G,child):
    parent = list(G.predecessors(child))
    if len(parent) == 0:
        print(f"found root: {child}")
        return child
    else:  
        return find_root(G, parent[0])

这是一个测试：

G = nx.DiGraph(data = [('glu', 'skin'), ('glu', 'bmi'), ('glu', 'bp'), ('glu', 'age'), ('npreg', 'glu')])
test = find_root(G, "age")
age
glu
npreg
found root: npreg

NetworkX 为有向图中的特定节点找到 root_node

NetworkX find root_node for a particular node in a directed graph

python

graph-theory

networkx