Trees

TreeNode

Tree nodes for class Tree.

Attributes:

Name	Type	Description
parent	TreeNode	Parent node of this node.
children	DLList	Child nodes of this node in a doubly-linked list.

Source code in tralda/datastructures/tree.py

class TreeNode:
    """Tree nodes for class Tree.

    Attributes:
        parent (TreeNode): Parent node of this node.
        children (dll.DLList): Child nodes of this node in a doubly-linked list.
    """

    def __init__(self, **kwargs: Any) -> None:
        """Constructor for TreeNode class.

        Args:
            **kwargs: Set arbitrary node attributes using key=value.
        """
        self.parent = None
        # reference to doubly-linked list element in the parents' children
        self._par_dll_node = None

        self.children = dll.DLList()

        self.__dict__.update(kwargs)

    def __str__(self) -> str:
        """Return the label of the tree node if available.

        Returns:
            The label of the tree node if available or an empty string.
        """
        return str(self.label) if hasattr(self, "label") else ""

    def __repr__(self) -> str:
        """Return a string representation of the tree node.

        If available, the `label` attribute will be contained, otherwise the object ID of the
        TreeNode instance.

        Returns:
            A string representation of the tree node.
        """
        return f"<TN: {self.label if hasattr(self, 'label') else id(self)}>"

    def attributes(self) -> Iterator[tuple[str, Any]]:
        """A generator for the node attributes.

        Yields:
            Pairs of str and the type of the corresponding value.
        """
        for key, value in self.__dict__.items():
            if key not in ("parent", "children", "_par_dll_node"):
                yield key, value

    def add_child(self, child_node: TreeNode) -> None:
        """Add a node as a child of this node.

        Does nothing if the node is already a child node of this node.

        Args:
            child_node: The node to add as a new child to this node.
        """
        if child_node.parent is None:
            child_node.parent = self
            child_node._par_dll_node = self.children.append(child_node)
        elif child_node.parent is not self:
            child_node.parent.remove_child(child_node)
            child_node.parent = self
            child_node._par_dll_node = self.children.append(child_node)

    def add_child_right_of(self, child_node: TreeNode, right_of: TreeNode) -> None:
        """Add a node as a child of this node as a right sibling of one of its children.

        Can also be used to change the position of a child node, i.e., to detach it and re-insert
        it to the right of the specified node.

        Args:
            child_node: The node to add as a new child to this node.
            right_of: The child of this node right of which 'child_node' gets inserted.

        Raises:
            KeyError: If 'right_of' is not a child of this node.
        """
        if right_of.parent is not self:
            raise KeyError(f"{right_of} is not a child of node {self}")

        if child_node.parent is not None:
            child_node.parent.remove_child(child_node)

        child_node.parent = self
        child_node._par_dll_node = self.children.insert_right_of(right_of._par_dll_node, child_node)

    def remove_child(self, child_node: TreeNode) -> None:
        """Remove a child node of this node.

        Args:
            child_node: The node to be removed from the list of children.

        Raises:
            KeyError: If the supplied node is not a child of this node.
        """
        if child_node.parent is self:
            self.children.remove_node(child_node._par_dll_node)
            child_node.parent = None
            child_node._par_dll_node = None
        else:
            raise KeyError(f"{child_node} is not a child of node {self}")

    def detach(self) -> None:
        """Detach this node from its parent.

        The node has no parent afterwards.
        """
        if self.parent is not None:
            self.parent.remove_child(self)
        else:
            self.parent = None
            self._par_dll_node = None

    def is_leaf(self) -> bool:
        """Return True if the node is a leaf, False otherwise.

        Returns:
            True if the node is a leaf, i.e., it has no children, else False.
        """
        return not self.children

    def child_subsequence(self, left_node: TreeNode, right_node: TreeNode) -> list[TreeNode]:
        """Consecutive subsequence of children within a left and right bound.

        Args:
            left_node: The left bound of the subsequence.
            right_node: The right bound of the subsequence.

        Returns:
            The children in the subsequence.

        Raises:
            KeyError: If 'right_node' or 'left_node' is not a child of this node.
        """
        if left_node.parent is not self:
            raise KeyError(f"{left_node} is not a child of node {self}")
        if right_node.parent is not self:
            raise KeyError(f"{right_node} is not a child of node {self}")

        return self.children.sublist(left_node._par_dll_node, right_node._par_dll_node)

__init__(**kwargs: Any) -> None

Constructor for TreeNode class.

Parameters:

Name	Type	Description	Default
**kwargs	Any	Set arbitrary node attributes using key=value.	{}

Source code in tralda/datastructures/tree.py

def __init__(self, **kwargs: Any) -> None:
    """Constructor for TreeNode class.

    Args:
        **kwargs: Set arbitrary node attributes using key=value.
    """
    self.parent = None
    # reference to doubly-linked list element in the parents' children
    self._par_dll_node = None

    self.children = dll.DLList()

    self.__dict__.update(kwargs)

__str__() -> str

Return the label of the tree node if available.

Returns:

Type	Description
str	The label of the tree node if available or an empty string.

Source code in tralda/datastructures/tree.py

def __str__(self) -> str:
    """Return the label of the tree node if available.

    Returns:
        The label of the tree node if available or an empty string.
    """
    return str(self.label) if hasattr(self, "label") else ""

__repr__() -> str

Return a string representation of the tree node.

If available, the label attribute will be contained, otherwise the object ID of the TreeNode instance.

Returns:

Type	Description
str	A string representation of the tree node.

Source code in tralda/datastructures/tree.py

def __repr__(self) -> str:
    """Return a string representation of the tree node.

    If available, the `label` attribute will be contained, otherwise the object ID of the
    TreeNode instance.

    Returns:
        A string representation of the tree node.
    """
    return f"<TN: {self.label if hasattr(self, 'label') else id(self)}>"

attributes() -> Iterator[tuple[str, Any]]

A generator for the node attributes.

Yields:

Type	Description
tuple[str, Any]	Pairs of str and the type of the corresponding value.

Source code in tralda/datastructures/tree.py

def attributes(self) -> Iterator[tuple[str, Any]]:
    """A generator for the node attributes.

    Yields:
        Pairs of str and the type of the corresponding value.
    """
    for key, value in self.__dict__.items():
        if key not in ("parent", "children", "_par_dll_node"):
            yield key, value

add_child(child_node: TreeNode) -> None

Add a node as a child of this node.

Does nothing if the node is already a child node of this node.

Parameters:

Name	Type	Description	Default
child_node	TreeNode	The node to add as a new child to this node.	required

Source code in tralda/datastructures/tree.py

def add_child(self, child_node: TreeNode) -> None:
    """Add a node as a child of this node.

    Does nothing if the node is already a child node of this node.

    Args:
        child_node: The node to add as a new child to this node.
    """
    if child_node.parent is None:
        child_node.parent = self
        child_node._par_dll_node = self.children.append(child_node)
    elif child_node.parent is not self:
        child_node.parent.remove_child(child_node)
        child_node.parent = self
        child_node._par_dll_node = self.children.append(child_node)

add_child_right_of(child_node: TreeNode, right_of: TreeNode) -> None

Add a node as a child of this node as a right sibling of one of its children.

Can also be used to change the position of a child node, i.e., to detach it and re-insert it to the right of the specified node.

Parameters:

Name	Type	Description	Default
child_node	TreeNode	The node to add as a new child to this node.	required
right_of	TreeNode	The child of this node right of which 'child_node' gets inserted.	required

Raises:

Type	Description
KeyError	If 'right_of' is not a child of this node.

Source code in tralda/datastructures/tree.py

def add_child_right_of(self, child_node: TreeNode, right_of: TreeNode) -> None:
    """Add a node as a child of this node as a right sibling of one of its children.

    Can also be used to change the position of a child node, i.e., to detach it and re-insert
    it to the right of the specified node.

    Args:
        child_node: The node to add as a new child to this node.
        right_of: The child of this node right of which 'child_node' gets inserted.

    Raises:
        KeyError: If 'right_of' is not a child of this node.
    """
    if right_of.parent is not self:
        raise KeyError(f"{right_of} is not a child of node {self}")

    if child_node.parent is not None:
        child_node.parent.remove_child(child_node)

    child_node.parent = self
    child_node._par_dll_node = self.children.insert_right_of(right_of._par_dll_node, child_node)

remove_child(child_node: TreeNode) -> None

Remove a child node of this node.

Parameters:

Name	Type	Description	Default
child_node	TreeNode	The node to be removed from the list of children.	required

Raises:

Type	Description
KeyError	If the supplied node is not a child of this node.

Source code in tralda/datastructures/tree.py

def remove_child(self, child_node: TreeNode) -> None:
    """Remove a child node of this node.

    Args:
        child_node: The node to be removed from the list of children.

    Raises:
        KeyError: If the supplied node is not a child of this node.
    """
    if child_node.parent is self:
        self.children.remove_node(child_node._par_dll_node)
        child_node.parent = None
        child_node._par_dll_node = None
    else:
        raise KeyError(f"{child_node} is not a child of node {self}")

detach() -> None

Detach this node from its parent.

The node has no parent afterwards.

Source code in tralda/datastructures/tree.py

def detach(self) -> None:
    """Detach this node from its parent.

    The node has no parent afterwards.
    """
    if self.parent is not None:
        self.parent.remove_child(self)
    else:
        self.parent = None
        self._par_dll_node = None

is_leaf() -> bool

Return True if the node is a leaf, False otherwise.

Returns:

Type	Description
bool	True if the node is a leaf, i.e., it has no children, else False.

Source code in tralda/datastructures/tree.py

def is_leaf(self) -> bool:
    """Return True if the node is a leaf, False otherwise.

    Returns:
        True if the node is a leaf, i.e., it has no children, else False.
    """
    return not self.children

child_subsequence(left_node: TreeNode, right_node: TreeNode) -> list[TreeNode]

Consecutive subsequence of children within a left and right bound.

Parameters:

Name	Type	Description	Default
left_node	TreeNode	The left bound of the subsequence.	required
right_node	TreeNode	The right bound of the subsequence.	required

Returns:

Type	Description
list[TreeNode]	The children in the subsequence.

Raises:

Type	Description
KeyError	If 'right_node' or 'left_node' is not a child of this node.

Source code in tralda/datastructures/tree.py

def child_subsequence(self, left_node: TreeNode, right_node: TreeNode) -> list[TreeNode]:
    """Consecutive subsequence of children within a left and right bound.

    Args:
        left_node: The left bound of the subsequence.
        right_node: The right bound of the subsequence.

    Returns:
        The children in the subsequence.

    Raises:
        KeyError: If 'right_node' or 'left_node' is not a child of this node.
    """
    if left_node.parent is not self:
        raise KeyError(f"{left_node} is not a child of node {self}")
    if right_node.parent is not self:
        raise KeyError(f"{right_node} is not a child of node {self}")

    return self.children.sublist(left_node._par_dll_node, right_node._par_dll_node)

Tree

Rooted tree whose nodes may have an arbitrary number of children.

Attributes:

Name	Type	Description
root	TreeNode	The root node of the tree.

Source code in tralda/datastructures/tree.py

