Labelled Graphs

This example demonstrates how to define new C-Sets from existing C-Sets via the example of adding labels to a graph. We treat labels as members of an arbitrary FinSet of labels rather than a data attribute for pedagogical reasons. When you think of graphs where the labels are numbers, colors, or values of some kind, you would want to make them attributes. The motivation for this example is to be the simplest extension to the theory of graphs that you could possibly make.

using Catlab, Catlab.Theories
using Catlab.CategoricalAlgebra
using Catlab.Graphs
using Catlab.Graphics
using Catlab.Graphics.Graphviz
using Colors
draw(g) = to_graphviz(g, node_labels=true, edge_labels=true)
draw (generic function with 1 method)

We start with the theory of graphs, which is copied from Catlab.Graphs.BasicGraphs. The two objects are the edges and vertices and we have two functions src,tgt that assign to every edge the source vertex and target vertex respectively. Functors from this category to Set (diagrams in Set of this shape) are category theoretic graphs (directed multigraphs).

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

to_graphviz(Catlab.Graphs.BasicGraphs.TheoryGraph)
G n1 V n2 E n2->n1 src n2->n1 tgt

To the theory of graphs we want to add a set of labels L and map that assigns to every vertex to its label in L.

@present TheoryLGraph <: TheoryGraph begin
  L::Ob
  label::Hom(V,L)
end
Presentation{Schema, Symbol}(Catlab.Theories.FreeSchema, (Ob = Catlab.Theories.FreeSchema.Ob{:generator}[V, E, L], Hom = Catlab.Theories.FreeSchema.Hom{:generator}[src, tgt, label], AttrType = Catlab.Theories.FreeSchema.AttrType{:generator}[], Attr = Catlab.Theories.FreeSchema.Attr{:generator}[]), Dict(:src => (:Hom => 1), :label => (:Hom => 3), :L => (:Ob => 3), :V => (:Ob => 1), :E => (:Ob => 2), :tgt => (:Hom => 2)), Pair[])

Catlab will automatically generate all the data structure and algorithms (storing, mutating, serializing, etc.) our LGraphs for us. This snippet declares that the Julia type LGraph should be composed of objects of the functor category TheoryLGraph → Skel(FinSet), where Skel(FinSet) is the subcategory of Set containing finite sets 1:n. We want our Julia type LGraph to inherit from the Graphs.jl type AbstractGraph so that we can run graph algorithms on it. And we want the generated data structures to make an index of the maps src, tgt, and label so that looking up the in and outneighbors of vertex is fast and accessing all vertices by label is also fast.

@acset_type LGraph(TheoryLGraph, index=[:src,:tgt,:label]) <: AbstractGraph

We need to tell Catlab how to convert our LGraph type into the normal Graph type by taking just the edges and vertices. This could be computed with Functorial Data Migration, but that is left for another sketch.

to_graph(g::LGraph) = begin
  h = Graphs.Graph(nparts(g,:V))
  for e in edges(g)
    add_edge!(h, g[e, :src], g[e,:tgt])
  end
  return h
end
to_graph (generic function with 1 method)

Graphviz doesn't automatically know how we want to draw the labels, so we have to explicitly provide code that converts them to colors on the vertices. Note that we aren't calling these colored graphs, because that would imply some connectivity constraints on which vertices are allowed to be colored with the same colors. These labels are arbitrary, but we use color to visually encode them.

GraphvizGraphs.to_graphviz(g::LGraph; kw...) =
  to_graphviz(GraphvizGraphs.to_graphviz_property_graph(g; kw...))

function GraphvizGraphs.to_graphviz_property_graph(g::LGraph; kw...)
  h = to_graph(g)
  pg = GraphvizGraphs.to_graphviz_property_graph(h; kw...)
  vcolors = hex.(range(colorant"#0021A5", stop=colorant"#FA4616", length=nparts(g, :L)))
  for v in vertices(g)
    l = g[v, :label]
    set_vprops!(pg, v, Dict(:color => "#$(vcolors[l])"))
  end
  pg
end

draw(G::LGraph) = to_graphviz(G, node_labels=true, edge_labels=true)
draw (generic function with 2 methods)

Now we can start making some LGraph instances.

G = @acset LGraph begin
  V = 4
  E = 4
  L = 4
  src = [1,1,2,3]
  tgt = [2,3,4,4]
  label = [1,2,3,4]
