Wiring Diagrams as Attributed C-Sets

Catlab supports many different flavors of diagrammatic syntax. These support the different combinatorial data structures that we use for representing categorical constructions. We will discuss DirectedWiringDiagrams, UndirectedWiringDiagrams, and CPortGraphs in this document.

using Catlab, Catlab.Theories
using Catlab.CategoricalAlgebra
using Catlab.WiringDiagrams
using Catlab.Graphics
using Catlab.Graphics.Graphviz
using Catlab.Programs
using Catlab.WiringDiagrams

draw(d::WiringDiagram) = to_graphviz(d,
  orientation=LeftToRight,
  labels=true, label_attr=:xlabel,
  node_attrs=Graphviz.Attributes(
    :fontname => "Courier",
  ),
  edge_attrs=Graphviz.Attributes(
    :fontname => "Courier",
  )
)

draw(uwd::AbstractUWD) = to_graphviz(uwd, junction_labels=:variable, box_labels=:name)
draw (generic function with 2 methods)

Directed Wiring Diagrams

DWDs are used to represent the morphisms in a symmetric monoidal category. You can get started by presenting a FreeSymmetricMonoidalCategory with the @present macro.

@present P(FreeSymmetricMonoidalCategory) begin
  (A,B,C,D)::Ob
  f::Hom(A,B)
  g::Hom(B,A)
  h::Hom(A⊗B, C)
  k::Hom(C,D⊗A)
end
generators(P)
8-element Vector{Any}:
 A
 B
 C
 D
 f: A → B
 g: B → A
 h: A⊗B → C
 k: C → D⊗A

These presentations are very syntactic objects and expose an API for manipulating expressions.

for g in generators(P)
  "$g is a $(gat_typeof(g)) with arguments $(gat_type_args(g))"
end

The gat_typeof function computes the algebraic type of a term by analogy to Base.typeof which computes the Julia type of a value.

homs_P = filter(generators(P)) do g
  gat_typeof(g) == :Hom
end
4-element Vector{Any}:
 f: A → B
 g: B → A
 h: A⊗B → C
 k: C → D⊗A

When the term is a Hom, you can get the domain and codomain of the morphism with the dom and codom functions.

map(homs_P) do f
  "$f: $(dom(f)) → $(codom(f))"
end
4-element Vector{String}:
 "f: A → B"
 "g: B → A"
 "h: otimes(A,B) → C"
 "k: C → otimes(D,A)"

With the presentation you can build up morphism expressions using a formula syntax.

P[:h]⋅P[:k]

\[h \cdot k : A \otimes B \to D \otimes A\]

This syntactic API is useful for manipulating terms in an arbitrary GAT and is the formal language of Catlab for representing and manipulating algebraic structures. However, when we want to work with big expressions in an SMC, the tree structure inherent to formulas is too verbose, and we want to move to a port-graph structure called DirectedWiringDiagrams. This gives us the benefits of combinatorial data structures like graphs with the right expressional power for representing the morphisms in an SMC.

wd = @program P (a::A, b::B) begin
  c = h(a,b)
  return k(c)
end

draw(wd)
G n1 h n0in1:e->n1:w A n0in2:e->n1:w B n2 k n1:e->n2:w C n2:e->n0out1:w D n2:e->n0out2:w A

Catlab gives you the tools for drawing wiring diagrams. Visualization of wiring diagrams is the oldest part of Catlab and the original motivation for its development. The @program macro allows you to define wiring diagrams using a syntax that feels like Julia code.

wd = @program P (a::A, b::B) begin
  c = h(a,b)
  d,a₁ = k(c)
  return d, f(a₁)
end
draw(wd)
G n1 h n0in1:e->n1:w A n0in2:e->n1:w B n2 k n1:e->n2:w C n2:e->n0out1:w D n3 f n2:e->n3:w A n3:e->n0out2:w B

The input wires are declared as arguments to the program, and the output wires are declared as returns from the function. Variables that are not consumed or by another function or returned by the program are automatically dropped.

wd = @program P (a::A, b::B) begin
  c = h(a,b)
  d,a₁ = k(c)
  return f(a₁)
end
draw(wd)
G n1 h n0in1:e->n1:w A n0in2:e->n1:w B n2 k n1:e->n2:w C n3 f n2:e->n3:w A n3:e->n0out1:w B

You can copy a value by using it more than once. This is visualized as a wire being split into two wires.

wd = @program P (b::B) begin
  h(g(b),b)
end
draw(wd)
G n1 g n0in1:e->n1:w B n2 h n0in1:e->n2:w B n1:e->n2:w A n2:e->n0out1:w C

