Binary graph operations for tight-block search
DefinitionStableMSR_Recovery_Supplement_BinaryBlockSearchalgorithmsclustering
Finite lists implement adjacency, induced-component flooding, set comparisons and external boundaries on the distinct input variable names.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_FactorLayouts
import Definitions.Def_StableMSR_DecompositionSearch_Recurrence
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch
open Regional
abbrev GraphInput := Block × List Block
abbrev Vertex (z : GraphInput) := ↥z.1.toFinset
def cuts (z : GraphInput) (s : Block) : Finset (Vertex z) := Finset.univ.filter (fun x=>x.val∈s)
def names (xs : Block) : Block := xs.foldr (fun i a=>if a.contains i then a else i::a) []
def contained (z : GraphInput) (c d : Block) : Bool :=
z.1.all (fun i => !c.contains i || d.contains i)
def same (z : GraphInput) (c d : Block) : Bool := contained z c d && contained z d c
def meets (z : GraphInput) (c d : Block) : Bool :=
z.1.any (fun i=>c.contains i && d.contains i)
def edge (z : GraphInput) (i j : ℕ) : Bool :=
!decide (i=j) && z.2.any (fun s => s.contains i && s.contains j)
def outside (z : GraphInput) (s : Block) := z.1.filter (fun i=> !s.contains i)
def grow (z : GraphInput) (c : Block) (v : ℕ) := c.contains v || c.any (fun u=>edge z u v)
def repeatFilter {α β : Type} (p : α→List β→β→Bool) (a : α) (pool : List β) (n : ℕ) (init : List β) :=
(fun r => pool.filter (p a r))^[n] init
def flood (z : GraphInput) (s : Block) (i : ℕ) :=
repeatFilter grow z (outside z s) z.1.length [i]
def pieces (z : GraphInput) (s : Block) := (outside z s).map (flood z s)
def border (z : GraphInput) (c : Block) := z.1.filter (fun v =>
!c.contains v && z.1.any (fun u => c.contains u && edge z u v))
end StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch
Source
Size-ordered treewidth search in the stable sum-of-radii mission.