class Tree:
    """Rooted tree whose nodes may have an arbitrary number of children.

    Attributes:
        root (TreeNode): The root node of the tree.
    """

    def __init__(self, arg: TreeNode | str) -> None:
        """Constructor for the class Tree.

        Args:
            arg: The root node for the newly created tree or a Newick representation of a tree.

        Raises:
            TypeError: If 'arg' is neither a TreeNode instance nor a string.
        """
        if isinstance(arg, TreeNode) or arg is None:
            self.root = arg
        elif isinstance(arg, str):
            self.root = Tree._parse_newick_and_return_root(arg)
        else:
            raise TypeError(f"Tree cannot be initialized with argument of type {type(arg)}")

    def __len__(self) -> int:
        """Size of the tree (number of nodes).

        Runs in O(n) where n is the size of the tree.

        Returns:
            The number of nodes in the tree.
        """
        return sum(1 for _ in self.preorder())

    def height(self) -> int:
        """Height of the tree (number of edges in the longest path from the root to a leaf).

        Runs in O(n) where n is the size of the tree. Return -1 if the tree is empty.

        Returns:
            The height of the tree.
        """
        if not self.root:
            return -1

        return max(level for _, level in self.preorder_and_level())

    def leaves(self) -> Iterator[TreeNode]:
        """Generator for leaves of the tree.

        Yields:
            The leaf nodes of the tree.
        """

        def _leaves(node: TreeNode) -> Iterator[TreeNode]:
            if not node.children:
                yield node
            else:
                for child in node.children:
                    yield from _leaves(child)

        if self.root:
            yield from _leaves(self.root)
        else:
            yield from []

    def preorder(self) -> Iterator[TreeNode]:
        """Generator for a pre-order traversal of the tree.

        Yields:
            All nodes of the tree in pre-order.
        """

        def _preorder(node: TreeNode) -> Iterator[TreeNode]:
            yield node
            for child in node.children:
                yield from _preorder(child)

        if self.root:
            yield from _preorder(self.root)
        else:
            yield from []

    def preorder_and_level(self) -> Iterator[tuple[TreeNode, int]]:
        """Generator for a pre-order traversal with node levels.

        Yields:
            Nodes and their level (distance from the root) in pre-order.
        """

        def _preorder_level(node: TreeNode, level: int) -> Iterator[tuple[TreeNode, int]]:
            yield (node, level)
            for child in node.children:
                yield from _preorder_level(child, level + 1)

        if self.root:
            yield from _preorder_level(self.root, 0)
        else:
            yield from []

    def traverse_subtree(self, node: TreeNode) -> Iterator[TreeNode]:
        """Generator for a pre-order traversal of the subtree rooted at the given node.

        Args:
            node: The node whose subtree to traverse.

        Yields:
            All nodes in the subtree rooted at the given node in pre-order.
        """
        yield node

        for child in node.children:
            yield from self.traverse_subtree(child)

    def postorder(self) -> Iterator[TreeNode]:
        """Generator for post-order traversal of the tree.

        Yields:
            All nodes of the tree in post-order.
        """

        def _postorder(node: TreeNode) -> Iterator[TreeNode]:
            for child in node.children:
                yield from _postorder(child)
            yield node

        if self.root:
            yield from _postorder(self.root)
        else:
            yield from []

    def inner_nodes(self) -> Iterator[TreeNode]:
        """Generator for inner nodes in pre-order.

        Inner nodes are those nodes that do not have any children.

        Yields:
            All inner nodes of the tree in pre-order.
        """

        def _inner_nodes(node: TreeNode) -> Iterator[TreeNode]:
            if node.children:
                yield node
                for child in node.children:
                    yield from _inner_nodes(child)

        if self.root:
            yield from _inner_nodes(self.root)
        else:
            yield from []

    def edges(self) -> Iterator[tuple[TreeNode, TreeNode]]:
        """Generator for all edges of the tree.

        Yields:
            All edges of the tree as tuples of TreeNode instances.
        """

        def _edges(node: TreeNode) -> Iterator[tuple[TreeNode, TreeNode]]:
            for child in node.children:
                yield (node, child)
                yield from _edges(child)

        if self.root:
            yield from _edges(self.root)
        else:
            yield from []

    def edges_sibling_order(self) -> Iterator[tuple[TreeNode, TreeNode, int]]:
        """Generator for all edges of the tree with sibling order.

        Yields:
            Edges uv as tuples (u, v, nr) where nr is the index of v in the list of children of
            node u.
        """

        def _edges_sibling_order(node: TreeNode) -> Iterator[tuple[TreeNode, TreeNode, int]]:
            i = 0
            for child in node.children:
                yield (node, child, i)
                yield from _edges_sibling_order(child)
                i += 1

        if self.root:
            yield from _edges_sibling_order(self.root)
        else:
            yield from []

    def inner_edges(self) -> Iterator[tuple[TreeNode, TreeNode]]:
        """Generator for all inner edges of the tree.

        Yields:
            All inner edges uv of the tree, i.e., edges for which the child v of u is not a leaf.
        """

        def _inner_edges(node: TreeNode) -> Iterator[tuple[TreeNode, TreeNode]]:
            for child in node.children:
                if child.children:
                    yield (node, child)
                    yield from _inner_edges(child)

        if self.root:
            yield from _inner_edges(self.root)
        else:
            yield from []

    def euler_generator(self) -> Iterator[TreeNode]:
        """Generator for an Euler tour of the tree.

        Yields:
            Nodes in an Euler tour of the tree.
        """

        def _euler_generator(node: TreeNode) -> Iterator[TreeNode]:
            yield node
            for child in node.children:
                yield from _euler_generator(child)
                yield node

        if self.root:
            yield from _euler_generator(self.root)
        else:
            yield from []

    def euler_and_level(self) -> Iterator[tuple[TreeNode, int]]:
        """Generator for an Euler tour with node levels.

        Yields:
            Nodes and their level (distance from the root) in an Euler tour of the tree.
        """

        def _euler_level(node: TreeNode, level: int) -> Iterator[tuple[TreeNode, int]]:
            yield (node, level)
            for child in node.children:
                yield from _euler_level(child, level + 1)
                yield (node, level)

        if self.root:
            yield from _euler_level(self.root, 0)
        else:
            yield from []

    def leaf_dict(self) -> dict[TreeNode, list[TreeNode]]:
        """Leaves in the subtree rooted at each node.

        Computes the list of leaves for every node in the tree containing the leaf nodes in the
        subtree rooted at the node.

        Returns:
            The leaves under each vertex (as a dictionary with `TreeNode` keys and lists of
                `TreeNode` objects as values).
        """
        leaves = {}

        for v in self.postorder():
            if not v.children:
                leaves[v] = [v]
            else:
                leaves[v] = []
                for child in v.children:
                    leaves[v].extend(leaves[child])

        return leaves

    def contract(self, edges: Iterable[tuple[TreeNode]], inplace: bool = True) -> Tree:
        """Contract edges in the tree.

        Args:
            edges: The edges to be contracted in the tree.
            inplace: If True, the edges are contracted in this tree instance, otherwise a copy is
                returned and the original tree is not affected.

        Returns:
            The original tree with contracted edges or a copy in which the contractions are
                performed.
        """
        contracted = set()

        if not inplace:
            T_copy, mapping = self.copy(mapping=True)

        for _, v in edges:
            # avoid trying to contract the same edge multiple times
            if v in contracted:
                continue

            if inplace:
                self.delete_and_reconnect(v)
            else:
                T_copy.delete_and_reconnect(mapping[v])

            contracted.add(v)

        return self if inplace else T_copy

    def get_triples(self, label_only: bool = False) -> list[tuple[Any, Any, Any]]:
        """Retrieve a list of all (rooted) triples of the tree.

        A tree displays a triple ab|c on the leaf nodes a, b and c if the last common ancestor of a
        and b is a (proper) descendant of the last common ancestor of a and c (b and c).

        Args:
            label_only: If True, the triples are represented by the label attribute of the nodes.

        Returns:
            List of tuples where each tuple (a, b, c) represents the triple ab|c (=ba|c), i.e., the
                first two items are closer related in the tree.
        """
        if label_only:
            return [(a.label, b.label, c.label) for a, b, c in self._triple_generator()]
        else:
            return [t for t in self._triple_generator()]

    def _triple_generator(self) -> Iterator[tuple[TreeNode, TreeNode, TreeNode]]:
        """Iterator for all (rooted) triples displayed by the tree.

        Yields:
            The triples displayed by the tree.
        """
        leaves = self.leaf_dict()

        for u in self.preorder():
            for v1, v2 in itertools.permutations(u.children, 2):
                if len(leaves[v2]) <= 1:
                    continue

                for c in leaves[v1]:
                    for a, b in itertools.combinations(leaves[v2], 2):
                        yield a, b, c

    def delete_and_reconnect(self, node: TreeNode) -> TreeNode | None:
        """Delete a node from the tree and reconnect its parent and children.

        The function preserves the 'sibling order' of the remaining nodes of the tree.

        Args:
            node: The node to be deleted.

        Returns:
            The parent of the node, if it could be deleted, or None, if the node could not be
                deleted, i.e., it has no parent.
        """
        parent = node.parent

        if not parent:
            return None
        else:
            # copy list of children to edit edges
            children = [child for child in node.children]

            for child in children:
                parent.add_child_right_of(child, node)

            parent.remove_child(node)
            node.children.clear()

        return parent

    def random_leaves(self, proportion: int | float) -> list[TreeNode]:
        """A random sample of the leaves.

        Args:
            proportion: The proportion of the sample w.r.t. the full set of leaves.

        Returns:
            A randomly samples list of the leaves of the tree.

        Raises:
            ValueError: If 'proportion' is not a number between 0 and 1.
        """
        if not isinstance(proportion, (float, int)) or proportion < 0 or proportion > 1:
            raise ValueError("proportion must be a number 0 <= p <= 1")

        leaves = [v for v in self.leaves()]
        k = round(proportion * len(leaves))

        return random.sample(leaves, k)

    def is_binary(self) -> bool:
        """Check whether the tree is a binary tree.

        Nodes in (rooted) binary trees are either leaves or have exactly two children.

        Returns:
            True if the tree is binary, else False.
        """
        for v in self.preorder():
            if len(v.children) == 1 or len(v.children) > 2:
                return False

        return True

    def is_phylogenetic(self) -> bool:
        """Check whether the tree is a phylogenetic tree.

        Nodes in (rooted) phylogenetic trees are either leaves or have at least two children.

        Returns:
            True if the tree is phylogenetic, else False.
        """
        for v in self.preorder():
            if len(v.children) == 1:
                return False

        return True

    def get_hierarchy(self) -> set[tuple[Any]]:
        """Hierarchy set on the leaf labels defined by the tree.

        Every (phylogenetic) tree can be represented by a hierarchy on the set of its leaves. The
        label attributes of the leaf nodes must be set and unique for each leaf.

        Returns:
            A set of tuples representing the hierarchy where the leaves are represented by their
                labels.
        """
        leaves = self.leaf_dict()
        hierarchy = set()

        for v in self.preorder():
            hierarchy.add(tuple(sorted(leaf.label for leaf in leaves[v])))

        return hierarchy

    def equal_topology(self, other: Tree, verbose: bool = False) -> bool:
        """Compare the tree topology based on the leaf labels.

        Only works for phylogenetic trees with unique leaf labels.

        Args:
            other: Another tree which this tree shall be compared to.
            verbose: If True, print where the equality check failed (the first time).

        Returns:
            True if the topologies are equal, else False.
        """
        hierarchy1 = sorted(self.get_hierarchy())
        hierarchy2 = sorted(other.get_hierarchy())

        if len(hierarchy1) != len(hierarchy2):
            if verbose:
                print(
                    f"Unequal sizes of the hierarchy sets: {len(hierarchy1)} and {len(hierarchy2)}"
                )
            return False

        for i in range(len(hierarchy1)):
            if hierarchy1[i] != hierarchy2[i]:
                if verbose:
                    print(f"Hierarchies not equal:\n{hierarchy1[i]}\n{hierarchy2[i]}")
                return False

        return True

    def is_refinement(self, other: Tree) -> bool:
        """Checks whether the tree is a refinement of 'other' based on the leaf labels.

        Only works for phylogenetic trees with unique leaf labels.

        Args:
            other: Another tree which this tree shall be compared to.

        Returns:
            True if the tree is refinement of 'other', else False.
        """
        hierarchy1 = sorted(self.get_hierarchy())
        hierarchy2 = sorted(other.get_hierarchy())

        if len(hierarchy1) < len(hierarchy2):
            return False

        i1, i2 = 0, 0
        while i2 < len(hierarchy2):
            if i1 >= len(hierarchy1):
                return False

            if hierarchy1[i1] == hierarchy2[i2]:
                i1 += 1
                i2 += 1
            else:
                i1 += 1

        return True

    def _assert_integrity(self) -> bool:
        """Check whether all nodes in the tree are connected properly to their parents.

        Raises:
            RuntimeError: If there is a loop or a child of a node is not connected to that node via
                the `parent` attribute.

        Returns:
            True if the integrity check has been passed successfully.
        """
        for v in self.preorder():
            for child in v.children:
                if child is v:
                    raise RuntimeError(f"loop at {v}")
                if child.parent is not v:
                    raise RuntimeError(f"Tree invalid for {v} and {child}")

        return True

    def copy(self, mapping: bool = False) -> Tree | tuple[Tree, dict[TreeNode, TreeNode]]:
        """Return a copy of the tree.

        Constructs a copy of the tree to the level of nodes, i.e., the attributes are only copied as
        references. If the node attributes are all immutable data types, the original tree is not
        affected by operations on the copy.

        Args:
            mapping: If True, additionally return the mapping from original to copied nodes as
                dictionary.

        Returns:
            A copy of the tree and optionally the mapping from original to copied nodes.
        """
        if not self.root:
            return Tree(None)

        orig_to_new = {}

        for orig in self.preorder():
            new = TreeNode()
            orig_to_new[orig] = new
            if orig.parent:
                orig_to_new[orig.parent].add_child(new)

            # shallow copy of the node attributes
            for key, value in orig.attributes():
                setattr(new, key, value)

        if mapping:
            return Tree(orig_to_new[self.root]), orig_to_new
        else:
            return Tree(orig_to_new[self.root])

    # --------------------------------------------------------------------------
    #                         TREE  <--->  NEWICK
    # --------------------------------------------------------------------------

    def to_newick(self, node: TreeNode | None = None) -> str:
        """Newick representation of the tree.

        Args:
            node: The node whose subtree shall be returned as a Newick string, the default is None,
                in which case the whole tree is returned in Newick format.

        Returns:
            A newick representation of the (sub)tree.
        """

        def _to_newick(node: TreeNode) -> str:
            node_str = str(node)

            # add colon and distance if available
            if hasattr(node, "dist"):
                node_str += f":{node.dist}"

            if not node.children:
                return node_str
            else:
                s = ""
                for child in node.children:
                    s += _to_newick(child) + ","
                return f"({s[:-1]}){node_str}"

        if node:
            return _to_newick(node) + ";"
        elif self.root:
            return _to_newick(self.root) + ";"
        else:
            return ";"

    @staticmethod
    def _parse_newick_and_return_root(newick: str) -> TreeNode:
        """Parses trees in Newick format and returns the root.

        If available (after colons in the Newick strings), the distance is stored in the 'dist'
        attribute of the nodes. Moreover, labels are converted to integers if possible.

        Args:
            newick: A tree in Newick format.

        Returns:
            The root of the parsed tree.

        Raises:
            TypeError: If the input is not a string.
            ValueError: If the input is not a valid Newick string.
        """

        def _parse_subtree(subroot: TreeNode, subtree_string: str) -> None:
            """Recursive function to parse the subtrees.

            Args:
                subroot: The tree node to which parsed children are attached.
                subtree_string: The string containing the children to parse.

            Raises:
                ValueError: If the input is not a valid Newick string.
            """
            children = _split_children(subtree_string)

            for child in children:
                node = TreeNode()
                subroot.add_child(node)
                end = -1

                # the child has subtrees
                if child[0] == "(":
                    end = child.rfind(")")
                    if end == -1:
                        raise ValueError("invalid Newick string")
                    # recursive call
                    _parse_subtree(node, child[1:end])

                child = child[end + 1 :].strip()

                label = child

                if child.find(":") != -1:
                    label, dist = child.rsplit(":", 1)

                    try:
                        node.dist = float(dist)
                    except ValueError:
                        raise ValueError(f"invalid distance in Newick string: {dist}")

                # convert label to integer if possible
                node.label = int(label) if label.isdigit() else label

        def _split_children(child_string: str) -> list[str]:
            """Splits a given string by all ',' that are not enclosed by parentheses.

            Args:
                child_string: The string to split into the direct children.

            Returns:
                The split string.

            Raises:
                ValueError: If the input is not a valid Newick string.
            """
            stack = 0
            children = []
            current = ""

            for c in child_string:
                if (stack == 0) and c == ",":
                    children.append(current)
                    current = ""
                elif c == "(":
                    stack += 1
                    current += c
                elif c == ")":
                    if stack <= 0:
                        raise ValueError("invalid Newick string")
                    stack -= 1
                    current += c
                else:
                    current += c

            children.append(current.strip())
            return children

        if not isinstance(newick, str):
            raise TypeError("Newick parser needs a 'str' as input")

        end = newick.find(";")
        if end != -1:
            newick = newick[:end]

        temp_root = TreeNode()
        _parse_subtree(temp_root, newick)

        if temp_root.children:
            root = temp_root.children[0]
            # remove the parent temp_root
            root.detach()
            return root
        else:
            raise ValueError("invalid Newick string")

    @classmethod
    def parse_newick(cls, newick: str) -> Tree:
        """Parses trees in Newick format into Tree object.

        If available (after colons in the Newick strings), the distance is stored in the 'dist'
        attribute of the nodes. Moreover, labels are converted to integers if possible.

        NOTE: Do not use this function for serialization and reloading Tree objects. Use the
        'serialize()' function instead.

        Args:
            newick: A tree in Newick format.

        Returns:
            The parsed tree.

        Raises:
            TypeError: If the input is not a string.
            ValueError: If the input is not a valid Newick string.
        """
        return cls(cls._parse_newick_and_return_root(newick))

    # --------------------------------------------------------------------------
    #                         TREE  <--->  NETWORKX
    # --------------------------------------------------------------------------

    def to_nx(self) -> tuple[nx.DiGraph, int]:
        """Convert a Tree into a NetworkX DiGraph.

        The attributes correspond to the node attributes in the resulting graph. The nodes of the
        resulting graph correspond to the object ids of the TreeNode instances belonging to the
        tree.

        Returns:
            A graph representation of the tree and the object id of the root (and thus the
                corresponding node in the graph) in order to be able to completely reconstruct the
                tree.
        """
        self._assert_integrity()
        graph = nx.DiGraph()

        if not self.root:
            return graph, None

        for v in self.preorder():
            graph.add_node(id(v))
            for key, value in v.attributes():
                graph.nodes[id(v)][key] = value

        for u, v, sibling_nr in self.edges_sibling_order():
            if u is v:
                raise RuntimeError(f"loop at {u} and {v}")
            graph.add_edge(id(u), id(v))
            graph.nodes[id(v)]["sibling_nr"] = sibling_nr

        return graph, id(self.root)

    @classmethod
    def parse_nx(cls, graph: nx.DiGraph, root: int) -> Tree:
        """Convert a NetworkX DiGraph version back into a Tree.

        Args:
            graph: A tree represented as a Networkx DiGraph.
            root: The node in the graph corresponding to the root.

        Returns:
            The reconstructed tree.
        """
        number_of_leaves = 0

        if root is None:
            return cls(None)

        def _build_tree(graphnode, parent=None) -> TreeNode:
            nonlocal number_of_leaves

            treenode = TreeNode()

            if parent:
                parent.add_child(treenode)

            for key, value in graph.nodes[graphnode].items():
                setattr(treenode, key, value)

            children = sorted(
                graph.neighbors(graphnode), key=lambda item: graph.nodes[item]["sibling_nr"]
            )

            for c in children:
                _build_tree(c, parent=treenode)
            if graph.out_degree(graphnode) == 0:
                number_of_leaves += 1

            return treenode

        tree = cls(_build_tree(root))
        tree.number_of_species = number_of_leaves

        return tree

    # --------------------------------------------------------------------------
    #                           SERIALIZATION
    # --------------------------------------------------------------------------

    def to_dict(self) -> dict[str, Any]:
        """Convert the tree into a nested dictionary.

        Returns:
            A dict representation of the tree,

        Raises:
            RuntimeError: If the tree is empty.
        """

        def _to_dict(node: TreeNode) -> dict[str, Any]:
            node_dict = {k: v for k, v in node.attributes()}

            for i, child in enumerate(node.children):
                node_dict[f"_child{i}"] = _to_dict(child)

            return node_dict

        if self.root:
            return _to_dict(self.root)
        else:
            raise RuntimeError("cannot convert empty tree to dict")

    @classmethod
    def parse_dict(cls, tree_dict: dict[str, Any]) -> Tree:
        """Convert a dictionary representation back into a Tree.

        Args:
            tree_dict: A dictionary representation of the tree.

        Returns:
            The reconstructed tree.
        """

        def _parse_dict(node_dict: dict[str, Any]) -> TreeNode:
            """Recursive function for reconstructing the subtree represented by the dict.

            Args:
                node_dict: Dict representing a (sub)tree.

            Returns:
                The root node of reconstructed (sub)tree.
            """
            node = TreeNode()
            children = {}

            for k, v in node_dict.items():
                if k.startswith("_child"):
                    children[int(k[6:])] = _parse_dict(v)
                else:
                    setattr(node, k, v)

            for i in sorted(children):
                node.add_child(children[i])

            return node

        return cls(_parse_dict(tree_dict))

    @staticmethod
    def _infer_serialization_mode(filename: str) -> str:
        """Infer the serialization mode based on the file ending (.json or .pickle).

        Args:
            filename: The file name.

        Raises:
            ValueError: If the file extension is not supported.

        Returns:
            The inferred serialization mode.
        """
        _, file_ext = os.path.splitext(filename)

        if file_ext.lower() == ".json":
            return "json"
        elif file_ext.lower() == ".pickle":
            return "pickle"
        else:
            raise ValueError(
                "serialization format is not supplied and could not be inferred from file extension"
            )

    def serialize(self, filename: str, mode: str = None) -> None:
        """Serialize the tree using pickle or json.

        Args:
            filename: The filename (including the path) of the file to be created.
            mode: The serialization mode. Supported are pickle and json. The default is None in
                which case the mode is inferred from the file extension.

        Raises:
            ValueError: If the serialization mode is unknown or could not be inferred.
        """
        if not mode:
            mode = Tree._infer_serialization_mode(filename)

        if mode == "json":
            with open(filename, "w") as f:
                json.dump(self.to_dict(), f)
        elif mode == "pickle":
            tree_nx, root_id = self.to_nx()
            with open(filename, "wb") as f:
                pickle.dump((tree_nx, root_id), f)
        else:
            raise ValueError(f"serialization mode '{mode}' not supported")

    @classmethod
    def load(cls, filename: str, mode: bool = None) -> Tree:
        """Reload a Tree from a file (pickle or json).

        Args:
            filename: The filename (including the path) of the file to be loaded.
            mode: The serialization mode. Supported are pickle and json. The default is None in
                which case the mode is inferred from the file extension.

        Returns:
            The tree reloaded from file.

        Raises:
            ValueError: If the serialization mode is unknown or could not be inferred.
        """
        if not mode:
            mode = Tree._infer_serialization_mode(filename)

        if mode == "json":
            with open(filename, "r") as f:
                tree_dict = json.load(f)
            return Tree.parse_dict(tree_dict)
        elif mode == "pickle":
            with open(filename, "rb") as f:
                return Tree.parse_nx(*pickle.load(f))
        else:
            raise ValueError(f"serialization mode '{mode}' not supported")

    # --------------------------------------------------------------------------
    #                     Print the tree to the console
    # --------------------------------------------------------------------------

    def _lines_for_print_tree(self, child_indentation: int) -> list[str]:
        """Auxiliary function for generating the lines to print the tree.

        Args:
            child_indentation: The additional indentation to be added for each level.

        Returns:
            The lines to be printed.
        """
        symbols = ("\u2500", "\u2502", "\u2514", "\u251c")

        nodes = [node for node in self.preorder()]
        node_index = {node: i for i, node in enumerate(nodes)}
        n = len(node_index)

        lines = [[] for _ in range(n)]

        for node in self.preorder():
            lines[node_index[node]].append(str(node))

            if not node.children:
                continue

            last_child = node.children.last()

            for i in range(node_index[node] + 1, node_index[last_child] + 1):
                descendant = nodes[i]
                if descendant is last_child:
                    lines[node_index[descendant]].append(
                        symbols[2] + (child_indentation - 1) * symbols[0]
                    )
                elif node is descendant.parent:
                    lines[node_index[descendant]].append(
                        symbols[3] + (child_indentation - 1) * symbols[0]
                    )
                else:
                    lines[node_index[descendant]].append(symbols[1] + (child_indentation - 1) * " ")

            for descendant in self.traverse_subtree(last_child):
                if descendant is not last_child:
                    lines[node_index[descendant]].append(child_indentation * " ")

        lines = ["".join(line) for line in lines]

        return lines

    def print_tree(self, child_indentation: int = 3) -> None:
        """Print a representation of the tree to the console.

        Args:
            child_indentation: The indentation added per level of the nodes. Must be >= 1.
        """
        if not isinstance(child_indentation, int) or child_indentation < 1:
            raise ValueError("child indentation must be an integer >= 1")

        for line in self._lines_for_print_tree(child_indentation):
            print(line)

    def plot(
        self,
        *,
        backend: str = "matplotlib",
        path: str | os.PathLike | None = None,
        show: bool = False,
        **kwargs: Any,
    ) -> Any:
        """Render this tree; see :func:`tralda.visualization.plot_tree` for all parameters.

        Requires the optional visualization dependencies, e.g. ``pip install tralda[matplotlib]``,
        ``tralda[plotly]``, or ``tralda[viz]`` for both backends.

        Args:
            backend: ``"matplotlib"`` (default) or ``"plotly"``.
            path: If given, save the resulting figure to this path.
            show: If ``True``, display the figure after rendering.
            **kwargs: Additional keyword arguments forwarded to
                :func:`~tralda.visualization.plot_tree` (layout mode, tree style, etc.).

        Returns:
            ``(fig, ax)`` for the matplotlib backend, or a Plotly ``Figure`` for the plotly backend.
        """
        from tralda.visualization import plot_tree

        return plot_tree(self, backend=backend, path=path, show=show, **kwargs)

    # --------------------------------------------------------------------------
    #                             RANDOM TREE
    # --------------------------------------------------------------------------

    @classmethod
    def random_tree(cls, number_of_leaves: int, binary: bool = False) -> Tree:
        """A simple function to generate a random tree.

        The tree is generated by iteratively sampling a random node to which a new leaf is attached
        (or two leaves if the sampled node was a leaf). Each step increases the number of leaves by
        one. The procedure ends as soon as the desired number of leaves is reached.
        The resulting tree is always phylogenetic, i.e., each inner node has at least two children.

        Args:
            number_of_leaves: The desired number of leaves.
            binary: If True, the resulting tree is binary, otherwise it may contain multifurcations.

        Returns:
            A randomly generated tree with the specified number of leaves.

        Raises:
            TypeError: If `number_of_leaves` is not an integer >= 1.
        """
        if not (isinstance(number_of_leaves, int)) or number_of_leaves < 1:
            raise TypeError("`number_of_leaves` must be an `int` > 0")

        root = TreeNode(label=0)
        tree = cls(root)
        node_list = [root]
        nr, leaf_count = 1, 1

        while leaf_count < number_of_leaves:
            node = random.choice(node_list)

            if not node.children:
                # to be phylogenetic at least two children must be added
                new_child1 = TreeNode(label=nr)
                new_child2 = TreeNode(label=nr + 1)
                node.add_child(new_child1)
                node.add_child(new_child2)
                node_list.extend(node.children)
                nr += 2
                leaf_count += 1
            elif node.children and not binary:
                # add only one child if there are already children
                new_child = TreeNode(label=nr)
                node.add_child(new_child)
                node_list.append(new_child)
                nr += 1
                leaf_count += 1

        return tree

