Supertrees

BUILD Algorithm

build_supertree(trees: Iterable[Tree]) -> Tree | None

Supertree construction based on the BUILD algorithm.

Parameters:

Name	Type	Description	Default
trees	Iterable[Tree]	An iterable of Tree instances.	required

Returns:

Type	Description
Tree | None	A supertree for the input trees if existent, None otherwise.

Source code in tralda/supertree/build.py

def build_supertree(trees: Iterable[Tree]) -> Tree | None:
    """Supertree construction based on the BUILD algorithm.

    Args:
        trees: An iterable of Tree instances.

    Returns:
        A supertree for the input trees if existent, None otherwise.
    """
    leaves, triples = tree_profile_to_triples(trees)

    build = Build(triples, leaves, mincut=False)

    return build.build_tree()

tree_profile_to_triples(trees: Iterable[Tree]) -> tuple[set[Any], set[Triple]]

Construct leaf set and representative triples from a profile of trees.

Parameters:

Name	Type	Description	Default
trees	Iterable[Tree]	An iterable of Tree instances.	required

Returns The first set contains all leaf labels that appear in the tree profilea, and the second set contains a representative set of triples.

Source code in tralda/supertree/build.py

def tree_profile_to_triples(trees: Iterable[Tree]) -> tuple[set[Any], set[Triple]]:
    """Construct leaf set and representative triples from a profile of trees.

    Args:
        trees: An iterable of Tree instances.

    Returns
        The first set contains all leaf labels that appear in the tree profilea, and the second set
        contains a representative set of triples.
    """
    leaves = set()
    triples = set()

    for tree in trees:
        leaves.update(leaf.label for leaf in tree.leaves())
        triples.update((*sorted(t[:2]), t[2]) for t in minimal_identifying_triple_set(tree))

    return leaves, triples

Build

BUILD algorithm.

References

1. A. V. Aho, Y. Sagiv, T. G. Szymanski, and J. D. Ullman. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM Journal on Computing, 10:405-421, 1981. DOI: 10.1137/0210030.

Source code in tralda/supertree/build.py

class Build:
    """BUILD algorithm.

    References:
        1. A. V. Aho, Y. Sagiv, T. G. Szymanski, and J. D. Ullman. Inferring a tree from lowest
           common ancestors with an application to the optimization of relational expressions.
           SIAM Journal on Computing, 10:405-421, 1981. DOI: 10.1137/0210030.
    """

    def __init__(
        self,
        R: Iterable[Triple],
        L: Collection[Any],
        mincut: bool = False,
        weighted_mincut: bool = False,
        triple_weights: dict[Triple, int | float] | None = None,
    ):
        """Constructor for class implementing the BUILD algorithm.

        Args:
            R: An iterable of triples.
            L: A collection of leaf labels.
            mincut: If True, use MinCut to resolve triple inconsistencies. Otherwise, no tree is
                returned in case of such inconsistencies.
            weighted_mincut: If True, weight the edges in the resulting graph accordingto the number
                of corresponding triples (and their weights).
            triple_weights: Dictionary with tuples as keys and float values. The weights of the
                triples. The default is None, in which case every triple has weight one.
        """
        self.R = R
        self.L = L
        self.mincut = mincut
        self.weighted_mincut = weighted_mincut
        self.triple_weights = triple_weights

    def build_tree(
        self,
        return_root: bool = False,
        print_info: bool = False,
    ) -> Tree | TreeNode | None:
        """Build a tree displaying all triples in R if possible.

        Args:
            return_root: If True, return 'TreeNode' instead of 'Tree' instance.
            print_info: If True, print information about inconsistencies.

        Returns
            The BUILD tree on leaf set L displaying all triples in R if the triple set R is
            consistent.
        """
        self.cut_value = 0
        self.cut_list = []
        self.print_info = print_info

        root = self._aho(self.L, self.R)

        # case 1: building a tree was successful
        if root:
            return root if return_root else Tree(root)

        # case 2: inconsistent triple set --> return None
        if self.print_info:
            print("no such tree exists")

    def _aho(self, L: Collection[Any], R: Iterable[Triple]) -> TreeNode | None:
        """Recursive Aho-algorithm.

        Args:
            L: A collection of leaf labels.
            R: An iterable of triples.

        Returns:
            The root of the recursively built tree (or None if no tree exists).
        """
        # trivial cases: only one or two leaves left in L
        if len(L) == 1:
            leaf = L.pop()
            return TreeNode(label=leaf)
        elif len(L) == 2:
            node = TreeNode()
            for _ in range(2):
                leaf = L.pop()
                node.add_child(TreeNode(label=leaf))
            return node

        help_graph = aho_graph(
            R, L, weighted=self.weighted_mincut, triple_weights=self.triple_weights
        )
        conn_comps = self._connected_components(help_graph)

        # return if less than 2 connected components
        if len(conn_comps) <= 1:
            if self.print_info:
                print("Connected component:\n", conn_comps)
            return

        # otherwise proceed recursively
        node = TreeNode()  # place new inner node
        for cc in conn_comps:
            Li = set(cc)  # list/dictionary --> set
            Ri = []
            for t in R:  # construct triple subset
                if Li.issuperset(t):
                    Ri.append(t)
            Ti = self._aho(Li, Ri)  # recursive call
            if not Ti:
                return  # return None to previous call
            else:
                node.add_child(Ti)  # add root of the subtree

        return node

    def _connected_components(self, aho_graph: nx.Graph) -> list[set[Any]] | Partition:
        """Determines the connected components of the graph.

        And optionally executes a min cut if there is only one component.

        Args:
            aho_graph: The Aho graph.

        Returns:
            The connected components of the Aho graph or the result of applying the MinCut algorithm
                for resolving triple inconsistencies.
        """
        conn_comps = list(nx.connected_components(aho_graph))
        if (not self.mincut) or len(conn_comps) > 1:
            return conn_comps

        # execute MinCut using the Stoer–Wagner algorithm
        cut_value, partition = nx.stoer_wagner(aho_graph)
        self.cut_value += cut_value

        if len(partition[0]) < len(partition[1]):
            smaller_comp = partition[0]
        else:
            smaller_comp = partition[1]

        for edge in aho_graph.edges():
            if (edge[0] in smaller_comp and edge[1] not in smaller_comp) or (
                edge[1] in smaller_comp and edge[0] not in smaller_comp
            ):
                self.cut_list.append(edge)

        return partition