You can visualize the copy and delete morphisms explicitly with the add_junctions function. The dots with one wire input and multiple outputs are copying values and dots with no wires out are deletions (discarding values). Not all instances of a SymmetricMonoidalCategory support copy and delete, for example, in manufacturing you can't duplicate a resource, and in chemistry you can't discard species. Catlab would enforce that when you tried to interpret the wiring diagram in a specific SMC.

wd = @program P (b::B) begin
  c = h(g(b),b)
  d, a₁ = k(c)
  return f(a₁)
end
draw(add_junctions(wd))
G n5 n0in1:e->n5 B n1 g n2 h n1:e->n2:w A n3 k n2:e->n3:w C n4 f n3:e->n4:w A n6 n3:e->n6 D n4:e->n0out1:w B n5->n1:w B n5->n2:w B

For more details about working with wiring diagrams in Catlab, you should look at the other vignettes in this section which explain how wiring diagrams interact with SMC expressions and the basics of constructing and manipulation wiring diagrams.

Diagrams as C-Sets

The underlying data of a wiring diagram is combinatorial. That means we can represent it as a C-Set

wd.diagram
Catlab.WiringDiagrams.DirectedWiringDiagrams.WiringDiagramACSet{Any, Any, Any, DataType} with elements Box = 1:4, InPort = 1:5, OutPort = 1:5, OuterInPort = 1:1, OuterOutPort = 1:1, Wire = 1:3, InWire = 1:2, OutWire = 1:1, PassWire = 1:0
Box value box_type
1 g Box{Symbol}
2 h Box{Symbol}
3 k Box{Symbol}
4 f Box{Symbol}
InPort in_port_box in_port_type
1 1 B
2 2 A
3 2 B
4 3 C
5 4 A
OutPort out_port_box out_port_type
1 1 A
2 2 C
3 3 D
4 3 A
5 4 B
OuterInPort outer_in_port_type
1 B
OuterOutPort outer_out_port_type
1 B
Wire src tgt wire_value
1 4 5 nothing
2 1 2 nothing
3 2 4 nothing
InWire in_src in_tgt in_wire_value
1 1 1 nothing
2 1 3 nothing
OutWire out_src out_tgt out_wire_value
1 5 1 nothing

Ok, there is a lot in there. The columns with integer entries are the combinatorial data encoding the connectivity of the wiring diagram. The columns with Symbols in them are encoding the labels for the diagram, the value of a box is the content of the box. Ports have types and wires have values. When we define the wiring diagram with the @program macro, we get a diagram that has labels and types, but no values. These values are initialized to nothing, but could be filled with values to be carried down the wires in an application.

The schema of for wiring diagrams is called TheoryAttributedWiringDiagrams and is a little overwhelming, so we can explore how to build it up with C-Set schema inheritance.

to_graphviz(WiringDiagrams.DirectedWiringDiagrams.TheoryAttributedWiringDiagram)
G n1 Box n12 BoxValue n1->n12 value n13 BoxType n1->n13 box_type n2 InPort n2->n1 in_port_box n10 PortValue n2->n10 in_port_type n3 OutPort n3->n1 out_port_box n3->n10 out_port_type n4 OuterInPort n4->n10 outer_in_port_type n5 OuterOutPort n5->n10 outer_out_port_type n6 Wire n6->n2 tgt n6->n3 src n11 WireValue n6->n11 wire_value n7 InWire n7->n2 in_tgt n7->n4 in_src n7->n11 in_wire_value n8 OutWire n8->n3 out_src n8->n5 out_tgt n8->n11 out_wire_value n9 PassWire n9->n4 pass_src n9->n5 pass_tgt n9->n11 pass_wire_value

From the file Catlab/src/WiringDiagrams/Directed.jl

@present TheoryWiringDiagram(FreeSchema) begin
  Box::Ob
  (InPort, OutPort, OuterInPort, OuterOutPort)::Ob
  (Wire, InWire, OutWire, PassWire)::Ob

  src::Hom(Wire, OutPort)
  tgt::Hom(Wire, InPort)
  in_src::Hom(InWire, OuterInPort)
  in_tgt::Hom(InWire, InPort)
  out_src::Hom(OutWire, OutPort)
  out_tgt::Hom(OutWire, OuterOutPort)
  pass_src::Hom(PassWire, OuterInPort)
  pass_tgt::Hom(PassWire, OuterOutPort)

  in_port_box::Hom(InPort, Box)
  out_port_box::Hom(OutPort, Box)
end

@abstract_acset_type AbstractWiringDiagram <: AbstractGraph

@present TheoryTypedWiringDiagram <: TheoryWiringDiagram begin
  PortValue::AttrType
  in_port_type::Attr(InPort, PortValue)
  out_port_type::Attr(OutPort, PortValue)
  outer_in_port_type::Attr(OuterInPort, PortValue)
  outer_out_port_type::Attr(OuterOutPort, PortValue)