__init__(arg: TreeNode | str) -> None

Constructor for the class Tree.

Parameters:

Name	Type	Description	Default
arg	TreeNode | str	The root node for the newly created tree or a Newick representation of a tree.	required

Raises:

Type	Description
TypeError	If 'arg' is neither a TreeNode instance nor a string.

Source code in tralda/datastructures/tree.py

def __init__(self, arg: TreeNode | str) -> None:
    """Constructor for the class Tree.

    Args:
        arg: The root node for the newly created tree or a Newick representation of a tree.

    Raises:
        TypeError: If 'arg' is neither a TreeNode instance nor a string.
    """
    if isinstance(arg, TreeNode) or arg is None:
        self.root = arg
    elif isinstance(arg, str):
        self.root = Tree._parse_newick_and_return_root(arg)
    else:
        raise TypeError(f"Tree cannot be initialized with argument of type {type(arg)}")

__len__() -> int

Size of the tree (number of nodes).

Runs in O(n) where n is the size of the tree.

Returns:

Type	Description
int	The number of nodes in the tree.

Source code in tralda/datastructures/tree.py

def __len__(self) -> int:
    """Size of the tree (number of nodes).

    Runs in O(n) where n is the size of the tree.

    Returns:
        The number of nodes in the tree.
    """
    return sum(1 for _ in self.preorder())

