Enhancement/question: Find lowest common ancestor of two or more nodes?

[helske]

Is there any way to extract lowest common ancestor of nodes without iterating over the ancestor names and finding the common ancestor "manually"? For two nodes it's not too bad, but for more nodes I'm not actually sure how one would accomplish this.

[c0fec0de]

I will add an commonanchestors function the next days.

[wa-dev]

Here is a possible implementation...

def commonAncestor(n, *rest):
    '''
    :param n: 1st node to check
    :param rest: all remaining nodes check
    :type node: Node
    :type rest: list[Node]
    :return: deepest common Node

    >>> from anytree import Node, RenderTree
    >>> udo = Node("Udo")
    >>> marc = Node("Marc", parent=udo)
    >>> lian = Node("Lian", parent=marc)
    >>> dan = Node("Dan", parent=udo)
    >>> jet = Node("Jet", parent=dan)
    >>> jan = Node("Jan", parent=dan)
    >>> joe = Node("Joe", parent=dan)
    >>> mary = Node("Mary")
    >>> urs = Node("Urs", parent=mary)
    >>> chris = Node("Chris", parent=mary)
    >>> marta = Node("Marta", parent=mary)
    >>> udo.parent = mary
    >>> print(RenderTree(mary))
    Node('/Mary')
    ├── Node('/Mary/Urs')
    ├── Node('/Mary/Chris')
    ├── Node('/Mary/Marta')
    └── Node('/Mary/Udo')
        ├── Node('/Mary/Udo/Marc')
        │   └── Node('/Mary/Udo/Marc/Lian')
        └── Node('/Mary/Udo/Dan')
            ├── Node('/Mary/Udo/Dan/Jet')
            ├── Node('/Mary/Udo/Dan/Jan')
            └── Node('/Mary/Udo/Dan/Joe')
    >>> print(commonAncestors(marta))
    Node('/Mary/Marta')
    >>> print(commonAncestors(lian, joe))
    Node('/Mary/Udo')
    >>> print(commonAncestors(jet, jan))
    Node('/Mary/Udo/Dan')
    >>> print(commonAncestors(joe, marc, urs))
    Node('/Mary')
    '''

    if len(rest):
        common = list(reduce(lambda x,y: x & y, [set(nn.ancestors) for nn in rest], set(n.ancestors)))
        if not common:
            raise RuntimeError('No common nodes')
        common.sort(key=lambda x: x.depth)
        deepest = common[-1]
        return deepest
    return n

[c0fec0de]

Thanks for the request and the contribution.

The example
>>> print(commonAncestors(marta))
Node('/Mary/Marta')
should return just
Node('/Mary/Marta')
because marta is not an anchestor of herself.

I just added a function in a new utilities module.

[Paulo-Monteiro]

Could you please add the util package to the config['packages'] in the setup.py

[amecreate]

Hi, in anytree v 2.8.0, regarding the lowest common ancestor, using the example above:

commonancestors(marc, lian)
(Node('/Mary'), Node('/Mary/Udo'))

Since Lian is a direct descendant of Marc, shouldn't it return Node('/Mary/Udo/Marc') as well? Given this definition on Lowest Common Ancestor:

...where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).

Thank you!