Theory of hypergraph categories

Hypergraph categories are also known as "well-supported compact closed categories" and "spidered/dungeon categories", among other things.

FIXME: Should also inherit ThClosedMonoidalCategory and ThDaggerCategory, but multiple inheritance is not yet supported.


Convert wiring diagrams to and from syntactic expressions.

Wiring diagrams are a graphical syntax for morphisms in a monoidal category. As mathematical objects, they are intermediate between the morphisms themselves and expressions in the textual syntax: a single morphism may correspond to many wiring diagrams, and a single wiring diagram may correspond to many syntactic expressions.

It is trivial to convert a morphism expression to a wiring diagram, but not to go the other way around.


Bipartite graphs, directed and undirected, as C-sets.

A graph theorist might call these "bipartitioned graphs," as in a graph equipped with a bipartition, as opposed to "bipartite graphs," as in a graph that can be bipartitioned. Here we use the former notion, which is more natural from the structuralist perspective, but the latter terminology, which is shorter and more familiar.


An undirected bipartite graph.

It is a matter of perspective whether to consider such graphs "undirected," in the sense that the edges have no orientation, or "unidirected," in the sense that all edges go from vertices of type 1 to vertices of type 2.


Construct an undirected wiring diagram using relation notation.

Unlike the @program macro for directed wiring diagrams, this macro departs significantly from the usual semantics of the Julia programming language. Function calls with $n$ arguments are now interpreted as assertions that an $n$-ary relation holds at a particular point. For example, the composite of binary relations $R ⊆ X × Y$ and $S ⊆ Y × Z$ can be represented as an undirected wiring diagram by the macro call

@relation (x,z) where (x::X, y::Y, z::Z) begin

In general, the context in the where clause defines the set of junctions in the diagram and variable sharing defines the wiring of ports to junctions. If the where clause is omitted, the set of junctions is inferred from the variables used in the macro call.

The ports and junctions of the diagram may be typed or untyped, and the ports may be named or unnamed. Thus, four possible types of undirected wiring diagrams may be returned, with the type determined by the form of relation header:

  1. Untyped, unnamed: @relation (x,z) where (x,y,z) ...
  2. Typed, unnamed: @relation (x,z) where (x::X, y::Y, z::Z) ...
  3. Untyped, named: @relation (out1=x, out2=z) where (x,y,z) ...
  4. Typed, named: @relation (out=1, out2=z) where (x::X, y::Y, z::Z) ...

All four types of diagram are subtypes of RelationDiagram.


Act on undirected wiring diagram with a cospan, as in a cospan algebra.

A cospan algebra is a lax monoidal functor from a category of (typed) cospans (Cospan,⊕) to (Set,×) (Fong & Spivak, 2019, Hypergraph categories, §2.1: Cospans and cospan-algebras). Undirected wiring diagrams are a cospan algebra in essentially the same way that any hypergraph category is (Fong & Spivak, 2019, §4.1: Cospan-algebras and hypergraph categories are equivalent). In fact, we use this action to implement the hypergraph category structure, particularly composition, on undirected wiring diagrams.


2-category of categories, functors, and natural transformations.

Categories in mathematics appear in the large, often as categories of sets with extra structure, and in the small, as algebraic structures that generalize groups, monoids, preorders, and graphs. This division manifests in Catlab as well. Large categories (in spirit, if not in the technical sense) occur throughout Catlab as @instances of the theory of categories. For computational reasons, small categories are usually presented by generators and relations.

This module provides a minimal interface to accomodate both situations. Category instances are supported through the wrapper type TypeCat. Finitely presented categories are provided by another module, FinCats.


Abstract base type for a category.

The objects and morphisms in the category have Julia types Ob and Hom, respectively. Note that these types do not necessarily form an @instance of the theory of categories, as they may not meaningfully form a category outside the context of this object. For example, a finite category regarded as a reflexive graph with a composition operation might have type Cat{Int,Int}, where the objects and morphisms are numerical identifiers for vertices and edges in the graph.

The basic operations available in any category are: dom, codom, id, compose.


Abstract base type for a functor between categories.

A functor has a domain and a codomain (dom and codom), which are categories, and object and morphism maps, which can be evaluated using ob_map and hom_map. The functor object can also be called directly when the objects and morphisms have distinct Julia types. This is sometimes but not always the case (see Category), so when writing generic code one should prefer the ob_map and hom_map functions.


Abstract base type for a natural transformation between functors.

A natural transformation $α: F ⇒ G$ has a domain $F$ and codomain $G$ (dom and codom), which are functors $F,G: C → D$ having the same domain $C$ and codomain $D$. The transformation consists of a component $αₓ: Fx → Gx$ in $D$ for each object $x ∈ C$, accessible using component or indexing notation (Base.getindex).


Coerce or look up object in category.

Converts the input to an object in the category, which should be of type Ob in a category of type Cat{Ob,Hom}. How this works depends on the category, but a common case is to look up objects, which might be integers or GAT expressions, by their human-readable name, usually a symbol.

See also: hom.


Are two morphisms in a category equal?

By default, just checks for equality of Julia objects using $==$. In some categories, checking equality of morphisms may involve nontrivial reasoning.


Oppositization 2-functor.

The oppositization endo-2-functor on Cat, sending a category to its opposite, is covariant on objects and morphisms and contravariant on 2-morphisms, i.e., is a 2-functor $op: Catᶜᵒ → Cat$. For more explanation, see the nLab.


Leg of a structured (multi)cospan of acsets in R-form.

A convenience type that contains the data of an acset transformation, except for the codomain, since that data is already given by the decoration of the R-form structured cospan.


Structured cospan.

The first type parameter L encodes a functor L: A → X from the base category A, often FinSet, to a category X with "extra structure." An L-structured cospan is then a cospan in X whose feet are images under L of objects in A. The category X is assumed to have pushouts.

Structured cospans form a double category with no further assumptions on the functor L. To obtain a symmetric monoidal double category, L must preserve finite coproducts. In practice, L usually has a right adjoint R: X → A, which implies that L preserves all finite colimits. It also allows structured cospans to be constructed more conveniently from an object x in X plus a cospan in A with apex R(x).

See also: StructuredMulticospan.


Apply left adjoint L: C₀-Set → C-Set to morphism.


Apply left adjoint L: FinSet → C-Set to object.


Apply left adjoint L: FinSet → C-Set to morphism.


Apply left adjoint L: C₀-Set → C-Set to object.


Create types for open attributed C-sets from an attributed C-set type.

The type parameters of the given acset type should not be instantiated with specific Julia types. This function returns a pair of types, one for objects, a subtype of StructuredCospanOb, and one for morphisms, a subtype of StructuredMulticospan. Both types will have the same type parameters for attribute types as the given acset type.

Mathematically speaking, this function sets up structured (multi)cospans with a functor $L: A → X$ between categories of acsets that creates "discrete acsets." Such a "discrete acset functor" is a functor that is left adjoint to a certain kind of forgetful functor between categories of acsets, namely one that is a pullback along an inclusion of schemas such that the image of inclusion has no outgoing arrows. For example, the schema inclusion ${V} ↪ {E ⇉ V}$ has this property but ${E} ↪ {E ⇉ V}$ does not.

See also: OpenCSetTypes.


Theory of a distributive semiadditive category

This terminology is not standard but the concept occurs frequently. A distributive semiadditive category is a semiadditive category (or biproduct) category, written additively, with a tensor product that distributes over the biproduct.

FIXME: Should also inherit ThSemiadditiveCategory


Commutative square in a category.

Commutative squares in a category $C$ form the cells of a strict double category, the arrow double category or double category of squares in $C$, with composition in both directions given by pasting of commutative squares.

In this data structure, the four morphisms comprising the square are stored as a static vector of length 4, ordered as domain (top), codomain (bottom), source (left), and target (right). This convention agrees with the GAT for double categories (ThDoubleCategory).


The rig of booleans.

This struct is needed because in base Julia, the product of booleans is another boolean, but the sum of booleans is coerced to an integer: true + true == 2.


Binary relation between finite sets.

A morphism in the category of finite sets and relations. The relation can be represented implicitly by an arbitrary Julia function mapping pairs of elements to booleans or explicitly by a matrix (dense or sparse) taking values in the rig of booleans (BoolRig).


FinRel as a distributive bicategory of relations.

FIXME: Many methods only work for FinRel{Int}. The default methods should assume FinRel{<:AbstractSet} and the case FinRel{Int} should be handled specially.


Theory of cartesian closed categories, aka CCCs

A CCC is a cartesian category with internal homs (aka, exponential objects).

FIXME: This theory should also extend ThClosedMonoidalCategory, but multiple inheritance is not yet supported.


Free diagrams in a category.

A free diagram in a category is a diagram whose shape is a free category. Examples include the empty diagram, pairs of objects, discrete diagrams, parallel pairs, composable pairs, and spans and cospans. Limits and colimits are most commonly taken over free diagrams.


A free diagram with a bipartite structure.

Such diagrams include most of the fixed shapes, such as spans, cospans, and parallel morphisms. They are also the generic shape of diagrams for limits and colimits arising from undirected wiring diagrams. For limits, the boxes correspond to vertices in $V₁$ and the junctions to vertices in $V₂$. Colimits are dual.


Convert a free diagram to a bipartite free diagram.

Reduce a free diagram to a free bipartite diagram with the same limit (the default, colimit=false) or the same colimit (colimit=true). The reduction is essentially the same in both cases, except for the choice of where to put isolated vertices, where we follow the conventions described at cone_objects and cocone_objects. The resulting object is a bipartite free diagram equipped with maps from the vertices of the bipartite diagram to the vertices of the original diagram.


Bundle together legs of a multi(co)span.

