networkx DAG中的多重LCA

Question

我正在尝试使用python中的networkx包来查找图中两个节点的最低公共祖先。当我为此使用内置方法时，当存在多个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