python - DAG 中的 networkx 多个 LCA

Question

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