For example, calling bundle_legs(span, SVector((1,2),(3,4))) on a multispan with four legs gives a span whose left leg bundles legs 1 and 2 and whose right leg bundles legs 3 and 4. Note that in addition to bundling, this function can also permute legs and discard them.

The bundling is performed using the universal property of (co)products, which assumes that these (co)limits exist.


Objects in diagram that will have explicit legs in limit cone.

In category theory, it is common practice to elide legs of limit cones that can be computed from other legs, especially for diagrams of certain fixed shapes. For example, when it taking a pullback (the limit of a cospan), the limit object is often treated as having two projections, rather than three. This function encodes such conventions by listing the objects in the diagram that will have corresponding legs in the limit object created by Catlab.

See also: cocone_objects.


Theory of a category with (finite) products

Finite products are presented in biased style, via the nullary case (terminal objects) and the binary case (binary products). The equational axioms are standard, especially in type theory (Lambek & Scott, 1986, Section 0.5 or Section I.3). Strictly speaking, this theory is not of a "category with finite products" (a category in which finite products exist) but of a "category with chosen finite products".

For a monoidal category axiomatization of finite products, see ThCartesianCategory.


Theory of lattice of subobjects in a coherent category, such as a pretopos.

The axioms are omitted since this theory is the same as the theory Catlab.Theories.ThAlgebraicLattice except that the lattice elements are dependent on another type. In fact, if we supported GAT morphisms, it should be possible to define a projection morphism of GATs from ThSubobjectLattice to ThAlgebraicLattice that sends Ob to the unit type.


The data of the morphism of a slice category (call it h, and suppose a category C is sliced over an object X in Ob(C)) between objects f and g is a homomorphism in the underlying category that makes the following triangle commute.

h A –> B f ↘ ↙ g X


Convert a limit problem in the slice category to a limit problem of the underlying category.

Encode the base of slice as the first object in the new diagram


Graph with properties.

"Property graphs" are graphs with arbitrary named properties on the graph, vertices, and edges. They are intended for applications with a large number of ad-hoc properties. If you have a small number of known properties, it is better and more efficient to create a specialized C-set type using @acset_type.

See also: SymmetricPropertyGraph.


A data migration is guaranteed to contain a functor between schemas that can be used to migrate data between acsets on those schemas. The migration may be a pullback data migration (DeltaMigration), specified by a functor $D → C$ between the schemas, or $F$ may be a schema functor specifying a $Σ$ migration in the covariant direction. Other data migration types are defined in DataMigrations.jl.


Sigma or left pushforward functorial data migration between acsets.

Given a functor $F: C → D$, the sigma data migration $Σ_F$ is a functor from $C$-sets to $D$-sets that is left adjoint to the delta migration functor $Δ_F$ (DeltaMigration). Explicitly, the $D$-set $Σ_F(X)$ is given on objects $d ∈ D$ by the formula $Σ_F(x)(d) = \mathrm{colim}_{F ↓ d} X ∘ π$, where $π: (F ↓ d) → C$ is the projection.

See (Spivak, 2014, Category Theory for the Sciences) for details.


Objects: Fᴳ(c) = C-Set(C × G, F) where C is the representable c

Given a map f: a->b, we compute that f(Aᵢ) = Bⱼ by constructing the following: Aᵢ A × G → F f*↑ ↑ ↑ ↗ Bⱼ find the hom Bⱼ that makes this commute B × G

where f* is given by yoneda.


Construct a representable C-set.

Recall that a representable C-set is one of form $C(c,-): C → Set$ for some object $c ∈ C$.

This function computes the $c$ representable as the left pushforward data migration of the singleton ${c}$-set along the inclusion functor ${c} ↪ C$, which works because left Kan extensions take representables to representables (Mac Lane 1978, Exercise X.3.2). Besides the intrinsic difficulties with representables (they can be infinite), this function thus inherits any limitations of our implementation of left pushforward data migrations.


The subobject classifier Ω in a presheaf topos is the presheaf that sends each object A to the set of sieves on it (equivalently, the set of subobjects of the representable presheaf for A). Counting subobjects gives us the number of A parts; the hom data for f:A->B for subobject Aᵢ is determined via:

Aᵢ ↪ A ↑ ↑ f* PB⌝↪ B (PB picks out a subobject of B, up to isomorphism.)

(where A and B are the representables for objects A and B and f* is the unique map from B into the A which sends the point of B to f applied to the point of A)

Returns the classifier as well as a dictionary of subobjects corresponding to the parts of the classifier.


Compute the Yoneda embedding of a category C in the category of C-sets.

Because Catlab privileges copresheaves (C-sets) over presheaves, this is the contravariant Yoneda embedding, i.e., the embedding functor C^op → C-Set.

The first argument cons is a constructor for the ACSet, such as a struct acset type. If representables have already been computed (which can be expensive), they can be supplied via the cache keyword argument.

Returns a FinDomFunctor with domain op(C).


Pullback formed as composite of product and equalizer.

The fields of this struct are an implementation detail; accessing them directly violates the abstraction. Everything that you can do with a pushout, including invoking its universal property, should be done through the generic interface for limits.

See also: CompositePushout.


Meta-algorithm that reduces general limits to common special cases.

Reduces limits of free diagrams that happen to be discrete to products. If this fails, fall back to the given algorithm (if any).

TODO: Reduce free diagrams that are (multi)cospans to (wide) pullbacks.


Colimit of a diagram.

To define colimits in a category with objects Ob, override the method colimit(::FreeDiagram{Ob}) for general colimits or colimit(::D) with suitable type D <: FixedShapeFreeDiagram{Ob} for colimits of specific shape, such as coproducts or coequalizers.

See also: limit


The image and coimage are isomorphic. We get this isomorphism using univeral properties.

  CoIm′ ╌╌> I ↠ CoIm
    ┆ ⌟     |
    v       v
    I   ⟶  R ↩ Im
    |       ┆
    v    ⌜  v
    R ╌╌> Im′

Limit of a diagram.

To define limits in a category with objects Ob, override the method limit(::FreeDiagram{Ob}) for general limits or limit(::D) with suitable type D <: FixedShapeFreeDiagram{Ob} for limits of specific shape, such as products or equalizers.

See also: colimit


Pullback of a pair of morphisms with common codomain.

To implement for a type T, define the method limit(::Cospan{T}) and/or limit(::Multicospan{T}) or, if you have already implemented products and equalizers, rely on the default implementation.


Pushout of a pair of morphisms with common domain.

To implement for a type T, define the method colimit(::Span{T}) and/or colimit(::Multispan{T}) or, if you have already implemented coproducts and coequalizers, rely on the default implementation.


Coequalizer of morphisms with common domain and codomain.

To implement for a type T, define the method colimit(::ParallelPair{T}) or colimit(::ParallelMorphisms{T}).


Copairing of morphisms: universal property of coproducts/pushouts.

To implement for coproducts of type T, define the method universal(::BinaryCoproduct{T}, ::Cospan{T}) and/or universal(::Coproduct{T}, ::Multicospan{T}) and similarly for pushouts.


Coproduct of objects.

To implement for a type T, define the method colimit(::ObjectPair{T}) and/or colimit(::DiscreteDiagram{T}).


Unique morphism out of an initial object.

To implement for a type T, define the method universal(::Initial{T}, ::SMulticospan{0,T}).


Unique morphism into a terminal object.

To implement for a type T, define the method universal(::Terminal{T}, ::SMultispan{0,T}).


Equalizer of morphisms with common domain and codomain.

To implement for a type T, define the method limit(::ParallelPair{T}) and/or limit(::ParallelMorphisms{T}).


Factor morphism through (co)equalizer, via the universal property.

To implement for equalizers of type T, define the method universal(::Equalizer{T}, ::SMultispan{1,T}). For coequalizers of type T, define the method universal(::Coequalizer{T}, ::SMulticospan{1,T}).


Initial object.

To implement for a type T, define the method colimit(::EmptyDiagram{T}).


Pairing of morphisms: universal property of products/pullbacks.

To implement for products of type T, define the method universal(::BinaryProduct{T}, ::Span{T}) and/or universal(::Product{T}, ::Multispan{T}) and similarly for pullbacks.


Product of objects.

To implement for a type T, define the method limit(::ObjectPair{T}) and/or limit(::DiscreteDiagram{T}).


Terminal object.

To implement for a type T, define the method limit(::EmptyDiagram{T}).


Universal property of (co)limits.

Compute the morphism whose existence and uniqueness is guaranteed by the universal property of (co)limits.

See also: limit, colimit.


Catlab's standard library of generalized algebraic theories.

The focus is on categories and monoidal categories, but other related structures are also included.


Base type for GAT expressions in categories or other categorical structures.

All symbolic expression types exported by Catlab.Theories are subtypes of this abstract type.


Collect generators of object in monoidal category as a vector.


Number of "dimensions" of object in monoidal category.


Longest paths in a DAG.

Returns a vector of integers whose i-th element is the length of the longest path to vertex i. Requires a topological sort, which is computed if it is not supplied.


Transitive reduction of a DAG.

The algorithm computes the longest paths in the DAGs and keeps only the edges corresponding to longest paths of length 1. Requires a topological sort, which is computed if it is not supplied.


Theory of lattices as algebraic structures

This is one of two standard axiomatizations of a lattice, the other being ThLattice. Because the partial order is not present, this theory is merely an algebraic theory (no dependent types).

