用途:该技能面向树分解上的结构化分解(Structured Decompositions),用于以层(sheaves)方式实现固定参数可解(FPT)算法,并提供对分解结构的双向导航。版本 1.1.0,trit 为 0。
核心概念:定义 StrDecomp = 函子 d: ∫G → C,其中 ∫G 是形状图的元素范畴,C 是目标范畴(如 Graph、FinSet)。使用 using StructuredDecompositions 后,可通过 d = StrDecomp(graph) 从图创建分解。
主要能力:可访问组件 bags(d)(局部子结构)、adhesions(d)(重叠/共享边界)、adhesionSpans(d)(span 态射)。𝐃 函子将判定问题提升到分解空间,示例为 k_coloring(G) = homomorphisms(G, K_k),随后通过 𝐃(k_coloring, decomp, CoDecomposition) 求解,并用 (answer, witness) = decide_sheaf_tree_shape(k_coloring, decomp) 得到结果。
导航:借助 SpecterACSet 提供双向路径。选择用 select([decomp_bags, ALL, acset_parts(:V)], decomp);变换用 transform([decomp_adhesions, ALL], adh -> reindex_adhesion(adh, mapping), decomp)。导航器包括 decomp_bags、decomp_adhesions、decomp_spans、adhesion_between(i,j),分别用于选择与更新对应 ACSets、span 态射或特定 adhesion。
FPT 复杂度:运行时间为 O(f(width) × n),其中 width 为最大 adhesion 尺寸。层条件保证局部解可粘合为全局解,示例函数 verify_sheaf_condition 检查重叠上的 section 是否一致。
集成:可与 lispsyntax-acset 集成,将分解序列化为 S-表达式以便检查,如 sexp = sexp_of_strdecomp(decomp),并通过 strdecomp_of_sexp(GraphType, sexp) 往返还原。可用 Gay.jl 确定性着色,将 adhesion 表示为带颜色的边界(ColoredAdhesion 结构,color 由 seed 和 index 确定)。
相关主题:时间变化数据(结合 Brunton 与 Spivak),用于分解数据上的 DMD/Koopman 分析,通过时间变化分解 schema 与 colimit 重建动力学。
限制:资料未提供安装命令、具体依赖版本、完整 API 文档、性能基准或收费信息。使用前需自行确认 StructuredDecompositions.jl 的环境配置。