Split out of #18 during the feature/constraint-holes review; not a regression — verified identical on 99b79d8f and on that branch.
Two readings of a constraint, and the code uses both
?MaximizeParsimony's @param constraint promises the phyDat reading: returned trees are "perfectly compatible with each character in constraint", i.e. some edge separates the taxa coded 1 from those coded 0, with ? taxa free on either side.
The locked-node machinery enforces a stricter one. map_constraint_nodes (src/ts_constraint.cpp:180-225) accepts a split only when some node's tip set equals the 1 group exactly (or its complement) — free ? taxa excluded. wagner_tree_displays_constraint (src/ts_wagner.cpp:595) is the same exact test.
Strict implies loose, so no wrong answer is returned: every tree the search accepts satisfies the documented constraint. The problem is the trees it will not move.
Symptom
A tree that satisfies the documented constraint but not the strict form maps to no node, so regraft_violates_constraint (src/ts_constraint.cpp:354-360) reads it as already-violating and rejects every rearrangement. The replicate freezes and returns its start.
Deterministic, 8 taxa, cons = c(a=1, b=1, c=0, d=0, e:h="?"):
start <- ape::read.tree(text = "(((a,e),(b,f)),(c,(d,(g,h))));")
The split {a,e,b,f} | {c,d,g,h} separates {a,b} from {c,d}, so the constraint is satisfied as documented — confirmed via .ConstraintViolated() returning FALSE. But {a,b} is not a clade exactly, so TBR makes no move.
Reachable without a user tree =: the Wagner retry loop (ts_wagner.cpp:1062, :1099) breaks on violates_constraint_posthoc — the loose check — so it can hand the search a start it cannot move from. ts_sector.cpp:1769 reverts on the loose check too, so a sector move can leave a replicate in the same state mid-search.
Why it was not fixed with #18
The feature/constraint-holes gates use the loose reading deliberately: it is the documented contract, and gating the pool strictly would discard trees that satisfy the user. Repairing the start to the strict form instead would silently rearrange a start that already satisfies what the caller asked for — and would not touch the Wagner and sector entry points, so it would be an inconsistent half-measure.
vignettes/search-algorithm.Rmd now states the distinction explicitly rather than papering over it.
What would settle it
Decide which reading is canonical and make one of them true everywhere:
- Loosen the machinery — teach
map_constraint_nodes / regraft_violates_constraint the free-taxa reading, so the search explores everything the documented constraint permits. Larger job; touches the hottest constraint path.
- Tighten the documentation — state that a constraint character's
? taxa are excluded from the enforced clade, and tighten .PrepareConstraint to reject or warn on constraints where the two readings differ.
Worth measuring first: how much search space the strict reading forecloses when a constraint has many ? taxa.
Split out of #18 during the
feature/constraint-holesreview; not a regression — verified identical on99b79d8fand on that branch.Two readings of a constraint, and the code uses both
?MaximizeParsimony's@param constraintpromises the phyDat reading: returned trees are "perfectly compatible with each character inconstraint", i.e. some edge separates the taxa coded1from those coded0, with?taxa free on either side.The locked-node machinery enforces a stricter one.
map_constraint_nodes(src/ts_constraint.cpp:180-225) accepts a split only when some node's tip set equals the 1 group exactly (or its complement) — free?taxa excluded.wagner_tree_displays_constraint(src/ts_wagner.cpp:595) is the same exact test.Strict implies loose, so no wrong answer is returned: every tree the search accepts satisfies the documented constraint. The problem is the trees it will not move.
Symptom
A tree that satisfies the documented constraint but not the strict form maps to no node, so
regraft_violates_constraint(src/ts_constraint.cpp:354-360) reads it as already-violating and rejects every rearrangement. The replicate freezes and returns its start.Deterministic, 8 taxa,
cons = c(a=1, b=1, c=0, d=0, e:h="?"):The split
{a,e,b,f} | {c,d,g,h}separates{a,b}from{c,d}, so the constraint is satisfied as documented — confirmed via.ConstraintViolated()returningFALSE. But{a,b}is not a clade exactly, so TBR makes no move.Reachable without a user
tree =: the Wagner retry loop (ts_wagner.cpp:1062,:1099) breaks onviolates_constraint_posthoc— the loose check — so it can hand the search a start it cannot move from.ts_sector.cpp:1769reverts on the loose check too, so a sector move can leave a replicate in the same state mid-search.Why it was not fixed with #18
The
feature/constraint-holesgates use the loose reading deliberately: it is the documented contract, and gating the pool strictly would discard trees that satisfy the user. Repairing the start to the strict form instead would silently rearrange a start that already satisfies what the caller asked for — and would not touch the Wagner and sector entry points, so it would be an inconsistent half-measure.vignettes/search-algorithm.Rmdnow states the distinction explicitly rather than papering over it.What would settle it
Decide which reading is canonical and make one of them true everywhere:
map_constraint_nodes/regraft_violates_constraintthe free-taxa reading, so the search explores everything the documented constraint permits. Larger job; touches the hottest constraint path.?taxa are excluded from the enforced clade, and tighten.PrepareConstraintto reject or warn on constraints where the two readings differ.Worth measuring first: how much search space the strict reading forecloses when a constraint has many
?taxa.