python - BeautifulSoup lowest common ancestor

Question

Does the BeautifulSoup library for Python have any function that can take a list of nodes and return the lowest common ancestor?

If not, has any of you ever implemented such a function and care to share it?

Answer 1

我认为这就是您想要的，link1 是一个元素，而 link2 是另一个元素；

link_1_parents = list(link1.parents)[::-1]
link_2_parents = list(link2.parents)[::-1]

common_parent = [x for x,y in zip(link_1_parents, link_2_parents) if x is y][-1]

print common_parent
print common_parent.name

它基本上会从根向下遍历两个元素的父母，并返回最后一个共同的父母。

Answer 2

如果输入列表中的标签到最低共同祖先的距离对于输入中的每个节点都不完全相同，则接受的答案不起作用。

它还使用每个节点的每个祖先，这是不必要的，并且在某些情况下可能非常昂贵。

import collections
def lowest_common_ancestor(parents=None, *args):
    if parents is None:
        parents = collections.defaultdict(int)
    for tag in args:
        if not tag:
            continue
        parents[tag] += 1
        if parents[tag] == len(args):
            return tag
    return lowest_common_ancestor(parents, *[tag.parent if tag else None for tag in args])

Answer 3

由于亚瑟的回答在某些情况下是不正确的。我修改了亚瑟的答案，并给出了我的答案。我已经用两个节点作为输入测试了 LCA 的代码。

import collections
def lowest_common_ancestor(parents=None, *args):
    if parents is None:
        parents = collections.defaultdict(int)
    for tag in args:
        parents[tag] += 1
        if parents[tag] == NUM_OF_NODES:
            return tag
    next_arg_list = [tag.parent for tag in args if tag.parent is not None]

    return lowest_common_ancestor(parents, *next_arg_list)

像这样调用函数：

list_of_tag = [tag_a, tag_b]
NUM_OF_NODES = len(list_of_tag)
lca = lowest_common_ancestor(None, *list_of_tag)
print(lca)