height() -> int

Height of the tree (number of edges in the longest path from the root to a leaf).

Runs in O(n) where n is the size of the tree. Return -1 if the tree is empty.

Returns:

Type	Description
int	The height of the tree.

Source code in tralda/datastructures/tree.py

def height(self) -> int:
    """Height of the tree (number of edges in the longest path from the root to a leaf).

    Runs in O(n) where n is the size of the tree. Return -1 if the tree is empty.

    Returns:
        The height of the tree.
    """
    if not self.root:
        return -1

    return max(level for _, level in self.preorder_and_level())

leaves() -> Iterator[TreeNode]

Generator for leaves of the tree.

Yields:

Type	Description
TreeNode	The leaf nodes of the tree.

Source code in tralda/datastructures/tree.py

def leaves(self) -> Iterator[TreeNode]:
    """Generator for leaves of the tree.

    Yields:
        The leaf nodes of the tree.
    """

    def _leaves(node: TreeNode) -> Iterator[TreeNode]:
        if not node.children:
            yield node
        else:
            for child in node.children:
                yield from _leaves(child)

    if self.root:
        yield from _leaves(self.root)
    else:
        yield from []

preorder() -> Iterator[TreeNode]

Generator for a pre-order traversal of the tree.

Yields:

Type	Description
TreeNode	All nodes of the tree in pre-order.

Source code in tralda/datastructures/tree.py

def preorder(self) -> Iterator[TreeNode]:
    """Generator for a pre-order traversal of the tree.

    Yields:
        All nodes of the tree in pre-order.
    """

    def _preorder(node: TreeNode) -> Iterator[TreeNode]:
        yield node
        for child in node.children:
            yield from _preorder(child)

    if self.root:
        yield from _preorder(self.root)
    else:
        yield from []

preorder_and_level() -> Iterator[tuple[TreeNode, int]]

Generator for a pre-order traversal with node levels.

Yields:

Type	Description
tuple[TreeNode, int]	Nodes and their level (distance from the root) in pre-order.

Source code in tralda/datastructures/tree.py

def preorder_and_level(self) -> Iterator[tuple[TreeNode, int]]:
    """Generator for a pre-order traversal with node levels.

    Yields:
        Nodes and their level (distance from the root) in pre-order.
    """

    def _preorder_level(node: TreeNode, level: int) -> Iterator[tuple[TreeNode, int]]:
        yield (node, level)
        for child in node.children:
            yield from _preorder_level(child, level + 1)

    if self.root:
        yield from _preorder_level(self.root, 0)
    else:
        yield from []

traverse_subtree(node: TreeNode) -> Iterator[TreeNode]

Generator for a pre-order traversal of the subtree rooted at the given node.

Parameters:

Name	Type	Description	Default
node	TreeNode	The node whose subtree to traverse.	required

Yields:

Type	Description
TreeNode	All nodes in the subtree rooted at the given node in pre-order.

Source code in tralda/datastructures/tree.py

def traverse_subtree(self, node: TreeNode) -> Iterator[TreeNode]:
    """Generator for a pre-order traversal of the subtree rooted at the given node.

    Args:
        node: The node whose subtree to traverse.

    Yields:
        All nodes in the subtree rooted at the given node in pre-order.
    """
    yield node

    for child in node.children:
        yield from self.traverse_subtree(child)

postorder() -> Iterator[TreeNode]

Generator for post-order traversal of the tree.

Yields:

Type	Description
TreeNode	All nodes of the tree in post-order.

Source code in tralda/datastructures/tree.py

def postorder(self) -> Iterator[TreeNode]:
    """Generator for post-order traversal of the tree.

    Yields:
        All nodes of the tree in post-order.
    """

    def _postorder(node: TreeNode) -> Iterator[TreeNode]:
        for child in node.children:
            yield from _postorder(child)
        yield node

    if self.root:
        yield from _postorder(self.root)
    else:
        yield from []

inner_nodes() -> Iterator[TreeNode]

Generator for inner nodes in pre-order.

Inner nodes are those nodes that do not have any children.

Yields:

Type	Description
TreeNode	All inner nodes of the tree in pre-order.

Source code in tralda/datastructures/tree.py

def inner_nodes(self) -> Iterator[TreeNode]:
    """Generator for inner nodes in pre-order.

    Inner nodes are those nodes that do not have any children.

    Yields:
        All inner nodes of the tree in pre-order.
    """

    def _inner_nodes(node: TreeNode) -> Iterator[TreeNode]:
        if node.children:
            yield node
            for child in node.children:
                yield from _inner_nodes(child)

    if self.root:
        yield from _inner_nodes(self.root)
    else:
        yield from []

edges() -> Iterator[tuple[TreeNode, TreeNode]]

Generator for all edges of the tree.

Yields:

Type	Description
tuple[TreeNode, TreeNode]	All edges of the tree as tuples of TreeNode instances.

Source code in tralda/datastructures/tree.py

def edges(self) -> Iterator[tuple[TreeNode, TreeNode]]:
    """Generator for all edges of the tree.

    Yields:
        All edges of the tree as tuples of TreeNode instances.
    """

    def _edges(node: TreeNode) -> Iterator[tuple[TreeNode, TreeNode]]:
        for child in node.children:
            yield (node, child)
            yield from _edges(child)

    if self.root:
        yield from _edges(self.root)
    else:
        yield from []

edges_sibling_order() -> Iterator[tuple[TreeNode, TreeNode, int]]

Generator for all edges of the tree with sibling order.

Yields:

Type	Description
TreeNode	Edges uv as tuples (u, v, nr) where nr is the index of v in the list of children of
TreeNode	node u.

Source code in tralda/datastructures/tree.py

def edges_sibling_order(self) -> Iterator[tuple[TreeNode, TreeNode, int]]:
    """Generator for all edges of the tree with sibling order.

    Yields:
        Edges uv as tuples (u, v, nr) where nr is the index of v in the list of children of
        node u.
    """

    def _edges_sibling_order(node: TreeNode) -> Iterator[tuple[TreeNode, TreeNode, int]]:
        i = 0
        for child in node.children:
            yield (node, child, i)
            yield from _edges_sibling_order(child)
            i += 1

    if self.root:
        yield from _edges_sibling_order(self.root)
    else:
        yield from []

inner_edges() -> Iterator[tuple[TreeNode, TreeNode]]

Generator for all inner edges of the tree.

Yields:

Type	Description
tuple[TreeNode, TreeNode]	All inner edges uv of the tree, i.e., edges for which the child v of u is not a leaf.

Source code in tralda/datastructures/tree.py

def inner_edges(self) -> Iterator[tuple[TreeNode, TreeNode]]:
    """Generator for all inner edges of the tree.

    Yields:
        All inner edges uv of the tree, i.e., edges for which the child v of u is not a leaf.
    """

    def _inner_edges(node: TreeNode) -> Iterator[tuple[TreeNode, TreeNode]]:
        for child in node.children:
            if child.children:
                yield (node, child)
                yield from _inner_edges(child)

    if self.root:
        yield from _inner_edges(self.root)
    else:
        yield from []

euler_generator() -> Iterator[TreeNode]

Generator for an Euler tour of the tree.

Yields:

Type	Description
TreeNode	Nodes in an Euler tour of the tree.

Source code in tralda/datastructures/tree.py

def euler_generator(self) -> Iterator[TreeNode]:
    """Generator for an Euler tour of the tree.

    Yields:
        Nodes in an Euler tour of the tree.
    """

    def _euler_generator(node: TreeNode) -> Iterator[TreeNode]:
        yield node
        for child in node.children:
            yield from _euler_generator(child)
            yield node

    if self.root:
        yield from _euler_generator(self.root)
    else:
        yield from []

euler_and_level() -> Iterator[tuple[TreeNode, int]]

Generator for an Euler tour with node levels.

Yields:

Type	Description
tuple[TreeNode, int]	Nodes and their level (distance from the root) in an Euler tour of the tree.

Source code in tralda/datastructures/tree.py

def euler_and_level(self) -> Iterator[tuple[TreeNode, int]]:
    """Generator for an Euler tour with node levels.

    Yields:
        Nodes and their level (distance from the root) in an Euler tour of the tree.
    """

    def _euler_level(node: TreeNode, level: int) -> Iterator[tuple[TreeNode, int]]:
        yield (node, level)
        for child in node.children:
            yield from _euler_level(child, level + 1)
            yield (node, level)

    if self.root:
        yield from _euler_level(self.root, 0)
    else:
        yield from []

leaf_dict() -> dict[TreeNode, list[TreeNode]]

Leaves in the subtree rooted at each node.

Computes the list of leaves for every node in the tree containing the leaf nodes in the subtree rooted at the node.

Returns:

Type	Description
dict[TreeNode, list[TreeNode]]	The leaves under each vertex (as a dictionary with TreeNode keys and lists of TreeNode objects as values).

Source code in tralda/datastructures/tree.py

def leaf_dict(self) -> dict[TreeNode, list[TreeNode]]:
    """Leaves in the subtree rooted at each node.

    Computes the list of leaves for every node in the tree containing the leaf nodes in the
    subtree rooted at the node.

    Returns:
        The leaves under each vertex (as a dictionary with `TreeNode` keys and lists of
            `TreeNode` objects as values).
    """
    leaves = {}

    for v in self.postorder():
        if not v.children:
            leaves[v] = [v]
        else:
            leaves[v] = []
            for child in v.children:
                leaves[v].extend(leaves[child])

    return leaves

contract(edges: Iterable[tuple[TreeNode]], inplace: bool = True) -> Tree

Contract edges in the tree.

Parameters:

Name	Type	Description	Default
edges	Iterable[tuple[TreeNode]]	The edges to be contracted in the tree.	required
inplace	bool	If True, the edges are contracted in this tree instance, otherwise a copy is returned and the original tree is not affected.	True

Returns:

Type	Description
Tree	The original tree with contracted edges or a copy in which the contractions are performed.

Source code in tralda/datastructures/tree.py

def contract(self, edges: Iterable[tuple[TreeNode]], inplace: bool = True) -> Tree:
    """Contract edges in the tree.

    Args:
        edges: The edges to be contracted in the tree.
        inplace: If True, the edges are contracted in this tree instance, otherwise a copy is
            returned and the original tree is not affected.

    Returns:
        The original tree with contracted edges or a copy in which the contractions are
            performed.
    """
    contracted = set()

    if not inplace:
        T_copy, mapping = self.copy(mapping=True)

    for _, v in edges:
        # avoid trying to contract the same edge multiple times
        if v in contracted:
            continue

        if inplace:
            self.delete_and_reconnect(v)
        else:
            T_copy.delete_and_reconnect(mapping[v])

        contracted.add(v)

    return self if inplace else T_copy

get_triples(label_only: bool = False) -> list[tuple[Any, Any, Any]]

Retrieve a list of all (rooted) triples of the tree.

A tree displays a triple ab|c on the leaf nodes a, b and c if the last common ancestor of a and b is a (proper) descendant of the last common ancestor of a and c (b and c).