end

@present TheoryAttributedWiringDiagram <: TheoryTypedWiringDiagram begin
  WireValue::AttrType
  BoxValue::AttrType
  BoxType::AttrType

  value::Attr(Box, BoxValue)
  box_type::Attr(Box, BoxType)
  wire_value::Attr(Wire, WireValue)
  in_wire_value::Attr(InWire, WireValue)
  out_wire_value::Attr(OutWire, WireValue)
  pass_wire_value::Attr(PassWire, WireValue)
end

The bare minimum diagram language is:

to_graphviz(WiringDiagrams.DirectedWiringDiagrams.TheoryWiringDiagram)
G n1 Box n2 InPort n2->n1 in_port_box n3 OutPort n3->n1 out_port_box n4 OuterInPort n5 OuterOutPort n6 Wire n6->n2 tgt n6->n3 src n7 InWire n7->n2 in_tgt n7->n4 in_src n8 OutWire n8->n3 out_src n8->n5 out_tgt n9 PassWire n9->n4 pass_src n9->n5 pass_tgt

And then you can add back in the types.

to_graphviz(WiringDiagrams.DirectedWiringDiagrams.TheoryTypedWiringDiagram)

#Layout is hard, so if you want to understand the `TheoryAttributedWiringDiagrams`, you should do the layout by hand as an exercise.

We can create our own version of the theory of DWDs to see how it works:

@present MyTheoryWiringDiagram(FreeSchema) begin
  Box::Ob
  (InPort, OutPort, OuterInPort, OuterOutPort)::Ob
  (Wire, InWire, OutWire, PassWire)::Ob

  src::Hom(Wire, OutPort)
  tgt::Hom(Wire, InPort)
  in_src::Hom(InWire, OuterInPort)
  in_tgt::Hom(InWire, InPort)
  out_src::Hom(OutWire, OutPort)
  out_tgt::Hom(OutWire, OuterOutPort)
  pass_src::Hom(PassWire, OuterInPort)
  pass_tgt::Hom(PassWire, OuterOutPort)

  in_port_box::Hom(InPort, Box)
  out_port_box::Hom(OutPort, Box)
end
Presentation{Schema, Symbol}(Catlab.Theories.FreeSchema, (Ob = Catlab.Theories.FreeSchema.Ob{:generator}[Box, InPort, OutPort, OuterInPort, OuterOutPort, Wire, InWire, OutWire, PassWire], Hom = Catlab.Theories.FreeSchema.Hom{:generator}[src, tgt, in_src, in_tgt, out_src, out_tgt, pass_src, pass_tgt, in_port_box, out_port_box], AttrType = Catlab.Theories.FreeSchema.AttrType{:generator}[], Attr = Catlab.Theories.FreeSchema.Attr{:generator}[]), Dict(:InPort => (:Ob => 2), :InWire => (:Ob => 7), :in_port_box => (:Hom => 9), :Box => (:Ob => 1), :OuterOutPort => (:Ob => 5), :in_src => (:Hom => 3), :in_tgt => (:Hom => 4), :src => (:Hom => 1), :OuterInPort => (:Ob => 4), :out_port_box => (:Hom => 10)…), Pair[])

If your application of wiring diagrams needs to attach numeric or textual information to the boxes of a wiring diagram, you would extend the TheoryWiringDiagram with the attributes that you need. That will give you a custom data structure that has those fields. One of the goals of Catlab is to make it so much easier to generate custom data structures that interoperate, that you don't need to create generic structures that can be used for many purposes. Just snap your fingers and create a new structure perfectly tailored to your needs, when your needs change, snap again to get a new version of that structure.

The @acset_type macro does the hard work of generating the data structure and accessors and mutators for you. The form of this call is @acset_type NewStructName(Schema, index=[morphisms in Schema]) <: Supertype. You should index any morphism where you need to use incident frequently. For wiring diagrams you will often want to know what all the wires that are incident to a port.

@acset_type MyWiringDiagramACSet(MyTheoryWiringDiagram,
  index=[:src, :tgt, :in_src, :in_tgt, :out_src, :out_tgt, :pass_src, :pass_tgt]) <: WiringDiagrams.DirectedWiringDiagrams.AbstractWiringDiagram

We get the @acset macro from Catlab and can create DWDs by hand. It is very tedious, which is why the @program macro exists!

md = @acset MyWiringDiagramACSet begin
  Box = 3
  InPort = 6
  OutPort = 3
  Wire = 3
  src = [1,2,3]
  tgt = [3,4,5]
  in_port_box = [1,1,2,2,3,3]
  out_port_box = [1,2,3]
