Pushout of sheaves over pushout of graphs

[jpfairbanks]

Feature Request: Pushout of Sheaves Over a Span of Graph Homomorphisms

Prerequisites

This feature depends on prior features -- make sure we merge those first #9 #10 #11

1. Fixed-graph pushout: pushout_sheaf(f, g, FK, FG, FH) in
   src/network_sheaves/Morphisms.jl (or Pushouts.jl)
2. Graph pushout: graph_pushout(φ, ψ, G, H, K) and compose in
   src/network_sheaves/GraphHomomorphisms.jl

Mathematical Background

Given a span of graph homomorphisms G ←φ— K —ψ→ H and sheaves F_G, F_K, F_H
with morphisms f : F_K → F_G over φ and g : F_K → F_H over ψ, the pushout
is a sheaf P on Q = G ⊔_K H with canonical morphisms iG : F_G → P and
iH : F_H → P, universal among all such cocones.

Reduction to existing operations

Step 1 — Compute Q, jG, jH = graph_pushout(φ, ψ, G, H, K).

Step 2 — Pushforward both feet onto Q this is the action of the canonical graph inclusions (jG, jH) on the feet of the span of sheaves:

• PF_G = pushforward_sheaf(jG, FG)
• PF_H = pushforward_sheaf(jH, FH)

Step 3 — Form the induced span over the fixed graph Q. Since Q is the pushout
of graphs, jG ∘ φ = jH ∘ ψ; call this map κ = compose(φ, jG) : K → Q. Then:

• PF_K = pushforward_sheaf(κ, FK)
• Derive induced morphisms pf_f : PF_K → PF_G and pf_g : PF_K → PF_H

Step 4 — Apply the fixed-graph pushout:
P, iG, iH = pushout_sheaf(pf_f, pf_g, PF_K, PF_G, PF_H)

Codebase Orientation

Files to read before writing any code:

File	Why
src/network_sheaves/GraphHomomorphisms.jl	GraphHomomorphism, compose, graph_pushout (from Issue A)
src/network_sheaves/Pushforwards.jl	pushforward_sheaf, all_fiber_bases, fiber_vertices — all reused
src/network_sheaves/Morphisms.jl	SheafMorphism, pushout_sheaf (from fixed-graph prerequisite)
src/network_sheaves/EuclideanSheaves.jl	EuclideanSheaf{T} fields
src/network_sheaves/NetworkSheaves.jl	Module aggregator — add include and export
test/runtests.jl	Add include for the new test file

Types:

• SheafMorphism — Vmap::Vector{Int} encodes the underlying graph homomorphism;
  Vmaps::Vector and Emaps::Vector hold per-stalk linear maps
• GraphHomomorphism — vertex_map::Vector{Int}, n_target::Int
• pushforward_sheaf(hom, F) — already implemented in Pushforwards.jl
• pushout_sheaf(f, g, FK, FG, FH) — implemented in prerequisite Issue Implement pushout of cellular sheaves over a fixed graph #9 / PR Implement categorical pushout of cellular sheaves over a fixed graph #10

Requested Implementation

New file

Create src/network_sheaves/PushoutSheaves.jl. Include it from NetworkSheaves.jl.

Top-level function

"""
    pushout_sheaf_over_span(f::SheafMorphism, g::SheafMorphism,
                            FK, FG, FH)
        -> (EuclideanSheaf, SheafMorphism, SheafMorphism)

Compute the pushout of the diagram

    (G, FG) <--f-- (K, FK) --g--> (H, FH)

where f and g are sheaf morphisms over graph homomorphisms φ = GraphHomomorphism(f.Vmap)
and ψ = GraphHomomorphism(g.Vmap).

Returns `(P, iG, iH)` where P is the pushout sheaf on G ⊔_K H, and iG, iH are
the canonical sheaf morphisms.
"""
function pushout_sheaf_over_span(f::SheafMorphism, g::SheafMorphism,
                                 FK::EuclideanSheaf,
                                 FG::EuclideanSheaf,
                                 FH::EuclideanSheaf)
    φ  = GraphHomomorphism(f.Vmap)
    ψ  = GraphHomomorphism(g.Vmap)
    nK = nv(FK.underlying_graph)

    _, jG, jH = graph_pushout(φ, ψ, FG.underlying_graph, FH.underlying_graph, nK)

    PF_G = pushforward_sheaf(jG, FG)
    PF_H = pushforward_sheaf(jH, FH)

    k    = compose(φ, jG)
    PF_K = pushforward_sheaf(k, FK)
    pf_f = induced_sheaf_morphism(f, φ, jG, FK, FG, PF_K, PF_G)
    pf_g = induced_sheaf_morphism(g, ψ, jH, FK, FH, PF_K, PF_H)

    return pushout_sheaf(pf_f, pf_g, PF_K, PF_G, PF_H)