The partial order is recovered as $A ≤ B$ iff $A ∧ B = A$ iff $A ∨ B = B$. This definition could be reintroduced into a generalized algebraic theory using an equality type Eq(lhs::El, rhs::El)::TYPE combined with term constructors `meet_leq(eq::Eq(A∧B, A))::(A ≤ B) and join_leq(eq::Eq(A∨B, B))::(A ≤ B). We do not employ that trick here because at that point it is more convenient to just start with the poset structure, as in ThLattice.


The "vec-permutation" matrix, aka the "perfect shuffle" permutation matrix.

This formula is (Henderson & Searle, 1981, "The vec-permutation matrix, the vec operator and Kronecker products: a review", Equation 18). Many other formulas are given there.


Algebra of subobjects in a category.

This module defines the interface for subobjects as well as some generic algorithm for computing subobjects using limits and colimits. Concrete instances such as subsets (subobjects in Set or FinSet) and sub-C-sets (subobjects in C-Set) are defined elsewhere.


Subobject in a category.

By definition, a subobject of an object $X$ in a category is a monomorphism into $X$. This is the default representation of a subobject. Certain categories may support additional representations. For example, if the category has a subobject classifier $Ω$, then subobjects of $X$ are also morphisms $X → Ω$.


Join (union) of subobjects.


Theory of monoidal categories with diagonals

A monoidal category with diagonals is a symmetric monoidal category equipped with coherent operations of copying and deleting, also known as a supply of commutative comonoids. Unlike in a cartesian category, the naturality axioms need not be satisfied.


  • Fong & Spivak, 2019, "Supplying bells and whistles in symmetric monoidal categories" (arxiv:1908.02633)
  • Selinger, 2010, "A survey of graphical languages for monoidal categories", Section 6.6: "Cartesian center"
  • Selinger, 1999, "Categorical structure of asynchrony"

Theory of monoidal categories with bidiagonals

The terminology is nonstandard (is there any standard terminology?) but is supposed to mean a monoidal category with coherent diagonals and codiagonals. Unlike in a biproduct category, the naturality axioms need not be satisfied.


Data structure for (directed) wiring diagrams, aka string diagrams.

A (directed) wiring diagram consists of a collection of boxes with input and output ports connected by wires. A box can be atomic (possessing no internal structure) or can itself be a wiring diagram. Thus, wiring diagrams can be nested recursively. Wiring diagrams are closely related to what the CS literature calls "directed graphs with ports" or more simply "port graphs". The main difference is that a wiring diagram has an "outer box": a wiring diagram has its own ports that can be connected to the ports of its boxes.

This module provides a generic data structure for wiring diagrams. Arbitrary data can be attached to the boxes, ports, and wires of a wiring diagram. The diagrams are "abstract" in the sense that they cannot be directly rendered as raster or vector graphics. However, they form a useful intermediate representation that can be serialized to and from GraphML or translated into Graphviz or other declarative diagram languages.


Are the two wiring diagrams equal?

Warning: This method checks equality of the underlying C-set representation. Use is_isomorphic to check isomorphism of wiring diagrams.


Grapn underlying wiring diagram, including parts for noin-internal wires.

The graph has two special vertices representing the input and output boundaries of the outer box.


Create an encapsulating box for a set of boxes in a wiring diagram.

To a first approximation, the union of input ports of the given boxes will become the inputs ports of the encapsulating box and likewise for the output ports. However, when copies or merges occur, as in a cartesian or cocartesian category, a simplification procedure may reduce the number of ports on the encapsulating box.


  1. Each input port of an encapsulated box will have at most one incoming wire

from the encapsulating outer box, and each output port of an encapsulated box will have at most one outgoing wire to the encapsulating outer box.

  1. A set of ports connected to the same outside (non-encapsulated) ports will be

simplified into a single port of the encapsulating box.

See also induced_subdiagram.


Operadic composition of wiring diagrams.

This generic function has two different signatures, corresponding to the "full" and "partial" notions of operadic composition (Yau, 2018, Operads of Wiring Diagrams, Definitions 2.3 and 2.10).

This operation is a simple wrapper around substitute.


Theory of a rig category, also known as a bimonoidal category

Rig categories are the most general in the hierarchy of distributive monoidal structures.

Question: Do we also want the distributivty and absorption isomorphisms? Usually we ignore coherence isomorphisms such as associators and unitors.

FIXME: This theory should also inherit ThMonoidalCategory, but multiple inheritance is not supported.


Theory of an opindexed monoidal category with lax transition functors.

This is a pseudofunctor into MonCatLax, the 2-category of monoidal categories, lax monoidal functors, and monoidal natural transformations. In (Hofstra & De Marchi 2006), these are called simply "(op)indexed monoidal categories," but that is not the standard usage.


  • Hofstra & De Marchi, 2006: Descent for monads
  • Moeller & Vasilakopoulou, 2020: Monoidal Grothendieck construction, Remark 3.18 [this paper is about monoidal indexed categories, a different notion!]

Draw an undirected wiring diagram using Graphviz.

Creates an undirected, bipartite Graphviz graph, with the boxes and outer ports of the diagram becoming nodes of one kind and the junctions of the diagram becoming nodes of the second kind.


  • graph_name="G": name of Graphviz graph
  • prog="neato": Graphviz program, usually "neato" or "fdp"
  • box_labels=false: if boolean, whether to label boxes with their number; if a symbol, name of data attribute for box label
  • port_labels=false: whether to label ports with their number
  • junction_labels=false: if boolean, whether to label junctions with their number; if a symbol, name of data attribute for junction label
  • junction_size="0.075": size of junction nodes, in inches
  • implicit_junctions=false: whether to represent a junction implicity as a wire when it has exactly two incident ports
  • graph_attrs=Dict(): top-level graph attributes
  • node_attrs=Dict(): top-level node attributes
  • edge_attrs=Dict(): top-level edge attributes

Draw a circular port graph using Graphviz.

Creates a Graphviz graph. Ports are currently not respected in the image, but the port index for each box can be displayed to provide clarification.


  • graph_name="G": name of Graphviz graph
  • prog="neato": Graphviz program, usually "neato" or "fdp"
  • box_labels=false: whether to label boxes with their number
  • port_labels=false: whether to label ports with their number
  • graph_attrs=Dict(): top-level graph attributes
  • node_attrs=Dict(): top-level node attributes
  • edge_attrs=Dict(): top-level edge attributes

TODO: The lack of ports might be able to be resolved by introducing an extra node per port which is connected to its box with an edge of length 0.


Draw a wiring diagram using Graphviz.

The input can also be a morphism expression, in which case it is first converted into a wiring diagram. This function requires Graphviz v2.42 or higher.


  • graph_name="G": name of Graphviz digraph
  • orientation=TopToBottom: orientation of layout. One of LeftToRight, RightToLeft, TopToBottom, or BottomToTop.
  • node_labels=true: whether to label the nodes
  • labels=false: whether to label the edges
  • label_attr=:label: what kind of edge label to use (if labels is true). One of :label, :xlabel, :headlabel, or :taillabel.
  • port_size="24": minimum size of ports on box, in points
  • junction_size="0.05": size of junction nodes, in inches
  • outer_ports=true: whether to display the outer box's input and output ports. If disabled, no incoming or outgoing wires will be shown either!
  • anchor_outer_ports=true: whether to enforce ordering of the outer box's input and output, i.e., ordering of the incoming and outgoing wires
  • graph_attrs=Dict(): top-level graph attributes
  • node_attrs=Dict(): top-level node attributes
  • edge_attrs=Dict(): top-level edge attributes
  • cell_attrs=Dict(): main cell attributes in node HTML-like label

Lay out directed wiring diagram using Graphviz.

Note: At this time, only the positions and sizes of the boxes, and the positions of the outer ports, are used. The positions of the box ports and the splines for the wires are ignored.


Transformation between attributed C-sets.

Homomorphisms of attributed C-sets generalize homomorphisms of C-sets (CSetTransformation), which you should understand before reading this.

A homomorphism of attributed C-sets with schema S: C ↛ A (a profunctor) is a natural transformation between the corresponding functors col(S) → Set, where col(S) is the collage of S. When the components on attribute types, indexed by objects of A, are all identity functions, the morphism is called tight; in general, it is called loose. With this terminology, acsets on a fixed schema are the objects of an ℳ-category (see Catlab.Theories.MCategory). Calling ACSetTransformation will construct a tight or loose morphism as appropriate, depending on which components are specified.

Since every tight morphism can be considered a loose one, the distinction between tight and loose may seem a minor technicality, but it has important consequences because limits and colimits in a category depend as much on the morphisms as on the objects. In particular, limits and colimits of acsets differ greatly depending on whether they are taken in the category of acsets with tight morphisms or with loose morphisms. Tight morphisms suffice for many purposes, including most applications of colimits. However, when computing limits of acsets, loose morphisms are usually preferable. For more information about limits and colimits in these categories, see TightACSetTransformation and LooseACSetTransformation.


Transformation between C-sets.

Recall that a C-set homomorphism is a natural transformation: a transformation between functors C → Set satisfying the naturality axiom for every morphism, or equivalently every generating morphism, in C.

This data type records the data of a C-set transformation. Naturality is not strictly enforced but is expected to be satisfied. It can be checked using the function is_natural.

If the schema of the dom and codom has attributes, this has the semantics of being a valid C-set transformation on the combinatorial data alone (including attribute variables, if any).


Loose transformation between attributed C-sets.

Limits and colimits in the category of attributed C-sets and loose homomorphisms are computed pointwise on both objects and attribute types. This implies that (co)limits of Julia types must be computed. Due to limitations in the expressivity of Julia's type system, only certain simple kinds of (co)limits, such as products, are supported.

Alternatively, colimits involving loose acset transformations can be constructed with respect to explicitly given attribute type components for the legs of the cocone, via the keyword argument type_components to colimit and related functions. This uses the universal property of the colimit. To see how this works, notice that a diagram of acsets and loose acset transformations can be expressed as a diagram D: J → C-Set (for the C-sets) along with another diagram A: J → C-Set (for the attribute sets) and a natural transformation α: D ⇒ A (assigning attributes). Given a natural transformation τ: A ⇒ ΔB to a constant functor ΔB, with components given by type_components, the composite transformation α⋅τ: D ⇒ ΔB is a cocone under D, hence factors through the colimit cocone of D. This factoring yields an assigment of attributes to the colimit in C-Set.

For the distinction between tight and loose, see ACSetTranformation.


Tight transformation between attributed C-sets.

The category of attributed C-sets and tight homomorphisms is isomorphic to a slice category of C-Set, as explained in our paper "Categorical Data Structures for Technical Computing". Colimits in this category thus reduce to colimits of C-sets, by a standard result about slice categories. Limits are more complicated and are currently not supported.

For the distinction between tight and loose, see ACSetTranformation.


Create FinDomFunction for morphism or attribute of attributed C-set.

Indices are included whenever they exist. Unlike the FinFunction constructor, the codomain of the result is always of type TypeSet.


Inverse f (from A to B) as a map from subobjects of B to subobjects of A. Cast an ACSet to subobject, though this has a trivial answer when computing the preimage (it is necessarily the top subobject of A).


Inverse of f (from A to B) as a map of subobjects of B to subjects of A.


Check whether an ACSetTransformation is still valid, despite possible deletion of elements in the codomain. An ACSetTransformation that isn't in bounds will throw an error, rather than return false, if run through is_natural.


Returns a dictionary whose keys are contained in the names in arrows(S) and whose value at :f, for an arrow (f,c,d), is a lazy iterator over the elements of X(c) on which α's naturality square for f does not commute. Components should be a NamedTuple or Dictionary with keys contained in the names of S's morphisms and values vectors or dicts defining partial functions from X(c) to Y(c).


Make limit of acsets from limits of underlying sets, ignoring attributes.

If one wants to consider the attributes of the apex, the following type_components - TBD abstract_product - places attribute variables in the apex attrfun - allows one to, instead of placing an attribute in the apex, apply a function to the values of the projections. Can be applied to an AttrType or an Attr (which takes precedence).


Check naturality condition for a purported ACSetTransformation, α: X→Y. For each hom in the schema, e.g. h: m → n, the following square must commute:

  Xₘ --> Yₘ
Xₕ ↓  ✓  ↓ Yₕ
  Xₙ --> Yₙ

You're allowed to run this on a named tuple partly specifying an ACSetTransformation, though at this time the domain and codomain must be fully specified ACSets.


Variables are used for the attributes in the apex of limit of CSetTransformations when there happen to be attributes. However, a commutative monoid on the attribute type may be provided in order to avoid introducing variables.


A limit of a diagram of ACSets with LooseACSetTransformations.

For general diagram shapes, the apex of the categorical limit will not have clean Julia types for its attributes, i.e. predicates will be needed to further constrain them. product_attrs must be turned on in order to avoid an error in cases where predicates would be needed.

product_attrs=true will take a limit of the purely combinatorial data, and the attribute data of the apex is dictated purely by the ACSets that are have explicit cone legs: the value of an attribute (e.g. f) for the i'th part in the apex is the product (f(π₁(i)), ..., f(πₙ(i))) where π maps come from the combinatorial part of the limit legs. The type components of the j'th leg of the limit is just the j'th cartesian projection.


Implication of sub-C-sets.

By (Reyes et al 2004, Proposition 9.1.5), the implication $A ⟹ B$ for two sub-$C$-sets $A,B ↪ X$ is given by

$x ∈ (A ⟹ B)(c) iff ∀f: c → c′, x⋅f ∈ A(c′) ⟹ x⋅f ∈ B(c′)$

for all $c ∈ C$ and $x ∈ X(c)$. By the definition of implication and De Morgan's law in classical logic, this is equivalent to

$x ∉ (A ⟹ B)(c) iff ∃f: c → c′, x⋅f ∈ A(c′) ∧ x⋅f ∉ B(c′)$.

In this form, we can clearly see the duality to formula and algorithm for subtraction of sub-C-sets (subtract).


Subtraction of sub-C-sets.

By (Reyes et al 2004, Sec 9.1, pp. 144), the subtraction $A ∖ B$ for two sub-$C$-sets $A,B ↪ X$ is given by

$x ∈ (A ∖ B)(c) iff ∃f: c′ → c, ∃x′ ∈ f⁻¹⋅x, x′ ∈ A(c′) ∧ x′ ∉ B(c′)$

for all $c ∈ C$ and $x ∈ X(c)$. Compare with implies.


Theory of a proarrow equipment, or equipment for short

Equipments have also been called "framed bicategories," "fibrant double categories," and "gregarious double categories" (?!).


  • Shulman, 2008: Framed bicategories and monoidal fibrations
  • Cruttwell & Shulman, 2010: A unified framework for generalized multicategories

Visualize a function between finite sets using Graphviz.

Visualize a function (FinFunction) between two finite sets (FinSets). Reduces to drawing an undirected bipartite graph; see that method for more.


Data structures for graphs, based on C-sets.

This module provides the category theorist's four basic kinds of graphs: graphs (aka directed multigraphs), symmetric graphs, reflexive graphs, and symmetric reflexive graphs. It also defines half-edge graphs, which are isomorphic to symmetric graphs, and a few standard kinds of attributed graphs, such as weighted graphs.

The graphs API generally follows that of Graphs.jl, with some departures due to differences between the data structures.


Abstract type for C-sets that contain a graph.

This type encompasses C-sets where the schema for graphs is a subcategory of C. This includes, for example, graphs, symmetric graphs, and reflexive graphs, but not half-edge graphs.


Abstract type for C-sets that contain vertices.

This type encompasses C-sets where the schema C contains an object V interpreted as vertices. This includes, for example, graphs and half-edge graphs, but not bipartite graphs or wiring diagrams.


A labeled graph.

By convention, a "labeled graph" without qualification is a vertex-labeled graph. We do not require that the label be unique, and in this data type, the label attribute is not indexed.


A symmetric graph, or graph with an orientation-reversing edge involution.

Symmetric graphs are closely related, but not identical, to undirected graphs.


Involution on half-edge(s) in a half-edge graph.


Involution on edge(s) in a symmetric graph.


Interchange src and tgt, keeping all other data the same


Add a dangling edge to a half-edge graph.

A "dangling edge" is a half-edge that is paired with itself under the half-edge involution. They are usually interpreted differently than "self-loops", i.e., a pair of distinct half-edges incident to the same vertex.


Number of edges in a graph, or between two vertices in a graph.

In a symmetric graph, this function counts both edges in each edge pair, so that the number of edges in a symmetric graph is twice the number of edges in the corresponding undirected graph (at least when the edge involution has no fixed points).


Neighbors of vertex in a graph.

In a graph, this function is an alias for outneighbors; in a symmetric graph, a vertex has the same out-neighbors and as in-neighbors, so the distinction is moot.

In the presence of multiple edges, neighboring vertices are given with multiplicity. To get the unique neighbors, call unique(neighbors(g)).


Remove a vertex from a graph.

When keep_edges is false (the default), all edges incident to the vertex are also deleted. When keep_edges is true, incident edges are preserved but their source/target vertices become undefined.


Wire together two ports in an undirected wiring diagram.

A convenience method that creates and sets junctions as needed. Ports are only allowed to have one junction, so if both ports already have junctions, then the second port is assigned the junction of the first. The handling of the two arguments is otherwise symmetric.

FIXME: When both ports already have junctions, the two junctions should be merged. To do this, we must implement merge_junctions! and thus also rem_part!.


A circular port graph.

Circular port graphs consist of boxes with ports connected by directed wires. The ports are not seperated into inputs and outputs, so the "boxes" are actually circular, hence the name.


An open circular port graph.

Open circular port graphs are circular port graphs with a distinguished set of outer ports. They have a natural operad structure and can be seen as a specialization of directed wiring diagrams.


Generate and parse Julia programs based on diagrams.


Theory of a symmetric monoidal copresheaf

The name is not standard but refers to a lax symmetric monoidal functor into Set. This can be interpreted as an action of a symmetric monoidal category, just as a copresheaf (set-valued functor) is an action of a category. The theory is simpler than that of a general lax monoidal functor because (1) the domain is a strict monoidal category and (2) the codomain is fixed to the cartesian monoidal category Set.

FIXME: This theory should also extend ThCopresheaf but multiple inheritance is not yet supported.


Theory of monoidal double categories

To avoid associators and unitors, we assume that the monoidal double category is fully strict: both the double category and its monoidal product are strict. Apart from assuming strictness, this theory agrees with the definition of a monoidal double category in (Shulman 2010) and other recent works.

In a monoidal double category $(D,⊗,I)$, the underlying categories $D₀$ and $D₁$ are each monoidal categories, $(D₀,⊗₀,I₀)$ and $(D₁,⊗₁,I₁)$, subject to further axioms such as the source and target functors $S, T: D₁ → D₀$ being strict monoidal functors.

Despite the apparent asymmetry in this setup, the definition of a monoidal double category unpacks to be nearly symmetric with respect to arrows and proarrows, except that the monoidal unit $I₀$ of $D₀$ induces the monoidal unit of $D₁$ as $I₁ = U(I₀)$.


  • Shulman, 2010: Constructing symmetric monoidal bicategories

FIXME: Should also inherit ThMonoidalCategory{Ob,Hom} but multiple inheritance is not supported.


Diagram in a category.

Recall that a diagram in a category $C$ is a functor $D: J → C$, where for us the shape category $J$ is finitely presented. Although such a diagram is captured perfectly well by a FinDomFunctor, there are several different notions of morphism between diagrams. The first type parameter T in this wrapper type distinguishes which diagram category the diagram belongs to. See DiagramHom for more about the possible choices. The parameter T may also be Any to indicate that no choice has (yet) been made.


Morphism of diagrams in a category.

In fact, this type encompasses several different kinds of morphisms from a diagram $D: J → C$ to another diagram $D′: J′ → C$:

  1. DiagramHom{id}: a functor $F: J → J′$ together with a natural transformation $ϕ: D ⇒ F⋅D′$
  2. DiagramHom{op}: a functor $F: J′ → J$ together with a natural transformation $ϕ: F⋅D ⇒ D′$
  3. DiagramHom{co}: a functor $F: J → J′$ together with a natural transformation $ϕ: F⋅D′ ⇒ D$.

Note that Diagram{op} is not the opposite category of Diagram{id}, but Diagram{op} and Diagram{co} are opposites of each other. Explicit support is included for both because they are useful for different purposes: morphisms of type DiagramHom{id} and DiagramHom{op} induce morphisms between colimits and between limits of the diagrams, respectively, whereas morphisms of type DiagramHom{co} generalize morphisms of polynomial functors.


Theory of a cartesian double category

Loosely speaking, a cartesian double category is a double category $D$ such that the underlying catgories $D₀$ and $D₁$ are both cartesian categories, in a compatible way.

Reference: Aleiferi 2018, PhD thesis.


Serialize abstract wiring diagrams as GraphML.

Serialization of box, port, and wire values can be overloaded by data type (see convert_to_graphml_data and convert_from_graphml_data).

GraphML is the closest thing to a de jure and de facto standard in the space of graph data formats, supported by a variety of graph applications and libraries. We depart mildly from the GraphML spec by allowing JSON data attributes for GraphML nodes, ports, and edges.


  • GraphML Primer:
  • GraphML DTD:

Category of (possibly infinite) sets and functions.

This module defines generic types for the category of sets (SetOb, SetFunction), as well as a few basic concrete types, such as a wrapper type to view Julia types as sets (TypeSet). Extensive support for finite sets is provided by another module, FinSets.


Abstract type for morphism in the category Set.

Every instance of SetFunction{<:SetOb{T},<:SetOb{T′}} is callable with elements of type T, returning an element of type T′.

Note: This type would be better called simply Function but that name is already taken by the base Julia type.


Abstract type for object in the category Set.

The type parameter T is the element type of the set.

Note: This type is more abstract than the built-in Julia types AbstractSet and Set, which are intended for data structures for finite sets. Those are encompassed by the subtype FinSet.


Forgetful functor Ob: Cat → Set.

Sends a category to its set of objects and a functor to its object map.


Conventions for serialization of wiring diagrams.

Defines a consistent set of names for boxes, ports, and wires to be used when serializing wiring diagrams, as well as conventions for serializing box, port, and wire attributes.


The chase is an algorithm which subjects a C-Set instance to constraints expressed in the language of regular logic, called embedded dependencies (EDs, or 'triggers').

A morphism S->T, encodes an embedded dependency. If the pattern S is matched (via a homomorphism S->I), we demand there exist a morphism T->I (for some database instance I) that makes the triangle commute in order to satisfy the dependency (if this is not the case, then the trigger is 'active').

Homomorphisms can merge elements and introduce new ones. The former kind are called "equality generating dependencies" (EGDs) and the latter "tuple generating dependencies" (TGDs). Any homomorphism can be factored into EGD and TGD components by, respectively, restricting the codomain to the image or restricting the domain to the coimage.


Naively determine active triggers of EDs (S->T) by filtering all triggers (i.e. maps S->I) to see which are active (i.e. there exists no T->I such that S->T->I = S->I). Store the trigger with the ED as a span, I<-S->T.

Optionally initialize the homomorphism search to control the chase process.

chase(I::ACSet, Σ::AbstractDict, n::Int)

Chase a C-Set or C-Rel instance given a list of embedded dependencies. This may not terminate, so a bound n on the number of iterations is required.


ΣS ⟶ Iₙ ⊕↓ ⋮ (resulting morphism) ΣT ... Iₙ₊₁

There is a copy of S and T for each active trigger. A trigger is a map from S into the current instance. What makes it 'active' is that there is no morphism from T to I that makes the triangle commute.

Each iteration constructs the above pushout square. The result is a morphism, so that one can keep track of the provenance of elements in the original CSet instance within the chased result.

Whether or not the result is due to success or timeout is returned as a boolean flag.

TODO: this algorithm could be made more efficient by homomorphism caching.


An equation is a pair of paths: ↗ a₁ → ... → aₙ start ↘ b₁ → ... → bₙ

The EGD that enforces the equation has, as domain a CSet whose category of elements looks like the above graphic. Its codomain is the same, with aₙ and bₙ merged. This merging is performed via a pushout. The diagram above corresponds to l, while r1 is a single point of type aₙ. r2 has two points of that type, with a unique map to r1 and picking out aₙ and bₙ in its map into l.


Given a span of morphisms, we seek to find a morphism B → C that makes a commuting triangle if possible. Accepts homomorphism search keyword arguments to constrain the Hom(B,C) search.


Given a span of morphisms, we seek to find all morphisms B → C that make a commuting triangle.


g ↗ ↘ ? A ⟶ C f This may be impossible, because f(a₁)≠f(a₂) but g(a₁)=g(a₂), in which case return nothing. Otherwise, return a Dict which can be used to initialize the homomorphism search Hom(B,C).


A partially defined inverse to tocrel.

This fails if a C-Rel morphism is non-unique and returns a C-set with undefined references if the morphism isn't total (a return flag signals whether this occured).


Create constraints for enforcing a C-Set schema on a C-Rel instance.

A presentation implies constraints of foreign keys being functional (total and unique) in addition to any extra equations.


We do not have general limits for ACSet transformations, so we cannot yet automatically factor an ED into an EGD+TGD. However, it should be possible to define limits such that the CSetTransformation code above works for ACSets too.


Theory of a displayed category.

More precisely, this is the theory of a category $C$ (Ob,Hom) together with a displayed category over $C$ (Fib,FibHom). Displayed categories axiomatize lax functors $C → **Span**$, or equivalently objects of a slice category $**Cat**/C$, in a generalized algebraic style.



Theory of dagger compact categories

In a dagger compact category, there are two kinds of adjoints of a morphism f::Hom(A,B), the adjoint mate mate(f)::Hom(dual(B),dual(A)) and the dagger adjoint dagger(f)::Hom(B,A). In the category of Hilbert spaces, these are respectively the Banach space adjoint and the Hilbert space adjoint (Reed-Simon, Vol I, Sec VI.2). In Julia, they would correspond to transpose and adjoint in the official LinearAlegbra module. For the general relationship between mates and daggers, see Selinger's survey of graphical languages for monoidal categories.

FIXME: This theory should also extend ThDaggerCategory, but multiple inheritance is not yet supported.


Generate a Julia function expression that will record function calls.

Rewrites the function body so that:

  1. Ordinary function calls are mapped to recorded calls, e.g., f(x,y) becomes recorder(f,x,y)
  2. "Curly" function calls are mapped to ordinary function calls, e.g., f{X,Y} becomes f(X,Y)

Parse a wiring diagram from a Julia program.

For the most part, this is standard Julia code but a few liberties are taken with the syntax. Products are represented as tuples. So if x and y are variables of type $X$ and $Y$, then (x,y) has type $X ⊗ Y$. Also, both () and nothing are interpreted as the monoidal unit $I$.

Unlike standard Julia, the function call expressions f(x,y) and f((x,y)) are equivalent. Consequently, given morphisms $f: W → X ⊗ Y$ and $g: X ⊗ Y → Z$, the code

x, y = f(w)

is equivalent to g(f(w)). In standard Julia, at most one of these calls to g would be valid, unless g had multiple signatures.

The diagonals (copying and deleting) of a cartesian category are implicit in the Julia syntax: copying is variable reuse and deleting is variable non-use. For the codiagonals (merging and creating), a special syntax is provided, reinterpreting Julia's vector literals. The merging of x1 and x2 is represented by the vector [x1,x2] and creation by the empty vector []. For example, f([x1,x2]) translates to compose(mmerge(X),f).

This macro is a wrapper around parse_wiring_diagram.

erdos_renyi(GraphType, n, ne)

Create an Erdős–Rényi random graph with n vertices and ne edges.


erdos_renyi(GraphType, n, p)

Create an Erdős–Rényi random graph with n vertices. Edges are added between pairs of vertices with probability p.

Optional Arguments

  • seed=-1: set the RNG seed.
  • rng: set the RNG directly


expected_degree_graph(GraphType, ω)

Given a vector of expected degrees ω indexed by vertex, create a random undirected graph in which vertices i and j are connected with probability ω[i]*ω[j]/sum(ω).

Optional Arguments

  • seed=-1: set the RNG seed.
  • rng: set the RNG directly

Implementation Notes

The algorithm should work well for maximum(ω) << sum(ω). As maximum(ω) approaches sum(ω), some deviations from the expected values are likely.


randbn(n, p, seed=-1)

Return a binomally-distribted random number with parameters n and p and optional seed.

Optional Arguments

  • seed=-1: set the RNG seed.
  • rng: set the RNG directly


  • "Non-Uniform Random Variate Generation," Luc Devroye, p. 522. Retrieved via
watts_strogatz(n, k, β)

Return a Watts-Strogatz small world random graph with n vertices, each with expected degree k (or `k

  • 1ifkis odd). Edges are randomized per the model based on probabilityβ`.

The algorithm proceeds as follows. First, a perfect 1-lattice is constructed, where each vertex has exacly div(k, 2) neighbors on each side (i.e., k or k - 1 in total). Then the following steps are repeated for a hop length i of 1 through div(k, 2).

  1. Consider each vertex s in turn, along with the edge to its ith nearest neighbor t, in a clockwise sense.

  2. Generate a uniformly random number r. If r ≥ β, then the edge (s, t) is left unaltered. Otherwise, the edge is deleted and rewired so that s is connected to some vertex d, chosen uniformly at random from the entire graph, excluding s and its neighbors. (Note that t is a valid candidate.)

For β = 0, the graph will remain a 1-lattice, and for β = 1, all edges will be rewired randomly.

Optional Arguments

  • is_directed=false: if true, return a directed graph.
  • seed=-1: set the RNG seed.



AST and pretty printer for Graphviz's DOT language.


  • DOT grammar:
  • DOT language guide:

labelloc defaults: "t" (clusters) , "b" (root graphs) , "c" (nodes) For graphs and clusters, only labelloc=t and labelloc=b are allowed


Run a Graphviz program.

Invokes Graphviz through its command-line interface. If the Graphviz_jll package is installed and loaded, it is used; otherwise, Graphviz must be installed on the local system.

For bindings to the Graphviz C API, see the the package GraphViz.jl. At the time of this writing, GraphViz.jl is unmaintained.


Serialize abstract wiring diagrams as JSON.

JSON data formats are convenient when programming for the web. Unfortunately, no standard for JSON graph formats has gained any kind of widespread adoption. We adopt a format compatible with that used by the KEILER project and its successor ELK (Eclipse Layout Kernel). This format is roughly feature compatible with GraphML, supporting nested graphs and ports. It also supports layout information like node position and size.


  • KEILER's JSON graph format:
  • ELK's JSON graph format:

Function between finite sets.

The function can be defined implicitly by an arbitrary Julia function, in which case it is evaluated lazily, or explictly by a vector of integers. In the vector representation, the function (1↦1, 2↦3, 3↦2, 4↦3), for example, is represented by the vector [1,3,2,3].

FinFunctions can be constructed with or without an explicitly provided codomain. If a codomain is provided, by default the constructor checks it is valid.

This type is mildly generalized by FinDomFunction.


Finite set.

A finite set has abstract type FinSet{S,T}. The second type parameter T is the element type of the set and the first parameter S is the collection type, which can be a subtype of AbstractSet or another Julia collection type. In addition, the skeleton of the category FinSet is the important special case S = Int. The set ${1,…,n}$ is represented by the object FinSet(n) of type FinSet{Int,Int}.


Limit of finite sets with a reverse mapping or index into the limit set.

This type provides a fallback for limit algorithms that do not come with a specialized algorithm to apply the universal property of the limit. In such cases, you can explicitly construct a mapping from tuples of elements in the feet of the limit cone to elements in the apex of the cone.

The index is constructed the first time it is needed. Thus there is no extra cost to using this type if the universal property will not be invoked.


Indexed function between finite sets of type FinSet{Int}.

Indexed functions store both the forward map $f: X → Y$, as a vector of integers, and the backward map $f: Y → X⁻¹$, as a vector of vectors of integers, accessible through the preimage function. The backward map is called the index. If it is not supplied through the keyword argument index, it is computed when the object is constructed.

This type is mildly generalized by IndexedFinDomFunctionVector.


Compute colimit of finite sets whose elements are meaningfully named.

This situation seems to be mathematically uninteresting but is practically important. The colimit is computed by reduction to the skeleton of FinSet (FinSet{Int}) and the names are assigned afterwards, following some reasonable conventions and add tags where necessary to avoid name clashes.


Limit of finite sets viewed as a table.

Any limit of finite sets can be canonically viewed as a table (TabularSet) whose columns are the legs of the limit cone and whose rows correspond to elements of the limit object. To construct this table from an already computed limit, call TabularLimit(::AbstractLimit; ...). The column names of the table are given by the optional argument names.

In this tabular form, applying the universal property of the limit is trivial since it is just tupling. Thus, this representation can be useful when the original limit algorithm does not support efficient application of the universal property. On the other hand, this representation has the disadvantage of generally making the element type of the limit set more complicated.


Finite set whose elements are rows of a table.

The underlying table should be compliant with Tables.jl. For the sake of uniformity, the rows are provided as named tuples, which assumes that the table is not "extremely wide". This should not be a major limitation in practice but see the Tables.jl documentation for further discussion.


Data type of a map out of a set of attribute variables

Currently, domains are FinSet{Int} and codomains are expected to be FinSet{Int}. This could be generalized to being FinSet{Symbol} to allow for symbolic attributes. (Likewise, AttrVars will have to wrap Any rather than Int)


Compute all possible equalizers in a bipartite free diagram.

The result is a new bipartite free diagram that has the same vertices but is simple, i.e., has no multiple edges. The list of inclusion morphisms into layer 1 of the original diagram is also returned.


Perform all possible pairings in a bipartite free diagram.

The resulting diagram has the same layer 1 vertices but a possibly reduced set of layer 2 vertices. Layer 2 vertices are merged when they have exactly the same multiset of adjacent vertices.


Syntax for a free cartesian category.

In this syntax, the pairing and projection operations are defined using duplication and deletion, and do not have their own syntactic elements. This convention could be dropped or reversed.


Apply category of elements functor to a morphism f: X->Y. This relies on the fact elements of an object puts El components from the same Ob in a contiguous index range.


construct the category of elements from an ACSet. This only correctly handles the CSet part. This transformation converts an instance of C into a Graph homomorphism. The codomain of the homomorphism is a graph shaped like the schema. This is one half of the isomorphism between databases and knowledge graphs.

inverse_elements(X::AbstractElements, typ::StructACSet)

Compute inverse grothendieck transformation on the result of elements. Does not assume that the elements are ordered. Rather than dynamically create a new ACSet type, it requires any instance of the ACSet type that it's going to try to create

If the typed graph tries to assert conflicting values for a foreign key, fail. If no value is specified for a foreign key, the result will have 0's.


convert a category of elements into a new schema. This is useful for generating large schemas that are defined as the category of elements of a specified C-Set. For example, the schema for Bipartite Graphs is the category of elements of the graph with 2 vertices and 1 edge. The 2 vertices will get mapped to elements V_1, V_2 and the one edge will be E_1 and the source and target maps will be mapped to src_E_1, tgt_E_1.


Theory of a distributive bicategory of relations


  • Carboni & Walters, 1987, "Cartesian bicategories I", Remark 3.7 (mention in passing only)
  • Patterson, 2017, "Knowledge representation in bicategories of relations", Section 9.2

FIXME: Should also inherit ThBicategoryOfRelations, but multiple inheritance is not yet supported.


Theory of a distributive (symmetric) monoidal category

Reference: Jay, 1992, LFCS tech report LFCS-92-205, "Tail recursion through universal invariants", Section 3.2

FIXME: Should also inherit ThCocartesianCategory.


Theory of an ℳ-category.

The term "ℳ-category", used on the nLab is not very common, but the concept itself shows up commonly. An ℳ-category is a category with a distinguished wide subcategory, whose morphisms are suggestively called tight; for contrast, a generic morphism is called loose. Equivalently, an ℳ-category is a category enriched in the category ℳ of injections, the full subcategory of the arrow category of Set spanned by injections.

In the following GAT, tightness is axiomatized as a property of morphisms: a dependent family of sets over the hom-sets, each having at most one inhabitant.


Theory of monoidal categories

To avoid associators and unitors, we assume that the monoidal category is strict. By the coherence theorem this involves no loss of generality, but we might add a theory for weak monoidal categories later.


Theory of an opindexed, or covariantly indexed, monoidal category.

An opindexed monoidal category is a pseudofunctor into MonCat, the 2-category of monoidal categories, strong monoidal functors, and monoidal natural transformations. For simplicity, we take the pseudofunctor, the monoidal categories, and the monoidal functors all to be strict.



Theory of lattices as posets

A (bounded) lattice is a poset with all finite meets and joins. Viewed as a thin category, this means that the category has all finite products and coproducts, hence the names for the inequality constructors in the theory. Compare with ThCartesianCategory and ThCocartesianCategory.

This is one of two standard axiomatizations of a lattice, the other being ThAlgebraicLattice.


Theory of thin categories

Thin categories have at most one morphism between any two objects and are isomorphic to preorders.


Parse Graphviz output in JSON format.

Returns a property graph with graph layout and other metadata. Each node has a position and size.

All units are in points. Note that Graphviz has 72 points per inch.


Parse Graphviz spline.

In Graphviz, a "spline" is a cubic B-spline of overlapping cubic Bezier curves. It consists of 3n+1 points, where n is the number of Bezier curves.


Convert a property graph to a Graphviz graph.

This method is usually more convenient than direct AST manipulation for creating simple Graphviz graphs. For more advanced features, like nested subgraphs, you must use the Graphviz AST.


Visualize a bipartite graph using Graphviz.

Works for both directed and undirected bipartite graphs. Both types of vertices in the bipartite graph become nodes in the Graphviz graph.


  • prog="dot": Graphviz program to use
  • graph_attrs: Graph-level Graphviz attributes
  • node_attrs: Node-level Graphviz attributes
  • edge_attrs: Edge-level Graphviz attributes
  • node_labels=false: whether to label nodes and if so, which pair of data attributes to use
  • edge_labels=false: whether to label edges and if so, which data attribute (undirected case) or pair of attributes (directed case) to use
  • invis_edge=true: whether to add invisible edges between vertices of same type, which ensures that the order of the nodes is preserved.

Convert a graph to a Graphviz graph.

A simple default style is applied. For more control over the visual appearance, first convert the graph to a property graph, define the Graphviz attributes as needed, and finally convert the property graph to a Graphviz graph.


Visualize a graph homomorphism using Graphviz.

Visualize a homomorphism (ACSetTransformation) between two graphs (instances of AbstractGraph). By default, the domain and codomain are drawn as subgraphs and the vertex mapping is drawn using dotted edges, whereas the edge map is suppressed. The vertex and edge mapping can also be shown using colors, via the node_colors and edge_colors keyword arguments.


  • draw_codom=true: whether to draw the codomain graph
  • draw_mapping=true: whether to draw the vertex mapping using edges
  • prog="dot": Graphviz program to use
  • graph_attrs: Graph-level Graphviz attributes
  • node_attrs: Node-level Graphviz attributes
  • edge_attrs: Edge-level Graphviz attributes
  • node_labels=false: whether to draw node labels and which vertex attribute to use
  • edge_labels=false: whether to draw edge labels and which edge attribute to use
  • node_colors=!draw_codom: whether and how to color nodes based on vertex map
  • edge_colors=!draw_codom: whether and how to color edges based on edge map

Theory of a double category with tabulators

A tabulator of a proarrow is a double-categorical limit. It is a certain cell with identity domain to the given proarrow that is universal among all cells of that form. A double category "has tabulators" if the external identity functor has a right adjoint. The values of this right adjoint are the apex objects of its tabulators. The counit of the adjunction provides the universal cells. Tabulators figure in the double-categorical limit construction theorem of Grandis-Pare 1999. In the case where the double category is actually a 2-category, tabulators specialize to cotensors, a more familiar 2-categorical limit.

bfs_parents(g, s[; dir=:out])

Perform a breadth-first search of graph g starting from vertex s. Return a vector of parent vertices indexed by vertex. If dir is specified, use the corresponding edge direction (:in and :out are acceptable values).


This implementation is designed to perform well on large graphs. There are implementations which are marginally faster in practice for smaller graphs, but the performance improvements using this implementation on large graphs can be significant.

bfs_tree(g, s[; dir=:out])

Provide a breadth-first traversal of the graph g starting with source vertex s, and return a directed acyclic graph of vertices in the order they were discovered. If dir is specified, use the corresponding edge direction (:in and :out are acceptable values).

dfs_parents(g, s[; dir=:out])

Perform a depth-first search of graph g starting from vertex s. Return a vector of parent vertices indexed by vertex. If dir is specified, use the corresponding edge direction (:in and :out are acceptable values).

Implementation Notes

This version of DFS is iterative.


Theory of a pointed set-enriched category. We axiomatize a category equipped with zero morphisms.

A functor from an ordinary category into a freely generated pointed-set enriched category, equivalently, a pointed-set enriched category in which no two nonzero maps compose to a zero map, is a good notion of a functor that's total on objects and partial on morphisms.


The GAT that parameterizes Attributed C-sets A schema is comprised of a category C, a discrete category D, and a profunctor Attr : C^op x D → Set. In GAT form, this is given by extending the theory of categories with two extra types, AttrType for objects of D, and Attr, for elements of the sets given by the profunctor.


Theory of an opindexed monoidal category with cocartesian indexing category.

This is equivalent via the Grothendieck construction to a monoidal opfibration over a cocartesian monoidal base (Shulman 2008, Theorem 12.7). The terminology "coindexed monoidal category" used here is not standard and arguably not good, but I'm running out of ways to combine these adjectives.


  • Shulman, 2008: Framed bicategories and monoidal fibrations
  • Shulman, 2013: Enriched indexed categories

Theory of an opindexed, or covariantly indexed, category.

An opindexed category is a Cat-valued pseudofunctor. For simplicitly, we assume that the functor is strict.

Just as a copresheaf, or Set-valued functor, can be seen as a category action on a family of sets, an opindexed category can be seen as a category action on a family of categories. This picture guides our axiomatization of an opindexed category as a generalized algebraic theory. The symbol * is used for the actions since a common mathematical notation for the "pushforward functor" induced by an indexing morphism $f: A → B$ is $f_*: F(A) o F(B)$.


Theory of preorders

The generalized algebraic theory of preorders encodes inequalities $A≤B$ as dependent types `$Leq(A,B)$ and the axioms of reflexivity and transitivity as term constructors.