__init__(R: Iterable[Triple], L: Collection[Any], mincut: bool = False, weighted_mincut: bool = False, triple_weights: dict[Triple, int | float] | None = None)

Constructor for class implementing the BUILD algorithm.

Parameters:

Name	Type	Description	Default
R	Iterable[Triple]	An iterable of triples.	required
L	Collection[Any]	A collection of leaf labels.	required
mincut	bool	If True, use MinCut to resolve triple inconsistencies. Otherwise, no tree is returned in case of such inconsistencies.	False
weighted_mincut	bool	If True, weight the edges in the resulting graph accordingto the number of corresponding triples (and their weights).	False
triple_weights	dict[Triple, int | float] | None	Dictionary with tuples as keys and float values. The weights of the triples. The default is None, in which case every triple has weight one.	None

Source code in tralda/supertree/build.py

def __init__(
    self,
    R: Iterable[Triple],
    L: Collection[Any],
    mincut: bool = False,
    weighted_mincut: bool = False,
    triple_weights: dict[Triple, int | float] | None = None,
):
    """Constructor for class implementing the BUILD algorithm.

    Args:
        R: An iterable of triples.
        L: A collection of leaf labels.
        mincut: If True, use MinCut to resolve triple inconsistencies. Otherwise, no tree is
            returned in case of such inconsistencies.
        weighted_mincut: If True, weight the edges in the resulting graph accordingto the number
            of corresponding triples (and their weights).
        triple_weights: Dictionary with tuples as keys and float values. The weights of the
            triples. The default is None, in which case every triple has weight one.
    """
    self.R = R
    self.L = L
    self.mincut = mincut
    self.weighted_mincut = weighted_mincut
    self.triple_weights = triple_weights

build_tree(return_root: bool = False, print_info: bool = False) -> Tree | TreeNode | None

Build a tree displaying all triples in R if possible.

Parameters:

Name	Type	Description	Default
return_root	bool	If True, return 'TreeNode' instead of 'Tree' instance.	False
print_info	bool	If True, print information about inconsistencies.	False

Returns The BUILD tree on leaf set L displaying all triples in R if the triple set R is consistent.

Source code in tralda/supertree/build.py

def build_tree(
    self,
    return_root: bool = False,
    print_info: bool = False,
) -> Tree | TreeNode | None:
    """Build a tree displaying all triples in R if possible.

    Args:
        return_root: If True, return 'TreeNode' instead of 'Tree' instance.
        print_info: If True, print information about inconsistencies.

    Returns
        The BUILD tree on leaf set L displaying all triples in R if the triple set R is
        consistent.
    """
    self.cut_value = 0
    self.cut_list = []
    self.print_info = print_info

    root = self._aho(self.L, self.R)

    # case 1: building a tree was successful
    if root:
        return root if return_root else Tree(root)

    # case 2: inconsistent triple set --> return None
    if self.print_info:
        print("no such tree exists")

greedy_build(R: Iterable[Triple], L: Collection[Any], triple_weights: dict[Triple, int | float] | None = None, return_root: bool = False) -> Tree | TreeNode

Greedy heuristic for triple consistency.

Add triples one by one and checks consistency via BUILD.

Parameters:

Name	Type	Description	Default
R	Iterable[Triple]	An iterable of triples.	required
L	Collection[Any]	A collection of leaf labels.	required
triple_weights	dict[Triple, int | float] | None	Weights for the triples; default is None in which case all triples are uniformly weighted.	None
return_root	bool	If True, return 'TreeNode' instead of 'Tree' instance.	False

Returns:

Type	Description
Tree | TreeNode	The constructed tree.

Source code in tralda/supertree/build.py

def greedy_build(
    R: Iterable[Triple],
    L: Collection[Any],
    triple_weights: dict[Triple, int | float] | None = None,
    return_root: bool = False,
) -> Tree | TreeNode:
    """Greedy heuristic for triple consistency.

    Add triples one by one and checks consistency via BUILD.

    Args:
        R: An iterable of triples.
        L: A collection of leaf labels.
        triple_weights: Weights for the triples; default is None in which case all triples are
            uniformly weighted.
        return_root: If True, return 'TreeNode' instead of 'Tree' instance.

    Returns:
        The constructed tree.
    """
    if triple_weights:
        triples = sorted(R, key=lambda triple: triple_weights[triple], reverse=True)
    else:
        triples = R

    consistent_triples = []
    root = None

    for t in triples:
        consistent_triples.append(t)
        build = Build(consistent_triples, L, mincut=False)
        new_root = build.build_tree(return_root=True)
        if new_root:
            root = new_root
        else:
            consistent_triples.pop()

    return root if return_root else Tree(root)

