Executable enumeration of tight blocks and successful separator choices
DefinitionStableMSR_Recovery_Supplement_TightBlockPoliciesalgorithmsclustering
Enumerate small separators and candidate bags. Repeated filtering keeps every bag choice whose component children already have witnesses. A successful policy covers all graph components and stores the recursive data of every chosen bag.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_BinaryBlockSearch
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch
open Regional DecompositionSearch
abbrev Rule := Block × Block × List Block
def childrenOf (z : GraphInput) (b c : Block) := (pieces z b).filter (fun d=>contained z d c)
def candidates (z : GraphInput) (t : ℕ) (s c : Block) : List Rule :=
((tuples z.1 (t+1)).filter (fun b=>contained z s b && contained z b (s++c) && meets z b c)).map
fun b=>(c,b,childrenOf z b c)
def rules (z : GraphInput) (t : ℕ) : List Rule :=
(tuples z.1 t).flatMap (fun s=>
((pieces z s).filter (fun c=>same z s (border z c))).flatMap (candidates z t s))
def seen (z : GraphInput) (known : List Rule) (c : Block) := known.any (fun r=>same z c r.1)
def enabled (z : GraphInput) (known : List Rule) (r : Rule) := r.2.2.all (seen z known)
def winners (z : GraphInput) (t m : ℕ) : List Rule := repeatFilter enabled z (rules z t) m []
def policy (t : ℕ) (z : GraphInput) := winners z t (names z.1).length
def decideWidth (t : ℕ) (z : GraphInput) := (pieces z []).all (seen z (policy t z))
def Presents (z : GraphInput) (t : ℕ) (rs : List Rule) : Prop :=
(∀ C∈PartialDecompositions.components (scopeGraph z.1 z.2) ∅, ∃ r∈rs,cuts z r.1=C) ∧
∀ r∈rs, let G := scopeGraph z.1 z.2
let C := cuts z r.1
let B := cuts z r.2.1
Havens.IsFlap G (boundary G C) C ∧ boundary G C ⊆ B ∧ B ⊆ boundary G C ∪ C ∧
B.card≤t+1 ∧ (B∩C).Nonempty ∧
(∀ D, D∈children G B C ↔ ∃ d∈r.2.2,cuts z d=D) ∧
∀ d∈r.2.2, ∃ q∈rs,cuts z q.1=cuts z d
end StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch
Source
Constructive binary version of StableMSR.Recovery.DecompositionSearch.accepts.