Theory of additive categories

An additive category is a biproduct category enriched in abelian groups. Thus, it is a semiadditive category where the hom-monoids have negatives.


Crossing minimization by sorting a univariate statistic.

The boxes in sources and/or targets are fixed and the boxes in vs are permuted. A permutation σ of the latter is returned, such that vs[σ] are the sorted box IDs. Both one-sided and two-sided crossing minimization are supported, depending on whether just one, or both, of sources and targets are given.

In this simple but popular heuristic algorithm, the boxes are permuted by sorting a univariate statistic of the positions of incoming and/or outgoing wires. Typical choices are:

  • mean: the sample mean, yielding the "barycenter method"
  • median: the sample median

In both cases, this algorithm has the property that if there is a permutation with no crossings, it will find it.


Normalize copies in a wiring diagram.

This function maximizes sharing of intermediate computations in a wiring diagram where copies are natural.

This algorithm is basically the same as the congruence closure algorithm on term graphs, in the special case of the empty relation R = ∅ (Baader & Nipkow, 1998, Term Rewriting and All That, Sec. 4.4). The main difference is the possibility of zero or many function outputs.


Wiring diagrams as a symmetric monoidal category.

This module provides a high-level categorical interface to wiring diagrams, building on the low-level imperative interface and the operadic interface. It also defines data types and functions to represent diagonals, codiagonals, duals, caps, cups, daggers, and other gadgets in wiring diagrams.