Parameters:

Name	Type	Description	Default
label_only	bool	If True, the triples are represented by the label attribute of the nodes.	False

Returns:

Type	Description
list[tuple[Any, Any, Any]]	List of tuples where each tuple (a, b, c) represents the triple ab|c (=ba|c), i.e., the first two items are closer related in the tree.

Source code in tralda/datastructures/tree.py

def get_triples(self, label_only: bool = False) -> list[tuple[Any, Any, Any]]:
    """Retrieve a list of all (rooted) triples of the tree.

    A tree displays a triple ab|c on the leaf nodes a, b and c if the last common ancestor of a
    and b is a (proper) descendant of the last common ancestor of a and c (b and c).

    Args:
        label_only: If True, the triples are represented by the label attribute of the nodes.

    Returns:
        List of tuples where each tuple (a, b, c) represents the triple ab|c (=ba|c), i.e., the
            first two items are closer related in the tree.
    """
    if label_only:
        return [(a.label, b.label, c.label) for a, b, c in self._triple_generator()]
    else:
        return [t for t in self._triple_generator()]

delete_and_reconnect(node: TreeNode) -> TreeNode | None

Delete a node from the tree and reconnect its parent and children.

The function preserves the 'sibling order' of the remaining nodes of the tree.

Parameters:

Name	Type	Description	Default
node	TreeNode	The node to be deleted.	required

Returns:

Type	Description
TreeNode | None	The parent of the node, if it could be deleted, or None, if the node could not be deleted, i.e., it has no parent.

Source code in tralda/datastructures/tree.py

def delete_and_reconnect(self, node: TreeNode) -> TreeNode | None:
    """Delete a node from the tree and reconnect its parent and children.

    The function preserves the 'sibling order' of the remaining nodes of the tree.

    Args:
        node: The node to be deleted.

    Returns:
        The parent of the node, if it could be deleted, or None, if the node could not be
            deleted, i.e., it has no parent.
    """
    parent = node.parent

    if not parent:
        return None
    else:
        # copy list of children to edit edges
        children = [child for child in node.children]

        for child in children:
            parent.add_child_right_of(child, node)

        parent.remove_child(node)
        node.children.clear()

    return parent

random_leaves(proportion: int | float) -> list[TreeNode]

A random sample of the leaves.

Parameters:

Name	Type	Description	Default
proportion	int | float	The proportion of the sample w.r.t. the full set of leaves.	required

Returns:

Type	Description
list[TreeNode]	A randomly samples list of the leaves of the tree.

Raises:

Type	Description
ValueError	If 'proportion' is not a number between 0 and 1.

Source code in tralda/datastructures/tree.py

def random_leaves(self, proportion: int | float) -> list[TreeNode]:
    """A random sample of the leaves.

    Args:
        proportion: The proportion of the sample w.r.t. the full set of leaves.

    Returns:
        A randomly samples list of the leaves of the tree.

    Raises:
        ValueError: If 'proportion' is not a number between 0 and 1.
    """
    if not isinstance(proportion, (float, int)) or proportion < 0 or proportion > 1:
        raise ValueError("proportion must be a number 0 <= p <= 1")

    leaves = [v for v in self.leaves()]
    k = round(proportion * len(leaves))

    return random.sample(leaves, k)

is_binary() -> bool

Check whether the tree is a binary tree.

Nodes in (rooted) binary trees are either leaves or have exactly two children.

Returns:

Type	Description
bool	True if the tree is binary, else False.

Source code in tralda/datastructures/tree.py

def is_binary(self) -> bool:
    """Check whether the tree is a binary tree.

    Nodes in (rooted) binary trees are either leaves or have exactly two children.

    Returns:
        True if the tree is binary, else False.
    """
    for v in self.preorder():
        if len(v.children) == 1 or len(v.children) > 2:
            return False

    return True

is_phylogenetic() -> bool

Check whether the tree is a phylogenetic tree.

Nodes in (rooted) phylogenetic trees are either leaves or have at least two children.

Returns:

Type	Description
bool	True if the tree is phylogenetic, else False.

Source code in tralda/datastructures/tree.py

def is_phylogenetic(self) -> bool:
    """Check whether the tree is a phylogenetic tree.

    Nodes in (rooted) phylogenetic trees are either leaves or have at least two children.

    Returns:
        True if the tree is phylogenetic, else False.
    """
    for v in self.preorder():
        if len(v.children) == 1:
            return False

    return True

get_hierarchy() -> set[tuple[Any]]

Hierarchy set on the leaf labels defined by the tree.

Every (phylogenetic) tree can be represented by a hierarchy on the set of its leaves. The label attributes of the leaf nodes must be set and unique for each leaf.

Returns:

Type	Description
set[tuple[Any]]	A set of tuples representing the hierarchy where the leaves are represented by their labels.

Source code in tralda/datastructures/tree.py

def get_hierarchy(self) -> set[tuple[Any]]:
    """Hierarchy set on the leaf labels defined by the tree.

    Every (phylogenetic) tree can be represented by a hierarchy on the set of its leaves. The
    label attributes of the leaf nodes must be set and unique for each leaf.

    Returns:
        A set of tuples representing the hierarchy where the leaves are represented by their
            labels.
    """
    leaves = self.leaf_dict()
    hierarchy = set()

    for v in self.preorder():
        hierarchy.add(tuple(sorted(leaf.label for leaf in leaves[v])))

    return hierarchy

equal_topology(other: Tree, verbose: bool = False) -> bool

Compare the tree topology based on the leaf labels.

Only works for phylogenetic trees with unique leaf labels.

Parameters:

Name	Type	Description	Default
other	Tree	Another tree which this tree shall be compared to.	required
verbose	bool	If True, print where the equality check failed (the first time).	False

Returns:

Type	Description
bool	True if the topologies are equal, else False.

Source code in tralda/datastructures/tree.py

def equal_topology(self, other: Tree, verbose: bool = False) -> bool:
    """Compare the tree topology based on the leaf labels.

    Only works for phylogenetic trees with unique leaf labels.

    Args:
        other: Another tree which this tree shall be compared to.
        verbose: If True, print where the equality check failed (the first time).

    Returns:
        True if the topologies are equal, else False.
    """
    hierarchy1 = sorted(self.get_hierarchy())
    hierarchy2 = sorted(other.get_hierarchy())

    if len(hierarchy1) != len(hierarchy2):
        if verbose:
            print(
                f"Unequal sizes of the hierarchy sets: {len(hierarchy1)} and {len(hierarchy2)}"
            )
        return False

    for i in range(len(hierarchy1)):
        if hierarchy1[i] != hierarchy2[i]:
            if verbose:
                print(f"Hierarchies not equal:\n{hierarchy1[i]}\n{hierarchy2[i]}")
            return False

    return True

is_refinement(other: Tree) -> bool

Checks whether the tree is a refinement of 'other' based on the leaf labels.

Only works for phylogenetic trees with unique leaf labels.

Parameters:

Name	Type	Description	Default
other	Tree	Another tree which this tree shall be compared to.	required

Returns:

Type	Description
bool	True if the tree is refinement of 'other', else False.

Source code in tralda/datastructures/tree.py

def is_refinement(self, other: Tree) -> bool:
    """Checks whether the tree is a refinement of 'other' based on the leaf labels.

    Only works for phylogenetic trees with unique leaf labels.

    Args:
        other: Another tree which this tree shall be compared to.

    Returns:
        True if the tree is refinement of 'other', else False.
    """
    hierarchy1 = sorted(self.get_hierarchy())
    hierarchy2 = sorted(other.get_hierarchy())

    if len(hierarchy1) < len(hierarchy2):
        return False

    i1, i2 = 0, 0
    while i2 < len(hierarchy2):
        if i1 >= len(hierarchy1):
            return False

        if hierarchy1[i1] == hierarchy2[i2]:
            i1 += 1
            i2 += 1
        else:
            i1 += 1

    return True

copy(mapping: bool = False) -> Tree | tuple[Tree, dict[TreeNode, TreeNode]]

Return a copy of the tree.

Constructs a copy of the tree to the level of nodes, i.e., the attributes are only copied as references. If the node attributes are all immutable data types, the original tree is not affected by operations on the copy.

Parameters:

Name	Type	Description	Default
mapping	bool	If True, additionally return the mapping from original to copied nodes as dictionary.	False

Returns:

Type	Description
Tree | tuple[Tree, dict[TreeNode, TreeNode]]	A copy of the tree and optionally the mapping from original to copied nodes.

Source code in tralda/datastructures/tree.py

def copy(self, mapping: bool = False) -> Tree | tuple[Tree, dict[TreeNode, TreeNode]]:
    """Return a copy of the tree.

    Constructs a copy of the tree to the level of nodes, i.e., the attributes are only copied as
    references. If the node attributes are all immutable data types, the original tree is not
    affected by operations on the copy.

    Args:
        mapping: If True, additionally return the mapping from original to copied nodes as
            dictionary.

    Returns:
        A copy of the tree and optionally the mapping from original to copied nodes.
    """
    if not self.root:
        return Tree(None)

    orig_to_new = {}

    for orig in self.preorder():
        new = TreeNode()
        orig_to_new[orig] = new
        if orig.parent:
            orig_to_new[orig.parent].add_child(new)

        # shallow copy of the node attributes
        for key, value in orig.attributes():
            setattr(new, key, value)

    if mapping:
        return Tree(orig_to_new[self.root]), orig_to_new
    else:
        return Tree(orig_to_new[self.root])

to_newick(node: TreeNode | None = None) -> str

Newick representation of the tree.

Parameters:

Name	Type	Description	Default
node	TreeNode | None	The node whose subtree shall be returned as a Newick string, the default is None, in which case the whole tree is returned in Newick format.	None

Returns:

Type	Description
str	A newick representation of the (sub)tree.

Source code in tralda/datastructures/tree.py

def to_newick(self, node: TreeNode | None = None) -> str:
    """Newick representation of the tree.

    Args:
        node: The node whose subtree shall be returned as a Newick string, the default is None,
            in which case the whole tree is returned in Newick format.

    Returns:
        A newick representation of the (sub)tree.
    """

    def _to_newick(node: TreeNode) -> str:
        node_str = str(node)

        # add colon and distance if available
        if hasattr(node, "dist"):
            node_str += f":{node.dist}"

        if not node.children:
            return node_str
        else:
            s = ""
            for child in node.children:
                s += _to_newick(child) + ","
            return f"({s[:-1]}){node_str}"

    if node:
        return _to_newick(node) + ";"
    elif self.root:
        return _to_newick(self.root) + ";"
    else:
        return ";"

parse_newick(newick: str) -> Tree classmethod

Parses trees in Newick format into Tree object.

If available (after colons in the Newick strings), the distance is stored in the 'dist' attribute of the nodes. Moreover, labels are converted to integers if possible.

NOTE: Do not use this function for serialization and reloading Tree objects. Use the 'serialize()' function instead.

Parameters:

Name	Type	Description	Default
newick	str	A tree in Newick format.	required

Returns:

Type	Description
Tree	The parsed tree.

Raises:

Type	Description
TypeError	If the input is not a string.
ValueError	If the input is not a valid Newick string.

Source code in tralda/datastructures/tree.py

@classmethod
def parse_newick(cls, newick: str) -> Tree:
    """Parses trees in Newick format into Tree object.

    If available (after colons in the Newick strings), the distance is stored in the 'dist'
    attribute of the nodes. Moreover, labels are converted to integers if possible.

    NOTE: Do not use this function for serialization and reloading Tree objects. Use the
    'serialize()' function instead.

    Args:
        newick: A tree in Newick format.

    Returns:
        The parsed tree.

    Raises:
        TypeError: If the input is not a string.
        ValueError: If the input is not a valid Newick string.
    """
    return cls(cls._parse_newick_and_return_root(newick))

to_nx() -> tuple[nx.DiGraph, int]

Convert a Tree into a NetworkX DiGraph.

The attributes correspond to the node attributes in the resulting graph. The nodes of the resulting graph correspond to the object ids of the TreeNode instances belonging to the tree.

Returns:

Type	Description
tuple[DiGraph, int]	A graph representation of the tree and the object id of the root (and thus the corresponding node in the graph) in order to be able to completely reconstruct the tree.

Source code in tralda/datastructures/tree.py

def to_nx(self) -> tuple[nx.DiGraph, int]:
    """Convert a Tree into a NetworkX DiGraph.

    The attributes correspond to the node attributes in the resulting graph. The nodes of the
    resulting graph correspond to the object ids of the TreeNode instances belonging to the
    tree.

    Returns:
        A graph representation of the tree and the object id of the root (and thus the
            corresponding node in the graph) in order to be able to completely reconstruct the
            tree.
    """
    self._assert_integrity()
    graph = nx.DiGraph()

    if not self.root:
        return graph, None

    for v in self.preorder():
        graph.add_node(id(v))
        for key, value in v.attributes():
            graph.nodes[id(v)][key] = value

    for u, v, sibling_nr in self.edges_sibling_order():
        if u is v:
            raise RuntimeError(f"loop at {u} and {v}")
        graph.add_edge(id(u), id(v))
        graph.nodes[id(v)]["sibling_nr"] = sibling_nr

    return graph, id(self.root)