end

draw(G)
G n1 1 n2 2 n1->n2 1 n3 3 n1->n3 2 n4 4 n2->n4 3 n3->n4 4

The graph G has a 1-1 map between vertices and labels. That isn't necessary.

H = @acset LGraph begin
  V = 4
  E = 4
  L = 3
  src = [1,1,2,3]
  tgt = [2,3,4,4]
  label = [1,2,2,3]
end

draw(H)
G n1 1 n2 2 n1->n2 1 n3 3 n1->n3 2 n4 4 n2->n4 3 n3->n4 4

We can look at some homomorphisms from G to H by their action on the labels or on the vertices.

homsᵥ(G,H) = map(α -> α[:V], homomorphisms(G, H))
homsₗ(G,H) = map(α -> α[:L], homomorphisms(G, H))
homsₗ (generic function with 1 method)

αₗ: G→ H

homsₗ(G,H)
4-element Vector{Catlab.CategoricalAlgebra.FinSets.FinDomFunctionVector{Int64, Vector{Int64}, Catlab.CategoricalAlgebra.FinSets.FinSetInt}}:
 FinFunction([1, 2, 2, 3], 4, 3)
 FinFunction([1, 2, 2, 3], 4, 3)
 FinFunction([1, 2, 2, 3], 4, 3)
 FinFunction([1, 2, 2, 3], 4, 3)

αᵥ: G→ H

homsᵥ(G,H)
4-element Vector{Catlab.CategoricalAlgebra.FinSets.FinDomFunctionVector{Int64, Vector{Int64}, Catlab.CategoricalAlgebra.FinSets.FinSetInt}}:
 FinFunction([1, 2, 2, 4], 4, 4)
 FinFunction([1, 2, 3, 4], 4, 4)
 FinFunction([1, 3, 2, 4], 4, 4)
 FinFunction([1, 3, 3, 4], 4, 4)

Note that if we reverse the direction of our homomorphism search, we get fewer matches even though the two LGraphs are isomorphic as graphs. The fact that in H vertex two and three are the same label means we have to send them to the same vertex in G.

homsᵥ(H,G)
2-element Vector{Catlab.CategoricalAlgebra.FinSets.FinDomFunctionVector{Int64, Vector{Int64}, Catlab.CategoricalAlgebra.FinSets.FinSetInt}}:
 FinFunction([1, 2, 2, 4], 4, 4)
 FinFunction([1, 3, 3, 4], 4, 4)

We can build some bigger examples like A.

A = @acset LGraph begin
  V = 6
  E = 7
  L = 3
  src = [1,1,2,3,2,5,4]
  tgt = [2,3,4,4,5,6,6]
  label = [1,2,2,3,2,3]
end
draw(A)
G n1 1 n2 2 n1->n2 1 n3 3 n1->n3 2 n4 4 n2->n4 3 n5 5 n2->n5 5 n3->n4 4 n6 6 n4->n6 7 n5->n6 6

and B.

B = @acset LGraph begin
  V = 6
  E = 7
  L = 4
  src = [1,1,2,3,2,5,4]
  tgt = [2,3,4,4,5,6,6]
  label = [1,2,4,3,2,3]
end
draw(B)
G n1 1 n2 2 n1->n2 1 n3 3 n1->n3 2 n4 4 n2->n4 3 n5 5 n2->n5 5 n3->n4 4 n6 6 n4->n6 7 n5->n6 6

The morphisms from A to B and B to A are also different, showing how the labels affect the structure in this category.

homsᵥ(A,B)
1-element Vector{Catlab.CategoricalAlgebra.FinSets.FinDomFunctionVector{Int64, Vector{Int64}, Catlab.CategoricalAlgebra.FinSets.FinSetInt}}:
 FinFunction([1, 2, 2, 4, 5, 6], 6, 6)

There are more morphisms from B to A than A to B.

homsᵥ(B,A)
2-element Vector{Catlab.CategoricalAlgebra.FinSets.FinDomFunctionVector{Int64, Vector{Int64}, Catlab.CategoricalAlgebra.FinSets.FinSetInt}}:
 FinFunction([1, 2, 2, 4, 5, 6], 6, 6)
 FinFunction([1, 2, 3, 4, 5, 6], 6, 6)

There are two automorphisms on A