best_pair_merge_first(R: Iterable[Triple], L: Collection[Any], triple_weights: dict[Triple, int | float] | None = None, return_root: bool = False) -> Tree | TreeNode

Wu's (2004) Best-Pair-Merge-First (BPMF) heuristic.

Modified version by Byrka et al. (2010) and added weights.

Parameters:

Name	Type	Description	Default
R	Iterable[Triple]	An iterable of triples.	required
L	Collection[Any]	A collection of leaf labels.	required
triple_weights	dict[Triple, int | float] | None	Weights for the triples; default is None in which case all triples are uniformly weighted.	None
return_root	bool	If True, return 'TreeNode' instead of 'Tree' instance.	False

Returns:

Type	Description
Tree | TreeNode	The constructed tree.

Source code in tralda/supertree/build.py

def best_pair_merge_first(
    R: Iterable[Triple],
    L: Collection[Any],
    triple_weights: dict[Triple, int | float] | None = None,
    return_root: bool = False,
) -> Tree | TreeNode:
    """Wu's (2004) Best-Pair-Merge-First (BPMF) heuristic.

    Modified version by Byrka et al. (2010) and added weights.

    Args:
        R: An iterable of triples.
        L: A collection of leaf labels.
        triple_weights: Weights for the triples; default is None in which case all triples are
            uniformly weighted.
        return_root: If True, return 'TreeNode' instead of 'Tree' instance.

    Returns:
        The constructed tree.
    """
    # initialization
    nodes = {TreeNode(label=leaf): {leaf} for leaf in L}
    leaf_to_node = {}

    for node in nodes:
        leaf_to_node[node.label] = node

    # merging
    for i in range(len(L) - 1):
        score = {(S_i, S_j): 0 for S_i, S_j in itertools.combinations(nodes.keys(), 2)}

        for x, y, z in R:
            w = triple_weights[(x, y, z)] if triple_weights else 1

            S_i, S_j, S_k = (leaf_to_node[x], leaf_to_node[y], leaf_to_node[z])

            if (S_i is not S_j) and (S_i is not S_k) and (S_j is not S_k):
                if (S_i, S_j) in score:
                    score[(S_i, S_j)] += 2 * w
                else:
                    score[(S_j, S_i)] += 2 * w

                if (S_i, S_k) in score:
                    score[(S_i, S_k)] -= w
                else:
                    score[(S_k, S_i)] -= w

                if (S_j, S_k) in score:
                    score[(S_j, S_k)] -= w
                else:
                    score[(S_k, S_j)] -= w

        current_max = float("-inf")
        S_i, S_j = None, None

        for pair, pair_score in score.items():
            if pair_score > current_max:
                current_max = pair_score
                S_i, S_j = pair

        # create new node S_k connecting S_i and S_j
        S_k = TreeNode()
        S_k.add_child(S_i)
        S_k.add_child(S_j)

        nodes[S_k] = nodes[S_i] | nodes[S_j]  # set union
        for leaf in nodes[S_k]:
            leaf_to_node[leaf] = S_k

        del nodes[S_i]
        del nodes[S_j]

    if len(nodes) != 1:
        raise RuntimeError("more than 1 node left")

    root = next(iter(nodes))

    return root if return_root else Tree(root)

---

BuildST Algorithm

build_st(trees: Collection[Tree]) -> Tree | None

Supertree construction based on BuildST algorithm.

NOTE: The graph connecting to trees in the input set whenever they share at least one leaf label must be connected. Otherwise, the implementation returns None, even though a supertree may exist.

Parameters:

Name	Type	Description	Default
trees	Collection[Tree]	A collection of Tree instances.	required

Return

The constructed supertree if it exists; None otherwise.

References

1. Yun Deng and David Fernández-Baca. Fast Compatibility Testing for Rooted Phylogenetic Trees. 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). DOI: 10.4230/LIPIcs.CPM.2016.12

Source code in tralda/supertree/build_st.py

def build_st(trees: Collection[Tree]) -> Tree | None:
    """Supertree construction based on BuildST algorithm.

    NOTE: The graph connecting to trees in the input set whenever they share at least one leaf
    label must be connected. Otherwise, the implementation returns None, even though a supertree may
    exist.

    Args:
        trees: A collection of Tree instances.

    Return:
        The constructed supertree if it exists; None otherwise.

    References:
        1. Yun Deng and David Fernández-Baca. Fast Compatibility Testing for Rooted Phylogenetic
           Trees. 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016).
           DOI: 10.4230/LIPIcs.CPM.2016.12
    """
    st_builder = BuildST(trees)

    return st_builder.run()

BuildST

BuildST algorithm.

NOTE: The graph connecting to trees in the input set whenever they share at least one leaf label must be connected. Otherwise, the implementation returns None, even though a supertree may exist.

References

1. Yun Deng and David Fernández-Baca. Fast Compatibility Testing for Rooted Phylogenetic Trees. 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). DOI: 10.4230/LIPIcs.CPM.2016.12

Source code in tralda/supertree/build_st.py

