Binary leaf elimination orders for finite trees
DefinitionStableMSR_Recovery_Supplement_TreeLeafSchedulesalgorithmsclustering
From the active list, remove its first vertex with at most one active neighbor. The order records these choices on the explicit number of input vertices. A good order is a permutation with at most one later neighbor per vertex.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_FiniteMenuTrees set_option autoImplicit false namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree def adjB (L : FactorLayout) (i j : ℕ) : Bool := !(i==j) && ((L[i]?.getD ([],[])).2.contains j || (L[j]?.getD ([],[])).2.contains i) def neighbors (L : FactorLayout) (xs : Block) (i : ℕ) := xs.filter (adjB L i) def firstLeaf (L : FactorLayout) (xs : Block) := (xs.filter (fun i => decide ((neighbors L xs i).length≤1))).headD 0 def pruneLeaf (L : FactorLayout) (xs : Block) := xs.filter (fun i => !(i == firstLeaf L xs)) def liveNodes (L : FactorLayout) (d : ℕ) := ((List.range L.length).take d).foldl (fun xs _ => pruneLeaf L xs) (List.range L.length) def leafOrder (L : FactorLayout) := (List.range L.length).map (fun d => firstLeaf L (liveNodes L d)) def Thin (L : FactorLayout) : Block→Prop | [] => True | i::is => (neighbors L is i).length≤1 ∧ Thin L is def GoodOrder (L : FactorLayout) (xs : Block) := xs.Perm (List.range L.length) ∧ Thin L xs end StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree
Source
Finite forest leaf elimination for the exact-count tree dynamic program of Ravichandran and Reyzin, Appendix A.6.