homsᵥ(A,A)
2-element Vector{Catlab.CategoricalAlgebra.FinSets.FinDomFunctionVector{Int64, Vector{Int64}, Catlab.CategoricalAlgebra.FinSets.FinSetInt}}:
 FinFunction([1, 2, 2, 4, 5, 6], 6, 6)
 FinFunction([1, 2, 3, 4, 5, 6], 6, 6)

And two automorphisms on B

homsᵥ(B,B)
2-element Vector{Catlab.CategoricalAlgebra.FinSets.FinDomFunctionVector{Int64, Vector{Int64}, Catlab.CategoricalAlgebra.FinSets.FinSetInt}}:
 FinFunction([1, 2, 2, 4, 5, 6], 6, 6)
 FinFunction([1, 2, 3, 4, 5, 6], 6, 6)

But if we forget about the labels and look at the automorphisms of the underlying graph, we get more automorphisms!

A₀ = to_graph(A)
homsᵥ(A₀, A₀)
8-element Vector{Catlab.CategoricalAlgebra.FinSets.FinDomFunctionVector{Int64, Vector{Int64}, Catlab.CategoricalAlgebra.FinSets.FinSetInt}}:
 FinFunction([1, 2, 2, 4, 4, 6], 6, 6)
 FinFunction([1, 2, 2, 4, 5, 6], 6, 6)
 FinFunction([1, 2, 2, 5, 4, 6], 6, 6)
 FinFunction([1, 2, 2, 5, 5, 6], 6, 6)
 FinFunction([1, 2, 3, 4, 4, 6], 6, 6)
 FinFunction([1, 2, 3, 4, 5, 6], 6, 6)
 FinFunction([1, 3, 2, 4, 4, 6], 6, 6)
 FinFunction([1, 3, 3, 4, 4, 6], 6, 6)

Limits and Composition by Multiplication

Catlab has an implementation of limits for any C-Sets over any schema. So, we can just ask about labelled graphs. Notice that we get more distinct colors in the product than in either initial graph. This is because the labels of the product are pairs of labels from the factors. If G has n colors and H has m colors G×H will have n×m colors.

draw(apex(product(G,G)))
G n1 1 n6 6 n1->n6 1 n7 7 n1->n7 2 n10 10 n1->n10 5 n11 11 n1->n11 6 n2 2 n8 8 n2->n8 3 n12 12 n2->n12 7 n3 3 n3->n8 4 n3->n12 8 n4 4 n5 5 n14 14 n5->n14 9 n15 15 n5->n15 10 n16 16 n6->n16 11 n7->n16 12 n9 9 n9->n14 13 n9->n15 14 n10->n16 15 n11->n16 16 n13 13

The graph above looks weirdly disconnected and probably wasn't what you expected to see as the product. When we compose with products, we often want to add the reflexive edges in order to get the expected notion of product.

add_loops!(G::LGraph) = begin
  for v in parts(G,:V)
    add_edge!(G, v,v)
  end
  return G
end
add_loops(G::LGraph) = add_loops!(copy(G))

Gᵣ = add_loops(G)
P = apex(product(Gᵣ, G))
draw(apex(product(Gᵣ, G)))
G n1 1 n5 5 n1->n5 5 n6 6 n1->n6 1 n7 7 n1->n7 2 n9 9 n1->n9 13 n10 10 n1->n10 9 n11 11 n1->n11 10 n2 2 n2->n6 6 n8 8 n2->n8 3 n2->n10 14 n12 12 n2->n12 11 n3 3 n3->n7 7 n3->n8 4 n3->n11 15 n3->n12 12 n4 4 n4->n8 8 n4->n12 16 n13 13 n5->n13 21 n14 14 n5->n14 17 n15 15 n5->n15 18 n6->n14 22 n16 16 n6->n16 19 n7->n15 23 n7->n16 20 n8->n16 24 n9->n13 29 n9->n14 25 n9->n15 26 n10->n14 30 n10->n16 27 n11->n15 31 n11->n16 28 n12->n16 32

We can look at the shape of commuting triangle, which is our favorite 3-vertex graph.

T = @acset LGraph begin
  V = 3
  E = 3
  L = 3
  src = [1,1,2]
  tgt = [2,3,3]
  label = [1,2,3]
end
Tᵣ = add_loops(T)
draw(Tᵣ)