parse_nx(graph: nx.DiGraph, root: int) -> Tree classmethod

Convert a NetworkX DiGraph version back into a Tree.

Parameters:

Name	Type	Description	Default
graph	DiGraph	A tree represented as a Networkx DiGraph.	required
root	int	The node in the graph corresponding to the root.	required

Returns:

Type	Description
Tree	The reconstructed tree.

Source code in tralda/datastructures/tree.py

@classmethod
def parse_nx(cls, graph: nx.DiGraph, root: int) -> Tree:
    """Convert a NetworkX DiGraph version back into a Tree.

    Args:
        graph: A tree represented as a Networkx DiGraph.
        root: The node in the graph corresponding to the root.

    Returns:
        The reconstructed tree.
    """
    number_of_leaves = 0

    if root is None:
        return cls(None)

    def _build_tree(graphnode, parent=None) -> TreeNode:
        nonlocal number_of_leaves

        treenode = TreeNode()

        if parent:
            parent.add_child(treenode)

        for key, value in graph.nodes[graphnode].items():
            setattr(treenode, key, value)

        children = sorted(
            graph.neighbors(graphnode), key=lambda item: graph.nodes[item]["sibling_nr"]
        )

        for c in children:
            _build_tree(c, parent=treenode)
        if graph.out_degree(graphnode) == 0:
            number_of_leaves += 1

        return treenode

    tree = cls(_build_tree(root))
    tree.number_of_species = number_of_leaves

    return tree

to_dict() -> dict[str, Any]

Convert the tree into a nested dictionary.

Returns:

Type	Description
dict[str, Any]	A dict representation of the tree,

Raises:

Type	Description
RuntimeError	If the tree is empty.

Source code in tralda/datastructures/tree.py

def to_dict(self) -> dict[str, Any]:
    """Convert the tree into a nested dictionary.

    Returns:
        A dict representation of the tree,

    Raises:
        RuntimeError: If the tree is empty.
    """

    def _to_dict(node: TreeNode) -> dict[str, Any]:
        node_dict = {k: v for k, v in node.attributes()}

        for i, child in enumerate(node.children):
            node_dict[f"_child{i}"] = _to_dict(child)

        return node_dict

    if self.root:
        return _to_dict(self.root)
    else:
        raise RuntimeError("cannot convert empty tree to dict")

parse_dict(tree_dict: dict[str, Any]) -> Tree classmethod

Convert a dictionary representation back into a Tree.

Parameters:

Name	Type	Description	Default
tree_dict	dict[str, Any]	A dictionary representation of the tree.	required

Returns:

Type	Description
Tree	The reconstructed tree.

Source code in tralda/datastructures/tree.py

@classmethod
def parse_dict(cls, tree_dict: dict[str, Any]) -> Tree:
    """Convert a dictionary representation back into a Tree.

    Args:
        tree_dict: A dictionary representation of the tree.

    Returns:
        The reconstructed tree.
    """

    def _parse_dict(node_dict: dict[str, Any]) -> TreeNode:
        """Recursive function for reconstructing the subtree represented by the dict.

        Args:
            node_dict: Dict representing a (sub)tree.

        Returns:
            The root node of reconstructed (sub)tree.
        """
        node = TreeNode()
        children = {}

        for k, v in node_dict.items():
            if k.startswith("_child"):
                children[int(k[6:])] = _parse_dict(v)
            else:
                setattr(node, k, v)

        for i in sorted(children):
            node.add_child(children[i])

        return node

    return cls(_parse_dict(tree_dict))

serialize(filename: str, mode: str = None) -> None

Serialize the tree using pickle or json.

Parameters:

Name	Type	Description	Default
filename	str	The filename (including the path) of the file to be created.	required
mode	str	The serialization mode. Supported are pickle and json. The default is None in which case the mode is inferred from the file extension.	None

Raises:

Type	Description
ValueError	If the serialization mode is unknown or could not be inferred.

Source code in tralda/datastructures/tree.py

def serialize(self, filename: str, mode: str = None) -> None:
    """Serialize the tree using pickle or json.

    Args:
        filename: The filename (including the path) of the file to be created.
        mode: The serialization mode. Supported are pickle and json. The default is None in
            which case the mode is inferred from the file extension.

    Raises:
        ValueError: If the serialization mode is unknown or could not be inferred.
    """
    if not mode:
        mode = Tree._infer_serialization_mode(filename)

    if mode == "json":
        with open(filename, "w") as f:
            json.dump(self.to_dict(), f)
    elif mode == "pickle":
        tree_nx, root_id = self.to_nx()
        with open(filename, "wb") as f:
            pickle.dump((tree_nx, root_id), f)
    else:
        raise ValueError(f"serialization mode '{mode}' not supported")

load(filename: str, mode: bool = None) -> Tree classmethod

Reload a Tree from a file (pickle or json).

Parameters:

Name	Type	Description	Default
filename	str	The filename (including the path) of the file to be loaded.	required
mode	bool	The serialization mode. Supported are pickle and json. The default is None in which case the mode is inferred from the file extension.	None

Returns:

Type	Description
Tree	The tree reloaded from file.

Raises:

Type	Description
ValueError	If the serialization mode is unknown or could not be inferred.

Source code in tralda/datastructures/tree.py

@classmethod
def load(cls, filename: str, mode: bool = None) -> Tree:
    """Reload a Tree from a file (pickle or json).

    Args:
        filename: The filename (including the path) of the file to be loaded.
        mode: The serialization mode. Supported are pickle and json. The default is None in
            which case the mode is inferred from the file extension.

    Returns:
        The tree reloaded from file.

    Raises:
        ValueError: If the serialization mode is unknown or could not be inferred.
    """
    if not mode:
        mode = Tree._infer_serialization_mode(filename)

    if mode == "json":
        with open(filename, "r") as f:
            tree_dict = json.load(f)
        return Tree.parse_dict(tree_dict)
    elif mode == "pickle":
        with open(filename, "rb") as f:
            return Tree.parse_nx(*pickle.load(f))
    else:
        raise ValueError(f"serialization mode '{mode}' not supported")

print_tree(child_indentation: int = 3) -> None

Print a representation of the tree to the console.

Parameters:

Name	Type	Description	Default
child_indentation	int	The indentation added per level of the nodes. Must be >= 1.	3

Source code in tralda/datastructures/tree.py

def print_tree(self, child_indentation: int = 3) -> None:
    """Print a representation of the tree to the console.

    Args:
        child_indentation: The indentation added per level of the nodes. Must be >= 1.
    """
    if not isinstance(child_indentation, int) or child_indentation < 1:
        raise ValueError("child indentation must be an integer >= 1")

    for line in self._lines_for_print_tree(child_indentation):
        print(line)

plot(*, backend: str = 'matplotlib', path: str | os.PathLike | None = None, show: bool = False, **kwargs: Any) -> Any

Render this tree; see :func:tralda.visualization.plot_tree for all parameters.

Requires the optional visualization dependencies, e.g. pip install tralda[matplotlib], tralda[plotly], or tralda[viz] for both backends.

Parameters:

Name	Type	Description	Default
backend	str	"matplotlib" (default) or "plotly".	'matplotlib'
path	str | PathLike | None	If given, save the resulting figure to this path.	None
show	bool	If True, display the figure after rendering.	False
**kwargs	Any	Additional keyword arguments forwarded to :func:~tralda.visualization.plot_tree (layout mode, tree style, etc.).	{}

Returns:

Type	Description
Any	(fig, ax) for the matplotlib backend, or a Plotly Figure for the plotly backend.

Source code in tralda/datastructures/tree.py

def plot(
    self,
    *,
    backend: str = "matplotlib",
    path: str | os.PathLike | None = None,
    show: bool = False,
    **kwargs: Any,
) -> Any:
    """Render this tree; see :func:`tralda.visualization.plot_tree` for all parameters.

    Requires the optional visualization dependencies, e.g. ``pip install tralda[matplotlib]``,
    ``tralda[plotly]``, or ``tralda[viz]`` for both backends.

    Args:
        backend: ``"matplotlib"`` (default) or ``"plotly"``.
        path: If given, save the resulting figure to this path.
        show: If ``True``, display the figure after rendering.
        **kwargs: Additional keyword arguments forwarded to
            :func:`~tralda.visualization.plot_tree` (layout mode, tree style, etc.).

    Returns:
        ``(fig, ax)`` for the matplotlib backend, or a Plotly ``Figure`` for the plotly backend.
    """
    from tralda.visualization import plot_tree

    return plot_tree(self, backend=backend, path=path, show=show, **kwargs)

random_tree(number_of_leaves: int, binary: bool = False) -> Tree classmethod

A simple function to generate a random tree.

The tree is generated by iteratively sampling a random node to which a new leaf is attached (or two leaves if the sampled node was a leaf). Each step increases the number of leaves by one. The procedure ends as soon as the desired number of leaves is reached. The resulting tree is always phylogenetic, i.e., each inner node has at least two children.

Parameters:

Name	Type	Description	Default
number_of_leaves	int	The desired number of leaves.	required
binary	bool	If True, the resulting tree is binary, otherwise it may contain multifurcations.	False

Returns:

Type	Description
Tree	A randomly generated tree with the specified number of leaves.

Raises:

Type	Description
TypeError	If number_of_leaves is not an integer >= 1.

Source code in tralda/datastructures/tree.py

@classmethod
def random_tree(cls, number_of_leaves: int, binary: bool = False) -> Tree:
    """A simple function to generate a random tree.

    The tree is generated by iteratively sampling a random node to which a new leaf is attached
    (or two leaves if the sampled node was a leaf). Each step increases the number of leaves by
    one. The procedure ends as soon as the desired number of leaves is reached.
    The resulting tree is always phylogenetic, i.e., each inner node has at least two children.

    Args:
        number_of_leaves: The desired number of leaves.
        binary: If True, the resulting tree is binary, otherwise it may contain multifurcations.

    Returns:
        A randomly generated tree with the specified number of leaves.

    Raises:
        TypeError: If `number_of_leaves` is not an integer >= 1.
    """
    if not (isinstance(number_of_leaves, int)) or number_of_leaves < 1:
        raise TypeError("`number_of_leaves` must be an `int` > 0")

    root = TreeNode(label=0)
    tree = cls(root)
    node_list = [root]
    nr, leaf_count = 1, 1

    while leaf_count < number_of_leaves:
        node = random.choice(node_list)

        if not node.children:
            # to be phylogenetic at least two children must be added
            new_child1 = TreeNode(label=nr)
            new_child2 = TreeNode(label=nr + 1)
            node.add_child(new_child1)
            node.add_child(new_child2)
            node_list.extend(node.children)
            nr += 2
            leaf_count += 1
        elif node.children and not binary:
            # add only one child if there are already children
            new_child = TreeNode(label=nr)
            node.add_child(new_child)
            node_list.append(new_child)
            nr += 1
            leaf_count += 1

    return tree

LCA

Compute last common ancestors in a tree efficiently.

Uses a reduction to a +/-1 Range minimum query (RMQ) problem and a sparse table implementation. - Preprocessing complexity: O(n) where n is the number of nodes in the tree - Query complexity: O(1)

References

1. M. A. Bender, M. Farach-Colton, G. Pemmasani, S. Skiena, P. Sumazin. Lowest common ancestors in trees and directed acyclic graphs. In: Journal of Algorithms. 57, Nr. 2, November 2005, S. 75-94. DOI: 10.1016/j.jalgor.2005.08.001
2. https://cp-algorithms.com/data_structures/sparse-table.html
3. https://cp-algorithms.com/graph/lca_farachcoltonbender.html

Source code in tralda/datastructures/last_common_ancestor.py