class BuildST:
    """BuildST algorithm.

    NOTE: The graph connecting to trees in the input set whenever they share at least one leaf
    label must be connected. Otherwise, the implementation returns None, even though a supertree may
    exist.

    References:
        1. Yun Deng and David Fernández-Baca. Fast Compatibility Testing for Rooted Phylogenetic
           Trees. 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016).
           DOI: 10.4230/LIPIcs.CPM.2016.12
    """

    def __init__(self, trees: Collection[Tree]) -> None:
        """Constructor for BuildST algorithm.

        Args:
            trees: A collection of Tree instances.
        """
        # collection of k trees
        self.trees = trees

        # leaf label --> _XpNode
        self.label2xp_node: dict[Any, _XpNode] = {}

        # set U (marked nodes)
        self.marked: set[TreeNode] = set()

        # node --> index of the tree
        self.node2tree_index: dict[TreeNode, int] = {}

        # node --> doubly-linked list element
        self.list_pointer: dict[TreeNode, DLListNode] = {}

        # node --> doubly-linked list element
        self.singleton_pointer: dict[TreeNode, DLListNode] = {}

        # the graph H_p using HDT datastructure for dynamic graph connectivity
        self.hdt_graph = HDTGraph()

        # save why tree construction failed
        self.fail_message = ""

    def run(self) -> Tree | None:
        """Build the supertree from the given tree list if existent.

        Returns:
            The constructed supertree if it exits; None otherwise.
        """
        self._prepare_trees()  # tree indices, Xp nodes

        U_init = self._initialize()
        if not U_init:
            return

        root = self._buildst(U_init)

        if not root:
            return
        else:
            return Tree(root)

    def _prepare_trees(self) -> None:
        """Initialize lookups node2tree_index and label2xp_node."""
        for i in range(len(self.trees)):
            tree = self.trees[i]
            for node in tree.preorder():
                self.node2tree_index[node] = i  # enable access to tree index i in [k]
                if node.children:
                    continue

                if node.label not in self.label2xp_node:
                    self.label2xp_node[node.label] = _XpNode(node.label)
                self.label2xp_node[node.label].leafnodes.append(node)

    def _initialize(self) -> _ConnectedComp:
        """Construct the initial auxiliary graph H_p(U_init) as described in the paper.

        Returns:
            The initial connected component of the auxiliary graph H_p.
        """
        conn_comp_Y = _ConnectedComp(
            len(self.trees),
            self.hdt_graph,
            self.trees[0].root,
            count=len(self.label2xp_node),
        )

        for i, tree in enumerate(self.trees):
            # Y_init.singleton is the set i in [k] such that |U(i)|= 1
            self.singleton_pointer[tree.root] = conn_comp_Y.singleton.append(i)

            # append the root to DLList at Y.List[i]
            self.list_pointer[tree.root] = conn_comp_Y.List[i].append(tree.root)

            # add all the edges in the trees
            conn_comp_Y.initialize_tree_edges(tree)

            # mark root as part of set U_init
            self.marked.add(tree.root)

        # glue together the leafnodes and the label nodes in Xp
        for label_node in self.label2xp_node.values():
            for leafnode in label_node.leafnodes:
                conn_comp_Y.add_edge(label_node, leafnode)

        if self.hdt_graph and not self.hdt_graph.is_connected():
            self.failmessage = "initialization failed because graph is not fully connected"
            return

        return conn_comp_Y

    def _buildst(self, U: _ConnectedComp) -> TreeNode | None:
        """Recursive function for constructing the supertree.

        Args:
            U: A connected component of the auxiliary graph H_p.

        Returns:
            The root of the constructed supertree for the input trees if existent, None otherwise.
        """
        # --------------------------------------------------
        # if |L(U)| = 1 then
        #    return the tree consisting of node r_U, labeled by the single species in L(U)
        # --------------------------------------------------
        if U.count == 1:
            label_node = U.get_label_nodes()[0]
            return TreeNode(label=label_node.label)

        r_U = TreeNode()  # create a node r_U

        # --------------------------------------------------
        # if |L(U)| = 2 then
        #    return the tree consisting of node r_U and two children each labeled by a different
        #    species in L(U)
        # --------------------------------------------------
        if U.count == 2:
            labels = U.get_label_nodes()
            if len(labels) != 2:
                self.failmessage = "could not find 2 labeled nodes"
                return
            node1 = TreeNode(label=labels[0].label)
            node2 = TreeNode(label=labels[1].label)
            r_U.add_child(node1)
            r_U.add_child(node2)
            return r_U

        # --------------------------------------------------
        # foreach i in [k] such that |U(i)| = 1 do
        #    Let v be the single element in U(i)
        #    U = (U \ {v}) union Ch(v)
        # --------------------------------------------------
        W = [U]  # list of connected components
        J = [j for j in U.singleton]  # elements in singleton
        V = [U.List[i][0] for i in J]  # singleton nodes to be deleted

        for i in J:
            v_i = U.List[i][0]
            U.List[i].remove_node(self.list_pointer[v_i])
            U.singleton.remove_node(self.singleton_pointer[v_i])

            # unmark v_i and mark its children
            self.marked.discard(v_i)
            for child in v_i.children:
                self.marked.add(child)
                self.list_pointer[child] = U.List[i].append(child)

        for v_i in V:
            Y_current = None

            # find the component in W that contains v_i
            for Y in W:
                if v_i in Y:
                    Y_current = Y
                    break

            if not Y_current:
                return

            for u in v_i.children:
                # the edge deletion method guarantees that v_i is in conn_comp[0]
                conn_comp = Y_current.delete_edge(v_i, u)

                if len(conn_comp) == 2:
                    # case 1: u is the last child of v_i, then conn_comp[0] is actually empty
                    if len(conn_comp[0]) == 1:
                        Y_current.representative = u
                        break

                    # case 2: two actual components emerge
                    Y_new = conn_comp[1]

                    if len(Y_current) < len(Y_new):
                        self._update_conn_comps(Y_current, Y_new, first_swap=True)
                    else:
                        self._update_conn_comps(Y_new, Y_current)

                    W.append(Y_new)

        # --------------------------------------------------
        # Let W_1, W_2, ..., W_p be the connected components
        # if p = 1 then
        #    return incompatible
        # --------------------------------------------------
        if len(W) == 1:
            self.failmessage = "the trees are incompatible"
            return

        # --------------------------------------------------
        # foreach j in [p] do
        #    Let t_j = BuildST(W_j)
        #    if t j is a tree then
        #       Add t_j to the set of subtrees of r_U
        #    else
        #       return incompatible
        # --------------------------------------------------
        for W_j in W:
            t_j = self._buildst(W_j)
            if t_j:
                r_U.add_child(t_j)
            else:
                return

        # return the tree with root r_U
        return r_U

    def _update_conn_comps(
        self,
        Y1: _ConnectedComp,
        Y2: _ConnectedComp,
        first_swap: bool = False,
    ) -> None:
        """Updates Y.count, Y.singleton and Y.List of two newly split components.

        Component Y1 is supposed to be the smaller one and is scanned for label nodes (Xp) and for
        marked nodes.

        Args:
            Y1: The first connected component (should be the smaller one).
            Y2: The second connected component.
            first_swap: Should be set to True if Y1 (i.e., the smaller component) contains the
                information about count, List and singleton instead of Y2. In this case, these
                attributes need to be swapped first.
        """
        if first_swap:
            Y1.count, Y2.count = Y2.count, Y1.count
            Y1.List, Y2.List = Y2.List, Y1.List
            Y1.singleton, Y2.singleton = Y2.singleton, Y1.singleton

        for v in Y1:
            if isinstance(v, _XpNode):
                Y1.count += 1
                Y2.count -= 1
                continue

            if v not in self.marked:
                continue

            i = self.node2tree_index[v]
            Y2.List[i].remove_node(self.list_pointer[v])
            self.list_pointer[v] = Y1.List[i].append(v)

            # v becomes singleton
            if len(Y2.List[i]) == 1:
                singleton_node = Y2.List[i][0]
                self.singleton_pointer[singleton_node] = Y2.singleton.append(i)
            # index i is no longer singleton, i.e., it must have been a singleton
            elif len(Y2.List[i]) == 0:
                Y2.singleton.remove_node(self.singleton_pointer[v])

            # v becomes singleton
            if len(Y1.List[i]) == 1:
                self.singleton_pointer[v] = Y1.singleton.append(i)
            # index i is no longer singleton
            elif len(Y1.List[i]) == 2:
                Y1.singleton.remove_node(self.singleton_pointer[Y1.List[i][0]])