E = @acset LGraph begin
  V = 2
  E = 1
  L = 2
  src = [1]
  tgt = [2]
  label = [1,2]
end
Eᵣ = add_loops(E)
draw(Eᵣ)
G n1 1 n1->n1 2 n2 2 n1->n2 1 n2->n2 3

We can draw the product of the edge graph and the triangle graph to get the shape of a triangular prism. You can view this product as extruding Tᵣ along Eᵣ. Catlab provides a ReflexiveGraph as a type that handles these self-loops more intelligently than we are here. Graphviz struggles with the layout here because the product graph will include edges that are a step in both directions. This blog post does a good job explaining products in differnt kinds of graph categories.

draw(apex(product(Tᵣ,Eᵣ)))
legs(product(Tᵣ, Eᵣ))[1][:V] |> collect
6-element Vector{Int64}:
 1
 2
 3
 1
 2
 3

Another limit is the pullback. If you have a cospan, which is a diagram of the shape X ⟶ A ⟵ Y, you can pull back one arrow along the other by solving a system of equations.

PB₂₂ = pullback(homomorphisms(Tᵣ,Eᵣ)[2],homomorphisms(Tᵣ,Eᵣ)[2]);
draw(apex(PB₂₂))
G n1 1 n1->n1 9 n2 2 n1->n2 8 n3 3 n1->n3 2 n4 4 n1->n4 1 n5 5 n1->n5 4 n2->n2 10 n2->n4 3 n2->n5 5 n3->n3 12 n3->n4 11 n3->n5 6 n4->n4 13 n4->n5 7 n5->n5 14

Note that the pullback depends not only on X,A,Y but also on the two arrows. You can play around with the choice of morphisms to gain an intuition of how the pullback depends on the morphisms.

PB₂₃ = pullback(homomorphisms(Tᵣ,Eᵣ)[2],homomorphisms(Tᵣ,Eᵣ)[3]);
draw(apex(PB₂₃))
G n1 1 n1->n1 7 n2 2 n1->n2 6 n3 3 n1->n3 1 n4 4 n1->n4 3 n2->n2 8 n2->n3 2 n2->n4 4 n3->n3 9 n3->n4 5 n4->n4 10

By constructions, the pullback is always a subobject (monic homomorphism) into the product. Catlab can enumerate all such monoic homs.

homomorphisms(apex(PB₂₂), apex(product(Tᵣ,Tᵣ)), monic=true) |> length
34

Colimits and Composition by Glueing

The dual concept to limits is colimits and if limits have vibes of taking all pairs that satisfy certain constraints, colimits have the vibes of designers just gluing stuff together to make it work.

In order to illustrate this we will be gluing triangles together to make a mesh. We start by defining the point X, which is the shape of the boundary along which we will glue and the morphism ℓ₁, which is the place in T that we consider as the boundary.

X = @acset LGraph begin
  E = 0
  V = 1
  L = 3
  label=[2]
end
ℓ₁ = ACSetTransformation(X,T, V=[2],L=1:3)
draw(X)
G n1 1

We have to check that the morphism is valid before we go and compute out pushout.

is_natural(ℓ₁)
P = pushout(ℓ₁, ℓ₁)
draw(apex(P))
G n1 1 n2 2 n1->n2 1 n3 3 n1->n3 2 n2->n3 3 n5 5 n2->n5 6 n4 4 n4->n2 4 n4->n5 5

Now we want to repeat the gluing process to get a bigger mesh. So we are going to need a bigger interface.

I = @acset LGraph begin
  V = 2
  L = 3
  label = [1,1]
end
draw(I)
G n1 1 n2 2

We have to specify how this interface embeds into both of the things we want to glue. In this case we are gluing a copy of P onto itself.

ll = ACSetTransformation(I, apex(P), V=[3,5], L =[3,1,2])
is_natural(ll)
lr = ACSetTransformation(I, apex(P), V=[1,4], L =[1,3,2])
is_natural(lr)
P₂ = pushout(ll, lr);
draw(apex(P₂))
G n1 1 n2 2 n1->n2 1 n3 3 n1->n3 2 n2->n3 3 n5 5 n2->n5 6 n6 6 n3->n6 7 n7 7 n3->n7 8 n4 4 n4->n2 4 n4->n5 5 n5->n6 10 n8 8 n5->n8 11 n6->n7 9 n6->n8 12