random_constrained_tree() samples only the strict-reading corner of the legal topologies

[ms609]

Follow-up to #54, which loosened constraint enforcement to the documented
free-taxa contract. random_constrained_tree() (src/ts_wagner.cpp, the
RANDOM_TREE start strategy) still applies the strict reading when it builds a
start tree.

It reads cd.split_tips only. Every tip the constraint does not name is
collected as a root-level item, so it is placed outside every constrained
group, and each "together" group comes out as an exact clade.

Every tree it returns is compliant — strict implies loose — so this is not a
soundness bug. It is a sampling bug: most of the compliant topologies are
unreachable at every seed.

Exhaustively, on 6 taxa with one constraint character ({c,d} together,
{a,b} apart, {e,f} coded ?): 35 of the 105 unrooted binary trees are
compliant, and the generator can produce only 15 of them. The other 20 are
never drawn, whatever the seed.

Expected: a free taxon may sit on either side of every constraint edge, so a
random constrained start tree should be able to place it inside a constrained
group as readily as outside one.

[ms609]

Claimed. Working on branch feature/constraint-random-tree, worktree worktrees/TreeSearch/sad-newton-6a59cc. Branched from feature/constraint-loosen (PR #84), so the PR will stack on that one.

[ms609]

Fixed in #122, stacked on #84 (feature/constraint-loosen) so the diff is only the start-tree generator. GHA green on 3fa12e92 (run 30994851997, ubuntu-arm64 + windows).

Exhaustive confirmation of the reported figure: on 6 taxa, 35 of the 105 unrooted trees comply and the old generator drew 15 of them over 4000 seeds; the new one draws all 35, at rates consistent with uniform (counts 86-135 against an expectation of 114.3, chi-square p = 0.27).

One residual, documented in place rather than fixed: a tip that IS named, but by a different constraint character, keeps its backbone position. Given {a,b} vs {c,d} and {e,f} vs {g,h}, tip c is free of the second split and could legally sit inside {e,f}, but is held at root level. Reaching those positions needs a per-tip edge list filtered against the clades its own splits bar it from, O(n) per tip rather than O(1). Reopen against that if it turns out to matter.

[ms609]

Scope corrected while working on this. The first fix (3fa12e92) let the ?-coded taxa roam, which closes the reported 6-taxon case (15 → 35 of 35). It does not close the general one: taxa named by another character stayed put, and two characters' clades could never nest inside one another.

Exhaustively, on 8 taxa with two characters ({a,b}|{c,d} and {e,f}|{g,h}), 1155 of the 10395 unrooted trees comply and the backbone construction draws 105 of them at any seed — the same 105 before and after the free-taxon scatter, since that example has no unnamed taxa.

64bebf41 replaces the backbone (for constrained-with-free-taxa inputs only) with tip-at-a-time insertion: a rejection pass that is exactly uniform where it lands, a legality-filtered pass that always lands, then the unnamed taxa unfiltered. Both exhaustive cases now reach every compliant tree (35/35 and 1155/1155) with 0 violations in 20000 draws and per-tree counts consistent with uniform.

Constraints that name every taxon keep the old backbone, which is complete and uniform in that case — so build_constraint_from_bitsets()'s consensus splits are untouched.

Remaining limit, stated rather than glossed: where a constraint pins down most of a large tree the rejection pass cannot land, and the filtered fallback reaches every legal topology but not at equal rates.