2-category of finitely presented categories.

This module is for the 2-category Cat what the module FinSets is for the category Set: a finitary, combinatorial setting where explicit calculations can be carried out. We emphasize that the prefix Fin means "finitely presented," not "finite," as finite categories are too restrictive a notion for many purposes. For example, the free category on a graph is finite if and only if the graph is DAG, which is a fairly special condition. This usage of Fin is also consistent with FinSet because for sets, being finite and being finitely presented are equivalent.


Category presented by a finite graph together with path equations.

The objects of the category are vertices in the graph and the morphisms are paths, quotiented by the congruence relation generated by the path equations. See (Spivak, 2014, Category theory for the sciences, §4.5).


Category defined by a Presentation object.

The presentation type can, of course, be a category (Theories.Category). It can also be a schema (Theories.Schema). In this case, the schema's objects and attribute types are regarded as the category's objects and the schema's morphisms, attributes, and attribute types as the category's morphisms (where the attribute types are identity morphisms). When the schema is formalized as a profunctor whose codomain category is discrete, this amounts to taking the collage of the profunctor.


A natural transformation whose domain category is finitely generated.

This type is for natural transformations $α: F ⇒ G: C → D$ such that the domain category $C$ is finitely generated. Such a natural transformation is given by a finite amount of data (one morphism in $D$ for each generating object of $C$) and its naturality is verified by finitely many equations (one equation for each generating morphism of $C$).