end

Key private helper: induced_sheaf_morphism

This is the hardest step. Given original morphism f : FK → FG over φ : K → G, and
the pushforwards PF_K = k_* FK and PF_G = (jG)_* FG, produce a SheafMorphism
pf_f : PF_K → PF_G over the identity on Q.

For each target vertex u ∈ Q:

1. BK = all_fiber_bases(k, FK)[u] — orthonormal basis matrix for PF_K's stalk at u
2. BG = all_fiber_bases(jG, FG)[u] — same for PF_G
3. Let verts_K = fiber_vertices(k, u). For each basis column b of BK:
   • Split b into per-vertex blocks according to the stalk dimensions of FK at verts_K
   • Apply f.Vmaps[v] to each block (where v is the position of the K-fiber vertex in f.Vmap)
   • Reassemble into a vector in ⊕_{w ∈ fiber_vertices(jG, u)} FG(w)
   • Project onto BG via BG' * result (BG is orthonormal)
4. The stalk map matrix for pf_f at u has size size(BG, 2) × size(BK, 2)

The identity Vmap for pf_f is collect(1:nv(Q)) (morphism over identity graph map).

Tests to Write

Create test/network_sheaves/PushoutSheaves.jl, include from test/runtests.jl.

Concrete test setup

using Graphs
K = path_graph(2)           # 2 vertices, 1 edge
G = path_graph(3)           # 3 vertices, 2 edges
H = path_graph(3)

φ = GraphHomomorphism([1, 2], 3)   # K → G: vertex 1→1, 2→2
ψ = GraphHomomorphism([2, 3], 3)   # K → H: vertex 1→2, 2→3
# Pushout should be a 4-vertex path

# 1-dimensional stalks, identity restriction maps everywhere
FK = sheaf_from_graph(K, 1, (v1,v2) -> (ones(1,1), ones(1,1)))
FG = sheaf_from_graph(G, 1, (v1,v2) -> (ones(1,1), ones(1,1)))
FH = sheaf_from_graph(H, 1, (v1,v2) -> (ones(1,1), ones(1,1)))

# Identity sheaf morphisms (f.Vmaps[v] = I for all v)
f = SheafMorphism(φ.vertex_map, <edge_map>, [ones(1,1), ones(1,1)], [...])
g = SheafMorphism(ψ.vertex_map, <edge_map>, [ones(1,1), ones(1,1)], [...])

Test cases

1. Pushout graph is correct

P, iG, iH = pushout_sheaf_over_span(f, g, FK, FG, FH)
@test nv(P.underlying_graph) == 4
@test ne(P.underlying_graph) == 3

2. Canonical morphisms are valid

@test is_morphism(iG, FG, P)
@test is_morphism(iH, FH, P)

3. Commutativity of the sheaf square

iG_cm  = ComplexMorphism(FG,  P,    iG)
iH_cm  = ComplexMorphism(FH,  P,    iH)
pf_f_cm = ComplexMorphism(PF_K, PF_G, pf_f)
pf_g_cm = ComplexMorphism(PF_K, PF_H, pf_g)
@test norm(iG_cm.V * pf_f_cm.V - iH_cm.V * pf_g_cm.V) < 1e-10
@test norm(iG_cm.E * pf_f_cm.E - iH_cm.E * pf_g_cm.E) < 1e-10

4. Disjoint union as degenerate case
With K = empty graph (nK = 0), the pushout sheaf on G ⊔ H should have stalks
equal to the direct sum of FG and FH stalks at corresponding vertices.

Verification Checklist

• nv(P.underlying_graph) and ne(P.underlying_graph) match expected pushout graph
• compose(φ, jG).vertex_map == compose(ψ, jH).vertex_map (verified internally)
• is_morphism(iG, FG, P) and is_morphism(iH, FH, P) both true
• Commutativity of the sheaf square within 1e-10
• No new entries in Project.toml
• All prior tests still pass: julia --project=. test/runtests.jl
• New tests pass

Out of Scope

• Pullback of sheaves (dual construction)
• DSL (@cellular_sheaf) extensions
• Compatibility with PotentialSheaf or ConicSheaf