Agreement forests#

The agreement-forest stage, passed as maf= to optimize(), optimize_many() and structure(). Any agreement forest gives the exact optimum; a smaller one only makes the dynamic program faster (see Agreement-forest stages).

Built-in stages#

class forestpd.maf.HeuristicMAF(lookahead=32)[source]#

Heuristic agreement forest by common-neighbourhood contraction.

Parameters:: lookahead (int | None, default 32) – When no blocks can be merged, how many of the highest-ranked blocks to try cutting before choosing the one that makes the most blocks mergeable. None tries every block: slower on large clusters, but it can give smaller forests.
Variables:: trusted (bool) – True: every forest is an agreement forest by construction (contraction merges only common neighbourhoods, and cutting only refines), so the solver may skip the full validation.
Raises:: ForestPDValueError – If lookahead is not a positive integer or None.

Examples

>>> from forestpd.core.tree import PhyloTree
>>> t = PhyloTree.from_edges(6, [(0, 4), (1, 4), (4, 5), (2, 5), (3, 5)],
...                          [1.0] * 5, {0: 0, 1: 1, 2: 2, 3: 3})
>>> HeuristicMAF().compute([t, t])          # identical trees agree completely
((0, 1, 2, 3),)

compute(trees)[source]#

Compute a small valid agreement forest of trees.

Parameters:: trees (Sequence[PhyloTree]) – The local trees of one cluster, all on leaves 0..n_leaves-1.
Returns:: The components, each a sorted tuple of leaf ids, ordered by smallest leaf.
Return type:: Forest

class forestpd.maf.TieredMAF(k_threshold=14)[source]#

The heuristic forest, replaced by rooted maffe’s on clusters where it has k >= k_threshold.

Needs maffe installed (see MaffeRMAF). Maffe’s forest is used if it has fewer components; like MaffeRMAF, it is trusted, not checked. If maffe cannot handle a cluster (it raises a ForestPDError, e.g. for a polytomy), the heuristic forest is kept. Other exceptions from maffe itself are not caught.

Parameters:

k_threshold (int, default 14) – Smallest heuristic forest size at which rooted maffe is tried.

Variables:

heuristic (HeuristicMAF) – The first stage.
maffe (MaffeRMAF) – The second stage.
trusted (bool) – True: both stages return agreement forests by construction.
uses_rooting (bool) – True: the solver’s Rooting is passed on to maffe.

Raises:

ForestPDValueError – If k_threshold is not an integer of at least 2.
ForestPDImportError – If maffe is not installed.

compute(trees, rooting=None)[source]#

The heuristic forest of trees, or rooted maffe’s where that is smaller.

Parameters:

trees (Sequence[PhyloTree]) – The local trees of one cluster, all on leaves 0..n_leaves-1.
rooting (Rooting | None, optional) – Where maffe roots the trees (see MaffeRMAF).

Returns:

The forest used.

Return type:

Forest

class forestpd.maf.MaffeRMAF(approx_factor=1.0, approx_offset=0, log_level=0)[source]#

Minimum rooted agreement forest by maffe, rooted where the solver says.

With a Rooting every tree is rooted on the pendant edge of the cluster’s root leaf (x_C^*, or leaf 0 at the top cluster) and x_C^* is removed from the result. Without one, the trees are rooted at leaf 0.

Marked trusted: maffe’s forests are agreement forests by construction, so the solver builds the profiles from the split tables (fast), with only its partial check. The partition itself is always checked here, and TieredMAF validates maffe’s forest fully before using it.

Parameters:

approx_factor (float, default 1.0) – Passed to maffe: accept a forest within this factor of the minimum. 1.0 is exact.
approx_offset (int, default 0) – Passed to maffe: accept a forest within this many components of the minimum.
log_level (int | str, default 0) – Passed to maffe: 0/"quiet", 1/"normal" or 2/"verbose".

Variables:

uses_rooting (bool) – True: the solver passes each cluster’s Rooting.
trusted (bool) – True (see above).

Raises:

ForestPDImportError – If maffe is not installed.

compute(trees, rooting=None)[source]#

Compute a minimum rooted agreement forest of trees with maffe.

Parameters:

trees (Sequence[PhyloTree]) – The local trees of one cluster, all on leaves 0..n_leaves-1. They must be binary.
rooting (Rooting | None, optional) – Where to root. None roots trees at leaf 0.

Returns:

The components on the leaves of trees, each sorted, ordered by smallest leaf.

Return type:

Forest

Raises:

ForestPDValueError – If a tree is not binary.
ForestPDInputError – If maffe’s components are not a partition of the leaves.

class forestpd.maf.MaffeUMAF(log_level=0)[source]#

Minimum unrooted agreement forest by maffe.

Uses maffe.solve_unrooted, which so far exists only in maffe’s unrooted branch. Marked trusted, as MaffeRMAF.

Parameters:: log_level (int | str, default 0) – Passed to maffe: 0/"quiet", 1/"normal" or 2/"verbose".
Variables:: trusted (bool) – True, as for MaffeRMAF.
Raises:: ForestPDImportError – If maffe, or its unrooted solver, is not installed.

compute(trees)[source]#

Compute a minimum unrooted agreement forest of trees with maffe.

Parameters:

trees (Sequence[PhyloTree]) – The local trees of one cluster, all on leaves 0..n_leaves-1. They must be binary.

Returns:

The components, each a sorted tuple of leaf ids, ordered by smallest leaf.

Return type:

Forest

Raises:

ForestPDValueError – If a tree is not binary.
ForestPDInputError – If maffe’s components are not a partition of the leaves.

Writing your own stage#

Any object with a compute method of the form below can be passed as maf=.

class forestpd.maf.MAFComputer(*args, **kwargs)[source]#

Strategy that partitions a cluster’s leaf set into agreement-forest components.

Any object with a matching compute() method satisfies the protocol. An optional attribute trusted = True declares that every forest it returns is an agreement forest by construction; the solver then builds the clusters’ profiles from their split tables, which is faster but checks the forest only partially. Without it, every forest is fully validated. An optional attribute uses_rooting = True makes the solver pass rooting= (a Rooting) as well.

compute(trees)[source]#

Return an agreement forest of trees as a partition of leaves 0..n_leaves-1.

The forest must be a valid agreement forest; it need not be minimum.

Parameters:: trees (Sequence[PhyloTree]) – The local trees of one cluster, all on leaves 0..n_leaves-1.
Returns:: The components, each a tuple of leaf ids; together they partition the leaf set.
Return type:: Forest

class forestpd.maf.Rooting(trees, leaf, extra)[source]#

Where a cluster’s trees are rooted, for MAF computers with uses_rooting = True.

Variables:

trees (Sequence[PhyloTree]) – The cluster’s trees containing the root leaf. When extra is true these are the trees passed to MAFComputer.compute() plus the leaf x_C^*; otherwise they are the same trees.
leaf (int) – The root leaf: x_C^* (always the last leaf) or leaf 0 at the top cluster.
extra (bool) – Whether leaf is an extra leaf, absent from the trees passed to compute. A forest computed on trees must then have it removed (see drop_leaf_from_forest()).

forestpd.maf.Forest#

Built-in immutable sequence.

If no argument is given, the constructor returns an empty tuple. If iterable is specified the tuple is initialized from iterable’s items.

If the argument is a tuple, the return value is the same object.

alias of tuple[tuple[int, …], …]