Reinterpret a functor on a finitely presented category as a functor on the equivalent category (ignoring equations) free on a graph. Also normalizes the input to have vector obmap and hommap, with valtype optionally specified. This is useful when the domain is empty or when the maps might be tightly typed but need to allow for types such as that of identity morphisms upon mutation.


Force evaluation of lazily defined function or functor. The resulting obmap and hommap are guaranteed to have valtype or eltype, as appropriate, equal to Ob and Hom, respectively.


Failures of the purported functor on a presented category to be functorial.

Similar to is_functorial (and with the same caveats) but returns iterators of functoriality failures: one for domain incompatibilities, one for codomain incompatibilities, and one for equations that are not satisfied.


Coerce or look up morphism generator in a finitely presented category.

Since morphism generators often have a different data type than morphisms (e.g., in a free category on a graph, the morphism generators are edges and the morphisms are paths), the return type of this function is generally different than that of hom.


Is the purported functor on a presented category functorial?

This function checks that functor preserves domains and codomains. When check_equations is true (the default is false), it also purports to check that the functor preserves all equations in the domain category. No nontrivial checks are currently implemented, so this only functions for identity functors.

See also: `functoriality_failures' and is_natural.


Dual to a final functor, an initial functor is one for which pulling back diagrams along it does not change the limits of these diagrams.

This amounts to checking, for a functor C->D, that, for every object d in Ob(D), the comma category (F/d) is connected.


Is the transformation between FinDomFunctors a natural transformation?

This function uses the fact that to check whether a transformation is natural, it suffices to check the naturality equations on a generating set of morphisms of the domain category. In some cases, checking the equations may be expensive or impossible. When the keyword argument check_equations is false, only the domains and codomains of the components are checked.

See also: is_functorial.


Maps f over a UnitRange to produce a Vector, or else over anything to produce a Dict. The type paramter functions to ensure the return type is as desired even when the input is empty.


Coerce or look up object generator in a finitely presented category.

Because object generators usually coincide with objects, the default method for ob in finitely presented categories simply calls this function.


Object generators of finitely presented category.

The object generators of finite presented category are almost always the same as the objects. In principle, however, it is possible to have equations between objects, so that there are fewer objects than object generators.


Computes the graph generating a finitely presented category. Ignores any attribute side and any equations. Optionally returns the mappings from generators to their indices in the resulting graph.


Backend-agnostic layout of wiring diagrams via morphism expressions.

This module lays out wiring diagrams for visualization, independent of any specific graphics system. It uses the structure of a morphism expression to determine the layout. Thus, the first step of the algorithm is to convert the wiring diagram to a symbolic expression, using the submodule WiringDiagrams.Expressions. Morphism expressions may also be given directly.


Layout for box in a wiring diagram.

Suggests a shape, size, and position for the box. Also includes the box's value, typically used for labels, and a style name, which does not affect the layout but is interpreted by graphics backends to adjust the visual style.

Specific features of the shape are determined by the graphics backend. For example, a rectangle could be rendered with or without rounded corners or even as another, similar shape, such as a parallelogram.


Compute the default size of a rectangular box from the number of its ports.

We use the unique formula consistent with the padding for monoidal products, ensuring that the size of a product of boxes depends only on the total number of ports, not on the number of boxes.


Lay out a wiring diagram or morphism expression for visualization.

If a wiring diagram is given, it is first to converted to a morphism expression.

The layout is calculated with respect to a cartesian coordinate system with origin at the center of the diagram and the positive y-axis pointing downwards. Box positions are relative to their centers. All positions and sizes are dimensionless (unitless).


Compose morphisms according to UWD.

The morphisms corresponding to the boxes, and optionally also the objects corresponding to the junctions, are given by dictionaries indexed by box/junction attributes. The default attributes are those compatible with the @relation macro.


Evaluate a conjunctive query on an attributed C-set.

The conjunctive query is represented as an undirected wiring diagram (UWD) whose boxes and ports are named via the attributes :name, :port_name, and :outer_port_name. To define such a diagram, use the @relation macro with its named syntax. Parameters to the query may be passed as a collection of pairs using the optional third argument.

The result is data table whose columns correspond to the outer ports of the UWD. By default, a data frame is returned if the package DataFrames.jl is loaded; otherwise, a named tuple is returned. To change this behavior, set the keyword argument table_type to a type or function taking two arguments, a vector of columns and a vector of column names. There is one exceptional case: if the UWD has no outer ports, the query is a counting query and the result is a vector whose length is the number of results.

For its implementation, this function wraps the oapply method for multispans, which defines the UWD algebra of multispans.


AST and pretty printer for TikZ.

This module does not provide bindings to the TikZ LaTeX package. For that, see the TikzPictures.jl package:

The AST is large but still incomplete! It supports:

  • Nodes (\node) and edges (\draw)
  • Nodes along edges (\draw ... node ...)
  • Graphs (\graph)
  • Matrices (\matrix)
  • Scopes and nested pictures

The AST is adapted from the (also incomplete) BNF grammar for TikZ in TikZit.


Theory of a (finitely) complete category

Finite limits are presented in biased style, via finite products and equalizers. The equational axioms for equalizers are obscure, but can found in (Lambek & Scott, 1986, Section 0.5), who in turn attribute them to "Burroni's pioneering ideas". Strictly speaking, this theory is not of a "finitely complete category" (a category in which finite limits exist) but of a "category with chosen finite limits".


Functionality related to search problems involving ACSets, e.g.:

  • enumerating Hom(X,Y) where X,Y are ACSets
  • enumerating subobjects of an ACSet, X
  • enumerating partial overlaps between ACSets

Find attributed $C$-set homomorphisms using backtracking search.

This procedure uses the classic backtracking search algorithm for a combinatorial constraint satisfaction problem (CSP). As is well known, the homomorphism problem for relational databases is reducible to CSP. Since the C-set homomorphism problem is "the same" as the database homomorphism problem (insofar as attributed C-sets are "the same" as relational databases), it is also reducible to CSP. Backtracking search for CSP is described in many computer science textbooks, such as (Russell & Norvig 2010, Artificial Intelligence, Third Ed., Chapter 6: Constraint satisfaction problems, esp. Algorithm 6.5). In our implementation, the search tree is ordered using the popular heuristic of "minimum remaining values" (MRV), also known as "most constrained variable.


Internal state for backtracking search for ACSet homomorphisms.

Assignment of attribute variables maintains both the assignment as well as the number of times that variable has been bound. We can only freely assign the variable to match any AttrVar or concrete attribute value if it has not yet been bound.


Find attributed $C$-set homomorphisms using a conjunctive query.

This algorithm evaluates a conjunctive query (limit in FinSet) to find all homomorphisms between two $C$-sets. In fact, conjunctive queries are exactly the representable functors from $C$-sets to sets, so every conjunctive query arises in this way, with the caveat that conjunctive queries may correspond to to infinite $C$-sets when $C$ is infinite (but possibly finitely presented).


Given a list of ACSets X₁...Xₙ, find all multispans A ⇉ X ordered by decreasing number of total parts of A.

We search for overlaps guided by iterating through the subobjects of the smallest ACSet.

If a subobject of the first object, A↪X, has multiple maps into X₁, then we need to cache a lot of work because we consider each such subobject independently. This is the maps from A into all the other objects as well as the automorphisms of A.


Attempt to assign element (c,x) to (c,y) in the current assignment.

Returns whether the assignment succeeded. Note that the backtracking state can be mutated even when the assignment fails.


Find a homomorphism between two attributed $C$-sets.

Returns nothing if no homomorphism exists. For many categories $C$, the $C$-set homomorphism problem is NP-complete and thus this procedure generally runs in exponential time. It works best when the domain object is small.

To restrict to monomorphisms, or homomorphisms whose components are all injective functions, set the keyword argument monic=true. To restrict only certain components to be injective or bijective, use monic=[...] or iso=[...]. For example, setting monic=[:V] for a graph homomorphism ensures that the vertex map is injective but imposes no constraints on the edge map.

To restrict the homomorphism to a given partial assignment, set the keyword argument initial. For example, to fix the first source vertex to the third target vertex in a graph homomorphism, set initial=(V=Dict(1 => 3),). Use the keyword argument type_components to specify nontrivial components on attribute types for a loose homomorphism. These components must be callable: either Julia functions on the appropriate types or FinFunction(Dict(...)).

Use the keyword argument alg to set the homomorphism-finding algorithm. By default, a backtracking search algorithm is used (BacktrackingSearch). Use the keyword argument error_failures = true to get errors explaining any immediate inconsistencies in specified initial data.

The keyword predicates accepts a Dict{Ob, Dict{Int, Union{Nothing, AbstractVector{Int}}}} For each part of the domain, we have the option to give a constraint as a boolean function of the current assignment and tentative value to assign. E.g. predicates = (E = Dict(2 => [2,4,6])) would only find matches which assigned edge#2 to edge #2, #4, or #6 in the codomain.

See also: homomorphisms, isomorphism.


Compute the Maximimum Common C-Sets from a vector of C-Sets.

Find an ACSet `$a$ with maximum possible size ($|a|$) such that there is a monic span of ACSets $a₁ ← a → a₂$. There may be many maps from this overlap into each of the inputs, so a Vector{Vector{ACSetTransformations}} per overlap is returned (a cartesian product can be taken of these to obtain all possible multispans for that overlap). If there are multiple overlaps of equal size, these are all returned.

