Acsets Algebraic Databases

ACSets: Algebraic Databases Skill

"The category of simple graphs does not even have a terminal object!" — AlgebraicJulia Blog, with characteristic ironic detachment

bmorphism Contributions

"Parametrised optics model cybernetic systems, namely dynamical systems steered by one or more agents. Then ⊛ represents agency being exerted on systems" — @bmorphism, GitHub bio

"universal topos construction for social cognition and democratization of mathematical approach to problem-solving to all" — Plurigrid: the story thus far

Related repos:

• plurigrid/act - "building blocks for cognitive category theory" (active inference + ACT + enacted cognition)
• bmorphism/awesome-applied-category-theory - ACT community resources

What Are ACSets?

ACSets ("attributed C-sets") are a family of data structures generalizing both graphs and data frames. They are an efficient in-memory implementation of a category-theoretic formalism for relational databases.

C-set = Functor X: C → Set where C is a small category (schema)

┌─────────────────────────────────────────────────────────────┐
│  Schema (Small Category C)                                  │
│  ┌─────┐  src   ┌─────┐                                     │
│  │  E  │───────▶│  V  │                                     │
│  │     │  tgt   │     │                                     │
│  └──┬──┘───────▶└─────┘                                     │
│     │                                                       │
│     │ A C-set X assigns:                                    │
│     │   X(V) = set of vertices                              │
│     │   X(E) = set of edges                                 │
│     │   X(src): X(E) → X(V)                                 │
│     │   X(tgt): X(E) → X(V)                                 │
└─────────────────────────────────────────────────────────────┘

Core Concepts

1. Schema Definition

using Catlab.CategoricalAlgebra

@present SchGraph(FreeSchema) begin
  V::Ob
  E::Ob
  src::Hom(E,V)
  tgt::Hom(E,V)
end

@acset_type Graph(SchGraph, index=[:src,:tgt])

2. Symmetric Graphs (Undirected)

@present SchSymmetricGraph <: SchGraph begin
  inv::Hom(E,E)

  compose(inv,src) == tgt
  compose(inv,tgt) == src
  compose(inv,inv) == id(E)
end

@acset_type SymmetricGraph(SchSymmetricGraph, index=[:src])

3. Attributed ACSets (with Data)

@present SchWeightedGraph <: SchGraph begin
  Weight::AttrType
  weight::Attr(E, Weight)
end

@acset_type WeightedGraph(SchWeightedGraph, index=[:src,:tgt]){Float64}

GF(3) Conservation for ACSets

Integrate with Music Topos 3-coloring:

# Map ACSet parts to trits for GF(3) conservation
function acset_to_trits(g::Graph, seed::UInt64)
    rng = SplitMix64(seed)
    trits = Int[]
    for e in parts(g, :E)
        h = next_u64!(rng)
        hue = (h >> 16 & 0xffff) / 65535.0 * 360
        trit = hue < 60 || hue >= 300 ? 1 :
               hue < 180 ? 0 : -1
        push!(trits, trit)
    end
    trits
end

# Verify conservation: sum(trits) ≡ 0 (mod 3)
function gf3_conserved(trits)
    sum(trits) % 3 == 0
end