__init__(trees: Collection[Tree]) -> None

Constructor for BuildST algorithm.

Parameters:

Name	Type	Description	Default
trees	Collection[Tree]	A collection of Tree instances.	required

Source code in tralda/supertree/build_st.py

def __init__(self, trees: Collection[Tree]) -> None:
    """Constructor for BuildST algorithm.

    Args:
        trees: A collection of Tree instances.
    """
    # collection of k trees
    self.trees = trees

    # leaf label --> _XpNode
    self.label2xp_node: dict[Any, _XpNode] = {}

    # set U (marked nodes)
    self.marked: set[TreeNode] = set()

    # node --> index of the tree
    self.node2tree_index: dict[TreeNode, int] = {}

    # node --> doubly-linked list element
    self.list_pointer: dict[TreeNode, DLListNode] = {}

    # node --> doubly-linked list element
    self.singleton_pointer: dict[TreeNode, DLListNode] = {}

    # the graph H_p using HDT datastructure for dynamic graph connectivity
    self.hdt_graph = HDTGraph()

    # save why tree construction failed
    self.fail_message = ""

run() -> Tree | None

Build the supertree from the given tree list if existent.

Returns:

Type	Description
Tree | None	The constructed supertree if it exits; None otherwise.

Source code in tralda/supertree/build_st.py

def run(self) -> Tree | None:
    """Build the supertree from the given tree list if existent.

    Returns:
        The constructed supertree if it exits; None otherwise.
    """
    self._prepare_trees()  # tree indices, Xp nodes

    U_init = self._initialize()
    if not U_init:
        return

    root = self._buildst(U_init)

    if not root:
        return
    else:
        return Tree(root)

---

Common Refinement

linear_common_refinement(trees: Collection[Tree]) -> Tree | None

Minimal common refinement for a set of trees with the same leaf set.

All input trees must be phylogenetic and have the same set of leaf labels. In each tree, the leaves' label attributes must be set and unique.

Parameters:

Name	Type	Description	Default
trees	Collection[Tree]	A collection of of Tree instances.	required

Returns:

Type	Description
Tree | None	A common refinement of the input trees if existent, None otherwise.

References