If there are attributes, we ignore these and use variables in the apex of the overlap.


Compute the size of a C-Set

Defintion: let 𝐺: C → 𝐒et be a C-set, we define the size of 𝐺 to be ∑_{c ∈ C} |𝐺c|. For example, under this definition, the size of:

  • a graph G is |GE| + |GV| (num edges + num vertices)
  • a Petri net P is |PT| + |PS| + |PI| + |PO| (num transitions + num species + num input arcs + num output arcs).

Provides a shorthand for constructing a tight acset transformation by giving its components. Homomorphism search allows partial specification, with the return value being the unique extension if it exists.

Keyword arguments can be passed on to the search function after the body of the transformation.

Example usage for transformation between WeightedGraph{String}:

@acset_transformation A B begin
  V = [3,5,2] #complete specification can be a vector
  E = Dict(1 => 3, 4 => 3) #otherwise use a dict
end monic=true iso=[:V] or [:V,:E], etc

Theory of double categories

A strict double category $D$ is an internal category

$(S,T: D₁ ⇉ D₀, U: D₀ → D₁, *: D₁ ×_{D₀} D₁ → D₁)$

in Cat where

  • objects of $D₀$ are objects of $D$
  • morphisms of $D₀$ are arrows (vertical morphisms) of $D$
  • objects of $D₁$ are proarrows (horizontal morphisms) of $D$
  • morphisms of $D₁$ are cells of $D$.