end
Main.ex-wd_cset.MyWiringDiagramACSet with elements Box = 1:3, InPort = 1:6, OutPort = 1:3, OuterInPort = 1:0, OuterOutPort = 1:0, Wire = 1:3, InWire = 1:0, OutWire = 1:0, PassWire = 1:0
InPort in_port_box
1 1
2 1
3 2
4 2
5 3
6 3
OutPort out_port_box
1 1
2 2
3 3
Wire src tgt
1 1 3
2 2 4
3 3 5

Undirected Wiring Diagrams

A much simpler structure than DWDs are known as undirected wiring diagrams. They are called undirected because ports boxes have one set of ports that aren't divided into inputs and outputs, and the wires are undirected. Wires connect junctions to ports (which live on boxes).

to_graphviz(WiringDiagrams.UndirectedWiringDiagrams.TheoryUWD)
G n1 Box n2 Port n2->n1 box n4 Junction n2->n4 junction n3 OuterPort n3->n4 outer_junction

These UWDs are combinatorial syntax for relations. The junctions are variables and the boxes are the relations. A relation R ⊆ X × Y has two ports one for the value of X and one for the value of Y. The expression R(x:X, y:Y) says to connect the X port of R to the junction for the variable x, and the Y port of R to the y variable junction. If two ports are attached to the same junction, then you have a constraint that those values must be equal. The outer ports are the components of the final relation. For example the following UWD encodes the relation {(x,y,z) | R(x,y) and S(y,z) for all x∈X, y∈Y, z∈Z}.

uwd = @relation (x, y, z) begin
  R(x,y)
  S(y,z)
end
Catlab.Programs.RelationalPrograms.UntypedUnnamedRelationDiagram{Symbol, Symbol} with elements Box = 1:2, Port = 1:4, OuterPort = 1:3, Junction = 1:3
Box name
1 R
2 S
Port box junction
1 1 1
2 1 2
3 2 2
4 2 3
OuterPort outer_junction
1 1
2 2
3 3
Junction variable
1 x
2 y
3 z

These UWDs are drawn with circular boxes and undirected wires. Note that since all wires go from junction to port, they are not symmetric wires.

draw(uwd)
G n1 R n6 x n1--n6 n7 y n1--n7 n2 S n2--n7 n8 z n2--n8 n3--n6 n4--n7 n5--n8

By adding more relations we can get bigger relations.

uwd₂ = @relation (x, z) begin
  R(x,y)
  S(y,z)
  T(x,z,y)
end
Catlab.Programs.RelationalPrograms.UntypedUnnamedRelationDiagram{Symbol, Symbol} with elements Box = 1:3, Port = 1:7, OuterPort = 1:2, Junction = 1:3
Box name
1 R
2 S
3 T
Port box junction
1 1 1
2 1 3
3 2 3
4 2 2
5 3 1
6 3 2
7 3 3
OuterPort outer_junction
1 1
2 2
Junction variable
1 x
2 z
3 y

Not all of the junctions have to be exposed to the outside world. Note that there is no distinction between arguments and return values in the relation macro. This is because relations are inherently undirected, unlike functions.

draw(uwd₂)
G n1 R n6 x n1--n6 n8 y n1--n8 n2 S n7 z n2--n7 n2--n8 n3 T n3--n6 n3--n7 n3--n8 n4--n6 n5--n7

Circular Port Graphs

CPGs are the natural data structure for representing process of interconnected systems that share information along wires, but send different information to their different neighbors.

to_graphviz(ThCPortGraph)
G n1 Box n2 Port n2->n1 box n3 Wire n3->n2 src n3->n2 tgt

They are also a kind of CSet, so we can use the @acset macro to construct them.

cpg = @acset CPortGraph begin
  Box = 3
  Port = 6
  Wire = 5

  box = [1,1,2,2,3,3]
  src = [1,2,5,2,6]
  tgt = [3,4,2,4,1]
end
CPortGraph with elements Box = 1:3, Port = 1:6, Wire = 1:5
Port box
1 1
2 1
3 2
4 2
5 3
6 3
Wire src tgt
1 1 3
2 2 4
3 5 2
4 2 4
5 6 1

the layout for CPGs is not great with graphviz.

to_graphviz(cpg, port_labels=true, graph_attrs=Dict("nodesep"=>"2", "ranksep"=>"2"))
G n1 n1 n2 n2 n1->n2 1 1 n1->n2 2 2 n1->n2 2 2 n3 n3 n3->n1 2 1 n3->n1 1 2

Almost every application of graphs in computer science could be better served by using one of these extensions to the basic graph data structure.