networkx несколько LCA в DAG

Question

Я пытаюсь использовать пакет networkx в python, чтобы найти наименьшего общего предка для 2 узлов в графе. Когда я использую для этого встроенный метод, он получает только один LCA, если их несколько. Есть идеи, как получить все LCA?

Пример:

G = nx.DiGraph()
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_node(4)
G.add_edge(1,3)
G.add_edge(1,2)
nx.all_pairs_lowest_common_ancestor(G, 2,3) # returns 1
G.add_edge(4,3)
G.add_edge(4,2)
nx.all_pairs_lowest_common_ancestor(G, 2,3) # returns 4 # desired return should be 1 and 4

Answer 1

Что, вероятно, сбивает вас с толку, так это то, что nx.all_pairs_lowest_common_ancestor возвращает единственного наименьшего общего предка (только одного, даже если их несколько на одном уровне). Под all_pairs... подразумевается, что он находит общего предка для всех пар указанных узлов. Это означает, что, рассматривая, например, следующий график, мы могли бы сделать:

list(nx.all_pairs_lowest_common_ancestor(G, [('pine','eucaliptus'), ('pine','daisy')]))
# [(('pine', 'daisy'), 'plant'), (('pine', 'eucaliptus'), 'tree')]

И получить наименьшего общего предка для всех указанных пар . Но в вашем примере, поскольку вы указали только одну пару, вы получите соответствующий LCA:

G = nx.DiGraph()
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_node(4)
G.add_edge(1,3)
G.add_edge(1,2)
G.add_edge(4,3)
G.add_edge(4,2)

list(nx.all_pairs_lowest_common_ancestor(G, pairs=[(2, 3)]))
# [((2, 3), 4)]

Какой то же, что:

nx.lowest_common_ancestor(G, 2,3)
# 4