1. D. Schaller, M. Hellmuth, P.F. Stadler (2021). A simpler linear-time algorithm for the common refinement of rooted phylogenetic trees on a common leaf set. Algorithms Mol Biol. 16(1):23. DOI: 10.1186/s13015-021-00202-8.

Source code in tralda/supertree/common_refinement.py

def linear_common_refinement(trees: Collection[Tree]) -> Tree | None:
    """Minimal common refinement for a set of trees with the same leaf set.

    All input trees must be phylogenetic and have the same set of leaf labels. In each tree, the
    leaves' label attributes must be set and unique.

    Args:
        trees: A collection of of Tree instances.

    Returns:
        A common refinement of the input trees if existent, None otherwise.

    References:
        1. D. Schaller, M. Hellmuth, P.F. Stadler (2021). A simpler linear-time algorithm for the
           common refinement of rooted phylogenetic trees on a common leaf set. Algorithms Mol Biol.
           16(1):23. DOI: 10.1186/s13015-021-00202-8.
    """
    cr = LinCR(trees)

    return cr.run()

LinCR

Minimal common refinement for a set of trees with the same leaf set in linear time.

References

1. D. Schaller, M. Hellmuth, P.F. Stadler (2021). A simpler linear-time algorithm for the common refinement of rooted phylogenetic trees on a common leaf set. Algorithms Mol Biol. 16(1):23. DOI: 10.1186/s13015-021-00202-8.

Source code in tralda/supertree/common_refinement.py

class LinCR:
    """Minimal common refinement for a set of trees with the same leaf set in linear time.

    References:
        1. D. Schaller, M. Hellmuth, P.F. Stadler (2021). A simpler linear-time algorithm for the
           common refinement of rooted phylogenetic trees on a common leaf set. Algorithms Mol Biol.
           16(1):23. DOI: 10.1186/s13015-021-00202-8.
    """

    def __init__(self, trees: Collection[Tree]) -> None:
        """Constructor of the LinCR class.

        Args:
            trees: A collection of of Tree instances.

        Raises:
            ValueError: If the trees do not have the same leaf labels.
        """
        self.trees = trees
        self.L = assert_leaf_sets_equal(trees)

        if not self.L:
            raise ValueError("trees must have the same leaf labels")

        # ensure that the run() method is only called once
        self.already_run = False

        self.T: Tree | None = None  # the common refinement (CR) candidate
        self.queue = deque[TreeNode]()

        # vertices in the CR
        self.vertices_in_cr: set[TreeNode] = set()

        # vertex v in an input trees --> number of leaves below v
        self.vertex2num_leaves: dict[TreeNode, int] = {}

        # list of dict per tree Ti mapping the nodes v in the constructed tree --> lca_Ti (L(Ti(v)))
        self.p: list[dict[TreeNode, TreeNode]] = [{} for _ in range(len(self.trees))]

        # vertex in the common refinement --> indices of the trees with corresponding vertex
        self.J: dict[TreeNode, dict[int, TreeNode | None]] = {}

        # inner vertex in input tree --> corresponding vertex in the common refinement
        self.vi_to_v: dict[TreeNode, TreeNode] = {}

    def run(self) -> Tree | None:
        """Run the the algorithm for constructing the minimal common refinement.

        Returns:
            The minimal common refinement if it exits; None otherwise.

        Raises:
            ValueError: If the method was already called for this instance.
        """
        if self.already_run:
            raise ValueError("the 'run' method can only be run once")

        self.already_run = True
        self._initialize()
        self._build_tree()

        if self.T and self.T.is_phylogenetic() and self._check_displayed():
            return self.T

        # otherwise return None

    def _initialize(self) -> None:
        """Initialize the lookups."""
        # compute the number of leaves below each vertex
        for T_i in self.trees:
            for v in T_i.postorder():
                if v.is_leaf():
                    self.vertex2num_leaves[v] = 1
                else:
                    self.vertex2num_leaves[v] = sum(self.vertex2num_leaves[w] for w in v.children)

        # label --> leaf vertex in the common refinement
        label2vertex_in_cr = {}

        # initialize the other mappings
        for label in self.L:
            v = TreeNode(label=label)
            self.queue.append(v)
            self.vertices_in_cr.add(v)
            label2vertex_in_cr[label] = v
            self.J[v] = {i: None for i in range(len(self.trees))}
            self.vertex2num_leaves[v] = 1

        for i, T_i in enumerate(self.trees):
            for v_i in T_i.leaves():
                v = label2vertex_in_cr[v_i.label]
                self.p[i][v] = v_i
                self.J[v][i] = v_i
                self.vi_to_v[v_i] = v

    def _build_tree(self) -> None:
        """Constructs the candidate for the common refinement tree.

        Raises:
            RuntimeError: If the root could not be determined.
        """
        self.root = None

        while self.queue:
            v = self.queue.popleft()
            u = None
            l_min = len(self.L)
            J_u = {}

            for i in range(len(self.trees)):
                if i in self.J[v]:
                    u2 = self.J[v][i].parent
                else:
                    u2 = self.p[i][v]

                if u is None or self.vertex2num_leaves[u2] < l_min:
                    u = u2
                    l_min = self.vertex2num_leaves[u2]
                    J_u.clear()
                    J_u[i] = u2
                elif self.vertex2num_leaves[u2] == l_min:
                    J_u[i] = u2

            if self.vertex2num_leaves[v] < l_min:
                if u in self.vi_to_v:
                    u = self.vi_to_v[u]
                else:
                    u = TreeNode()
                    self.J[u] = J_u
                    for i, u_i in J_u.items():
                        self.vi_to_v[u_i] = u
                        self.J[u][i] = u_i
                    self.vertex2num_leaves[u] = l_min
                u.add_child(v)
            else:
                return

            if u not in self.vertices_in_cr and l_min < len(self.L):
                self.queue.append(u)
                self.vertices_in_cr.add(u)
                if len(self.vertices_in_cr) > 2 * len(self.L) - 2:
                    return

                for i in range(len(self.trees)):
                    if i in self.J[u]:
                        self.p[i][u] = self.J[u][i]
                    elif i in self.J[v]:
                        self.p[i][u] = self.J[v][i].parent
                    else:
                        self.p[i][u] = self.p[i][v]

            elif l_min == len(self.L):
                self.root = u

        if not self.root:
            raise RuntimeError("could not determine root")

        self.T = Tree(self.root)

    def _check_displayed(self) -> bool:
        """Checks whether all input trees are displayed by the constructed tree.

        Returns:
            True if all trees are displayed by the constructed tree candidate, False otherwise.
        """
        for i, T_i in enumerate(self.trees):
            T_copy, v_copy = self.T.copy(mapping=True)

            to_contract = [
                (v_copy[v].parent, v_copy[v])
                for v in self.T.inner_nodes()
                if i not in self.J[v] and v.parent
            ]

            T_copy.contract(to_contract)

            for v_i in T_i.preorder():
                if v_i not in self.vi_to_v:
                    return False
                elif v_i.parent is None:
                    if v_copy[self.vi_to_v[v_i]].parent is not None:
                        return False
                elif v_i.parent not in self.vi_to_v:
                    return False
                elif v_copy[self.vi_to_v[v_i.parent]] is not v_copy[self.vi_to_v[v_i]].parent:
                    return False

        return True

