NetworkX найти root_node для конкретного узла в ориентированном графе

Question

Пусть я ориентированный граф G в сети X таким образом, что:

1. G имеет несколько деревьев в нем
2. Каждый узел N в G имеет ровно 1 или 0 родителей.

Для конкретного узла N1 я хочу найти корневой узел дерева, в котором он находится (его предок, который имеет степень 0). Есть ли простой способ сделать это в сети x?

Я смотрел: Getting the root (head) of a DiGraph in networkx (Python) Но на моем графике есть несколько корневых узлов. Только один корневой узел, находящийся в том же дереве, что и N1.

Answer 1

Редактировать ноябрь 2017 Обратите внимание, что это было написано до того, как был выпущен networkx 2.0. Существует migration guide для обновления кода 1.x в 2.0 кода (и, в частности, что делает его совместимым для обоих)

---

Вот простой рекурсивный алгоритм. Предполагается, что существует не более одного родителя. Если у кого-то нет родителя, это корень. В противном случае он возвращает корень своего родителя.

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

Я позволил обновить сценарий Джоэла. Его оригинальный пост не работал для меня.

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