Open hfr1tz3 opened 2 months ago
codecov[bot]
commented
2 months ago All modified and coverable lines are covered by tests :white_check_mark:
Project coverage is 86.65%. Comparing base (
e7fdbe1) to head (4229bfd). Report is 14 commits behind head on main.
petrelharp
commented
1 month ago Proposal for the basis for a test: here is a definition of what should be extendable by this method; so we can check if there remain no extendable edges (when run until no further changes are made).
A right extendable path from $x$ to $y$ in a tree $T_k$ is a path $x <_k a_1 <_k \cdots <_k a_n <_k y$ (where $<_k$ denotes "below in tree $T_k$" that has the properties:
The nodes $a_i$ are right extendable, and the nodes $b_i$ are left extendable.
Why is this the right definition? Well, first it's clear we can't extend nodes that are in the next tree. Next, suppose that there is a $bj$ on the path from $x$ to $y$ in $T{k+1}$ that is also in $T_k$, but not on the path from $x$ to $y$. If $b_j <_k x$ then we can take $b_j$ as the other endpoint of the extendable path instead of $y$. If $b_j \nless_k x$, then that implies ancestry above $b_j$ was inherited along a different path back to the time of $x$, so we can't use inheritance from $x$ as a criteria for extending. A similar argument holds if $y <_k b_j$ or and $y \nless_k b_j$.
petrelharp
commented
1 month ago I've added two things:
Next step: compare it to the non-naive version.
New extension (pun intended) to the
extend_edgesalgorithm now calledextend_paths(subject to change). We noticed that certain examples within unary regions would not be extended simply with extend edges. We propose this algorithm to handle examples like the following: For edge path $a \to b \to c$ in tree $T_1$ and edge $a \to d \to c$ in $T_2$, assuming $d\notin T_1$ and $b\notin T_2$ and $t(b)>t(d)$ we should have extended path $a\to b \to d \to c$ in tree $T_2$. Unit tests still need to be built, and the algorithm needs to be cleaned.We hypothesize that using this alongside extend edges could be the optimal strategy for minimizing edges in tree sequences.