__init__(trees: Collection[Tree]) -> None

Constructor of the LinCR class.

Parameters:

Name	Type	Description	Default
trees	Collection[Tree]	A collection of of Tree instances.	required

Raises:

Type	Description
ValueError	If the trees do not have the same leaf labels.

Source code in tralda/supertree/common_refinement.py

def __init__(self, trees: Collection[Tree]) -> None:
    """Constructor of the LinCR class.

    Args:
        trees: A collection of of Tree instances.

    Raises:
        ValueError: If the trees do not have the same leaf labels.
    """
    self.trees = trees
    self.L = assert_leaf_sets_equal(trees)

    if not self.L:
        raise ValueError("trees must have the same leaf labels")

    # ensure that the run() method is only called once
    self.already_run = False

    self.T: Tree | None = None  # the common refinement (CR) candidate
    self.queue = deque[TreeNode]()

    # vertices in the CR
    self.vertices_in_cr: set[TreeNode] = set()

    # vertex v in an input trees --> number of leaves below v
    self.vertex2num_leaves: dict[TreeNode, int] = {}

    # list of dict per tree Ti mapping the nodes v in the constructed tree --> lca_Ti (L(Ti(v)))
    self.p: list[dict[TreeNode, TreeNode]] = [{} for _ in range(len(self.trees))]

    # vertex in the common refinement --> indices of the trees with corresponding vertex
    self.J: dict[TreeNode, dict[int, TreeNode | None]] = {}

    # inner vertex in input tree --> corresponding vertex in the common refinement
    self.vi_to_v: dict[TreeNode, TreeNode] = {}

run() -> Tree | None

Run the the algorithm for constructing the minimal common refinement.

Returns:

Type	Description
Tree | None	The minimal common refinement if it exits; None otherwise.

Raises:

Type	Description
ValueError	If the method was already called for this instance.

Source code in tralda/supertree/common_refinement.py

def run(self) -> Tree | None:
    """Run the the algorithm for constructing the minimal common refinement.

    Returns:
        The minimal common refinement if it exits; None otherwise.

    Raises:
        ValueError: If the method was already called for this instance.
    """
    if self.already_run:
        raise ValueError("the 'run' method can only be run once")

    self.already_run = True
    self._initialize()
    self._build_tree()

    if self.T and self.T.is_phylogenetic() and self._check_displayed():
        return self.T

---

Consensus Tree

loose_consensus_tree(trees: Collection[Tree]) -> Tree | None

Compute the loose consensus tree for trees with the same leaf set.

All input trees must be phylogenetic and have the same set of leaf labels. In each tree, the leaves' label attributes must be set and unique.

Parameters:

Name	Type	Description	Default
trees	Collection[Tree]	A collection of of Tree instances.	required

Returns:

Type	Description
Tree | None	The loose consensus tree; None if 'trees' is empty.

References

1. J. Jansson, C. Shen, W.-K. Sung. Improved Algorithms for Constructing Consensus Trees. J. ACM 63, 3, Article 28 (June 2016), 24 pages. DOI: 10.1145/2925985.

Source code in tralda/supertree/consensus.py