Gay.jl Color Bindings for @acset_colim (PR #990)

Since Catlab PR #990, @acset_colim exposes name→part bindings. Combine with Gay.jl for:

Named Part Coloring

using Gay

# Build ACSet with named parts
result, bindings = @acset_colim SchGraph begin
  e::E
  v1::V; v2::V
  src(e) == v1
  tgt(e) == v2
end

# Color each named part deterministically
seed = 0x114514
colors = Dict{Symbol, String}()
for (name, (ob, idx)) in bindings
    colors[name] = Gay.color_at(seed, idx)  # deterministic hex
end
# => Dict(:e => "#A855F7", :v1 => "#3B82F6", :v2 => "#10B981")

Two Modalities for XOR Validation

Modality 1: Different seeds (parallel verification)

seeds = [0x1, 0x2, 0x3]  # Three independent streams
colors_per_seed = [Gay.palette(s, length(bindings)) for s in seeds]

# XOR guarantee: if all three agree on structure, computation is stable
# Divergence → indicates floating-point or algorithmic instability

Modality 2: Same seed, staggered indices (convergence test)

seed = 0x114514

# Run same computation 3 times, color at indices 1, 2, 3
c1 = compute_and_color(data, seed, index=1)
c2 = compute_and_color(data, seed, index=2)  
c3 = compute_and_color(data, seed, index=3)

# Convergence: c1 == c2 == c3 within bounded iterations → stable
# Divergence: colors differ → numerical instability detected automatically

Empty Block = Initial Object = Neutral Color

# Empty block produces initial object (fixed in PR #990)
init, _ = @acset_colim SchGraph begin end  # ∅

# Initial object gets neutral/zero color (the "0" in GF(3))
neutral_color = Gay.color_at(seed, 0)  # or special "initial" marker

Bidirectional Index with Color Tags

struct ColoredACSet{T}
    acset::T
    bindings::Dict{Symbol, Tuple{Symbol, Int}}
    colors::Dict{Symbol, String}
    seed::UInt64
end

function colored_acset_colim(schema, seed, block)
    acset, bindings = @acset_colim schema block
    colors = Dict(name => Gay.color_at(seed, idx) 
                  for (name, (_, idx)) in bindings)
    ColoredACSet(acset, bindings, colors, seed)
end

# Lookup by name → part index → color (all directions)
# name → color: ca.colors[:v1]
# color → name: findfirst(==(hex), ca.colors)
# name → part: ca.bindings[:v1][2]

Instability Detection Pattern

function detect_instability(f, input, seed; tolerance=3)
    """
    Run f three times with same seed at staggered indices.
    If colors diverge beyond tolerance, flag instability.
    """
    results = [f(input) for _ in 1:3]
    colors = [Gay.color_at(seed, i) for i in 1:3]
    
    # Compare results - if they should be identical but aren't,
    # the divergent colors make the instability visually obvious
    for i in 1:3, j in i+1:3
        if results[i] ≠ results[j]
            @warn "Instability detected" color_i=colors[i] color_j=colors[j]
            return false
        end
    end
    true
end

This integrates the semantic naming from PR #990 with Gay.jl's deterministic coloring to create self-validating, visually debuggable ACSet constructions.

Specter-Style Bidirectional Navigation

Inspired by Nathan Marz's Specter library, navigate ACSets with paths that work for both select AND transform.

The Key Insight: comp-navs = alloc + field sets

From Marz: "comp-navs is fast because it's just object allocation + field sets"

# What comp_navs actually does:
comp_navs(a, b, c) = ComposedNav([a, b, c])  # That's it!
# No compilation, no interpretation, no optimization
# Just: allocate struct, set field, done

# All work happens at traversal via CPS:
nav_select(nav1, data, 
    r1 -> nav_select(nav2, r1,
        r2 -> nav_select(nav3, r2, identity)))

This means:

• O(1) composition - constant time path building
• Inline caching - paths compiled once per callsite
• Near-hand-written speed - CPS eliminates intermediate allocations

ACSet Navigators

using SpecterACSet

# Navigate morphism values
acset_field(:E, :src)         # All source vertex IDs
acset_field(:E, :tgt)         # All target vertex IDs

# Filter parts by predicate
acset_where(:E, :src, ==(1))  # Edges where src == 1

# Navigate all parts of an object
acset_parts(:V)               # All vertex IDs
acset_parts(:E)               # All edge IDs

Bidirectional Example

g = @acset Graph begin V=4; E=3; src=[1,2,3]; tgt=[2,3,4] end

# Select: get all source vertices
select([acset_field(:E, :src)], g)  # → [1, 2, 3]

# Transform: shift all targets (same path!)
g2 = transform([acset_field(:E, :tgt)], t -> mod1(t+1, 4), g)
select([acset_field(:E, :tgt)], g2)  # → [3, 4, 1]

Cross-Domain Bridge (Sexp ↔ ACSet)

# ACSet → Sexp → Navigate → Transform → Sexp → ACSet
sexp = sexp_of_acset(g)

# Navigate sexp to find all morphism names
morphism_names = select([SEXP_CHILDREN, sexp_nth(1), ATOM_VALUE], sexp)

# Roundtrip back to ACSet
g2 = acset_of_sexp(Graph, sexp)

Higher-Order Functions on ACSets

From Issue #7, implement functional patterns:

Open ACSets (Composable Interfaces)

# From Issue #89: Open versions of InterType ACSets
using ACSets.OpenACSetTypes

# Create open ACSet with exposed ports
@open_acset_type OpenGraph(SchGraph, [:V])

# Compose via pushout
g1 = OpenGraph(...)  # ports: v1, v2
g2 = OpenGraph(...)  # ports: v3, v4
g_composed = compose(g1, g2, [:v2 => :v3])

Why Simple Graphs Are Badly Behaved

The category of simple graphs does not even have a terminal object. Under the standard definition (symmetric, irreflexive edge relation), there's no "universal" graph that every other graph maps to uniquely. This reveals hidden assumptions in the simple graph model.

Simple graph: G = (V, E) where E is a binary relation on V that is:

• Symmetric: E(v,u) whenever E(u,v)
• Irreflexive: E(v,v) for no vertex v

Category theorist's graph: G consists of:

• Vertex set G(V)
• Edge set G(E)
• Functions G(src), G(tgt): G(E) → G(V)

This allows:

• Multiple edges between vertices (multigraph)
• Self-loops
• Edges as first-class citizens with identity

C-Sets: The Mathematical Foundation

A C-set is a functor X: C → Set where C is a small category (schema).

Schema C (small category)     C-set X (functor C → Set)
──────────────────────────    ─────────────────────────
Objects c ∈ C          ────▶  Sets X(c)
Morphisms f: c → d     ────▶  Functions X(f): X(c) → X(d)

Terminology

The Schema for Graphs

The schema Sch(Graph) is the category with:

• Two objects: E, V
• Two non-identity morphisms: src: E → V, tgt: E → V

    ┌───┐  src   ┌───┐
    │ E │───────▶│ V │
    │   │  tgt   │   │
    └───┘───────▶└───┘

A graph G is a Sch(Graph)-set, meaning:

• G(V) = set of vertices
• G(E) = set of edges
• G(src): G(E) → G(V) assigns source vertex to each edge
• G(tgt): G(E) → G(V) assigns target vertex to each edge

Creating Graphs in Catlab

using Catlab.CategoricalAlgebra
using Catlab.Graphs, Catlab.Graphics

# Create empty graph and add parts
g = Graph()
add_parts!(g, :V, 3)
add_parts!(g, :E, 4, src=[1,2,2,3], tgt=[2,3,3,3])

# Query incident edges (uses index)
incident(g, 3, :tgt)  # => [2, 3, 4]

# Graphs.jl-style convenience interface
g2 = Graph()
add_vertices!(g2, 3)
add_edges!(g2, [1,2,2,3], [2,3,3,3])

# Visualization
to_graphviz(g, node_labels=true, edge_labels=true)

Indexing for Efficient Queries

The index=[:src,:tgt] parameter creates inverse lookups:

@acset_type Graph(SchGraph, index=[:src,:tgt])

# Without index: O(|E|) to find edges incident to vertex
# With index: O(k) where k = number of incident edges

Symmetric Graphs (Undirected)

The schema for symmetric graphs extends the graph schema with an involution:

    ┌───┐  src   ┌───┐
    │ E │───────▶│ V │
    │   │  tgt   │   │
    │   │───────▶│   │
    │   │  inv   │   │
    │   │◀──────▶│   │
    └───┘        └───┘

Subject to equations:

inv ⨟ src = tgt
inv ⨟ tgt = src  
inv² = id_E

Meaning of Equations

For every edge e ∈ G(E):

• e.inv.src = e.tgt (inverted edge starts where original ends)
• e.inv.tgt = e.src (inverted edge ends where original starts)
• e.inv.inv = e (involution is self-inverse)

@present SchSymmetricGraph <: SchGraph begin
  inv::Hom(E,E)

  compose(inv,src) == tgt
  compose(inv,tgt) == src
  compose(inv,inv) == id(E)
end

@acset_type SymmetricGraph(SchSymmetricGraph, index=[:src])

# Create symmetric 4-cycle
g = SymmetricGraph()
add_vertices!(g, 4)
add_edges!(g, [1,2,3,4], [2,3,4,1])
# Creates 8 edges: 4 original + 4 inverses

Indexing Optimization

Only src needs indexing. Target queries use: incident(g, v, :tgt) = incident(g, v, :src) .|> (e -> g[e, :inv])

Blog Post Series

1. Graphs and C-sets I: What is a graph?
2. Graphs and C-sets II: Half-edges and rotation systems
3. Graphs and C-sets III: Reflexive graphs and C-set homomorphisms
4. Graphs and C-sets IV: Propositional logic of subgraphs

Half-Edge Graphs (Blog II)

Half-edges are paired by involution rather than having distinct source/target:

Schema Sch(HGraph):
    ┌───┐  vertex  ┌───┐
    │ H │─────────▶│ V │
    │   │   inv    │   │
    │   │◀────────▶│   │
    └───┘          └───┘

Equation: inv² = id_H

@present SchHalfEdgeGraph(FreeSchema) begin
  V::Ob
  H::Ob
  vertex::Hom(H,V)
  inv::Hom(H,H)

  compose(inv, inv) == id(H)
end

@acset_type HalfEdgeGraph(SchHalfEdgeGraph, index=[:vertex])

Dangling Edges

Fixed points h·inv = h are dangling edges — half-edges not paired with others, left at the boundary. Distinct half-edges h ≠ h' with h·inv = h' and same vertex are self-loops.

g = HalfEdgeGraph(3)
add_edges!(g, [1,2,3], [2,3,1])      # 6 paired half-edges
add_dangling_edges!(g, [1,1,3])      # 3 dangling half-edges (fixed points)

Schema Isomorphism: Symmetric ≅ Half-Edge

Functor F: Sch(SGraph) → Sch(HGraph):

V ↦ V
E ↦ H  
src ↦ vertex
tgt ↦ inv ⨟ vertex
inv ↦ inv

This is an isomorphism (invertible). The two perspectives are mathematically equivalent but have different interpretations.

Rotation Systems (Topological Graph Theory)

A rotation system adds a permutation σ on half-edges where cycles = vertices:

@present SchRotationGraph <: SchHalfEdgeGraph begin
  σ::Hom(H,H)
  compose(σ, vertex) == vertex  # cycles stay at same vertex
end

The schema Sch(RotSys) with just H, α (involution), σ (permutation) is a group — making rotation systems group actions.

Key theorem: Rotation systems ↔ cellular embeddings in oriented surfaces (1-1 correspondence).

Reflexive Graphs (Blog III)

A reflexive graph has a distinguished self-loop at each vertex:

    ┌───┐  src   ┌───┐  refl
    │ E │───────▶│ V │───────▶│ E │
    │   │  tgt   │   │        
    └───┘───────▶└───┘        

Equations:
  refl ⨟ src = id_V
  refl ⨟ tgt = id_V

@present SchReflexiveGraph <: SchGraph begin
  refl::Hom(V,E)

  compose(refl, src) == id(V)
  compose(refl, tgt) == id(V)
end

C-Set Homomorphisms

A homomorphism α: X → Y of C-sets is a natural transformation:

For each object c ∈ C: function α_c: X(c) → Y(c)
For each morphism f: c → d: naturality square commutes

    X(c) ──α_c──▶ Y(c)
      │             │
   X(f)           Y(f)
      ▼             ▼
    X(d) ──α_d──▶ Y(d)

Graph homomorphism: vertex map + edge map preserving src/tgt.

Reflexive graph homomorphism: additionally preserves refl, so can "collapse" edges onto reflexive loops — enables quotient operations.

Products of Graphs

Products computed pointwise: (G × H)(c) = G(c) × H(c)

Box product (graph theorist's "Cartesian product"): Pushout construction

function box_product(g::T, h::T)
  g₀, h₀ = T(nv(g)), T(nv(h))  # discrete subgraphs
  # ... pushout of inclusions with product projections
end

Terminal Objects and Generalized Elements

Terminal graph = self-loop.

• Graph without self-loops: no generalized elements (no morphisms from terminal)
• Reflexive graph: generalized elements = vertices (expected behavior)

This makes reflexive graphs more "geometric" — they discretize continuous spaces properly.

Propositional Logic of Subgraphs (Blog IV)

Sub-C-sets as propositions, logical connectives derived from adjoints.

Logical Connectives as Adjoints

Two Types of Negation

¬A (not-A, conservative): x ∈ ¬A iff no element reachable from x is in A

x ∈ (¬A)(c) iff x·f ∉ A(c') for ALL f: c → c' in C

~A (non-A, liberal complement): x ∈ ~A iff some element reaching x is not in A

x ∈ (~A)(c) iff x' ∉ A(c') for SOME f: c' → c and x' ∈ f⁻¹·x

Always: ¬A ≤ ~A (negation ⊆ complement)

Boundary, Expansion, Contraction

Law of Excluded Middle

A ∨ ¬A = ⊤ holds iff graph is discrete (no edges).

For connected graphs: excluded middle fails. This isn't a bug — it's topology speaking through logic.

Devil's Avocado Synthesis (GF(3) Review)

−1 Critique (Negative)

• Missing complexity analysis: Subobject lattices can explode combinatorially
• Schema isomorphism "≅" underspecified: Equivalence vs strict isomorphism matters for implementation
• Rotation → surfaces jump too fast: Hides Edmonds algorithm, genus, non-orientable cases
• Dangling edges unmotivated: Application to open systems/composition unstated
• Products need worked examples: Claims without small computations leave readers unable to verify
• Subobject logic assumes topos background: "Adjoints give connectives" requires Lawvere familiarity
• ¬ vs ~ notation collision: Conflicts with standard pseudocomplement usage
• No connection to ACSets.jl code: Gap between categorical exposition and macros

+1 Appreciation (Positive)

• Schema isomorphism reveals deep identity: Source-target graphs = half-edge graphs in different clothes
• Rotation systems as groups: Invertibility + algebraic topology without coordinates
• Dangling edges model open systems: Boundary conditions, interfaces solved structurally
• Reflexive homomorphisms = quotients done right: Contraction/abstraction as natural transformations
• Two negations unify constructive/classical: Failure of excluded middle is topology through logic
• ∂A = A ∧ ~A: Boundary operator derived from pure logic (Stokes theorem intuition)
• Product proliferation is a feature: Each schema choice gives different tensor product

0 Neutral Integration

The skill presents the neutral synthesis: rigorous definitions with practical Catlab code, acknowledging both the elegant mathematical structure and the implementation gaps.

Key References

• Reyes, Reyes & Zolfaghari (2004): Generic Figures and Their Glueings — C-sets as category actions
• Spivak (2009): Higher-Dimensional Models of Networks — C-sets for scientific modeling
• Lando & Zvonkin (2004): Graphs on Surfaces — Rotation systems, σ/α notation
• Gross & Tucker (1987): Topological Graph Theory — Cellular embeddings theorem
• Hell & Nešetřil (2004): Graphs and Homomorphisms — Nonexpansive maps, reflexive graphs
• Lawvere (1986): Categories of Spaces — Topos-theoretic perspective on reflexive graphs
• Hammack, Imrich & Klavžar (2011): Handbook of Product Graphs — Product taxonomy

Citation

@article{patterson2022categorical,
  title={Categorical data structures for technical computing},
  author={Patterson, Evan and Lynch, Owen and Fairbanks, James},
  journal={Compositionality},
  volume={4},
  number={5},
  year={2022},
  doi={10.32408/compositionality-4-5}
}

GeoACSets: Spatial + Categorical

GeoACSets.jl combines ACSets with geospatial capabilities:

Use morphisms for structural navigation, geometry for filtering.

SpatialCity Schema

# 4-level hierarchy: Region → District → Parcel → Building
@present SchSpatialCity(FreeSchema) begin
    Region::Ob
    District::Ob
    Parcel::Ob
    Building::Ob
    
    district_of::Hom(District, Region)
    parcel_of::Hom(Parcel, District)
    building_on::Hom(Building, Parcel)
    
    GeomType::AttrType
    region_geom::Attr(Region, GeomType)
    footprint::Attr(Building, GeomType)
end

@acset_type SpatialCity(SchSpatialCity, 
    index=[:district_of, :parcel_of, :building_on])

Traversal Patterns

# Downward: O(depth) via incident queries
buildings_in_region(city, region_id)

# Upward: O(1) via subpart lookups  
region_of_building(city, building_id)

# Combine spatial + morphism
nearby = spatial_filter(city, :Building, :footprint,
    g -> LibGEOS.distance(g, query_point) < 100)
for b in nearby
    district = traverse_up(city, b, :building_on, :parcel_of)
end

OlmoEarth/Terra Extension (Spatio-Temporal)

GeoACSets needs extension for foundation model integration:

SchOlmoEarthPatch

@present SchOlmoEarthPatch(FreeSchema) begin
    Patch::Ob           # Variable-size spatial patch
    Timestep::Ob        # Monthly temporal unit
    Modality::Ob        # Sentinel-1/2, Landsat, Maps
    Token::Ob           # Encoded representation
    View::Ob            # For instance contrastive
    
    patch_timestep::Hom(Patch, Timestep)
    patch_modality::Hom(Patch, Modality)
    token_patch::Hom(Token, Patch)
    
    # Masking as structured decomposition
    MaskedPatch::Ob
    MaskConfig::Ob
    masked_patch::Hom(MaskedPatch, Patch)
    mask_state::Attr(MaskedPatch, MaskStateType)  # encode/decode/both/none
end

Masking as Span Decomposition

# OlmoEarth masking creates:
#   EncodeBag ← Apex (both) → DecodeBag

function create_masking_decomposition(patches, config_id)
    encode_bag = filter(p -> mask_state(p) ∈ [:encode_only, :both], patches)
    decode_bag = filter(p -> mask_state(p) ∈ [:decode_only, :both], patches)
    apex = filter(p -> mask_state(p) == :both, patches)
    (encode_bag, apex, decode_bag)
end

Instance Contrastive as Sheaf Condition

# Two views must agree on pooled representation
function verify_sheaf_condition(patches; threshold=0.99)
    pooled1 = patches[view1, :pooled_repr]
    pooled2 = patches[view2, :pooled_repr]
    cosine_sim(pooled1, pooled2) >= threshold
end

Gay.jl Label Ontology for ACSets

Gay.jl uses a categorical label system on GitHub issues. These map directly to ACSet concepts:

Ternary Trit Labels (GF(3) Colors)

ACSet-Specific Labels

Sheaf Condition Labels

Chromatic (SPI) Labels

Spectral Analysis Labels

Coherence & Monoidal Labels

Health & Remediation Labels

Scoped Propagator Labels

Gay.jl × ACSet Integration Points

1. Subobject Classifier Ω (Issue #219)

Gay.jl implements topos-theoretic gamut classification:

# Truth values with distance semantics
struct GamutTruth
    in_gamut::Bool
    distance::Float64  # 0 = boundary, - = inside, + = outside
    boundary_hue::Float64
end

# Characteristic morphism χ: Color → Ω
χ_srgb = characteristic_morphism(GaySRGBGamut(), GayRec2020Gamut())
truth = χ_srgb(RGB(0.5, 0.8, 0.3))
# => GamutTruth(true, -0.2, 120.0)

# Pullback recovers subobject (sub-C-set!)
in_srgb = gamut_pullback(χ_srgb, colors)

ACSet connection: Subobject classifier Ω in topos of C-sets = propositional logic from Blog IV.

2. Operad of Scoped Propagators (Issue #201)

Propagators form an operad with ACSet adhesions:

# Operadic composition
P(n) = {n-ary propagators: (source₁,...,sourceₙ, target) → target'}

# Example composition
p: (a,b) → c    ∈ P(2)
q: (x) → a      ∈ P(1)  
r: (y,z) → b    ∈ P(2)

γ(p; q, r): (x, y, z) → c    ∈ P(3)

Colored operad: Types = Seed, Color, Sound, Contract

P(Seed → Color) ∘ P(Color → Sound) : P(Seed → Sound)

3. Obstruction Detection Framework (Issue #206)

7 obstruction detectors map to C-set/sheaf failures:

# Analyze obstructions
report = analyze_obstructions(1069)

# Mine for obstructed seeds
bad_seeds = mine_obstructed_seeds(1:1000, 10)

# Remediate
better_seed = remediate_spectral(SPISeed(35))

4. Čech Cohomology H^1 (Issue #212)

H^1 measures "how far from being a sheaf":

# H^1 = 0 → proper sheaf (sections glue)
# H^1 ≠ 0 → obstruction class exists

function cech_h1_obstruction(seed, depth=7)
    fingerprints = [xor_fingerprint(gay_split(seed, i)) for i in 1:depth]
    # Check if local fingerprints glue globally
    failures = count(i -> fingerprints[i] ⊻ fingerprints[i+1] ≠ expected[i], 1:depth-1)
    failures > 0  # true = obstruction detected
end

5. Coherence Violation Detection (Issue #214)

Mac Lane's pentagon and hexagon for monoidal categories:

# Pentagon identity for 4-way associativity
# ((a ⊗ b) ⊗ c) ⊗ d  must equal  a ⊗ (b ⊗ (c ⊗ d))
# via ANY path through the pentagon

function verify_pentagon(split_fn, seed)
    paths = enumerate_pentagon_paths(seed)
    all(p1 ≈ p2 for (p1, p2) in pairs(paths))
end

# Hexagon identity for braiding
function verify_hexagon(split_fn, seed)
    # σ_{a,b⊗c} = (1 ⊗ σ_{a,c}) ∘ (σ_{a,b} ⊗ 1)
    left_path = braid_then_tensor(seed)
    right_path = tensor_then_braid(seed)
    left_path ≈ right_path
end

6. Canonical Seed 1069: [+1, -1, -1, +1, +1, +1, +1]

The canonical seed used across Gay.jl issues:

seed = 1069
trits = [+1, -1, -1, +1, +1, +1, +1]  # 7-trit signature

# Properties:
# - Passes all spectral tests
# - Clean H^1 (no Čech obstructions)
# - Pentagon/hexagon coherent
# - health:composable (≥60 score)

7. ACSet Rewriting with Gay Colors

Local rewriting rules colored by Gay.jl:

using AlgebraicRewriting, Gay

# Rule: merge two vertices
rule = @rule SchGraph begin
    L = @acset begin v1::V; v2::V end
    R = @acset begin v::V end
    # L → R collapses v1, v2 → v
end

# Color the rewrite
seed = 1069
L_colors = Gay.palette(seed, nparts(L, :V))
R_colors = Gay.palette(seed, nparts(R, :V))

# Verify: rewrite preserves GF(3) trit sum
@assert gf3_conserved(L_colors) == gf3_conserved(R_colors)

8. Structured Decomposition Adhesions

From StructuredDecompositions.jl + Gay.jl:

# Adhesion = shared boundary between decomposition pieces
# Color adhesions to track gluing

struct ColoredAdhesion
    left_piece::ACSet
    right_piece::ACSet
    adhesion::ACSet  # shared sub-ACSet
    color::String    # Gay.jl deterministic color
end

function color_decomposition(decomp, seed)
    [ColoredAdhesion(
        piece.left, piece.right, piece.adhesion,
        Gay.color_at(seed, i)
    ) for (i, piece) in enumerate(decomp.pieces)]
end

Related Packages

• Catlab.jl: Full categorical algebra (homomorphisms, limits, colimits)
• AlgebraicRewriting.jl: Declarative rewriting for ACSets
• AlgebraicDynamics.jl: Compositional dynamical systems
• GeoACSets.jl: Spatial geometry + morphism navigation
• StructuredDecompositions.jl: Sheaf-based decision problems
• Gay.jl: Deterministic colors with SPI + sheaf obstruction detection

Xenomodern Integration

The ironic detachment comes from recognizing that:

1. Category theory isn't about abstraction for its own sake — it's about finding the right abstractions that compose
2. Simple graphs are actually badly behaved — the terminal object problem reveals hidden assumptions
3. Functors are data structures — this reframes databases as applied category theory

         xenomodernity
              │
    ┌─────────┴─────────┐
    │                   │
 ironic              sincere
detachment          engagement
    │                   │
    └─────────┬─────────┘
              │
      C-sets as functors
      (both ironic AND sincere)

Ramanujan Spectral Integration (NEW 2025-12-22)

ACSet-based edge growth with spectral constraints:

Ramanujan-Preserving Growth

@present SchRamanujanGraph <: SchGraph begin
  SpectralData::AttrType
  lambda2::Attr(V, SpectralData)  # Track λ₂ per growth step
end

function grow_edge_ramanujan!(G::ACSet, u, v)
    """
    Add edge preserving Ramanujan property.
    Uses Alon-Boppana bound: λ₂ ≥ 2√(d-1).
    """
    d = degree(G)
    bound = 2 * sqrt(d - 1)
    
    # Tentatively add edge
    add_part!(G, :E, src=u, tgt=v)
    
    # Check spectral constraint
    λ₂ = second_eigenvalue(adjacency_matrix(G))
    
    if λ₂ > bound + 0.01  # Tolerance
        # Rollback: remove edge
        rem_part!(G, :E, nparts(G, :E))
        return false
    end
    
    return true
end

Non-Backtracking Edge Schema (Ihara Zeta)

@present SchNonBacktracking(FreeSchema) begin
  V::Ob; E::Ob; DE::Ob  # DE = directed edges
  src::Hom(E,V); tgt::Hom(E,V)
  forward::Hom(E, DE); backward::Hom(E, DE)
  de_src::Hom(DE, V); de_tgt::Hom(DE, V)
  
  # Non-backtracking constraint: head(e) = tail(f) ∧ e ≠ f⁻¹
  nonbacktrack::Hom(DE, DE)  # B matrix as morphism
end

# Ihara zeta via ACSet homomorphisms
function prime_cycles(G::ACSet, max_length)
    cycles = []
    for k in 1:max_length
        if moebius(k) != 0  # Only squarefree lengths
            push!(cycles, find_cycles(G, k))
        end
    end
    return cycles
end

Centrality via Möbius Inversion

function alternating_centrality(G::ACSet)
    """
    Centrality via Möbius-weighted path counts.
    c(v) = Σ_{k} μ(k) × paths_k(v) / k
    """
    n = nparts(G, :V)
    A = adjacency_matrix(G)
    c = zeros(n)
    
    for k in 1:diameter(G)
        μ_k = moebius(k)
        if μ_k != 0
            paths_k = diag(A^k)
            c .+= μ_k .* paths_k ./ k
        end
    end
    
    return c ./ sum(abs.(c))
end

StructACSet Internals (DeepWiki 2025-12-22)

Schema and attribute types known at compile time, enabling performance optimizations.

Type Parameters

StructACSet{S, Ts, PT}
# S  = TypeLevelSchema{Symbol} - schema at compile time
# Ts = Tuple of Julia types for attributes (e.g., Float64 for Weight)
# PT = PartsType strategy (IntParts or BitSetParts)

Column Storage

struct StructACSet{S, Ts, PT}
  parts::NamedTuple     # {:V => IntParts, :E => IntParts, ...}
  subparts::NamedTuple  # {:src => Column, :tgt => Column, :weight => Column, ...}
end

# Column types:
# - Homs: Vector{Int} mapping parts to parts
# - Attrs: Vector{Union{AttrVar,T}} for attribute values

Index Configuration

@acset_type Graph(SchGraph, 
    index=[:src, :tgt],         # Preimage cache: O(1) incident queries
    unique_index=[:inv]          # Injective cache: even faster
)

# Index types:
# - NoIndex: Linear scan O(n)
# - Index (StoredPreimageCache): O(1) average via hash
# - UniqueIndex (InjectiveCache): O(1) guaranteed, injective morphisms only

Part ID Allocation Strategies

# IntParts (default): contiguous IDs 1..n
add_parts!(G, :V, 3)  # IDs: 1, 2, 3
rem_part!(G, :V, 2)   # ID 3 → 2, ID 2 gone

# BitSetParts: sparse IDs with gaps
rem_part!(G, :V, 2)   # ID 2 marked deleted, ID 3 unchanged
gc!(G)                # Compact: removes gaps

Julia Scientific Package Integration

From julia-scientific skill - the full Julia package ecosystem that builds on ACSets:

The Homoiconic Bridge: Scheme ↔ SMILES ↔ ACSet

Deep structural insight: S-expressions (Scheme), SMILES strings (chemistry), and ACSets share the same foundation — trees/graphs with recursive self-reference:

S-expression:  (+ (* 2 3) (- 4 1))    → AST tree
SMILES:        CC(=O)Oc1ccccc1C(=O)O  → Molecular graph
ACSet:         Graph{V,E,src,tgt}      → Typed graph functor

All three: linearized representations of graph structure

# The bridge in code
using LispSyntax, MolecularGraph, Catlab

# Scheme → AST graph
sexp = @lisp (defun factorial (n) (if (<= n 1) 1 (* n (factorial (- n 1)))))
ast_graph = ast_to_acset(sexp)

# SMILES → Molecular graph
mol = smilestomol("CC(=O)Oc1ccccc1C(=O)O")  # Aspirin
mol_graph = mol_to_acset(mol)

# Both are ACSets! Same navigation works:
select([ALL, pred(is_branch_node)], ast_graph)
select([ALL, pred(is_ring_atom)], mol_graph)

What Comes After SMILES: Learnable Chemical Structure

The evolution: 7 parallel streams colored via Gay.jl (seed=137):

Parallel streams evolve independently — each generation has its own color trajectory:

Stream 1 (SMILES):      #43D9E1 → #B78225 → #D54E82
Stream 5 (GNN):         #E44ABB → #50CD2E → #942B89  (MPNN → GAT → SchNet)
Stream 7 (Foundation):  #BDB223 → #88ECA7 → #5CDA99

# From SMILES to learnable representation
using MolecularGraph, ChemistryFeaturization, AtomicGraphNets

mol = smilestomol("CCO")  # ethanol

# 1. Featurize (handcrafted → learnable)
fg = featurize(mol, GraphNodeFeaturization())

# 2. GNN embedding (fully learnable)
model = CGCGNModel(fg)
embedding = model(fg)  # 64-dim learned vector

# 3. This embedding captures chemical meaning
# similar molecules → similar embeddings

Spectral Bundle Triads (GF(3) Conserved)

ramanujan-expander (-1) ⊗ acsets (0) ⊗ gay-mcp (+1) = 0 ✓  [Graph Coloring]
ramanujan-expander (-1) ⊗ acsets (0) ⊗ moebius-inversion (+1) = 0 ✓  [Edge Growth]
ihara-zeta (-1) ⊗ acsets (0) ⊗ moebius-inversion (+1) = 0 ✓  [Prime Cycles]
sheaf-cohomology (-1) ⊗ acsets (0) ⊗ gay-mcp (+1) = 0 ✓  [ACSet Navigation]
scheme-lisp (-1) ⊗ acsets (0) ⊗ molecular-gnn (+1) = 0 ✓  [Homoiconic Bridge]

Related Spectral Skills

• ramanujan-expander: Alon-Boppana spectral bounds, LPS construction
• ihara-zeta: Non-backtracking walks, prime cycles, Graph RH
• moebius-inversion: Poset inversion, chromatic polynomials, μ(3) = -1
• deepwiki-mcp: Repository documentation (trit 0, substitutes in triads)

r2con Speaker Resources

Zignature and categorical database repositories from r2con speakers:

…(truncated)