acsets-algebraic-databases

ACSets (Attributed C-Sets): Algebraic databases with Specter-style bidirectional

Jump to install

Repository: plurigrid/asi
Last source activity: June 10, 2026 at 11:55
Detected SKILL.md language: English
Stars: 56
Forks: 13

Install options

The review-first prompt is selected by default. You can switch to a direct command or download a local copy.

Review the source files

Read SKILL.md and any companion files shown by SkillsMP before deciding whether to install.

Back to search Back to installation

name	acsets-algebraic-databases
description	ACSets (Attributed C-Sets): Algebraic databases with Specter-style bidirectional
version	1.0.0

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)                                 │
└─────────────────────────────────────────────────────────────┘

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])

@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])

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

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

# 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

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")

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

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 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

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]

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

# 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)))

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

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]

# 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)

# 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])

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)

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

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)

@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

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

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

@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

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])

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)

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

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

    ┌───┐  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

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)

Type	Product Name	Behavior
Graph	Categorical product	Disconnected diagonal paths
ReflexiveGraph	Categorical product	Grid with connections (reflexive loops fill gaps)
SymmetricGraph	Direct/tensor product	May split into components (bipartite → 2 components)
SymmetricReflexiveGraph	Strong product	Full grid connectivity

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

Connective	Definition	Meaning
A ∧ B	Right adjoint of Δ	Greatest lower bound (meet)
A ∨ B	Left adjoint of Δ	Least upper bound (join)
⊤	Right adjoint of !	Top element (full subgraph)
⊥	Left adjoint of !	Bottom element (empty)
B ⇒ C	Right adjoint of (−) ∧ B	Implication (exponential)
¬A	A ⇒ ⊥	Negation (Heyting)

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

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

Operation	Formula	For Graphs
Boundary	∂A = A ∧ ~A	Vertices in A connected to outside
Induced	¬¬A	Same vertices, all edges between them
Expansion	~¬A	A plus one layer outward
Contraction	¬~A	A minus one layer inward

@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}
}

# 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])

# 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

@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

# 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

# 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

Label	Color	Description
`sheaf:descent`	#97286e	Descent condition verification
`sheaf:covering`	#282e69	Covering sieve/condition
`sheaf:gluing`	#28a289	Gluing axiom / section construction
`sheaf:obstruction`	#96a428	Non-sheaf witness / descent failure

Label	Color	Description
`chromatic:spi`	#37dc48	Strong Parallelism Invariant
`chromatic:fingerprint`	#59dc8a	XOR fingerprint composition
`chromatic:propagation`	#93b7bd	Color propagation rules
`chromatic:split`	#92b8c8	gay_split() ancestry

Label	Color	Description
`spectral:fourier`	#282c5c	FFT/DFT presheaf operations
`spectral:periodicity`	#b24b60	Periodic structure detection
`spectral:quasi`	#6991dc	Quasi-sheaf / boundary cases
`spectral:threshold`	#28bc3f	Threshold boundary analysis

Label	Color	Description
`coherence:pentagon`	#f97316	Mac Lane pentagon identity
`coherence:hexagon`	#ef4444	Mac Lane hexagon identity
`monoidal:symmetric`	#a855f7	Symmetric monoidal structure
`logic:separation`	#6366f1	Separation logic for ownership

Label	Color	Description
`health:composable`	#10b981	Health score ≥60, composable seed
`health:obstructed`	#f43f5e	Health score <60, obstructed seed
`remediation:spectral`	#22c55e	Spectral obstruction remediation
`remediation:mixing`	#14b8a6	Additional mixing rounds

Label	Color	Description
`scope:change`	#b0dcb4	Propagator fires on property change
`scope:geo`	#36599a	Propagator fires on spatial overlap
`scope:tick`	#9f9565	Propagator fires on frame/timestep
`scope:click`	#472835	Propagator fires on explicit trigger

# 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)

# 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)

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

Detector	ACSet Interpretation
`spectral`	FFT presheaf descent failure
`linear`	LFSR complexity (non-randomness)
`gcd`	Marsaglia GCD test
`birthday`	Collision spacing
`cech`	H^1 cohomology = gluing failure
`fingerprint`	XOR collision = non-uniqueness
`coherence`	Pentagon/hexagon = associativity failure

# 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))

# 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

# 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

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)

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)

# 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

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

@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

@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

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{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)

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

@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

# 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

Package	Category	ACSet Integration
Catlab.jl	Core	Schema definitions, morphisms
AlgebraicRewriting.jl	Rewriting	Double-pushout rewriting
StructuredDecompositions.jl	Sheaves	Tree decomposition sheaves
AlgebraicDynamics.jl	Dynamics	Compositional ODEs
DataFrames.jl	Data	Tabular data (special case)
Graphs.jl	Networks	Graph ACSet instances
MolecularGraph.jl	Chemistry	Molecular graphs
BioStructures.jl	Bioinformatics	Protein structure graphs
GraphNeuralNetworks.jl	ML	GNN on ACSet graphs

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)

Gen	Color	Representation	Julia Package	Learnable?
1	`#43D9E1`	SMILES	MolecularGraph.jl	No
2	`#18CDEF`	SELFIES	PyCall+selfies	No
3	`#18D6D0`	Fingerprints	MolecularGraph.jl	Partially
4	`#C70D22`	Graph features	ChemistryFeaturization.jl	Partially
5	`#E44ABB`	GNN (MPNN/GAT/SchNet)	GraphNeuralNetworks.jl	Yes
6	`#58A021`	3D coordinates	Chemfiles.jl, DFTK.jl	Yes
7	`#BDB223`	Foundation	GraphNeuralNetworks.jl	Fully

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

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]

Speaker	Repository	Relevance
bmorphism	bmorphism/r2-zignatures	Function zigs as ACSet parts
bmorphism	bmorphism/Gay.jl	Deterministic coloring for ACSet viz
pancake	radare2/radare2	CFG schema as C-Set functor
swoops	swoops/libc_zignatures	Signature database (ACSet rows)
condret	radareorg/r2ghidra	ESIL → ACSet morphism

just acset-demo          # Run ACSet demonstration
just acset-graph         # Create and visualize graph
just acset-symmetric     # Symmetric graph example
just acset-gf3           # Check GF(3) conservation

# ∫G objects: (Ob, part_id) pairs
# Navigate to all elements
select([elements_of(:V)], g)  # → [(V,1), (V,2), (V,3), (V,4)]

# Navigate morphism structure
select([elements_of(:E), incident_to(:src, 1)], g)  # Edges from vertex 1

acsets (○) + SDF.Ch9 (○) + [balancer] (○) = 0