def loose_consensus_tree(trees: Collection[Tree]) -> Tree | None:
    """Compute the loose consensus tree for trees with the same leaf set.

    All input trees must be phylogenetic and have the same set of leaf labels. In each tree, the
    leaves' label attributes must be set and unique.

    Parameters:
        trees: A collection of of Tree instances.

    Returns:
        The loose consensus tree; None if 'trees' is empty.

    References:
        1. J. Jansson, C. Shen, W.-K. Sung. Improved Algorithms for Constructing Consensus Trees.
           J. ACM 63, 3, Article 28 (June 2016), 24 pages. DOI: 10.1145/2925985.
    """
    loose_consensus = LooseConsensusTree(trees)

    return loose_consensus.run()

LooseConsensusTree

Construction of the loose consensus tree.

References

1. J. Jansson, C. Shen, W.-K. Sung. Improved Algorithms for Constructing Consensus Trees. J. ACM 63, 3, Article 28 (June 2016), 24 pages. DOI: 10.1145/2925985.

Source code in tralda/supertree/consensus.py

class LooseConsensusTree:
    """Construction of the loose consensus tree.

    References:
        1. J. Jansson, C. Shen, W.-K. Sung. Improved Algorithms for Constructing Consensus Trees.
           J. ACM 63, 3, Article 28 (June 2016), 24 pages. DOI: 10.1145/2925985.
    """

    def __init__(self, trees: Collection[Tree]) -> None:
        """_summary_

        Args:
            trees: A collection of of Tree instances.

        Raises:
            ValueError: If the trees do not have the same leaf labels.
        """
        if not assert_leaf_sets_equal(trees):
            raise ValueError("trees must have the same leaf labels")

        self.trees = trees

        # the loose consensus tree to be contracted
        self.T: Tree | None = None

        # the total number of edges that were contracted
        self.total_contracted = 0

    def run(self) -> Tree | None:
        """Run the construction of the loose consensus tree.

        Returns:
            The loose consensus tree; None if the collection of trees is empty.
        """
        self.total_contracted = 0

        k = len(self.trees)
        if k == 0:
            return
        elif k == 1:
            return self.trees[0].copy()

        tree = self.trees[0]
        for j in range(1, k):
            compatible_tree, x = one_way_compatible(
                tree,
                self.trees[j],
                return_no_of_contractions=True,
            )
            self.total_contracted += x
            tree = merge_trees(compatible_tree, self.trees[j])

        for j in range(k):
            tree, x = one_way_compatible(tree, self.trees[j], return_no_of_contractions=True)
            self.total_contracted += x

        self.T = tree

        return self.T

__init__(trees: Collection[Tree]) -> None

summary

Parameters:

Name	Type	Description	Default
trees	Collection[Tree]	A collection of of Tree instances.	required

Raises:

Type	Description
ValueError	If the trees do not have the same leaf labels.

Source code in tralda/supertree/consensus.py

def __init__(self, trees: Collection[Tree]) -> None:
    """_summary_

    Args:
        trees: A collection of of Tree instances.

    Raises:
        ValueError: If the trees do not have the same leaf labels.
    """
    if not assert_leaf_sets_equal(trees):
        raise ValueError("trees must have the same leaf labels")

    self.trees = trees

    # the loose consensus tree to be contracted
    self.T: Tree | None = None

    # the total number of edges that were contracted
    self.total_contracted = 0

run() -> Tree | None

Run the construction of the loose consensus tree.

Returns:

Type	Description
Tree | None	The loose consensus tree; None if the collection of trees is empty.

Source code in tralda/supertree/consensus.py

def run(self) -> Tree | None:
    """Run the construction of the loose consensus tree.

    Returns:
        The loose consensus tree; None if the collection of trees is empty.
    """
    self.total_contracted = 0

    k = len(self.trees)
    if k == 0:
        return
    elif k == 1:
        return self.trees[0].copy()

    tree = self.trees[0]
    for j in range(1, k):
        compatible_tree, x = one_way_compatible(
            tree,
            self.trees[j],
            return_no_of_contractions=True,
        )
        self.total_contracted += x
        tree = merge_trees(compatible_tree, self.trees[j])

    for j in range(k):
        tree, x = one_way_compatible(tree, self.trees[j], return_no_of_contractions=True)
        self.total_contracted += x

    self.T = tree

    return self.T

merge_all(trees: Collection[Tree]) -> Tree | None

Common refinement for compatible trees with the same leaf set.

All input trees must be phylogenetic and have the same set of leaf labels. In each tree, the leaves' label attributes must be set and unique.

WARNING: The behavior of the function is undefined if the trees are not compatible, i.e., if no common refinement exists.

Parameters:

Name	Type	Description	Default
trees	Collection[Tree]	A collection of of Tree instances.	required

Returns:

Type	Description
Tree | None	A common refinement of the input trees; None if 'trees' is empty.

Source code in tralda/supertree/consensus.py

def merge_all(trees: Collection[Tree]) -> Tree | None:
    """Common refinement for compatible trees with the same leaf set.

    All input trees must be phylogenetic and have the same set of leaf labels. In each tree, the
    leaves' label attributes must be set and unique.

    WARNING: The behavior of the function is undefined if the trees are not compatible, i.e., if no
    common refinement exists.

    Args:
        trees: A collection of of Tree instances.

    Returns:
        A common refinement of the input trees; None if 'trees' is empty.
    """
    if not assert_leaf_sets_equal(trees):
        raise RuntimeError("trees must have the same leaf labels")

    k = len(trees)
    if k == 0:
        return None
    elif k == 1:
        return trees[0].copy()

    merged_tree = trees[0]
    for j in range(1, k):
        merged_tree = merge_trees(merged_tree, trees[j])

    return merged_tree