The domain and codomain (top and bottom) of a cell are given by the domain and codomain in $D₁$ and the source and target (left and right) are given by the functors $S,T$.


Evaluate a morphism as a function.

If the morphism will be evaluated only once (possibly with vectorized inputs), then direct evaluation will be much faster than compiling (via compile) and evaluating a standard Julia function.

Compare with functor.


Extends the basic graph types with vertex and/or edge names.

Naming vertices and edges and looking them up by name is a common requirement. This module provides a simple interface and default graph types for named graphs. Names are understood to be unique within the graph but are not assumed to be strings or symbols.


Syntax for a free cocartesian category.

In this syntax, the copairing and inclusion operations are defined using merging and creation, and do not have their own syntactic elements. This convention could be dropped or reversed.


Decompose permutation into adjacent transpositions using bubble sort.

An adjacent transposition, also known as a simple transposition, is a transposition of form (i i+1), represented here as simply the number i.

This algorithm appears as Algorithm 2.7 in the PhD thesis of Jonathan Huang, "Probabilistic reasonsing and learning on permutations: Exploiting structural decompositions of the symmetric group". As Huang notes, the algorithm is very similar to the well-known bubble sort. It has quadratic complexity.

See also: adjacent_transpositions_by_insertion_sort!.


Decompose permutation into adjacent transpositions using insertion sort.

An adjacent transposition, also known as a simple transposition, is a transposition of form (i i+1), represented here as simply the number i.

Bubble sort and insertion sort are, in a sense, dual algorithms (Knuth, TAOCP, Vol 3: Searching and Sort, Sec 5.3.4: Networks for sorting, Figures 45 & 46). A minimal example on which they give different decompositions is the permutation:

[1,2,3] ↦ [3,2,1]

See also: adjacent_transpositions_by_bubble_sort!.


Theory of bicategories of relations

TODO: The 2-morphisms are missing.


  • Carboni & Walters, 1987, "Cartesian bicategories I"
  • Walters, 2009, blog post, "Categorical algebras of relations",

Theory of symmetric monoidal double categories

Unlike the classical notion of strict double categories, symmetric monoidal double categories do not treat the two directions on an equal footing, even when everything (except the braiding) is strict. See ThMonoidalDoubleCategory for references.

FIXME: Should also inherit ThSymmetricMonoidalCategory{Ob,Hom} but multiple inheritance is not supported.