class LCA:
    """Compute last common ancestors in a tree efficiently.

    Uses a reduction to a +/-1 Range minimum query (RMQ) problem and a sparse table implementation.
    - Preprocessing complexity: O(n) where n is the number of nodes in the tree
    - Query complexity: O(1)

    References:
        1. M. A. Bender, M. Farach-Colton, G. Pemmasani, S. Skiena, P. Sumazin. Lowest common
           ancestors in trees and directed acyclic graphs. In: Journal of Algorithms. 57, Nr. 2,
           November 2005, S. 75-94. DOI: 10.1016/j.jalgor.2005.08.001
        2. https://cp-algorithms.com/data_structures/sparse-table.html
        3. https://cp-algorithms.com/graph/lca_farachcoltonbender.html
    """

    def __init__(self, tree: Tree, strict_labels: bool = True) -> None:
        """Constructor for class LCA.

        Args:
            tree: The Tree instance for which this instance will allow efficient last common
                ancestor queries.
            strict_labels: If True (default), raise a ``ValueError`` when two nodes share the
                same label, since label-based queries would be ambiguous.  Set to False to
                silently keep only the first occurrence in the label map; in that case
                label-based queries may return unexpected results for duplicate labels, so
                callers should use ``TreeNode`` objects directly.

        Raises:
            TypeError: If `tree` is not a Tree instance.
            ValueError: If `tree` is empty or if `strict_labels` is True and duplicate labels are
                found.
        """
        if not isinstance(tree, Tree):
            raise TypeError("`tree` must be of type `Tree`")
        if tree.root is None:
            raise ValueError("`tree` must be non-empty")

        self._tree = tree

        self._V = [v for v in self._tree.preorder()]
        self._index = {v: i for i, v in enumerate(self._V)}

        # store labels for queries via label; duplicate labels are an error
        self._label_dict: dict = {}
        for v in self._V:
            if not hasattr(v, "label"):
                continue

            if v.label in self._label_dict:
                if strict_labels:
                    raise ValueError(
                        f"Duplicate node label {v.label!r}: label-based queries require "
                        "unique labels"
                    )
                # else: keep the first occurrence; label-based queries are unreliable
            else:
                self._label_dict[v.label] = v

        self._euler_tour = []
        # levels of the vertices in the Euler tour
        self._L = []
        # repres. of vertices in the Euler tour (index of first occurrence)
        self._R = [None for _ in range(len(self._V))]

        for j, (v, level) in enumerate(self._tree.euler_and_level()):
            i = self._index[v]
            self._euler_tour.append(i)
            self._L.append(level)
            if self._R[i] is None:
                self._R[i] = j

        # build sparse table for range minimum query (RMQ)

        # initialize array and lookup dictionaries
        n = len(self._L)
        self._log_2 = self._precompute_logs(n)
        self._block_size = max(1, self._log_2[n] // 2)
        self._block_count = (n + self._block_size - 1) // self._block_size
        self._A = [0 for _ in range(self._block_count)]
        self._B = [0 for _ in range(self._block_count)]
        self._block_identifier = [0 for _ in range(self._block_count)]
        self._blocks: dict[int, list[int]] = {}
        self._block_st: dict[int, list[list[int]]] = {}

        # O(n) preprocessing
        self._A_st = self._linear_preprocessing()

    def __call__(self, a: NodeType, b: NodeType) -> TreeNode:
        """Last common ancestor of two nodes.

        Args:
            a: A node or its label in the tree corresponding to this LCA instance.
            b: A node or its label in the tree corresponding to this LCA instance.

        Returns:
            The last common ancestor of a and b.
        """
        return self._get_lca(self._label_to_treenode(a), self._label_to_treenode(b))

    def get(self, a: NodeType, b: NodeType) -> TreeNode:
        """Last common ancestor of two nodes.

        Args:
            a: A node or its label in the tree corresponding to this LCA instance.
            b: A node or its label in the tree corresponding to this LCA instance.

        Returns:
            The last common ancestor of a and b.
        """
        return self._get_lca(self._label_to_treenode(a), self._label_to_treenode(b))

    def displays_triple(self, a: NodeType, b: NodeType, c: NodeType) -> bool:
        """Return whether the tree displays the rooted triple ab|c (= ba|c).

        Args:
            a: A node or its label in the tree corresponding to this LCA instance.
            b: A node or its label in the tree corresponding to this LCA instance.
            c: A node or its label in the tree corresponding to this LCA instance.

        Returns:
            True if the tree displays the triple ab|c (= ba|c); False otherwise.
        """
        try:
            return self._has_triple(
                self._label_to_treenode(a), self._label_to_treenode(b), self._label_to_treenode(c)
            )
        except KeyError:
            return False

    def are_comparable(self, u: NodeOrEdge, v: NodeOrEdge) -> bool:
        """Returns True if two nodes/edges are comparable in the tree.

        Two nodes/edges are comparable if one lies on the unique path from the other to the root of
        the tree.

        Args:
            u: A node or edge in the tree corresponding to this LCA instance.
            v: A node or edge in the tree corresponding to this LCA instance.

        Returns:
            True if u and v are comparable in the tree, else False.
        """
        return self._are_comparable(self._label_to_treenode(u), self._label_to_treenode(v))

    def ancestor_or_equal(self, u: NodeOrEdge, v: NodeOrEdge) -> bool:
        """Return True if u is equal to or an ancestor of v.

        Args:
            u: A node or edge in the tree corresponding to this LCA instance.
            v: A node or edge in the tree corresponding to this LCA instance.

        Returns:
            True if u is equal or an ancestor of v, else False.
        """
        return self._ancestor_or_equal(self._label_to_treenode(u), self._label_to_treenode(v))

    def ancestor_not_equal(self, u: NodeOrEdge, v: NodeOrEdge) -> bool:
        """Return True if u is a strict ancestor of v.

        Args:
            u: A node or edge in the tree corresponding to this LCA instance.
            v: A node or edge in the tree corresponding to this LCA instance.

        Returns:
            True if u is a strict ancestor of v, else False.
        """
        u = self._label_to_treenode(u)
        v = self._label_to_treenode(v)

        return u != v and self._ancestor_or_equal(u, v)

    def descendant_or_equal(self, u: NodeOrEdge, v: NodeOrEdge) -> bool:
        """Return True if u is equal to or a descendant of v.

        Args:
            u: A node or edge in the tree corresponding to this LCA instance.
            v: A node or edge in the tree corresponding to this LCA instance.

        Returns:
            True if u is equal or a descendant of v, else False.
        """
        return self.ancestor_or_equal(v, u)

    def descendant_not_equal(self, u: NodeOrEdge, v: NodeOrEdge) -> bool:
        """Return True if u is a strict descendant of v.

        Args:
            u: A node or edge in the tree corresponding to this LCA instance.
            v: A node or edge in the tree corresponding to this LCA instance.

        Returns:
            True if u is a strict descendant of v, else False.
        """
        return self.ancestor_not_equal(v, u)

    def consistent_triples(self, triples: Iterable[Triple]) -> list[Triple]:
        """List with the subset of triples that are displayed by the tree.

        Args:
            triples: An iterable of triples of which each may or may not be displayed by the tree.

        Returns:
            A list containing the subset of the input list that are displayed by the tree.
        """
        return [t for t in triples if self.displays_triple(*t)]

    def consistent_triple_generator(self, triples: Iterable[Triple]) -> Iterator[Triple]:
        """Generator for the items in 'triples' that are displayed.

        Args:
            triples: An iterable of triples of which each may or may not be displayed by the tree.

        Yields:
            The triples in the input list that is displayed by the tree.
        """
        for t in triples:
            if self.displays_triple(*t):
                yield t

    def _precompute_logs(self, x: int) -> list[int]:
        """Efficiently pre-compute the floor(log2(x)) values.

        Args:
            x: The highest integer for which to pre-compute floor(log2(x)).

        Returns:
            A list of computed floor(log2(x)) values.
        """
        log_2 = [0 for _ in range(x + 1)]
        log_2[0] = -1
        for i in range(1, x + 1):
            log_2[i] = int(log_2[i // 2]) + 1

        return log_2

    def _linear_preprocessing(self) -> list[list[int]]:
        """Run the O(n) preprocessing.

        Returns:
            The range minimum query (RQM) sparse table.
        """
        n = len(self._L)

        for b in range(self._block_count):
            i = self._block_size * b
            j = 0
            block = [0 for _ in range(self._block_size)]

            current_min = self._L[i]
            self._A[b] = current_min
            self._B[b] = i

            for j in range(1, self._block_size):
                i += 1
                if i < n and self._L[i] < current_min:
                    current_min = self._L[i]
                    self._A[b] = current_min
                    self._B[b] = i
                if i >= n or self._L[i - 1] < self._L[i]:
                    block[j] = block[j - 1] + 1
                    self._block_identifier[b] += 1 << (j - 1)
                else:
                    block[j] = block[j - 1] - 1

            # precompute the corresponding RMQ sparse table if new block type is encountered
            b_id = self._block_identifier[b]
            if b_id not in self._blocks:
                self._blocks[b_id] = block
                self._block_st[b_id] = self._rmq_sparse_table(block)

        # precompute the RMQ sparse table for array A
        return self._rmq_sparse_table(self._A)

    def _rmq_sparse_table(self, A: list[int]) -> list[list[int]]:
        """Compute the RMQ sparse table for an array A.

        Args:
            A: The array for which to compute the RMQ sparse table.

        Returns:
            The RMQ sparse table for array A.
        """
        n = len(A)

        k = self._log_2[n]

        # sparse table for look up
        st = [[0 for _ in range(k + 1)] for _ in range(n)]

        # initialize the intervals with length 1
        for i in range(n):
            st[i][0] = i

        # dynamic programming: compute values from smaller to bigger intervals
        for j in range(1, k + 1):
            # compute minimum value for all intervals with size 2^j
            for i in range(n - (1 << j) + 1):
                if A[st[i][j - 1]] < A[st[i + (1 << (j - 1))][j - 1]]:
                    st[i][j] = st[i][j - 1]
                else:
                    st[i][j] = st[i + (1 << (j - 1))][j - 1]

        return st

    def _sparse_table_query(self, L: list[int], st: list[list[int]], i: int, j: int) -> int:
        """Sparse table query."""
        k = self._log_2[j - i + 1]
        if L[st[i][k]] < L[st[j - (1 << k) + 1][k]]:
            return st[i][k]
        else:
            return st[j - (1 << k) + 1][k]

    def _block_query(self, b: int, left: int, right: int) -> int:
        """Block query."""
        b_id = self._block_identifier[b]
        return (
            self._sparse_table_query(self._blocks[b_id], self._block_st[b_id], left, right)
            + b * self._block_size
        )

    def _rmq_query(self, i: int, j: int) -> int:
        """RQM query."""
        b_i = i // self._block_size
        b_j = j // self._block_size

        if b_i == b_j:
            return self._block_query(b_i, i % self._block_size, j % self._block_size)

        pos1 = self._block_query(b_i, i % self._block_size, self._block_size - 1)
        pos2 = self._block_query(b_j, 0, j % self._block_size)
        pos = pos1 if self._L[pos1] < self._L[pos2] else pos2

        if b_i + 1 < b_j:
            b = self._sparse_table_query(self._A, self._A_st, b_i + 1, b_j - 1)
            pos3 = self._B[b]
            pos = pos if self._L[pos] < self._L[pos3] else pos3

        return pos

    def _label_to_treenode(self, v: NodeOrEdge) -> TreeNode | tuple[TreeNode, TreeNode]:
        """Map labels of a node or edge to the corresponding TreeNode instance(s).

        Args:
            v: A node or edge represented by the TreeNode instances themselves or the node labels.

        Returns:
            The corresponding TreeNode instance or, in case of an edge, tuple of TreeNode instances.
        """
        if isinstance(v, TreeNode):
            return v
        elif isinstance(v, (tuple, list)) and len(v) == 2:
            return (self._label_to_treenode(v[0]), self._label_to_treenode(v[1]))
        else:
            return self._label_dict[v]

    def _get_lca(self, v1: TreeNode, v2: TreeNode) -> TreeNode:
        """Get the last common ancestor of two tree nodes in the tree.

        Args:
            v1: A node in the tree corresponding to this LCA instance.
            v2: A node in the tree corresponding to this LCA instance.

        Returns:
            The last common ancestor of v1 and v2.
        """
        if v1 is v2:
            return v1

        r1 = self._R[self._index[v1]]
        r2 = self._R[self._index[v2]]
        if r1 > r2:
            r1, r2 = r2, r1

        return self._V[self._euler_tour[self._rmq_query(r1, r2)]]

    def _has_triple(self, a: TreeNode, b: TreeNode, c: TreeNode) -> bool:
        """Return whether the tree displays the rooted triple ab|c (= ba|c).

        Args:
            a: A node in the tree corresponding to this LCA instance.
            b: A node in the tree corresponding to this LCA instance.
            c: A node in the tree corresponding to this LCA instance.

        Returns:
            True if the tree displays the triple ab|c (= ba|c); False otherwise.
        """
        if a is b:
            return False
        lca_ab = self._get_lca(a, b)

        return lca_ab is not self._get_lca(lca_ab, c)

    def _are_comparable(
        self,
        u: TreeNode | tuple[TreeNode, TreeNode],
        v: TreeNode | tuple[TreeNode, TreeNode],
    ) -> bool:
        """Returns True if two nodes/edges are comparable in the tree.

        Two nodes/edges are comparable if one lies on the unique path from the other to the root of
        the tree.

        Args:
            u: A node or edge in the tree corresponding to this LCA instance.
            v: A node or edge in the tree corresponding to this LCA instance.

        Returns:
            True if u and v are comparable in the tree, else False.
        """
        return self._ancestor_or_equal(u, v) or self._ancestor_or_equal(v, u)

    def _ancestor_or_equal(
        self,
        u: TreeNode | tuple[TreeNode, TreeNode],
        v: TreeNode | tuple[TreeNode, TreeNode],
    ) -> bool:
        """Return True if u is equal to or an ancestor of v.

        Args:
            u: A node or edge in the tree corresponding to this LCA instance.
            v: A node or edge in the tree corresponding to this LCA instance.

        Returns:
            True if u is equal or an ancestor of v, else False.
        """
        # both are nodes
        if isinstance(u, TreeNode) and isinstance(v, TreeNode):
            return u is self._get_lca(u, v)

        # u node, v edge
        elif isinstance(u, TreeNode) and isinstance(v, tuple):
            return u is self._get_lca(u, v[0])

        # u edge, v node
        elif isinstance(u, tuple) and isinstance(v, TreeNode):
            return u[1] is self._get_lca(u[1], v)

        # both are edges
        elif isinstance(u, tuple) and isinstance(v, tuple):
            return u[1] is v[1] or u[1] is self._get_lca(u[1], v[0])

__init__(tree: Tree, strict_labels: bool = True) -> None

Constructor for class LCA.

Parameters:

Name	Type	Description	Default
tree	Tree	The Tree instance for which this instance will allow efficient last common ancestor queries.	required
strict_labels	bool	If True (default), raise a ValueError when two nodes share the same label, since label-based queries would be ambiguous. Set to False to silently keep only the first occurrence in the label map; in that case label-based queries may return unexpected results for duplicate labels, so callers should use TreeNode objects directly.	True

Raises:

Type	Description
TypeError	If tree is not a Tree instance.
ValueError	If tree is empty or if strict_labels is True and duplicate labels are found.

Source code in tralda/datastructures/last_common_ancestor.py

def __init__(self, tree: Tree, strict_labels: bool = True) -> None:
    """Constructor for class LCA.

    Args:
        tree: The Tree instance for which this instance will allow efficient last common
            ancestor queries.
        strict_labels: If True (default), raise a ``ValueError`` when two nodes share the
            same label, since label-based queries would be ambiguous.  Set to False to
            silently keep only the first occurrence in the label map; in that case
            label-based queries may return unexpected results for duplicate labels, so
            callers should use ``TreeNode`` objects directly.

    Raises:
        TypeError: If `tree` is not a Tree instance.
        ValueError: If `tree` is empty or if `strict_labels` is True and duplicate labels are
            found.
    """
    if not isinstance(tree, Tree):
        raise TypeError("`tree` must be of type `Tree`")
    if tree.root is None:
        raise ValueError("`tree` must be non-empty")

    self._tree = tree

    self._V = [v for v in self._tree.preorder()]
    self._index = {v: i for i, v in enumerate(self._V)}

    # store labels for queries via label; duplicate labels are an error
    self._label_dict: dict = {}
    for v in self._V:
        if not hasattr(v, "label"):
            continue

        if v.label in self._label_dict:
            if strict_labels:
                raise ValueError(
                    f"Duplicate node label {v.label!r}: label-based queries require "
                    "unique labels"
                )
            # else: keep the first occurrence; label-based queries are unreliable
        else:
            self._label_dict[v.label] = v

    self._euler_tour = []
    # levels of the vertices in the Euler tour
    self._L = []
    # repres. of vertices in the Euler tour (index of first occurrence)
    self._R = [None for _ in range(len(self._V))]

    for j, (v, level) in enumerate(self._tree.euler_and_level()):
        i = self._index[v]
        self._euler_tour.append(i)
        self._L.append(level)
        if self._R[i] is None:
            self._R[i] = j

    # build sparse table for range minimum query (RMQ)

    # initialize array and lookup dictionaries
    n = len(self._L)
    self._log_2 = self._precompute_logs(n)
    self._block_size = max(1, self._log_2[n] // 2)
    self._block_count = (n + self._block_size - 1) // self._block_size
    self._A = [0 for _ in range(self._block_count)]
    self._B = [0 for _ in range(self._block_count)]
    self._block_identifier = [0 for _ in range(self._block_count)]
    self._blocks: dict[int, list[int]] = {}
    self._block_st: dict[int, list[list[int]]] = {}

    # O(n) preprocessing
    self._A_st = self._linear_preprocessing()

__call__(a: NodeType, b: NodeType) -> TreeNode

Last common ancestor of two nodes.

Parameters:

Name	Type	Description	Default
a	NodeType	A node or its label in the tree corresponding to this LCA instance.	required
b	NodeType	A node or its label in the tree corresponding to this LCA instance.	required

Returns:

Type	Description
TreeNode	The last common ancestor of a and b.

Source code in tralda/datastructures/last_common_ancestor.py

def __call__(self, a: NodeType, b: NodeType) -> TreeNode:
    """Last common ancestor of two nodes.

    Args:
        a: A node or its label in the tree corresponding to this LCA instance.
        b: A node or its label in the tree corresponding to this LCA instance.

    Returns:
        The last common ancestor of a and b.
    """
    return self._get_lca(self._label_to_treenode(a), self._label_to_treenode(b))

get(a: NodeType, b: NodeType) -> TreeNode

Last common ancestor of two nodes.

Parameters:

Name	Type	Description	Default
a	NodeType	A node or its label in the tree corresponding to this LCA instance.	required
b	NodeType	A node or its label in the tree corresponding to this LCA instance.	required

Returns:

Type	Description
TreeNode	The last common ancestor of a and b.

Source code in tralda/datastructures/last_common_ancestor.py

def get(self, a: NodeType, b: NodeType) -> TreeNode:
    """Last common ancestor of two nodes.

    Args:
        a: A node or its label in the tree corresponding to this LCA instance.
        b: A node or its label in the tree corresponding to this LCA instance.

    Returns:
        The last common ancestor of a and b.
    """
    return self._get_lca(self._label_to_treenode(a), self._label_to_treenode(b))

displays_triple(a: NodeType, b: NodeType, c: NodeType) -> bool

Return whether the tree displays the rooted triple ab|c (= ba|c).

Parameters:

Name	Type	Description	Default
a	NodeType	A node or its label in the tree corresponding to this LCA instance.	required
b	NodeType	A node or its label in the tree corresponding to this LCA instance.	required
c	NodeType	A node or its label in the tree corresponding to this LCA instance.	required

Returns:

Type	Description
bool	True if the tree displays the triple ab|c (= ba|c); False otherwise.

Source code in tralda/datastructures/last_common_ancestor.py

def displays_triple(self, a: NodeType, b: NodeType, c: NodeType) -> bool:
    """Return whether the tree displays the rooted triple ab|c (= ba|c).

    Args:
        a: A node or its label in the tree corresponding to this LCA instance.
        b: A node or its label in the tree corresponding to this LCA instance.
        c: A node or its label in the tree corresponding to this LCA instance.

    Returns:
        True if the tree displays the triple ab|c (= ba|c); False otherwise.
    """
    try:
        return self._has_triple(
            self._label_to_treenode(a), self._label_to_treenode(b), self._label_to_treenode(c)
        )
    except KeyError:
        return False

are_comparable(u: NodeOrEdge, v: NodeOrEdge) -> bool

Returns True if two nodes/edges are comparable in the tree.

Two nodes/edges are comparable if one lies on the unique path from the other to the root of the tree.

Parameters:

Name	Type	Description	Default
u	NodeOrEdge	A node or edge in the tree corresponding to this LCA instance.	required
v	NodeOrEdge	A node or edge in the tree corresponding to this LCA instance.	required

Returns:

Type	Description
bool	True if u and v are comparable in the tree, else False.

Source code in tralda/datastructures/last_common_ancestor.py

def are_comparable(self, u: NodeOrEdge, v: NodeOrEdge) -> bool:
    """Returns True if two nodes/edges are comparable in the tree.

    Two nodes/edges are comparable if one lies on the unique path from the other to the root of
    the tree.

    Args:
        u: A node or edge in the tree corresponding to this LCA instance.
        v: A node or edge in the tree corresponding to this LCA instance.

    Returns:
        True if u and v are comparable in the tree, else False.
    """
    return self._are_comparable(self._label_to_treenode(u), self._label_to_treenode(v))

ancestor_or_equal(u: NodeOrEdge, v: NodeOrEdge) -> bool

Return True if u is equal to or an ancestor of v.

Parameters:

Name	Type	Description	Default
u	NodeOrEdge	A node or edge in the tree corresponding to this LCA instance.	required
v	NodeOrEdge	A node or edge in the tree corresponding to this LCA instance.	required

Returns:

Type	Description
bool	True if u is equal or an ancestor of v, else False.

Source code in tralda/datastructures/last_common_ancestor.py

def ancestor_or_equal(self, u: NodeOrEdge, v: NodeOrEdge) -> bool:
    """Return True if u is equal to or an ancestor of v.

    Args:
        u: A node or edge in the tree corresponding to this LCA instance.
        v: A node or edge in the tree corresponding to this LCA instance.

    Returns:
        True if u is equal or an ancestor of v, else False.
    """
    return self._ancestor_or_equal(self._label_to_treenode(u), self._label_to_treenode(v))

ancestor_not_equal(u: NodeOrEdge, v: NodeOrEdge) -> bool

Return True if u is a strict ancestor of v.

Parameters:

Name	Type	Description	Default
u	NodeOrEdge	A node or edge in the tree corresponding to this LCA instance.	required
v	NodeOrEdge	A node or edge in the tree corresponding to this LCA instance.	required

Returns:

Type	Description
bool	True if u is a strict ancestor of v, else False.

Source code in tralda/datastructures/last_common_ancestor.py

def ancestor_not_equal(self, u: NodeOrEdge, v: NodeOrEdge) -> bool:
    """Return True if u is a strict ancestor of v.

    Args:
        u: A node or edge in the tree corresponding to this LCA instance.
        v: A node or edge in the tree corresponding to this LCA instance.

    Returns:
        True if u is a strict ancestor of v, else False.
    """
    u = self._label_to_treenode(u)
    v = self._label_to_treenode(v)

    return u != v and self._ancestor_or_equal(u, v)

descendant_or_equal(u: NodeOrEdge, v: NodeOrEdge) -> bool

Return True if u is equal to or a descendant of v.

Parameters:

Name	Type	Description	Default
u	NodeOrEdge	A node or edge in the tree corresponding to this LCA instance.	required
v	NodeOrEdge	A node or edge in the tree corresponding to this LCA instance.	required

Returns:

Type	Description
bool	True if u is equal or a descendant of v, else False.

Source code in tralda/datastructures/last_common_ancestor.py

def descendant_or_equal(self, u: NodeOrEdge, v: NodeOrEdge) -> bool:
    """Return True if u is equal to or a descendant of v.

    Args:
        u: A node or edge in the tree corresponding to this LCA instance.
        v: A node or edge in the tree corresponding to this LCA instance.

    Returns:
        True if u is equal or a descendant of v, else False.
    """
    return self.ancestor_or_equal(v, u)

descendant_not_equal(u: NodeOrEdge, v: NodeOrEdge) -> bool

Return True if u is a strict descendant of v.

Parameters:

Name	Type	Description	Default
u	NodeOrEdge	A node or edge in the tree corresponding to this LCA instance.	required
v	NodeOrEdge	A node or edge in the tree corresponding to this LCA instance.	required

Returns:

Type	Description
bool	True if u is a strict descendant of v, else False.

Source code in tralda/datastructures/last_common_ancestor.py

def descendant_not_equal(self, u: NodeOrEdge, v: NodeOrEdge) -> bool:
    """Return True if u is a strict descendant of v.

    Args:
        u: A node or edge in the tree corresponding to this LCA instance.
        v: A node or edge in the tree corresponding to this LCA instance.

    Returns:
        True if u is a strict descendant of v, else False.
    """
    return self.ancestor_not_equal(v, u)

consistent_triples(triples: Iterable[Triple]) -> list[Triple]

List with the subset of triples that are displayed by the tree.

Parameters:

Name	Type	Description	Default
triples	Iterable[Triple]	An iterable of triples of which each may or may not be displayed by the tree.	required

Returns:

Type	Description
list[Triple]	A list containing the subset of the input list that are displayed by the tree.

Source code in tralda/datastructures/last_common_ancestor.py

def consistent_triples(self, triples: Iterable[Triple]) -> list[Triple]:
    """List with the subset of triples that are displayed by the tree.

    Args:
        triples: An iterable of triples of which each may or may not be displayed by the tree.

    Returns:
        A list containing the subset of the input list that are displayed by the tree.
    """
    return [t for t in triples if self.displays_triple(*t)]

consistent_triple_generator(triples: Iterable[Triple]) -> Iterator[Triple]

Generator for the items in 'triples' that are displayed.

Parameters:

Name	Type	Description	Default
triples	Iterable[Triple]	An iterable of triples of which each may or may not be displayed by the tree.	required

Yields:

Type	Description
Triple	The triples in the input list that is displayed by the tree.

Source code in tralda/datastructures/last_common_ancestor.py

def consistent_triple_generator(self, triples: Iterable[Triple]) -> Iterator[Triple]:
    """Generator for the items in 'triples' that are displayed.

    Args:
        triples: An iterable of triples of which each may or may not be displayed by the tree.

    Yields:
        The triples in the input list that is displayed by the tree.
    """
    for t in triples:
        if self.displays_triple(*t):
            yield t