External boundaries and recursive connected components
DefinitionStableMSR_TightBlockSearchThe external boundary of a finite vertex set consists of vertices outside it that have a neighbor inside it. For a candidate bag B and an interior C, children are the connected components of G minus B contained in C. These definitions specify the finite states of a tight-boundary decomposition search.
Definition code
import Definitions.Def_Mazoit2013_PartialDecompositions
namespace StableMSR.Recovery.DecompositionSearch
open Havens PartialDecompositions
variable {V : Type} [Fintype V] [DecidableEq V]
noncomputable def boundary (G : SimpleGraph V) (C : Finset V) : Finset V := by
classical
exact Finset.univ.filter (fun v => v ∉ C ∧ ∃ u ∈ C, G.Adj u v)
lemma mem_boundary {G : SimpleGraph V} {C : Finset V} {v : V} :
v ∈ boundary G C ↔ v ∉ C ∧ ∃ u ∈ C, G.Adj u v := by
classical
simp [boundary]
noncomputable def children (G : SimpleGraph V) (B C : Finset V) : Finset (Finset V) := by
classical
exact (PartialDecompositions.components G B).filter (fun D => D ⊆ C)
lemma mem_children {G : SimpleGraph V} {B C D : Finset V} :
D ∈ children G B C ↔ IsFlap G B D ∧ D ⊆ C := by
classical
simp [children,mem_components]
end StableMSR.Recovery.DecompositionSearch
Source
Implementation-support definitions for finite bounded-treewidth decomposition search in the stable sum-of-radii clustering mission.