List encoding of tree decompositions for factor graphs
DefinitionStableMSR_Recovery_Supplement_FactorLayoutsalgorithmsclustering
A layout gives the variable names and neighboring node indices of each bag. Its correctness predicate certifies a native tree decomposition and bounds every bag size.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_ScopeGraph
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional
abbrev FactorLayout := List (Block × Block)
def layoutTree (L : FactorLayout) : SimpleGraph (Fin L.length) where
Adj i j := i≠j ∧ (j.val∈L[i].2 ∨ i.val∈L[j].2)
symm := ⟨fun _ _ h => ⟨h.1.symm,h.2.symm⟩⟩
loopless := ⟨fun _ h=>h.1 rfl⟩
def layoutBag (vs : Block) (L : FactorLayout) (i : Fin L.length) : Finset (↥vs.toFinset) :=
Finset.univ.filter (fun v=>v.val∈L[i].1)
def GoodLayout (vs : Block) (scopes : List Block) (t : ℕ) (L : FactorLayout) : Prop :=
RobertsonSeymour1986.GM5.IsTreeDecomposition (scopeGraph vs scopes) (layoutTree L) (layoutBag vs L) ∧
∀ i, (layoutBag vs L i).card≤t+1
end StableMSR.Recovery.Supplement.BinaryRecovery.Regional
Source
Binary encoding for the bounded-width factor dynamic program.