NetworkX查找某特定节点root_node在一个有向图

假设我有一个向图G中网络X，这样的：NetworkX查找某特定节点root_node在一个有向图

G具有在它
多个树G中的每个节点N具有恰好1或父母的0 。

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

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

来源

2016-04-07 mt88

你有没有想过只盯着它的父，那么它的父亲的父亲等，直到它停止？ - 即先进行深度优先搜索（或宽度优先搜索或任何其他类型的搜索）后面的边沿，直到它停止为止？最后一个节点必须是它。 – Joel

编辑2017年11月请注意，这是在networkx 2.0发布之前编写的。有更新的1.x代码到2.0的代码migration guide（尤其是使它成为兼容）

这里有一个简单的递归算法。它假定最多只有一位父母。如果某件事没有父母，那就是根。否则，它将返回其父项的根目录。

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

如果图表是向无环图，这仍然会发现一个根，虽然它可能不是唯一的根，甚至给定节点的唯一根祖先。

来源

2016-04-08 00:45:08 Joel

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

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

来源

2017-11-08 22:48:33 Jon

我是否正确使用了networkx 2.0？ – Joel

是的，你是对的 – Jon

NetworkX查找某特定节点root_node在一个有向图

回答

相关问题