`Catlab.Theories.ThHypergraphCategory`

— ModuleTheory 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.

`Catlab.WiringDiagrams.WiringDiagramExpressions`

— ModuleConvert 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.

`Catlab.WiringDiagrams.WiringDiagramExpressions.compose_simplify_id`

— MethodCompose morphism expressions, eliminating identities.

`Catlab.WiringDiagrams.WiringDiagramExpressions.find_one_sided_parallel`

— MethodFind one-sided parallel compositions in a directed graph.

Finds either input-sided or output-sided compositions. This weaker notion of parallel composition seems to be nonstandard.

`Catlab.WiringDiagrams.WiringDiagramExpressions.find_parallel`

— MethodFind parallel compositions in a directed graph.

This two-sided notion of parallel composition is standard in the literature on series-parallel digraphs.

`Catlab.WiringDiagrams.WiringDiagramExpressions.find_series`

— MethodFind series compositions in a directed graph.

`Catlab.WiringDiagrams.WiringDiagramExpressions.hom_expr_between`

— MethodMorphism expression for wires between two boxes.

Assumes that the wires form a permutation morphism.

`Catlab.WiringDiagrams.WiringDiagramExpressions.input_parallel_reduction`

— MethodInput-sided parallel reduction of a wiring diagram.

Because these reductions are not necessarily unique, only one is performed, the first one in topological sort order.

`Catlab.WiringDiagrams.WiringDiagramExpressions.junction_to_expr`

— MethodConvert a junction node to a morphism expression.

`Catlab.WiringDiagrams.WiringDiagramExpressions.output_parallel_reduction`

— MethodOutput-sided parallel reduction of a wiring diagram.

Because these reductions are not necessarily unique, only one is performed, the last one in topological sort order.

`Catlab.WiringDiagrams.WiringDiagramExpressions.parallel_reduction`

— MethodAll possible parallel reductions of a wiring diagram.

`Catlab.WiringDiagrams.WiringDiagramExpressions.series_reduction`

— MethodAll possible series reductions of a wiring diagram.

`Catlab.WiringDiagrams.WiringDiagramExpressions.to_hom_expr`

— MethodConvert a wiring diagram into a morphism expression.

`Catlab.WiringDiagrams.WiringDiagramExpressions.to_ob_expr`

— MethodConvert a port value into an object expression.

`Catlab.WiringDiagrams.WiringDiagramExpressions.to_undirected_wiring_diagram`

— MethodConvert a morphism expression into an undirected wiring diagram.

Returns a `HomUWD`

, or a UWD with outer ports partitioned domain and codomain.

`Catlab.WiringDiagrams.WiringDiagramExpressions.to_wiring_diagram`

— MethodConvert a morphism expression into a wiring diagram.

`Catlab.WiringDiagrams.WiringDiagramExpressions.transitive_reduction!`

— MethodAll possible transitive reductions of a wiring diagram.

`Catlab.Theories.ThCategoryWithCoproducts`

— ModuleTheory of a *category with (finite) coproducts*

Finite coproducts are presented in biased style, via the nullary case (initial objects) and the binary case (binary coproducts). The axioms are dual to those of `ThCategoryWithProducts`

.

For a monoidal category axiomatization of finite coproducts, see `ThCocartesianCategory`

.

`Catlab.Graphs.BipartiteGraphs`

— ModuleBipartite 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.

`Catlab.Graphs.BipartiteGraphs.AbstractBipartiteGraph`

— TypeAbstract type for bipartite graphs.

`Catlab.Graphs.BipartiteGraphs.AbstractUndirectedBipartiteGraph`

— TypeAbstract type for undirected bipartite graphs.

`Catlab.Graphs.BipartiteGraphs.BipartiteGraph`

— TypeA bipartite graph, better known as a bipartite directed multigraph.

Directed bipartite graphs are isomorphic to port hypergraphs and to whole grain Petri nets.

`Catlab.Graphs.BipartiteGraphs.HasBipartiteGraph`

— TypeAbstract type for C-sets that contain a (directed) bipartite graph.

`Catlab.Graphs.BipartiteGraphs.HasBipartiteVertices`

— TypeAbstract type for C-sets that contain a bipartition of vertices.

`Catlab.Graphs.BipartiteGraphs.UndirectedBipartiteGraph`

— TypeAn 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.

`Catlab.Graphs.BipartiteGraphs.add_edges₁₂!`

— MethodAdd edges from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.add_edges₂₁!`

— MethodAdd edges from V₂ to V₁ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.add_edge₁₂!`

— MethodAdd edge from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.add_edge₂₁!`

— MethodAdd edge from V₂ to V₁ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.add_vertex₁!`

— MethodAdd a vertex of type 1 to a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.add_vertex₂!`

— MethodAdd a vertex of type 2 to a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.add_vertices₁!`

— MethodAdd vertices of type 1 to a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.add_vertices₂!`

— MethodAdd vertices of type 2 to a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.edges₁₂`

— MethodEdges from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.edges₂₁`

— MethodEdges from V₂ to V₁ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.ne₁₂`

— MethodNumber of edges from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.ne₂₁`

— MethodNumber of edges from V₂ to V₁ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.nv₁`

— MethodNumber of vertices of type 1 in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.nv₂`

— MethodNumber of vertices of type 2 in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.rem_edges₁₂!`

— MethodRemove edges from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.rem_edges₂₁!`

— MethodRemove edges from V₂ to V₁ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.rem_edge₁₂!`

— MethodRemove edge from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.rem_edge₂₁!`

— MethodRemove edge from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.rem_vertex₁!`

— MethodRemove vertex of type 1 from a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.rem_vertex₂!`

— MethodRemove vertex of type 2 from a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.rem_vertices₁!`

— MethodRemove vertices of type 1 from a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.rem_vertices₂!`

— MethodRemove vertices of type 2 from a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.src₁`

— MethodSource vertex of edge from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.src₂`

— MethodSource vertex of edge from V₂ to V₁ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.tgt₁`

— MethodTarget vertex of edge from V₂ to V₁ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.tgt₂`

— MethodTarget vertex of edge from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.vertices₁`

— MethodVertices of type 1 in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.vertices₂`

— MethodVertices of type 2 in a bipartite graph.

`Catlab.Programs.RelationalPrograms`

— ModuleParse relation expressions in Julia syntax into undirected wiring diagrams.

`Catlab.Programs.RelationalPrograms.RelationDiagram`

— TypeAbstract type for UWDs created by `@relation`

macro.

`Catlab.Programs.RelationalPrograms.TypedRelationDiagram`

— TypeTyped UWD created by `@relation`

macro.

`Catlab.Programs.RelationalPrograms.UntypedRelationDiagram`

— TypeUntyped UWD created by `@relation`

macro.

`Catlab.Programs.RelationalPrograms.parse_relation_diagram`

— MethodParse an undirected wiring diagram from a relation expression.

For more information, see the corresponding macro `@relation`

.

`Catlab.Programs.RelationalPrograms.@relation`

— MacroConstruct 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
R(x,y)
S(y,z)
end
```

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:

- Untyped, unnamed:
`@relation (x,z) where (x,y,z) ...`

- Typed, unnamed:
`@relation (x,z) where (x::X, y::Y, z::Z) ...`

- Untyped, named:
`@relation (out1=x, out2=z) where (x,y,z) ...`

- Typed, named:
`@relation (out=1, out2=z) where (x::X, y::Y, z::Z) ...`

All four types of diagram are subtypes of `RelationDiagram`

.

`Catlab.WiringDiagrams.MonoidalUndirectedWiringDiagrams`

— ModuleUndirected wiring diagrams as SMCs and hypergraph categories.

`Catlab.WiringDiagrams.MonoidalUndirectedWiringDiagrams.HomUWD`

— TypeUndirected wiring diagram with specified domain and codomain.

The outer ports of the undirected wiring diagram are partitioned into domain and codomain by masks (bit vectors).

`Catlab.WiringDiagrams.MonoidalUndirectedWiringDiagrams.HypergraphDiagram`

— TypeDiagram to represent morphisms in hypergraph categories.

An undirected wiring diagram where the ports and junctions are typed and the boxes have names identifying the morphisms.

`Catlab.WiringDiagrams.MonoidalUndirectedWiringDiagrams.ObUWD`

— TypeList of port types representing outer boundary of undirected wiring diagram.

`Catlab.WiringDiagrams.MonoidalUndirectedWiringDiagrams.UntypedHypergraphDiagram`

— TypeDiagram to represent morphisms in single-sorted hypergraph categories.

By "single-sorted", we mean that the monoid of objects is free on one generator. See `HypergraphDiagram`

for the more standard case.

`Catlab.WiringDiagrams.MonoidalUndirectedWiringDiagrams.##docsink#3316`

— FunctionUndirected wiring diagrams as a hypergraph category.

The objects are lists of port types and morphisms are undirected wiring diagrams whose outer ports are partitioned into domain and codomain.

`Catlab.WiringDiagrams.MonoidalUndirectedWiringDiagrams.cospan_action`

— MethodAct 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.

`Catlab.Theories.ThAbelianBicategoryRelations`

— ModuleTheory of *abelian bicategories of relations*

Unlike `ThBicategoryRelations`

, this theory uses additive notation.

References:

- Carboni & Walters, 1987, "Cartesian bicategories I", Sec. 5
- Baez & Erbele, 2015, "Categories in control"

`Catlab.CategoricalAlgebra.Categories`

— Module2-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 `@instance`

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

.

`Catlab.CategoricalAlgebra.Categories.Cat`

— TypeAlias for `Category`

.

`Catlab.CategoricalAlgebra.Categories.CatSize`

— TypeSize of a category, used for dispatch and subtyping purposes.

A `Category`

type having a particular `CatSize`

means that categories of that type are *at most* that large.

`Catlab.CategoricalAlgebra.Categories.Category`

— TypeAbstract 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`

.

`Catlab.CategoricalAlgebra.Categories.CompositeFunctor`

— TypeComposite of functors.

`Catlab.CategoricalAlgebra.Categories.Functor`

— TypeAbstract 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.

`Catlab.CategoricalAlgebra.Categories.FunctorCallable`

— TypeFunctor defined by two Julia callables, an object map and a morphism map.

`Catlab.CategoricalAlgebra.Categories.IdentityFunctor`

— TypeIdentity functor on a category.

`Catlab.CategoricalAlgebra.Categories.LargeCatSize`

— TypeSize of a large category, such as Set.

To the extent that they form a category, we regard Julia types and functions (`TypeCat`

) as forming a large category.

`Catlab.CategoricalAlgebra.Categories.OppositeCat`

— TypeOpposite category, where morphism are reversed.

Call `op(::Cat)`

instead of directly instantiating this type.

`Catlab.CategoricalAlgebra.Categories.OppositeFunctor`

— TypeOpposite functor, given by the same mapping between opposite categories.

Call `op(::Functor)`

instead of directly instantiating this type.

`Catlab.CategoricalAlgebra.Categories.Transformation`

— TypeAbstract 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`

).

`Catlab.CategoricalAlgebra.Categories.TypeCat`

— TypePair of Julia types regarded as a category.

The Julia types should form an `@instance`

of the theory of categories (`Theories.Category`

).

`AlgebraicInterfaces.codom`

— MethodCodomain of morphism in category.

`AlgebraicInterfaces.compose`

— MethodCompose morphisms in a category.

`AlgebraicInterfaces.dom`

— MethodDomain of morphism in category.

`AlgebraicInterfaces.hom`

— FunctionCoerce or look up morphism in category.

See also: `ob`

.

`AlgebraicInterfaces.id`

— MethodIdentity morphism on object in category.

`AlgebraicInterfaces.ob`

— FunctionCoerce 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`

.

`Catlab.CategoricalAlgebra.Categories.co`

— Function2-cell dual of a 2-category.

`Catlab.CategoricalAlgebra.Categories.codom_ob`

— MethodCodomain object of natural transformation.

Given $α: F ⇒ G: C → D$, this function returns $D$.

`Catlab.CategoricalAlgebra.Categories.component`

— FunctionComponent of natural transformation.

`Catlab.CategoricalAlgebra.Categories.dom_ob`

— MethodDomain object of natural transformation.

Given $α: F ⇒ G: C → D$, this function returns $C$.

`Catlab.CategoricalAlgebra.Categories.hom_map`

— MethodEvaluate functor on morphism.

`Catlab.CategoricalAlgebra.Categories.is_hom_equal`

— MethodAre 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.

`Catlab.CategoricalAlgebra.Categories.ob_map`

— MethodEvaluate functor on object.

`GATlab.Stdlib.StdModels.op`

— MethodOppositization 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.

`Catlab.CategoricalAlgebra.StructuredCospans`

— ModuleStructured cospans.

This module provides a generic interface for structured cospans with a concrete implementation for attributed C-sets.

`Catlab.CategoricalAlgebra.StructuredCospans.AbstractDiscreteACSet`

— TypeAbstract type for functor L: A → X giving a discrete attribute C-set.

`Catlab.CategoricalAlgebra.StructuredCospans.DiscreteACSet`

— TypeA functor L: C₀-Set → C-Set giving the discrete C-set for C₀.

Unlike `FinSetDiscreteACSet`

, this type supports data attributes. In addition, the sub-schema C₀ may contain more than one object. In all cases, the inclusion of schemas $C₀ → C$ must satisfy the property described in `OpenACSetTypes`

.

`Catlab.CategoricalAlgebra.StructuredCospans.FinSetDiscreteACSet`

— TypeA functor L: FinSet → C-Set giving the discrete C-set wrt an object in C.

This functor has a right adjoint R: C-Set → FinSet giving the underlying set at that object.

`Catlab.CategoricalAlgebra.StructuredCospans.OpenACSetLeg`

— TypeLeg 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.

`Catlab.CategoricalAlgebra.StructuredCospans.StructuredCospan`

— TypeStructured 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`

.

`Catlab.CategoricalAlgebra.StructuredCospans.StructuredCospan`

— MethodConstruct structured cospan in R-form.

`Catlab.CategoricalAlgebra.StructuredCospans.StructuredCospan`

— MethodConstruct structured cospan in L-form.

`Catlab.CategoricalAlgebra.StructuredCospans.StructuredCospanOb`

— TypeObject in the category of L-structured cospans.

`Catlab.CategoricalAlgebra.StructuredCospans.StructuredMulticospan`

— TypeStructured multicospan.

A structured multicospan is like a structured cospan except that it may have a number of legs different than two.

See also: `StructuredCospan`

.

`Catlab.CategoricalAlgebra.StructuredCospans.StructuredMulticospan`

— MethodConstruct structured multicospan in R-form.

`Core.Type`

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

`Core.Type`

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

`Core.Type`

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

`Core.Type`

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

`Catlab.CategoricalAlgebra.StructuredCospans.OpenACSetTypes`

— MethodCreate 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`

.

`Catlab.CategoricalAlgebra.StructuredCospans.OpenCSetTypes`

— MethodCreate types for open C-sets from a C-set type.

A special case of `OpenACSetTypes`

. See there for details.

`Catlab.CategoricalAlgebra.StructuredCospans.induced_transformation`

— MethodC-set transformation b → a induced by function `f`

into parts of `a`

.

`Catlab.CategoricalAlgebra.StructuredCospans.shift_left`

— MethodConvert morphism a → R(x) to morphism L(a) → x using discrete-forgetful adjunction L ⊣ R: A ↔ X.

`Catlab.Theories.ThCategory2`

— ModuleTheory of *2-categories*

`Catlab.Theories.ThDistributiveSemiadditiveCategory`

— ModuleTheory 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`

`Catlab.CategoricalAlgebra.CommutativeDiagrams`

— ModuleCommutative diagrams in a category.

**Note**: This module is at an early stage of construction. For now, only commutative squares are implemented.

`Catlab.CategoricalAlgebra.CommutativeDiagrams.SquareDiagram`

— TypeCommutative 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`

).

`Catlab.CategoricalAlgebra.CommutativeDiagrams.SquareHom`

— TypeArrow or proarrow in the double category of squares.

See also: `SquareDiagram`

.

`Catlab.CategoricalAlgebra.CommutativeDiagrams.SquareOb`

— TypeObject in the double category of squares.

See also: `SquareDiagram`

.

`Catlab.CategoricalAlgebra.FinRelations`

— ModuleThe category of finite sets and relations, and its skeleton.

`Catlab.CategoricalAlgebra.FinRelations.BoolRig`

— TypeThe 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`

.

`Catlab.CategoricalAlgebra.FinRelations.FinRel`

— TypeObject in the category of finite sets and relations.

See also: `FinSet`

.

`Catlab.CategoricalAlgebra.FinRelations.FinRelation`

— TypeBinary 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`

).

`Catlab.CategoricalAlgebra.FinRelations.FinRelationCallable`

— TypeRelation in FinRel defined by a callable Julia object.

`Catlab.CategoricalAlgebra.FinRelations.FinRelationMatrix`

— TypeRelation in FinRel represented by a boolean matrix.

Boolean matrices are also known as logical matrices or relation matrices.

`Catlab.CategoricalAlgebra.FinRelations.##docsink#3141`

— FunctionFinRel 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.

`Catlab.Theories.ThDistributiveMonoidalCategoryWithDiagonals`

— ModuleTheory of a *distributive monoidal category with diagonals*

FIXME: Should also inherit `ThMonoidalCategoryWithDiagonals`

.

`Catlab.Theories.FreeClosedMonoidalCategory`

— ModuleSyntax for a free closed monoidal category.

`Catlab.Theories.ThCompactClosedCategory`

— ModuleTheory of *compact closed categories*

`Catlab.Theories.ThCartesianClosedCategory`

— ModuleTheory 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.

`Catlab.CategoricalAlgebra.FreeDiagrams`

— ModuleFree 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.

`Catlab.CategoricalAlgebra.FreeDiagrams.BasicBipartiteFreeDiagram`

— TypeThe default concrete type for bipartite free diagrams.

`Catlab.CategoricalAlgebra.FreeDiagrams.BipartiteFreeDiagram`

— TypeA 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.

`Catlab.CategoricalAlgebra.FreeDiagrams.BipartiteFreeDiagram`

— MethodConvert 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.

`Catlab.CategoricalAlgebra.FreeDiagrams.ComposableMorphisms`

— TypeComposable morphisms in a category.

Composable morphisms are a sequence of morphisms in a category that form a path in the underlying graph of the category.

For the common special case of two morphisms, see `ComposablePair`

.

`Catlab.CategoricalAlgebra.FreeDiagrams.ComposablePair`

— TypePair of composable morphisms in a category.

Composable pairs are a common special case of `ComposableMorphisms`

.

`Catlab.CategoricalAlgebra.FreeDiagrams.Cospan`

— TypeCospan of morphisms in a category.

A common special case of `Multicospan`

. See also `Span`

.

`Catlab.CategoricalAlgebra.FreeDiagrams.DiscreteDiagram`

— TypeDiscrete diagram: a diagram with no non-identity morphisms.

`Catlab.CategoricalAlgebra.FreeDiagrams.FixedShapeFreeDiagram`

— TypeAbstract type for free diagram of fixed shape.

`Catlab.CategoricalAlgebra.FreeDiagrams.FreeDiagramAsBipartite`

— TypeA free diagram that has been converted to a bipartite free diagram.

`Catlab.CategoricalAlgebra.FreeDiagrams.FreeDiagramFunctor`

— TypeWrapper type to interpret `FreeDiagram`

as a `FinDomFunctor`

.

`Catlab.CategoricalAlgebra.FreeDiagrams.Multicospan`

— TypeMulticospan of morphisms in a category.

A multicospan is like a `Cospan`

except that it may have a number of legs different than two. A limit of this shape is a pullback.

`Catlab.CategoricalAlgebra.FreeDiagrams.Multispan`

— Type`Catlab.CategoricalAlgebra.FreeDiagrams.ParallelMorphisms`

— TypeParallel morphims in a category.

Parallel morphisms are just morphisms with the same domain and codomain. A (co)limit of this shape is a (co)equalizer.

For the common special case of two morphisms, see `ParallelPair`

.

`Catlab.CategoricalAlgebra.FreeDiagrams.ParallelPair`

— TypePair of parallel morphisms in a category.

A common special case of `ParallelMorphisms`

.

`Catlab.CategoricalAlgebra.FreeDiagrams.Span`

— Type`Catlab.CategoricalAlgebra.FreeDiagrams.apex`

— MethodApex of multispan or multicospan.

The apex of a multi(co)span is the object that is the (co)domain of all the `legs`

.

`Catlab.CategoricalAlgebra.FreeDiagrams.bundle_legs`

— MethodBundle 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.

`Catlab.CategoricalAlgebra.FreeDiagrams.cocone_objects`

— MethodObjects in diagram that will have explicit legs in colimit cocone.

See also: `cone_objects`

.

`Catlab.CategoricalAlgebra.FreeDiagrams.cone_objects`

— MethodObjects 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`

.

`Catlab.CategoricalAlgebra.FreeDiagrams.diagram_type`

— FunctionGiven a diagram in a category $C$, return Julia type of objects and morphisms in $C$ as a tuple type of form $Tuple{Ob,Hom}$.

`Catlab.CategoricalAlgebra.FreeDiagrams.feet`

— MethodFeet of multispan or multicospan.

The feet of a multispan are the codomains of the `legs`

.

`Catlab.CategoricalAlgebra.FreeDiagrams.left`

— MethodLeft leg of span or cospan.

`Catlab.CategoricalAlgebra.FreeDiagrams.legs`

— MethodLegs of multispan or multicospan.

The legs are the morphisms comprising the multi(co)span.

`Catlab.CategoricalAlgebra.FreeDiagrams.right`

— MethodRight leg of span or cospan.

`Catlab.Theories.ThCategoryWithProducts`

— ModuleTheory 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`

.

`Catlab.CategoricalAlgebra.Subobjects.ThSubobjectLattice`

— ModuleTheory 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.

`Catlab.CategoricalAlgebra.SliceCategories.Slice`

— TypeThe data of the object of a slice category (say, some category C sliced over an object X in Ob(C)) is the data of a homomorphism in Hom(A,X) for some ob A.

`Catlab.CategoricalAlgebra.SliceCategories.SliceHom`

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

`Catlab.CategoricalAlgebra.Limits.limit`

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

`Catlab.CategoricalAlgebra.SliceCategories.slice_diagram`

— MethodGet the underlying diagram of a slice category diagram which has the object being sliced over explicitly, and arrows are ACSetTransformations

`Catlab.Graphs.PropertyGraphs.AbstractPropertyGraph`

— TypeAbstract type for graph with properties.

Concrete types are `PropertyGraph`

and `SymmetricPropertyGraph`

.

`Catlab.Graphs.PropertyGraphs.PropertyGraph`

— TypeGraph 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`

.

`Catlab.Graphs.PropertyGraphs.SymmetricPropertyGraph`

— TypeSymmetric graphs with properties.

The edge properties are preserved under the edge involution, so these can be interpreted as "undirected" property (multi)graphs.

See also: `PropertyGraph`

.

`Catlab.Graphs.PropertyGraphs.eprops`

— MethodProperties of edge in a property graph.

`Catlab.Graphs.PropertyGraphs.get_eprop`

— MethodGet property of edge or edges in a property graph.

`Catlab.Graphs.PropertyGraphs.get_gprop`

— MethodGet graph-level property of a property graph.

`Catlab.Graphs.PropertyGraphs.get_vprop`

— MethodGet property of vertex or vertices in a property graph.

`Catlab.Graphs.PropertyGraphs.gprops`

— MethodGraph-level properties of a property graph.

`Catlab.Graphs.PropertyGraphs.set_eprop!`

— MethodSet property of edge or edges in a property graph.

`Catlab.Graphs.PropertyGraphs.set_eprops!`

— MethodSet multiple properties of an edge in a property graph.

`Catlab.Graphs.PropertyGraphs.set_gprop!`

— MethodSet graph-level property in a property graph.

`Catlab.Graphs.PropertyGraphs.set_gprops!`

— MethodSet multiple graph-level properties in a property graph.

`Catlab.Graphs.PropertyGraphs.set_vprop!`

— MethodSet property of vertex or vertices in a property graph.

`Catlab.Graphs.PropertyGraphs.set_vprops!`

— MethodSet multiple properties of a vertex in a property graph.

`Catlab.Graphs.PropertyGraphs.vprops`

— MethodProperties of vertex in a property graph.

`Catlab.CategoricalAlgebra.FunctorialDataMigrations`

— ModuleFunctorial data migration for attributed C-sets.

`Catlab.CategoricalAlgebra.FreeDiagrams.FreeDiagram`

— MethodFreeDiagram(pres::Presentation{FreeSchema, Symbol})

Returns a `FreeDiagram`

whose objects are the generating objects of `pres`

and whose homs are the generating homs of `pres`

.

`Catlab.CategoricalAlgebra.FunctorialDataMigrations.AbstractDataMigration`

— TypeA 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`

.

`Catlab.CategoricalAlgebra.FunctorialDataMigrations.AbstractMigrationFunctor`

— TypeAbstract type for a data migration functor.

This allows a data migration to behave as an actual model of the theory of functors with domain and codomain categories of acsets rather than schemas, once one knows the exact concrete types Dom and Codom of the relevant acsets.

`Catlab.CategoricalAlgebra.FunctorialDataMigrations.DataMigrationFunctor`

— TypeData migration functor given contravariantly. Stores a contravariant migration.

`Catlab.CategoricalAlgebra.FunctorialDataMigrations.DeltaSchemaMigration`

— TypeSchema-level functor defining a pullback or delta data migration.

Given a functor $F: C → D$, the delta migration $Δ_F$ is a functor from $C$-sets to $D$-sets that simply sends a $C$-set $X$ to the $D$-set $X∘F$.

`Catlab.CategoricalAlgebra.FunctorialDataMigrations.SigmaSchemaMigration`

— TypeSigma 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.

`Catlab.CategoricalAlgebra.FunctorialDataMigrations.internal_hom`

— MethodObjects: 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`

.

`Catlab.CategoricalAlgebra.FunctorialDataMigrations.migrate!`

— MethodContravariantly migrate data from the acset `Y`

to the acset `X`

.

This is the mutating variant of `migrate!`

. When the functor on schemas is the identity, this operation is equivalent to `copy_parts!`

.

`Catlab.CategoricalAlgebra.FunctorialDataMigrations.migrate`

— MethodApply a $Δ$ migration by simple precomposition.

`Catlab.CategoricalAlgebra.FunctorialDataMigrations.migrate`

— MethodContravariantly migrate data from the acset `Y`

to a new acset of type `T`

.

The mutating variant of this function is `migrate!`

.

`Catlab.CategoricalAlgebra.FunctorialDataMigrations.representable`

— MethodConstruct 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.

`Catlab.CategoricalAlgebra.FunctorialDataMigrations.representable`

— MethodACSet types do not store info about equations, so this info is lost when we try to recover the presentation from the datatype. Thus, this method for `representable`

should only be used for free schemas

`Catlab.CategoricalAlgebra.FunctorialDataMigrations.split_r`

— MethodSplit an n-fold composite (n may be 1) Hom or Attr into its left n-1 and rightmost 1 components

`Catlab.CategoricalAlgebra.FunctorialDataMigrations.subobject_classifier`

— MethodThe 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.

`Catlab.CategoricalAlgebra.FunctorialDataMigrations.yoneda`

— MethodCompute 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)`

.

`GATlab.Models.SymbolicModels.functor`

— MethodGives the underlying schema functor of a data migration seen as a functor of acset categories.

`Catlab.CategoricalAlgebra.Limits`

— ModuleLimits and colimits in a category.

`Catlab.CategoricalAlgebra.Limits.AbstractColimit`

— TypeAbstract type for colimit in a category.

The standard concrete subtype is `Colimit`

, although for computational reasons certain categories may use different subtypes to include extra data.

`Catlab.CategoricalAlgebra.Limits.AbstractLimit`

— TypeAbstract type for limit in a category.

The standard concrete subtype is `Limit`

, although for computational reasons certain categories may use different subtypes to include extra data.

`Catlab.CategoricalAlgebra.Limits.BipartiteColimit`

— TypeLimit computed by reduction to the limit of a free bipartite diagram.

`Catlab.CategoricalAlgebra.Limits.BipartiteLimit`

— TypeLimit computed by reduction to the limit of a free bipartite diagram.

`Catlab.CategoricalAlgebra.Limits.Colimit`

— TypeColimit in a category.

`Catlab.CategoricalAlgebra.Limits.ColimitAlgorithm`

— TypeAlgorithm for computing colimits.

`Catlab.CategoricalAlgebra.Limits.ComposeCoproductCoequalizer`

— TypeCompute pushout by composing a coproduct with a coequalizer.

See also: `ComposeProductEqualizer`

.

`Catlab.CategoricalAlgebra.Limits.ComposeProductEqualizer`

— TypeCompute pullback by composing a product with an equalizer.

See also: `ComposeCoproductCoequalizer`

.

`Catlab.CategoricalAlgebra.Limits.CompositePullback`

— TypePullback 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`

.

`Catlab.CategoricalAlgebra.Limits.CompositePushout`

— TypePushout formed as composite of coproduct and equalizer.

See also: `CompositePullback`

.

`Catlab.CategoricalAlgebra.Limits.Limit`

— TypeLimit in a category.

`Catlab.CategoricalAlgebra.Limits.LimitAlgorithm`

— TypeAlgorithm for computing limits.

`Catlab.CategoricalAlgebra.Limits.SingletonColimit`

— TypeColimit of a singleton diagram.

`Catlab.CategoricalAlgebra.Limits.SingletonLimit`

— TypeLimit of a singleton diagram.

`Catlab.CategoricalAlgebra.Limits.SpecializeColimit`

— TypeMeta-algorithm that reduces general colimits to common special cases.

Dual to `SpecializeLimit`

.

`Catlab.CategoricalAlgebra.Limits.SpecializeLimit`

— TypeMeta-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.

`Catlab.CategoricalAlgebra.Limits.ToBipartiteColimit`

— TypeCompute a colimit by reducing the diagram to a free bipartite diagram.

`Catlab.CategoricalAlgebra.Limits.ToBipartiteLimit`

— TypeCompute a limit by reducing the diagram to a free bipartite diagram.

`Catlab.CategoricalAlgebra.Limits.coimage`

— Methodhttps://en.wikipedia.org/wiki/Coimage

`Catlab.CategoricalAlgebra.Limits.colimit`

— MethodColimit 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`

`Catlab.CategoricalAlgebra.Limits.epi_mono`

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

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

`Catlab.CategoricalAlgebra.Limits.image`

— Methodhttps://en.wikipedia.org/wiki/Image*(category*theory)#Second_definition

`Catlab.CategoricalAlgebra.Limits.limit`

— MethodLimit 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`

`Catlab.CategoricalAlgebra.Limits.pullback`

— MethodPullback 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.

`Catlab.CategoricalAlgebra.Limits.pushout`

— MethodPushout 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.

`Catlab.Theories.coequalizer`

— MethodCoequalizer of morphisms with common domain and codomain.

To implement for a type `T`

, define the method `colimit(::ParallelPair{T})`

or `colimit(::ParallelMorphisms{T})`

.

`Catlab.Theories.copair`

— MethodCopairing 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.

`Catlab.Theories.coproduct`

— MethodCoproduct of objects.

To implement for a type `T`

, define the method `colimit(::ObjectPair{T})`

and/or `colimit(::DiscreteDiagram{T})`

.

`Catlab.Theories.create`

— MethodUnique morphism out of an initial object.

To implement for a type `T`

, define the method `universal(::Initial{T}, ::SMulticospan{0,T})`

.

`Catlab.Theories.delete`

— MethodUnique morphism into a terminal object.

To implement for a type `T`

, define the method `universal(::Terminal{T}, ::SMultispan{0,T})`

.

`Catlab.Theories.equalizer`

— MethodEqualizer of morphisms with common domain and codomain.

To implement for a type `T`

, define the method `limit(::ParallelPair{T})`

and/or `limit(::ParallelMorphisms{T})`

.

`Catlab.Theories.factorize`

— MethodFactor 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})`

.

`Catlab.Theories.initial`

— MethodInitial object.

To implement for a type `T`

, define the method `colimit(::EmptyDiagram{T})`

.

`Catlab.Theories.pair`

— MethodPairing 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.

`Catlab.Theories.product`

— MethodProduct of objects.

To implement for a type `T`

, define the method `limit(::ObjectPair{T})`

and/or `limit(::DiscreteDiagram{T})`

.

`Catlab.Theories.terminal`

— MethodTerminal object.

To implement for a type `T`

, define the method `limit(::EmptyDiagram{T})`

.

`Catlab.Theories.universal`

— Function`Catlab.CategoricalAlgebra.Limits.@cartesian_monoidal_instance`

— MacroDefine cartesian monoidal structure using limits.

Implements an instance of `ThCartesianCategory`

assuming that finite products have been implemented following the limits interface.

`Catlab.CategoricalAlgebra.Limits.@cocartesian_monoidal_instance`

— MacroDefine cocartesian monoidal structure using colimits.

Implements an instance of `ThCocartesianCategory`

assuming that finite coproducts have been implemented following the colimits interface.

`Catlab.Theories`

— ModuleCatlab's standard library of generalized algebraic theories.

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

`Catlab.Theories.CategoryExpr`

— TypeBase type for GAT expressions in categories or other categorical structures.

All symbolic expression types exported by `Catlab.Theories`

are subtypes of this abstract type.

`Catlab.Theories.HomExpr`

— TypeBase type for morphism expressions in categorical structures.

`Catlab.Theories.ObExpr`

— TypeBase type for object expressions in categorical structures.

`Base.collect`

— MethodCollect generators of object in monoidal category as a vector.

`Base.ndims`

— MethodNumber of "dimensions" of object in monoidal category.

`Catlab.Theories.distribute_dagger`

— MethodDistribute dagger over composition.

`Catlab.Theories.distribute_mate`

— MethodDistribute adjoint mates over composition and products.

`Catlab.Theories.FreeDoubleCategory`

— ModuleSyntax for a double category.

Checks domains of morphisms but not 2-morphisms.

`Catlab.Graphs.GraphAlgorithms`

— ModuleAlgorithms on graphs based on C-sets.

`Catlab.Graphs.GraphAlgorithms.connected_component_projection`

— FunctionProjection onto (weakly) connected components of a graph.

Returns a function in FinSet{Int} from the vertex set to the set of components.

`Catlab.Graphs.GraphAlgorithms.connected_components`

— Method(Weakly) connected components of a graph.

Returns a vector of vectors, which are the components of the graph.

`Catlab.Graphs.GraphAlgorithms.enumerate_paths`

— MethodEnumerate all paths of an acyclic graph, indexed by src+tgt

`Catlab.Graphs.GraphAlgorithms.longest_paths`

— MethodLongest 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.

`Catlab.Graphs.GraphAlgorithms.topological_sort`

— MethodTopological sort of a directed acyclic graph.

The depth-first search algorithm is adapted from the function `topological_sort_by_dfs`

in Graphs.jl.

`Catlab.Graphs.GraphAlgorithms.transitive_reduction!`

— MethodTransitive 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.

`Catlab.Theories.ThAlgebraicLattice`

— ModuleTheory 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`

.

`Catlab.CategoricalAlgebra.Matrices`

— ModuleCategories of matrices.

`Catlab.CategoricalAlgebra.Matrices.MatrixDom`

— TypeDomain or codomain of a Julia matrix of a specific type.

Object in the category of matrices of this type.

`Catlab.CategoricalAlgebra.Matrices.##docsink#3116`

— FunctionBiproduct category of Julia matrices of specific type.

The matrices can be dense or sparse, and the element type can be any commutative rig (commutative semiring): any Julia type implementing `+`

, `*`

, `zero`

, `one`

and obeying the axioms. Note that commutativity is required only in order to define `braid`

.

For a similar design (only for sparse matrices) by the Julia core developers, see SemiringAlgebra.jl and accompanying short paper.

`Catlab.CategoricalAlgebra.Matrices.vec_permutation_matrix`

— MethodThe "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.

`Catlab.CategoricalAlgebra.Subobjects`

— ModuleAlgebra 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.

`Catlab.CategoricalAlgebra.Subobjects.SubOpAlgorithm`

— TypeAbstract type for algorithm to compute operation(s) on subobjects.

`Catlab.CategoricalAlgebra.Subobjects.SubOpWithLimits`

— TypeAlgorithm to compute subobject operations using limits and/or colimits.

`Catlab.CategoricalAlgebra.Subobjects.Subobject`

— TypeSubobject 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 → Ω$.

`Base.join`

— MethodJoin (union) of subobjects.

`Catlab.Theories.bottom`

— MethodBottom (empty) subobject.

`Catlab.Theories.meet`

— MethodMeet (intersection) of subobjects.

`Catlab.Theories.top`

— MethodTop (full) subobject.

`Catlab.Theories.ThSemiadditiveCategory`

— ModuleTheory of *semiadditive categories*

Mathematically the same as `ThBiproductCategory`

but written additively, instead of multiplicatively.

`Catlab.Theories.ThMonoidalCategoryWithDiagonals`

— ModuleTheory 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.

References:

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

`Catlab.Theories.ThDistributiveCategory`

— ModuleTheory of a *distributive category*

A distributive category is a distributive monoidal category whose tensor product is the cartesian product, see `ThDistributiveMonoidalCategory`

.

FIXME: Should also inherit `ThCartesianCategory`

.

`Catlab.Graphics.ComposeWiringDiagrams`

— ModuleDraw wiring diagrams using Compose.jl.

`Catlab.Graphics.ComposeWiringDiagrams.ComposeOptions`

— TypeInternal data type for configurable options of Compose.jl wiring diagrams.

`Catlab.Graphics.ComposeWiringDiagrams.ComposePicture`

— TypeA Compose context together with a given width and height.

We need this type because contexts have no notion of size or aspect ratio, but wiring diagram layouts have fixed aspect ratios.

`Catlab.Graphics.ComposeWiringDiagrams.box_props`

— MethodGet Compose.jl properties for box.

`Catlab.Graphics.ComposeWiringDiagrams.labeled_form`

— MethodDraw a form with centered text label in Compose.

`Catlab.Graphics.ComposeWiringDiagrams.layout_to_composejl`

— MethodDraw a wiring diagram in Compose.jl using the given layout.

`Catlab.Graphics.ComposeWiringDiagrams.piecewise_curve`

— MethodDraw a continuous piecewise cubic Bezier curve in Compose.

The points are given by a vector [p1, c1, c2, p2, c3, c4, p3, ...] of length 3n+1 where n >=1 is the number of Bezier curves.

`Catlab.Graphics.ComposeWiringDiagrams.render_box`

— MethodDraw an atomic box in Compose.jl.

`Catlab.Graphics.ComposeWiringDiagrams.rounded_rectangle`

— MethodDraw a rounded rectangle in Compose.

`Catlab.Graphics.ComposeWiringDiagrams.tangents_to_controls`

— MethodControl points for Bezier curve from endpoints and unit tangent vectors.

`Catlab.Graphics.ComposeWiringDiagrams.to_composejl`

— MethodDraw a wiring diagram in Compose.jl.

`Catlab.Theories.ThMonoidalCategoryWithBidiagonals`

— ModuleTheory 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.

`Catlab.Theories.ThCopresheaf`

— ModuleTheory of *copresheaves*.

Axiomatized as a covariant category action.

`Catlab.Theories.ThHypergraphCategoryAdditive`

— ModuleTheory of *hypergraph categories*, in additive notation

Mathematically the same as `ThHypergraphCategory`

but with different notation.

`Catlab.WiringDiagrams.DirectedWiringDiagrams`

— ModuleData 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.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.AbstractBox`

— TypeBase type for any box (node) in a wiring diagram.

This type represents an arbitrary black box with inputs and outputs.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.Box`

— TypeAn atomic box in a wiring diagram.

These boxes have no internal structure.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.Port`

— TypeA port on a box to which wires can be connected.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.PortKind`

— TypeKind of port: input or output.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.Wire`

— TypeA wire connecting one port to another.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.WiringDiagramGraphACSet`

— TypeGraph underlying a directed wiring diagram.

`Base.:==`

— MethodAre 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.

`Catlab.CategoricalAlgebra.FinCats.graph`

— MethodGrapn 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.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.encapsulate`

— MethodEncapsulate multiple boxes within a single sub-diagram.

This operation is a (one-sided) inverse to subsitution, see `substitute`

.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.encapsulated_subdiagram`

— MethodCreate 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.

Specifically:

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

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

.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.in_wires`

— MethodGet all wires coming into the box.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.in_wires`

— MethodGet all wires coming into the port.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.induced_subdiagram`

— MethodThe wiring diagram induced by a subset of its boxes.

See also `encapsulated_subdiagram`

.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.internal_graph`

— MethodGraph underlying wiring diagram, with edges for internal wires only.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.ocompose`

— MethodOperadic 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`

.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.out_wires`

— MethodGet all wires coming out of the box.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.out_wires`

— MethodGet all wires coming out of the port.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.singleton_diagram`

— MethodWiring diagram with a single box connected to the outer ports.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.substitute`

— MethodSubstitute wiring diagrams for boxes.

Performs one or more substitutions. When performing multiple substitutions, the substitutions are simultaneous.

This operation implements the operadic composition of wiring diagrams, see also `ocompose`

.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.substitute_wires!`

— MethodSubstitute wires of sub-diagram into containing wiring diagram.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.validate_ports`

— MethodCheck compatibility of source and target ports.

The default implementation is a no-op.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.wires`

— MethodGet all wires coming into or out of the box.

`Catlab.Theories.ThRigCategory`

— ModuleTheory 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.

`Catlab.Theories.ThOpindexedMonoidalCategoryLax`

— ModuleTheory 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.

References:

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

`Catlab.Graphics.GraphvizWiringDiagrams`

— ModuleLay out and draw wiring diagrams using Graphviz.

This module requires Graphviz v2.42 or higher.

`Catlab.Graphics.GraphvizGraphs.to_graphviz`

— MethodDraw 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.

**Arguments**

`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

`Catlab.Graphics.GraphvizGraphs.to_graphviz`

— MethodDraw 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.

**Arguments**

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

`Catlab.Graphics.GraphvizGraphs.to_graphviz`

— MethodDraw 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.

**Arguments**

`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

`Catlab.Graphics.GraphvizWiringDiagrams.box_html_label`

— MethodCreate "HTML-like" node label for a box.

`Catlab.Graphics.GraphvizWiringDiagrams.edge_label`

— MethodCreate a label for an edge.

`Catlab.Graphics.GraphvizWiringDiagrams.escape_html`

— MethodEscape special HTML characters: &, <, >, ", '

Adapted from HttpCommon.jl.

`Catlab.Graphics.GraphvizWiringDiagrams.graphviz_box`

— MethodGraphviz box for a generic box.

`Catlab.Graphics.GraphvizWiringDiagrams.graphviz_box`

— MethodGraphviz box for a junction.

`Catlab.Graphics.GraphvizWiringDiagrams.graphviz_layout`

— MethodLay 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.

`Catlab.Graphics.GraphvizWiringDiagrams.graphviz_outer_box`

— MethodGraphviz box for the outer box of a wiring diagram.

`Catlab.Graphics.GraphvizWiringDiagrams.graphviz_outer_ports`

— MethodCreate invisible nodes for the input or output ports of an outer box.

`Catlab.Graphics.GraphvizWiringDiagrams.html_attributes`

— MethodEncode attributes for Graphviz HTML-like labels.

`Catlab.Graphics.GraphvizWiringDiagrams.inverse_rank_dir`

— MethodLayout orientation for Graphviz rank direction (`rankdir`

).

Reference: https://www.graphviz.org/doc/info/attrs.html#k:rankdir

`Catlab.Graphics.GraphvizWiringDiagrams.layout_linear_ports`

— MethodLay out ports linearly, equispaced along a rectangular box.

FIXME: Should this be in `WiringDiagramLayouts`

as an alternative layout method?

`Catlab.Graphics.GraphvizWiringDiagrams.node_label`

— MethodCreate a label for the main content of a box.

`Catlab.Graphics.GraphvizWiringDiagrams.port_anchor`

— MethodGraphviz anchor for port.

`Catlab.Graphics.GraphvizWiringDiagrams.ports_horizontal_html_label`

— FunctionCreate horizontal "HTML-like" label for the input or output ports of a box.

`Catlab.Graphics.GraphvizWiringDiagrams.ports_vertical_html_label`

— FunctionCreate vertical "HTML-like" label for the input or output ports of a box.

`Catlab.Graphics.GraphvizWiringDiagrams.rank_dir`

— MethodGraphviz rank direction (`rankdir`

) for layout orientation.

Reference: https://www.graphviz.org/doc/info/attrs.html#k:rankdir

`Catlab.CategoricalAlgebra.CSets`

— ModuleCategories of C-sets and attributed C-sets.

`Catlab.CategoricalAlgebra.CSets.ACSetColimit`

— TypeColimit of attributed C-sets that stores the pointwise colimits in Set.

`Catlab.CategoricalAlgebra.CSets.ACSetFunctor`

— TypeWrapper type to interpret attributed C-set as a functor.

`Catlab.CategoricalAlgebra.CSets.ACSetLimit`

— TypeLimit of attributed C-sets that stores the pointwise limits in Set.

`Catlab.CategoricalAlgebra.CSets.ACSetMorphism`

— TypeCommon type for `ACSetTransformation`

and `CSetTransformation`

.

`Catlab.CategoricalAlgebra.CSets.ACSetTransformation`

— TypeTransformation 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`

.

`Catlab.CategoricalAlgebra.CSets.ACSetTransformation`

— MethodMove components as first argument

`Catlab.CategoricalAlgebra.CSets.ACSetTransformation`

— MethodA map f (from A to B) as a map from A to a subobject of B

**i.e. get the image of f as a subobject of B**

`Catlab.CategoricalAlgebra.CSets.ACSetTransformation`

— MethodA map f (from A to B) as a map of subobjects of A to subjects of B

`Catlab.CategoricalAlgebra.CSets.CSetTransformation`

— TypeTransformation 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).

`Catlab.CategoricalAlgebra.CSets.LooseACSetTransformation`

— TypeLoose 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`

.

`Catlab.CategoricalAlgebra.CSets.SubACSetComponentwise`

— TypeSub-C-set represented componentwise as a collection of subsets.

`Catlab.CategoricalAlgebra.CSets.SubCSet`

— TypeSub-C-set of a C-set.

`Catlab.CategoricalAlgebra.CSets.TightACSetTransformation`

— TypeTight 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`

.

`Catlab.CategoricalAlgebra.FinSets.FinDomFunction`

— MethodCreate `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`

.

`Catlab.CategoricalAlgebra.FinSets.FinDomFunction`

— MethodRuntime error if there are any attributes in the column

`Catlab.CategoricalAlgebra.FinSets.FinFunction`

— MethodCreate `FinFunction`

for morphism of attributed C-set.

Indices are included whenever they exist.

`Catlab.CategoricalAlgebra.FinSets.FinSet`

— MethodCreate `FinSet`

for object of attributed C-set.

`Catlab.CategoricalAlgebra.FinSets.VarSet`

— MethodCreate `VarSet`

for attribute type of attributed C-set.

`Catlab.CategoricalAlgebra.Sets.SetFunction`

— MethodCreate `SetFunction`

for morphism or attribute of attributed C-set.

For morphisms, the result is a `FinFunction`

; for attributes, a `FinDomFunction`

.

`Catlab.CategoricalAlgebra.Sets.SetOb`

— MethodCreate `SetOb`

for object or attribute type of attributed C-set.

For objects, the result is a `FinSet`

; for attribute types, a `TypeSet`

.

`Catlab.CategoricalAlgebra.Sets.TypeSet`

— MethodCreate `TypeSet`

for object or attribute type of attributed C-set.

`ACSets.ACSetInterface.copy_parts!`

— MethodCopy parts from a set-valued `FinDomFunctor`

to an `ACSet`

.

`ACSets.PreimageCaches.preimage`

— Method`preimage(f::ACSetTransformation,Y::StructACSet)`

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

`ACSets.PreimageCaches.preimage`

— Method`preimage(f::ACSetTransformation,Y::Subobject)`

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

`Catlab.CategoricalAlgebra.CSets.abstract_attributes`

— FunctionFor any ACSet, X, a canonical map A→X where A has distinct variables for all attributes valued in attrtypes present in `abstract`

(by default: all attrtypes)

`Catlab.CategoricalAlgebra.CSets.coerce_attrvar_component`

— MethodCoerce an arbitrary julia function to a LooseVarFunction assuming no variables

`Catlab.CategoricalAlgebra.CSets.colimit_attrs!`

— MethodSet data attributes of colimit of acsets using universal property.

`Catlab.CategoricalAlgebra.CSets.in_bounds`

— MethodCheck 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`

.

`Catlab.CategoricalAlgebra.CSets.naturality_failures`

— MethodReturns 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).

`Catlab.CategoricalAlgebra.CSets.pack_colimit`

— MethodMake colimit of acsets from colimits of sets, ignoring attributes.

`Catlab.CategoricalAlgebra.CSets.pack_components`

— MethodNamed tuple of vectors of FinFunctions → vector of C-set transformations.

`Catlab.CategoricalAlgebra.CSets.pack_limit`

— MethodMake 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).

`Catlab.CategoricalAlgebra.CSets.sets`

— MethodC-set → named tuple of sets.

`Catlab.CategoricalAlgebra.CSets.show_naturality_failures`

— MethodPretty-print failures of transformation to be natural.

See also: `naturality_failures`

.

`Catlab.CategoricalAlgebra.CSets.unpack_components`

— MethodVector of C-set transformations → named tuple of vectors of functions.

`Catlab.CategoricalAlgebra.CSets.unpack_diagram`

— MethodDiagram in C-Set → named tuple of diagrams in Set.

`Catlab.CategoricalAlgebra.CSets.unpack_sets`

— MethodVector of C-sets → named tuple of vectors of sets.

`Catlab.CategoricalAlgebra.CSets.var_reference`

— MethodFind some part + attr that refers to an AttrVar. Throw error if none exists (i.e. `i`

is a wandering variable).

`Catlab.CategoricalAlgebra.FinCats.is_natural`

— MethodCheck 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.

`Catlab.CategoricalAlgebra.Limits.limit`

— MethodVariables 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.

`Catlab.CategoricalAlgebra.Limits.limit`

— MethodA 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.

`Catlab.CategoricalAlgebra.Subobjects.implies`

— MethodImplication 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`

).

`Catlab.CategoricalAlgebra.Subobjects.subtract`

— MethodSubtraction 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`

.

`Catlab.Theories.ThEquipment`

— ModuleTheory of a *proarrow equipment*, or *equipment* for short

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

References:

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

`Catlab.Theories.ThPresheaf`

— ModuleTheory of *presheaves*.

Axiomatized as a contravariant category action.

`Catlab.Graphics.GraphvizCategories`

— ModuleGraphviz drawing of categories, functors, diagrams, and related structures.

`Catlab.Graphics.GraphvizGraphs.to_graphviz`

— MethodVisualize a function between finite sets using Graphviz.

Visualize a function (`FinFunction`

) between two finite sets (`FinSet`

s). Reduces to drawing an undirected bipartite graph; see that method for more.

`Catlab.Graphs.BasicGraphs`

— ModuleData 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.

`Catlab.Graphs.BasicGraphs.AbstractGraph`

— TypeAbstract type for graphs, aka directed multigraphs.

`Catlab.Graphs.BasicGraphs.AbstractHalfEdgeGraph`

— TypeAbstract type for half-edge graphs, possibly with data attributes.

`Catlab.Graphs.BasicGraphs.AbstractLabeledGraph`

— TypeAbstract type for labeled graphs.

`Catlab.Graphs.BasicGraphs.AbstractReflexiveGraph`

— TypeAbstract type for reflexive graphs, possibly with data attributes.

`Catlab.Graphs.BasicGraphs.AbstractSymmetricGraph`

— TypeAbstract type for symmetric graph, possibly with data attributes.

`Catlab.Graphs.BasicGraphs.AbstractSymmetricReflexiveGraph`

— TypeAbstract type for symmetric reflexive graphs, possibly with data attributes.

`Catlab.Graphs.BasicGraphs.AbstractSymmetricWeightedGraph`

— TypeAbstract type for symmetric weighted graphs.

`Catlab.Graphs.BasicGraphs.AbstractWeightedGraph`

— TypeAbstract type for weighted graphs.

`Catlab.Graphs.BasicGraphs.Graph`

— TypeA graph, also known as a directed multigraph.

`Catlab.Graphs.BasicGraphs.HalfEdgeGraph`

— TypeA half-edge graph.

Half-edge graphs are a variant of undirected graphs whose edges are pairs of "half-edges" or "darts". Half-edge graphs are isomorphic to symmetric graphs but have a different data model.

`Catlab.Graphs.BasicGraphs.HasGraph`

— TypeAbstract 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.

`Catlab.Graphs.BasicGraphs.HasVertices`

— TypeAbstract 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.

`Catlab.Graphs.BasicGraphs.LabeledGraph`

— TypeA 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.

`Catlab.Graphs.BasicGraphs.ReflexiveGraph`

— TypeA reflexive graph.

Reflexive graphs are graphs in which every vertex has a distinguished self-loop.

`Catlab.Graphs.BasicGraphs.SymmetricGraph`

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

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

`Catlab.Graphs.BasicGraphs.SymmetricReflexiveGraph`

— TypeA symmetric reflexive graph.

Symmetric reflexive graphs are both symmetric graphs (`SymmetricGraph`

) and reflexive graphs (`ReflexiveGraph`

) such that the reflexive loops are fixed by the edge involution.

`Catlab.Graphs.BasicGraphs.SymmetricWeightedGraph`

— TypeA symmetric weighted graph.

A symmetric graph in which every edge has a numerical weight, preserved by the edge involution.

`Catlab.Graphs.BasicGraphs.WeightedGraph`

— TypeA weighted graph.

A graph in which every edge has a numerical weight.

`Base.inv`

— MethodInvolution on half-edge(s) in a half-edge graph.

`Base.inv`

— MethodInvolution on edge(s) in a symmetric graph.

`Base.reverse!`

— MethodInterchange src and tgt, keeping all other data the same

`Catlab.Graphs.BasicGraphs.add_dangling_edge!`

— MethodAdd 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.

`Catlab.Graphs.BasicGraphs.add_dangling_edges!`

— MethodAdd multiple dangling edges to a half-edge graph.

`Catlab.Graphs.BasicGraphs.add_edge!`

— MethodAdd an edge to a graph.

`Catlab.Graphs.BasicGraphs.add_edges!`

— MethodAdd multiple edges to a graph.

`Catlab.Graphs.BasicGraphs.add_vertex!`

— MethodAdd a vertex to a graph.

`Catlab.Graphs.BasicGraphs.add_vertices!`

— MethodAdd multiple vertices to a graph.

`Catlab.Graphs.BasicGraphs.add_vertices_with_indices!`

— MethodAdd vertices with preallocated src/tgt indexes

`Catlab.Graphs.BasicGraphs.all_neighbors`

— MethodUnion of in-neighbors and out-neighbors in a graph.

`Catlab.Graphs.BasicGraphs.degree`

— MethodTotal degree of a vertex

Equivalent to length(all_neighbors(g,v)) but faster

`Catlab.Graphs.BasicGraphs.edges`

— MethodEdges in a graph, or between two vertices in a graph.

`Catlab.Graphs.BasicGraphs.half_edges`

— MethodHalf-edges in a half-edge graph, or incident to a vertex.

`Catlab.Graphs.BasicGraphs.has_edge`

— MethodWhether the graph has the given edge, or an edge between two vertices.

`Catlab.Graphs.BasicGraphs.has_vertex`

— MethodWhether the graph has the given vertex.

`Catlab.Graphs.BasicGraphs.induced_subgraph`

— MethodSubgraph induced by a set of a vertices.

The induced subgraph consists of the given vertices and all edges between vertices in this set.

`Catlab.Graphs.BasicGraphs.inedges`

— MethodEdges coming into a vertex

`Catlab.Graphs.BasicGraphs.inneighbors`

— MethodIn-neighbors of vertex in a graph.

`Catlab.Graphs.BasicGraphs.ne`

— MethodNumber 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).

`Catlab.Graphs.BasicGraphs.neighbors`

— MethodNeighbors 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))`

.

`Catlab.Graphs.BasicGraphs.nv`

— MethodNumber of vertices in a graph.

`Catlab.Graphs.BasicGraphs.outedges`

— MethodEdges coming out of a vertex

`Catlab.Graphs.BasicGraphs.outneighbors`

— MethodOut-neighbors of vertex in a graph.

`Catlab.Graphs.BasicGraphs.refl`

— MethodReflexive loop(s) of vertex (vertices) in a reflexive graph.

`Catlab.Graphs.BasicGraphs.rem_edge!`

— MethodRemove an edge from a graph.

`Catlab.Graphs.BasicGraphs.rem_edges!`

— MethodRemove multiple edges from a graph.

`Catlab.Graphs.BasicGraphs.rem_vertex!`

— MethodRemove 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.

`Catlab.Graphs.BasicGraphs.rem_vertices!`

— MethodRemove multiple vertices from a graph.

Edges incident to any of the vertices are treated as in `rem_vertex!`

.

`Catlab.Graphs.BasicGraphs.vertex`

— MethodIncident vertex (vertices) of half-edge(s) in a half-edge graph.

`Catlab.Graphs.BasicGraphs.vertices`

— MethodVertices in a graph.

`Catlab.Graphs.BasicGraphs.weight`

— MethodWeight(s) of edge(s) in a weighted graph.

`Catlab.Theories.src`

— MethodSource vertex (vertices) of edges(s) in a graph.

`Catlab.Theories.tgt`

— MethodTarget vertex (vertices) of edges(s) in a graph.

`Catlab.Theories.ThCocompleteCategory`

— ModuleTheory of a *(finitely) cocomplete category*

Finite colimits are presented in biased style, via finite coproducts and coequalizers. The axioms are dual to those of `ThCompleteCategory`

.

`Catlab.Theories.ThTracedMonoidalCategory`

— ModuleTheory of *traced monoidal categories*

`Catlab.WiringDiagrams.UndirectedWiringDiagrams`

— ModuleData structure for undirected wiring diagrams.

`Catlab.WiringDiagrams.UndirectedWiringDiagrams.AbstractUWD`

— TypeAbstract type for UWDs, typed or untyped, possibly with extra attributes.

`Catlab.WiringDiagrams.UndirectedWiringDiagrams.HasUWD`

— TypeAbstract type for C-sets that contain a UWD.

This type includes UWDs, scheduled UWDs, and nested UWDs.

`Catlab.WiringDiagrams.UndirectedWiringDiagrams.TypedUWD`

— TypeA typed undirected wiring diagram.

A UWD whose ports and junctions must be compatibly typed.

`Catlab.WiringDiagrams.UndirectedWiringDiagrams.UntypedUWD`

— TypeAn undirected wiring diagram.

The most basic kind of UWD, without types or other extra attributes.

`Catlab.WiringDiagrams.DirectedWiringDiagrams.add_wire!`

— MethodWire 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!`

.

`Catlab.WiringDiagrams.UndirectedWiringDiagrams.cospan_diagram`

— MethodUndirected wiring diagram defined by a cospan.

The wiring diagram has a single box. The ports of this box, the outer ports, the junctions, and the connections between them are defined by the cospan. Thus, this function generalizes `singleton_diagram`

.

See also: `junction_diagram`

.

`Catlab.WiringDiagrams.UndirectedWiringDiagrams.junction_diagram`

— MethodUndirected wiring diagram with no boxes, only junctions.

See also: `singleton_diagram`

, `cospan_diagram`

.

`Catlab.WiringDiagrams.CPortGraphs.AbstractCPortGraph`

— TypeAbstract type for circular port graphs.

`Catlab.WiringDiagrams.CPortGraphs.AbstractOpenCPortGraph`

— TypeAbstract type for open circular port graphs.

`Catlab.WiringDiagrams.CPortGraphs.CPortGraph`

— TypeA 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.

`Catlab.WiringDiagrams.CPortGraphs.OpenCPortGraph`

— TypeAn 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.

`Catlab.Programs`

— ModuleGenerate and parse Julia programs based on diagrams.

`Catlab.Theories.ThSymmetricMonoidalCopresheaf`

— ModuleTheory 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.

`Catlab.Theories.ThMonoidalDoubleCategory`

— ModuleTheory 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₀)$.

References:

- Shulman, 2010: Constructing symmetric monoidal bicategories

FIXME: Should also inherit `ThMonoidalCategory{Ob,Hom}`

but multiple inheritance is not supported.

`Catlab.CategoricalAlgebra.Subobjects.ThSubobjectHeytingAlgebra`

— ModuleTheory of Heyting algebra of subobjects in a Heyting category, such as a topos.

`Catlab.CategoricalAlgebra.Diagrams`

— ModuleDiagrams in a category and their morphisms.

`Catlab.CategoricalAlgebra.Diagrams.Diagram`

— TypeDiagram 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.

`Catlab.CategoricalAlgebra.Diagrams.DiagramHom`

— TypeMorphism 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$:

`DiagramHom{id}`

: a functor $F: J → J′$ together with a natural transformation $ϕ: D ⇒ F⋅D′$`DiagramHom{op}`

: a functor $F: J′ → J$ together with a natural transformation $ϕ: F⋅D ⇒ D′$`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.

`Catlab.CategoricalAlgebra.Diagrams.DiagramHom`

— MethodConvert the diagram category in which a diagram hom is being viewed.

`Catlab.CategoricalAlgebra.Diagrams.SimpleDiagram`

— TypeDefault concrete type for diagram in a category.

`Catlab.CategoricalAlgebra.Diagrams.diagram`

— MethodFunctor underlying a diagram in a category.

`Catlab.CategoricalAlgebra.Diagrams.functor`

— MethodFunctor underlying a diagram in a category.

`Catlab.CategoricalAlgebra.Diagrams.shape`

— MethodThe *shape* or *indexing category* of a diagram.

This is the domain of the underlying functor.

`Catlab.CategoricalAlgebra.FinCats.force`

— MethodForce-evaluate the functor in a diagram.

`Catlab.Theories.ThCartesianDoubleCategory`

— ModuleTheory 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.

`Catlab.Theories.ThSymmetricMonoidalCategoryAdditive`

— ModuleTheory of *symmetric monoidal categories*, in additive notation

Mathematically the same as `ThSymmetricMonoidalCategory`

but with different notation.

`Catlab.Theories.FreeCategory2`

— ModuleSyntax for a 2-category.

This syntax checks domains of morphisms but not 2-morphisms.

`Catlab.Theories.ThCocartesianCategory`

— ModuleTheory of *cocartesian (monoidal) categories*

For the traditional axiomatization of coproducts, see `ThCategoryWithCoproducts`

.

`Catlab.Theories.ThMonoidalCategoryWithCodiagonals`

— ModuleTheory of *monoidal categories with codiagonals*

A monoidal category with codiagonals is a symmetric monoidal category equipped with coherent collections of merging and creating morphisms (monoids). Unlike in a cocartesian category, the naturality axioms need not be satisfied.

For references, see `ThMonoidalCategoryWithDiagonals`

.

`Catlab.WiringDiagrams.GraphMLWiringDiagrams`

— ModuleSerialize 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.

References:

- GraphML Primer: http://graphml.graphdrawing.org/primer/graphml-primer.html
- GraphML DTD: http://graphml.graphdrawing.org/specification/dtd.html

`Catlab.WiringDiagrams.GraphMLWiringDiagrams.generate_graphml`

— MethodGenerate GraphML representing a wiring diagram.

`Catlab.WiringDiagrams.GraphMLWiringDiagrams.parse_graphml`

— MethodParse a wiring diagram from a GraphML string or XML document.

`Catlab.WiringDiagrams.GraphMLWiringDiagrams.parse_graphml_metagraph`

— MethodParse a property graph from a GraphML string or XML document.

The equivalent of NetworkX's `parse_graphml`

function.

`Catlab.WiringDiagrams.GraphMLWiringDiagrams.read_graphml`

— MethodRead a wiring diagram from a GraphML file.

`Catlab.WiringDiagrams.GraphMLWiringDiagrams.read_graphml_metagraph`

— MethodRead a property graph from a GraphML file.

The equivalent of NetworkX's `read_graphml`

function.

`Catlab.WiringDiagrams.GraphMLWiringDiagrams.write_graphml`

— MethodWrite a wiring diagram to a file as GraphML.

`Catlab.CategoricalAlgebra.Sets`

— ModuleCategory 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`

.

`Catlab.CategoricalAlgebra.Sets.CompositeFunction`

— TypeComposite of functions in **Set**.

Not to be confused with `Base.ComposedFunctions`

for ordinary Julia functions.

`Catlab.CategoricalAlgebra.Sets.ConstantFunction`

— TypeFunction in **Set** taking a constant value.

`Catlab.CategoricalAlgebra.Sets.IdentityFunction`

— TypeIdentity function in **Set**.

`Catlab.CategoricalAlgebra.Sets.PredicatedSet`

— TypeSet defined by a predicate (boolean-valued function) on a Julia data type.

`Catlab.CategoricalAlgebra.Sets.SetFunction`

— TypeAbstract 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.

`Catlab.CategoricalAlgebra.Sets.SetFunctionCallable`

— TypeFunction in **Set** defined by a callable Julia object.

`Catlab.CategoricalAlgebra.Sets.SetOb`

— TypeAbstract 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`

.

`Catlab.CategoricalAlgebra.Sets.TypeSet`

— TypeA Julia data type regarded as a set.

`AlgebraicInterfaces.Ob`

— MethodForgetful functor Ob: Cat → Set.

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

`Catlab.Theories.ThMonoidalCategoryAdditive`

— ModuleTheory of *monoidal categories*, in additive notation

Mathematically the same as `ThMonoidalCategory`

but with different notation.

`Catlab.WiringDiagrams.WiringDiagramSerialization`

— ModuleConventions 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.

`Catlab.Theories.ThSymmetricRigCategory`

— ModuleTheory of a *symmetric rig category*

FIXME: Should also inherit `ThSymmetricMonoidalCategory`

.

`Catlab.CategoricalAlgebra.Chase`

— ModuleThe 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.

`Catlab.CategoricalAlgebra.Chase.active_triggers`

— MethodNaively 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.

`Catlab.CategoricalAlgebra.Chase.add_term!`

— MethodModify C-Set representing a pattern to add a term. Assumes morphism begins from index 1.

`Catlab.CategoricalAlgebra.Chase.chase`

— Method`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.

`Catlab.CategoricalAlgebra.Chase.chase_step`

— MethodRun a single chase step.

`Catlab.CategoricalAlgebra.Chase.collage`

— MethodA collage of a functor is a schema encoding the data of the functor It has the mapping data in addition to injections from the (co)domain.

`Catlab.CategoricalAlgebra.Chase.collage`

— MethodConvert a CSet morphism X->Y into a CSet on the schema C->C (collage of id functor on C).

`Catlab.CategoricalAlgebra.Chase.combine_dicts!`

— MethodCombine a user-specified initial dict with `init`

, generated by constraints `Initial`

could contain vectors or int-keyed dicts as its data for each object.

`Catlab.CategoricalAlgebra.Chase.coproduct_fincat`

— MethodPreserves the original name of the inputs if it is unambiguous, otherwise disambiguates with index in original input. E.g. (A,B)⊔(B,C) → (A,B#1,B#2,C)

`Catlab.CategoricalAlgebra.Chase.crel_type`

— MethodCreate an ACSet type that replaces each Hom/Attr with a span. If a name is provided, return a ()->DynamicACSet, otherwise an AnonACSetType.

`Catlab.CategoricalAlgebra.Chase.egd`

— MethodDistill the component of a morphism that merges elements together

`Catlab.CategoricalAlgebra.Chase.equation_to_ed`

— MethodAn 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`

.

`Catlab.CategoricalAlgebra.Chase.extend_morphism`

— MethodGiven 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.

`Catlab.CategoricalAlgebra.Chase.extend_morphism_constraints`

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

`B`

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

`Catlab.CategoricalAlgebra.Chase.fire_triggers`

— MethodCompute pushout of all EDs in parallel by combining each list of morphisms into a single one & taking a pushout.

`Catlab.CategoricalAlgebra.Chase.from_c_rel`

— MethodA partially defined inverse to to*c*rel.

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

`Catlab.CategoricalAlgebra.Chase.from_c_rel`

— MethodA partially defined inverse to to*c*rel., on morphisms.

`Catlab.CategoricalAlgebra.Chase.no_change`

— MethodCheck if id up to isomorphism

`Catlab.CategoricalAlgebra.Chase.pres_to_eds`

— MethodCreate 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.

`Catlab.CategoricalAlgebra.Chase.split_Σ`

— MethodWe 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.

`Catlab.CategoricalAlgebra.Chase.split_Σ`

— MethodSplit a dict of (general) EDs into dicts of EGDs and TGDs

`Catlab.CategoricalAlgebra.Chase.tgd`

— MethodDistill the component of a morphism that adds new elements

`Catlab.CategoricalAlgebra.Chase.to_c_rel`

— MethodA functor C-Set -> C-Rel, on morphisms. It simply disregards the morphism data in C-Rel that keeps track of the span apex objects.

`Catlab.CategoricalAlgebra.Chase.to_c_rel`

— MethodA functor C-Set -> C-Rel, on objects. Can be applied safely to C-sets with undefined references.

`Catlab.Theories.ThBiproductCategory`

— ModuleTheory of *biproduct categories*

Mathematically the same as `ThSemiadditiveCategory`

but written multiplicatively, instead of additively.

`Catlab.Theories.ThDisplayedCategory`

— ModuleTheory 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.

References:

- nLab: displayed category
- Ahrens & Lumsdaine, 2019: Displayed categories, Definition 3.1

`Catlab.Theories.ThDaggerCompactCategory`

— ModuleTheory 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.

`Catlab.Theories.ThDaggerCategory`

— ModuleTheory of *dagger categories*

`Catlab.Programs.ParseJuliaPrograms`

— ModuleParse Julia programs into morphisms represented as wiring diagrams.

`Catlab.Programs.ParseJuliaPrograms.compile_recording_expr`

— MethodGenerate a Julia function expression that will record function calls.

Rewrites the function body so that:

- Ordinary function calls are mapped to recorded calls, e.g.,
`f(x,y)`

becomes`recorder(f,x,y)`

- "Curly" function calls are mapped to ordinary function calls, e.g.,
`f{X,Y}`

becomes`f(X,Y)`

`Catlab.Programs.ParseJuliaPrograms.eval_type_expr`

— MethodEvaluate pseudo-Julia type expression, such as `X`

or `otimes{X,Y}`

.

`Catlab.Programs.ParseJuliaPrograms.make_lookup_table`

— MethodMake a lookup table assigning names to generators or term constructors.

`Catlab.Programs.ParseJuliaPrograms.normalize_arguments`

— MethodNormalize arguments given as (possibly nested) tuples or vectors of values.

`Catlab.Programs.ParseJuliaPrograms.parse_wiring_diagram`

— MethodParse a wiring diagram from a Julia function expression.

For more information, see the corresponding macro `@program`

.

`Catlab.Programs.ParseJuliaPrograms.record_call!`

— MethodRecord a Julia function call as a box in a wiring diagram.

`Catlab.Programs.ParseJuliaPrograms.unique_symbols`

— MethodSet of all symbols occuring in a Julia expression.

`Catlab.Programs.ParseJuliaPrograms.@program`

— MacroParse 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)
g(x,y)
```

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`

.

`Catlab.Graphs.GraphGenerators.complete_graph`

— MethodComplete graph on $n$ vertices.

`Catlab.Graphs.GraphGenerators.cycle_graph`

— MethodCycle graph on $n$ vertices.

When $n = 1$, this is a loop graph.

`Catlab.Graphs.GraphGenerators.erdos_renyi`

— Method`erdos_renyi(GraphType, n, ne)`

Create an Erdős–Rényi random graph with `n`

vertices and `ne`

edges.

**References**

- https://github.com/JuliaGraphs/LightGraphs.jl/blob/2a644c2b15b444e7f32f73021ec276aa9fc8ba30/src/SimpleGraphs/generators/randgraphs.jl

`Catlab.Graphs.GraphGenerators.erdos_renyi`

— Method`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

**References**

- https://github.com/JuliaGraphs/LightGraphs.jl/blob/2a644c2b15b444e7f32f73021ec276aa9fc8ba30/src/SimpleGraphs/generators/randgraphs.jl

`Catlab.Graphs.GraphGenerators.expected_degree_graph`

— Method`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.

**References**

- Connected Components in Random Graphs with Given Expected Degree Sequences, Linyuan Lu and Fan Chung. https://link.springer.com/article/10.1007%2FPL00012580
- Efficient Generation of Networks with Given Expected Degrees, Joel C. Miller and Aric Hagberg. https://doi.org/10.1007/978-3-642-21286-4_10
- https://github.com/JuliaGraphs/LightGraphs.jl/blob/2a644c2b15b444e7f32f73021ec276aa9fc8ba30/src/SimpleGraphs/generators/randgraphs.jl#L187

`Catlab.Graphs.GraphGenerators.parallel_arrows`

— MethodGraph with two vertices and $n$ parallel edges.

`Catlab.Graphs.GraphGenerators.path_graph`

— MethodPath graph on $n$ vertices.

`Catlab.Graphs.GraphGenerators.randbn`

— Method`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

**References**

- "Non-Uniform Random Variate Generation," Luc Devroye, p. 522. Retrieved via http://www.eirene.de/Devroye.pdf.
- http://stackoverflow.com/questions/23561551/a-efficient-binomial-random-number-generator-code-in-java
- https://github.com/JuliaGraphs/LightGraphs.jl/blob/2a644c2b15b444e7f32f73021ec276aa9fc8ba30/src/SimpleGraphs/generators/randgraphs.jl#L90

`Catlab.Graphs.GraphGenerators.star_graph`

— MethodStar graph on $n$ vertices.

In the directed case, the edges point outward.

`Catlab.Graphs.GraphGenerators.watts_strogatz`

— Method`watts_strogatz(n, k, β)`

Return a Watts-Strogatz small world random graph with `n`

vertices, each with expected degree `k`

(or `k

- 1
`if`

k`is 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)`

.

Consider each vertex

`s`

in turn, along with the edge to its`i`

th nearest neighbor`t`

, in a clockwise sense.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.

**References**

- Collective dynamics of ‘small-world’ networks, Duncan J. Watts, Steven H. Strogatz. https://doi.org/10.1038/30918
- Small Worlds, Duncan J. watts. https://en.wikipedia.org/wiki/Special:BookSources?isbn=978-0691005416
- https://github.com/JuliaGraphs/LightGraphs.jl/blob/2a644c2b15b444e7f32f73021ec276aa9fc8ba30/src/SimpleGraphs/generators/randgraphs.jl#L187

`Catlab.Graphs.GraphGenerators.wheel_graph`

— MethodWheel graph on $n$ vertices.

In the directed case, the outer cycle is directed and the spokes point outward.

`Catlab.Graphics.Graphviz`

— ModuleAST and pretty printer for Graphviz's DOT language.

References:

- DOT grammar: http://www.graphviz.org/doc/info/lang.html
- DOT language guide: http://www.graphviz.org/pdf/dotguide.pdf

`Catlab.Graphics.Graphviz.Html`

— TypeAST type for Graphviz's "HTML-like" node labels.

For now, the HTML content is just a string.

`Catlab.Graphics.Graphviz.Label`

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

`Catlab.Graphics.Graphviz.pprint`

— MethodPretty-print the Graphviz expression.

`Catlab.Graphics.Graphviz.run_graphviz`

— MethodRun 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.

`Catlab.WiringDiagrams.JSONWiringDiagrams`

— ModuleSerialize 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.

References:

- KEILER's JSON graph format: https://rtsys.informatik.uni-kiel.de/confluence/display/KIELER/JSON+Graph+Format
- ELK's JSON graph format: https://www.eclipse.org/elk/documentation/tooldevelopers/graphdatastructure/jsonformat.html

`Catlab.WiringDiagrams.JSONWiringDiagrams.generate_json_graph`

— MethodGenerate a JSON dict representing a wiring diagram.

`Catlab.WiringDiagrams.JSONWiringDiagrams.parse_json_graph`

— MethodParse a wiring diagram from a JSON string or dict.

`Catlab.WiringDiagrams.JSONWiringDiagrams.read_json_graph`

— MethodRead a wiring diagram from a JSON file.

`Catlab.WiringDiagrams.JSONWiringDiagrams.write_json_graph`

— MethodWrite a wiring diagram to a file as JSON.

`Catlab.CategoricalAlgebra.FinSets`

— ModuleThe category of finite sets and functions, and its skeleton.

`Catlab.CategoricalAlgebra.FinSets.DiscreteCat`

— TypeDiscrete category on a finite set.

The only morphisms in a discrete category are the identities, which are here identified with the objects.

`Catlab.CategoricalAlgebra.FinSets.FinDomFunction`

— TypeFunction out of a finite set.

This class of functions is convenient because it is exactly the class that can be represented explicitly by a vector of values from the codomain.

`Catlab.CategoricalAlgebra.FinSets.FinDomFunctionDict`

— TypeFunction in **Set** represented by a dictionary.

The domain is a `FinSet{S}`

where `S`

is the type of the dictionary's `keys`

collection.

`Catlab.CategoricalAlgebra.FinSets.FinDomFunctionVector`

— TypeFunction in **Set** represented by a vector.

The domain of this function is always of type `FinSet{Int}`

, with elements of the form ${1,...,n}$.

`Catlab.CategoricalAlgebra.FinSets.FinFunction`

— TypeFunction 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`

.

`Catlab.CategoricalAlgebra.FinSets.FinFunctionDict`

— TypeFunction in **FinSet** represented by a dictionary.

`Catlab.CategoricalAlgebra.FinSets.FinFunctionVector`

— TypeFunction in **FinSet** represented explicitly by a vector.

`Catlab.CategoricalAlgebra.FinSets.FinSet`

— TypeFinite 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}`

.

`Catlab.CategoricalAlgebra.FinSets.FinSetCollection`

— TypeFinite set given by Julia collection.

The underlying collection should be a Julia iterable of definite length. It may be, but is not required to be, set-like (a subtype of `AbstractSet`

).

`Catlab.CategoricalAlgebra.FinSets.FinSetCompositeColimit`

— TypeColimit of general diagram of FinSets computed by coproduct-then-quotient.

See `Limits.CompositePushout`

for a very similar construction.

`Catlab.CategoricalAlgebra.FinSets.FinSetCompositeLimit`

— TypeLimit of general diagram of FinSets computed by product-then-filter.

See `Limits.CompositePullback`

for a very similar construction.

`Catlab.CategoricalAlgebra.FinSets.FinSetIndexedLimit`

— TypeLimit 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.

`Catlab.CategoricalAlgebra.FinSets.FinSetInt`

— TypeFinite set of the form ${1,…,n}$ for some number $n ≥ 0$.

`Catlab.CategoricalAlgebra.FinSets.HashJoin`

— TypeHash join algorithm.

`Catlab.CategoricalAlgebra.FinSets.IndexedFinDomFunctionVector`

— TypeIndexed function out of a finite set of type `FinSet{Int}`

.

Works in the same way as the special case of `IndexedFinFunctionVector`

, except that the index is typically a dictionary, not a vector.

`Catlab.CategoricalAlgebra.FinSets.IndexedFinFunctionVector`

— TypeIndexed 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`

.

`Catlab.CategoricalAlgebra.FinSets.JoinAlgorithm`

— TypeAlgorithm for limit of cospan or multicospan with feet being finite sets.

In the context of relational databases, such limits are called *joins*. The trivial join algorithm is `NestedLoopJoin`

, which is algorithmically equivalent to the generic algorithm `ComposeProductEqualizer`

. The algorithms `HashJoin`

and `SortMergeJoin`

are usually much faster. If you are unsure what algorithm to pick, use `SmartJoin`

.

`Catlab.CategoricalAlgebra.FinSets.NamedColimit`

— TypeCompute 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.

`Catlab.CategoricalAlgebra.FinSets.NestedLoopJoin`

— TypeNested-loop join algorithm.

This is the naive algorithm for computing joins.

`Catlab.CategoricalAlgebra.FinSets.SmartJoin`

— TypeMeta-algorithm for joins that attempts to pick an appropriate algorithm.

`Catlab.CategoricalAlgebra.FinSets.SortMergeJoin`

— TypeSort-merge join algorithm.

`Catlab.CategoricalAlgebra.FinSets.SubFinSet`

— TypeSubset of a finite set.

`Catlab.CategoricalAlgebra.FinSets.SubFinSetVector`

— TypeSubset of a finite set represented as a boolean vector.

This is the subobject classifier representation since `Bool`

is the subobject classifier for `Set`

.

`Catlab.CategoricalAlgebra.FinSets.SubOpBoolean`

— TypeAlgorithm to compute subobject operations using elementwise boolean logic.

`Catlab.CategoricalAlgebra.FinSets.TabularLimit`

— TypeLimit 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.

`Catlab.CategoricalAlgebra.FinSets.TabularSet`

— TypeFinite 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.

`Catlab.CategoricalAlgebra.FinSets.VarFunction`

— TypeData 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)

`Catlab.CategoricalAlgebra.FinSets.VarSet`

— TypeControl dispatch in the category of VarFunctions

`ACSets.PreimageCaches.preimage`

— MethodThe preimage (inverse image) of the value y in the codomain.

`AlgebraicInterfaces.compose`

— MethodCompose [n]->[m]+T with [m]->[p], yielding a [n]->T+[p]

`AlgebraicInterfaces.compose`

— MethodKleisi composition of [n]->T+[m] and [m]->T'+[p], yielding a [n]->T'+[p]

`Catlab.CategoricalAlgebra.FinSets.equalize_all`

— MethodCompute 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.

`Catlab.CategoricalAlgebra.FinSets.is_indexed`

— MethodWhether the given function is indexed, i.e., supports efficient preimages.

`Catlab.CategoricalAlgebra.FinSets.pair_all`

— MethodPerform 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.

`Catlab.CategoricalAlgebra.FinSets.pass_to_quotient`

— MethodGiven h: X → Y, pass to quotient q: X/~ → Y under projection π: X → X/~.

`Catlab.CategoricalAlgebra.FinSets.quotient_projection`

— MethodCreate projection map π: X → X/∼ from partition of X.

`Catlab.CategoricalAlgebra.FinSets.unique_by_tagging!`

— MethodMake list of elements unique by adding tags if necessary.

If the elements are already unique, they will not be mutated.

`Catlab.CategoricalAlgebra.Subobjects.ThSubobjectBiHeytingAlgebra`

— ModuleTheory of bi-Heyting algebra of subobjects in a bi-Heyting topos, such as a presheaf topos.

`Catlab.Theories.FreeCartesianCategory`

— ModuleSyntax 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.

`Catlab.CategoricalAlgebra.CatElements.elements`

— Method`elements(f::ACSetTransformation)`

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.

`Catlab.CategoricalAlgebra.CatElements.elements`

— Method`elements(X::AbstractACSet)`

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.

`Catlab.CategoricalAlgebra.CatElements.inverse_elements`

— Method`inverse_elements(X::AbstractElements, typ::StructACSet)`

Compute inverse grothendieck transformation on a morphism of Elements

`Catlab.CategoricalAlgebra.CatElements.inverse_elements`

— Method`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.

`Catlab.CategoricalAlgebra.CatElements.ob_ids`

— MethodDetermine the (partial) mapping from Elements to indices for each component E.g. [V,E,V,V,E] ⟶ [V=>{1↦1, 3↦2, 4↦3}, E=>{2↦1, 5↦2}]

`Catlab.CategoricalAlgebra.CatElements.presentation`

— Method`presentation(X::AbstractElements)`

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`

.

`Catlab.Theories.ThDistributiveBicategoryRelations`

— ModuleTheory of a *distributive bicategory of relations*

References:

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

`Catlab.Theories.ThDistributiveMonoidalCategory`

— ModuleTheory 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`

.

`Catlab.Theories.ThMCategory`

— ModuleTheory 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.

`Catlab.Theories.ThPoset`

— ModuleTheory of *partial orders* (posets)

`Catlab.Theories.ThMonoidalCategoryWithBidiagonalsAdditive`

— ModuleTheory of *monoidal categories with bidiagonals*, in additive notation

Mathematically the same as `ThMonoidalCategoryWithBidiagonals`

but written additively, instead of multiplicatively.

`Catlab.Theories.ThMonoidalCategory`

— ModuleTheory 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.

`Catlab.Theories.FreeCartesianClosedCategory`

— ModuleSyntax for a free cartesian closed category.

See also `FreeCartesianCategory`

.

`Catlab.Theories.ThOpindexedMonoidalCategory`

— ModuleTheory 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.

References:

- nLab: indexed monoidal category
- Shulman, 2008: Framed bicategories and monoidal fibrations
- Shulman, 2013: Enriched indexed categories

`Catlab.Theories.ThGroupoid`

— ModuleTheory of *groupoids*.

`Catlab.Theories.ThLattice`

— ModuleTheory 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`

.

`Catlab.Theories.ThThinCategory`

— ModuleTheory of *thin categories*

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

`Catlab.Graphics.GraphvizGraphs`

— ModuleGraphviz support for Catlab's graph types.

`Catlab.Graphics.GraphvizGraphs.parse_graphviz`

— MethodParse 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.

`Catlab.Graphics.GraphvizGraphs.parse_point`

— MethodParse Graphviz point.

http://www.graphviz.org/doc/info/attrs.html#k:point

`Catlab.Graphics.GraphvizGraphs.parse_spline`

— MethodParse 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.

http://www.graphviz.org/doc/info/attrs.html#k:splineType https://web.archive.org/web/20170418034924/http://www.graphviz.org/content/how-convert-b-spline-bezier

`Catlab.Graphics.GraphvizGraphs.parse_vector`

— MethodParse an array of floats in Graphviz's comma-separated format.

`Catlab.Graphics.GraphvizGraphs.to_graphviz`

— MethodConvert 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.

`Catlab.Graphics.GraphvizGraphs.to_graphviz`

— MethodVisualize 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.

**Arguments**

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

`Catlab.Graphics.GraphvizGraphs.to_graphviz`

— MethodConvert 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.

`Catlab.Graphics.GraphvizGraphs.to_graphviz`

— MethodVisualize 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.

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

`Catlab.Graphics.GraphvizGraphs.to_graphviz_property_graph`

— MethodConvert graph or other structure to a property graph suitable for Graphviz.

This function is an intermediate step in many methods of the generic function `to_graphviz`

, but can be useful in its own right for customizing the Graphviz graph beyond whatever options are supported by `to_graphviz`

.

`Catlab.Theories.ThDoubleCategoryWithTabulators`

— ModuleTheory 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.

`Catlab.Graphs.GraphSearching.bfs_parents`

— Method`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).

**Performance**

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.

`Catlab.Graphs.GraphSearching.bfs_tree`

— Method`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).

`Catlab.Graphs.GraphSearching.dfs_parents`

— Method`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.

`Catlab.Graphs.GraphSearching.dfs_tree`

— Method`dfs_tree(g, s)`

Return a directed acyclic graph based on depth-first traversal of the graph `g`

starting with source vertex `s`

.

`Catlab.Graphs.GraphSearching.tree`

— Method`tree(parents)`

Convert a parents array into a directed graph.

`Catlab.Theories.ThPointedSetCategory`

— ModuleTheory 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.

`Catlab.Theories.ThSchema`

— ModuleThe 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.

`Catlab.Graphics.TikZWiringDiagrams`

— ModuleDraw wiring diagrams using TikZ.

`Catlab.Graphics.TikZWiringDiagrams.TikZOptions`

— TypeInternal data type for configurable options of Compose.jl wiring diagrams.

`Catlab.Graphics.TikZWiringDiagrams.escape_latex`

— MethodEscape special LaTeX characters.

Reference: https://tex.stackexchange.com/a/34586/

`Catlab.Graphics.TikZWiringDiagrams.layout_to_tikz`

— MethodDraw a wiring diagram in TikZ using the given layout.

`Catlab.Graphics.TikZWiringDiagrams.tikz_box`

— MethodMake TikZ node for a box.

`Catlab.Graphics.TikZWiringDiagrams.tikz_edge`

— MethodMake a TikZ edge/path for a wire.

`Catlab.Graphics.TikZWiringDiagrams.tikz_node_style`

— MethodGet default TikZ style for given kind of node.

`Catlab.Graphics.TikZWiringDiagrams.tikz_node_style`

— MethodGet TikZ style for box.

`Catlab.Graphics.TikZWiringDiagrams.tikz_port`

— MethodMake TikZ coordinate and angle for a port.

`Catlab.Graphics.TikZWiringDiagrams.tikz_styles`

— MethodMake TikZ style definitions for wiring diagram.

`Catlab.Graphics.TikZWiringDiagrams.to_tikz`

— MethodDraw a wiring diagram in TikZ.

`Catlab.Theories.ThCoindexedMonoidalCategory`

— ModuleTheory 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.

References:

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

`Catlab.Theories.ThOpindexedCategory`

— ModuleTheory 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)$.

`Catlab.Theories.ThPreorder`

— ModuleTheory 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.

`Catlab.Theories.ThCartesianCategory`

— ModuleTheory of *cartesian (monoidal) categories*

For the traditional axiomatization of products, see `ThCategoryWithProducts`

.

`Catlab.Theories.ThAdditiveCategory`

— ModuleTheory 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.

`Catlab.WiringDiagrams.WiringDiagramAlgorithms`

— ModuleAlgorithms on wiring diagrams.

`Catlab.Graphs.GraphAlgorithms.topological_sort`

— MethodTopological sort of boxes in wiring diagram.

Returns a list of box IDs, excluding the outer box's input and output IDs.

`Catlab.WiringDiagrams.WiringDiagramAlgorithms.crossing_minimization_by_sort`

— MethodCrossing 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.

`Catlab.WiringDiagrams.WiringDiagramAlgorithms.normalize_cartesian!`

— MethodPut a wiring diagram for a cartesian category into normal form.

This function puts a wiring diagram representing a morphism in a free cartesian category into normal form. Copies and deletions are simplified as much as possible.

`Catlab.WiringDiagrams.WiringDiagramAlgorithms.normalize_copy!`

— MethodNormalize 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.

`Catlab.WiringDiagrams.WiringDiagramAlgorithms.normalize_delete!`

— MethodNormalize deletions in a wiring diagram.

This function removes all unused intermediate computations in a wiring diagram where deletion is natural.

`Catlab.WiringDiagrams.WiringDiagramAlgorithms.port_coords`

— MethodMake function mapping ports to logical coordinates.

`Catlab.Theories.ThDaggerSymmetricMonoidalCategory`

— ModuleTheory of *dagger symmetric monoidal categories*

Also known as a symmetric monoidal dagger category.

FIXME: This theory should also extend `ThDaggerCategory`

, but multiple inheritance is not yet supported.

`Catlab.WiringDiagrams.MonoidalDirectedWiringDiagrams`

— ModuleWiring 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.

`Catlab.WiringDiagrams.MonoidalDirectedWiringDiagrams.BoxOp`

— TypeBox wrapping another box.

Represents unary operations on boxes in wiring diagrams.

`Catlab.WiringDiagrams.MonoidalDirectedWiringDiagrams.Junction`

— TypeJunction node in a wiring diagram.

Junction nodes are used to explicitly represent copies, merges, deletions, creations, caps, and cups.

`Catlab.WiringDiagrams.MonoidalDirectedWiringDiagrams.PortOp`

— TypePort value wrapping another value.

Represents unary operations on ports in wiring diagrams.

`Catlab.WiringDiagrams.MonoidalDirectedWiringDiagrams.Ports`

— TypeA list of ports.

The objects in categories of wiring diagrams.

`Catlab.Theories.trace`

— MethodTrace (feedback loop) in a wiring diagram.

`Catlab.WiringDiagrams.MonoidalDirectedWiringDiagrams.##docsink#3296`

— FunctionWiring diagrams as a symmetric monoidal category.

Extra structure, such as copying or merging, can be added to wiring diagrams in different ways, but wiring diagrams always form a symmetric monoidal category in the same way.

`Catlab.WiringDiagrams.MonoidalDirectedWiringDiagrams.add_junctions`

— MethodAdd junction nodes to wiring diagram.

Transforms from the implicit to the explicit representation of diagonals and codiagonals. This operation is inverse to `rem_junctions`

.

`Catlab.WiringDiagrams.MonoidalDirectedWiringDiagrams.implicit_mcopy`

— MethodImplicit copy in wiring diagram.

Copies are represented by multiple outgoing wires from a single port and deletions by no outgoing wires.

`Catlab.WiringDiagrams.MonoidalDirectedWiringDiagrams.implicit_mmerge`

— MethodImplicit merge in wiring diagram.

Merges are represented by multiple incoming wires into a single port and creations by no incoming wires.

`Catlab.WiringDiagrams.MonoidalDirectedWiringDiagrams.junction_caps`

— MethodWiring diagram of nested caps made out of junction nodes.

`Catlab.WiringDiagrams.MonoidalDirectedWiringDiagrams.junction_cups`

— MethodWiring diagram of nested cups made out of junction nodes.

`Catlab.WiringDiagrams.MonoidalDirectedWiringDiagrams.junctioned_mcopy`

— MethodExplicit copy in wiring diagram.

Copies and deletions are represented by junctions (boxes of type `Junction`

).

`Catlab.WiringDiagrams.MonoidalDirectedWiringDiagrams.junctioned_mmerge`

— MethodExplicit merge in wiring diagram.

Merges and creations are represented by junctions (boxes of type `Junction`

).

`Catlab.WiringDiagrams.MonoidalDirectedWiringDiagrams.merge_junctions`

— MethodMerge adjacent junction nodes into single junctions.

`Catlab.WiringDiagrams.MonoidalDirectedWiringDiagrams.rem_junctions`

— MethodRemove junction nodes from wiring diagram.

Transforms from the explicit to the implicit representation of diagonals and codiagonals. This operation is inverse to `add_junctions`

.

`Catlab.WiringDiagrams.UndirectedWiringDiagrams.junction_diagram`

— MethodWiring diagram with a junction node for each of the given ports.

`GATlab.Models.SymbolicModels.functor`

— MethodApply functor in a category of wiring diagrams.

Defined by compatible mappings of ports and boxes.

`Catlab.CategoricalAlgebra.FinCats`

— Module2-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.

`Catlab.CategoricalAlgebra.FinCats.FinCat`

— TypeA finitely presented (but not necessarily finite!) category.

`Catlab.CategoricalAlgebra.FinCats.FinCatGraph`

— TypeAbstract type for category backed by finite generating graph.

`Catlab.CategoricalAlgebra.FinCats.FinCatGraphEq`

— TypeCategory 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).

`Catlab.CategoricalAlgebra.FinCats.FinCatPathGraph`

— TypeAbstract type for category whose morphisms are paths in a graph.

(Or equivalence classes of paths in a graph, but we compute with

`Catlab.CategoricalAlgebra.FinCats.FinCatPresentation`

— TypeCategory 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.

`Catlab.CategoricalAlgebra.FinCats.FinCatSize`

— TypeSize of a finitely presented category.

`Catlab.CategoricalAlgebra.FinCats.FinDomFunctor`

— TypeA functor out of a finitely presented category.

`Catlab.CategoricalAlgebra.FinCats.FinDomFunctorMap`

— TypeFunctor out of a finitely presented category given by explicit mappings.

`Catlab.CategoricalAlgebra.FinCats.FinFunctor`

— TypeA functor between finitely presented categories.

`Catlab.CategoricalAlgebra.FinCats.FinTransformation`

— TypeA 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$).

`Catlab.CategoricalAlgebra.FinCats.FinTransformationMap`

— TypeNatural transformation with components given by explicit mapping.

`Catlab.CategoricalAlgebra.FinCats.FreeCatGraph`

— TypeFree category generated by a finite graph.

The objects of the free category are vertices in the graph and the morphisms are (possibly empty) paths.

`Catlab.CategoricalAlgebra.FinCats.Path`

— TypePath in a graph.

The path is allowed to be empty but always has definite start and end points (source and target vertices).

`Catlab.CategoricalAlgebra.FinCats.collect_hom`

— MethodCollect assignments of functor's morphism map as a vector.

`Catlab.CategoricalAlgebra.FinCats.collect_ob`

— MethodCollect assignments of functor's object map as a vector.

`Catlab.CategoricalAlgebra.FinCats.components`

— MethodComponents of a natural transformation.

`Catlab.CategoricalAlgebra.FinCats.dom_to_graph`

— MethodReinterpret 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 ob*map and hom*map, 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.

`Catlab.CategoricalAlgebra.FinCats.force`

— FunctionForce evaluation of lazily defined function or functor. The resulting ob*map and hom*map are guaranteed to have valtype or eltype, as appropriate, equal to Ob and Hom, respectively.

`Catlab.CategoricalAlgebra.FinCats.functoriality_failures`

— MethodFailures 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.

`Catlab.CategoricalAlgebra.FinCats.graph`

— MethodGraph underlying a finitely presented category whose object and hom generators are indexable, other than one explicitly generated by a graph.

`Catlab.CategoricalAlgebra.FinCats.graph`

— MethodGenerating graph for a finitely presented category.

`Catlab.CategoricalAlgebra.FinCats.hom_generator`

— FunctionCoerce 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`

.

`Catlab.CategoricalAlgebra.FinCats.hom_generator_name`

— FunctionName of morphism generator, if any.

When morphism generators have names, this function is a one-sided inverse to `hom_generator`

. See also: `ob_generator_name`

.

`Catlab.CategoricalAlgebra.FinCats.hom_generators`

— FunctionMorphism generators of finitely presented category.

`Catlab.CategoricalAlgebra.FinCats.is_discrete`

— MethodIs the category discrete?

A category is *discrete* if it is has no non-identity morphisms.

`Catlab.CategoricalAlgebra.FinCats.is_free`

— MethodIs the category freely generated?

`Catlab.CategoricalAlgebra.FinCats.is_functorial`

— MethodIs 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`

.

`Catlab.CategoricalAlgebra.FinCats.is_initial`

— MethodDual 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.

`Catlab.CategoricalAlgebra.FinCats.is_natural`

— MethodIs 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`

.

`Catlab.CategoricalAlgebra.FinCats.make_map`

— MethodMaps `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.

`Catlab.CategoricalAlgebra.FinCats.mappairs`

— MethodMap two given functions across the respective keys and values of a dictionary.

`Catlab.CategoricalAlgebra.FinCats.mapvals`

— MethodMap a function, which may depend on the key, across the values of a dictionary.

`Catlab.CategoricalAlgebra.FinCats.ob_generator`

— FunctionCoerce 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.

`Catlab.CategoricalAlgebra.FinCats.ob_generator_name`

— FunctionName of object generator, if any.

When object generators have names, this function is a one-sided inverse to `ob_generator`

in that `ob_generator(C, ob_generator_name(C, x)) == x`

.

`Catlab.CategoricalAlgebra.FinCats.ob_generators`

— FunctionObject 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.

`Catlab.CategoricalAlgebra.FinCats.presentation`

— MethodComputes 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.

`Catlab.Theories.ThThinSymmetricMonoidalCategory`

— ModuleTheory of *thin symmetric monoidal category*

Thin SMCs are isomorphic to commutative monoidal prosets.

`Catlab.Graphics.WiringDiagramLayouts`

— ModuleBackend-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.

`Catlab.Graphics.WiringDiagramLayouts.BoxLayout`

— TypeLayout 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.

`Catlab.Graphics.WiringDiagramLayouts.LayoutOptions`

— TypeInternal data type for configurable options of wiring diagram layout.

`Catlab.Graphics.WiringDiagramLayouts.LayoutOrientation`

— TypeOrientation of wiring diagram.

`Catlab.Graphics.WiringDiagramLayouts.PortLayout`

— TypeLayout for port in a wiring diagram.

`Catlab.Graphics.WiringDiagramLayouts.WirePoint`

— TypeInterior point of wire in a wiring diagram.

`Catlab.Graphics.WiringDiagramLayouts.box_label`

— MethodLabel for box in wiring diagram.

`Catlab.Graphics.WiringDiagramLayouts.compose_with_layout!`

— MethodCompose wiring diagrams and their layouts.

Compare with: `WiringDiagram.compose`

.

`Catlab.Graphics.WiringDiagramLayouts.default_box_size`

— MethodCompute 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.

`Catlab.Graphics.WiringDiagramLayouts.diagram_element_label`

— MethodLabel for element in wiring diagram.

By default, both `box_label`

and `wire_label`

fall back to this function.

`Catlab.Graphics.WiringDiagramLayouts.layout_box`

— MethodLay out a box and its ports.

By default the box is rectangular, but other shapes are also supported.

`Catlab.Graphics.WiringDiagramLayouts.layout_circular_ports`

— MethodLay out ports along a circular arc.

`Catlab.Graphics.WiringDiagramLayouts.layout_diagram`

— MethodLay 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).

`Catlab.Graphics.WiringDiagramLayouts.layout_elliptical_ports`

— MethodLay out ports along an elliptical arc.

`Catlab.Graphics.WiringDiagramLayouts.layout_hom_expr`

— MethodLay out a morphism expression as a wiring diagram.

`Catlab.Graphics.WiringDiagramLayouts.layout_linear_ports`

— MethodLay out ports linearly, for use with a rectangular box.

Assumes the box is at least as large as `default_box_size()`

.

`Catlab.Graphics.WiringDiagramLayouts.layout_outer_ports!`

— MethodLay out outer ports of wiring diagram.

`Catlab.Graphics.WiringDiagramLayouts.layout_outer_ports`

— MethodLay out outer ports of wiring diagram.

`Catlab.Graphics.WiringDiagramLayouts.layout_pure_wiring`

— MethodLay out the wires in a wiring diagram with no boxes.

`Catlab.Graphics.WiringDiagramLayouts.minimum_diagram_size`

— MethodCompute the minimum size of a wiring diagram from the number of its ports.

`Catlab.Graphics.WiringDiagramLayouts.otimes_with_layout!`

— MethodTensor wiring diagrams and their layouts.

Compare with: `WiringDiagram.otimes`

.

`Catlab.Graphics.WiringDiagramLayouts.place_adjacent!`

— MethodPlace one box adjacent to another.

The absolute positions are undefined; only relative positions are guaranteed.

`Catlab.Graphics.WiringDiagramLayouts.shift_contents!`

— MethodShift all boxes and wires within wiring diagram by a fixed offset.

`Catlab.Graphics.WiringDiagramLayouts.size_to_fit!`

— MethodSize a wiring diagram to fit its contents.

The inner boxes are also shifted to be centered within the new bounds.

`Catlab.Graphics.WiringDiagramLayouts.substitute_with_layout!`

— MethodSubstitute sub-wiring diagrams, preserving their layouts.

`Catlab.Graphics.WiringDiagramLayouts.wire_label`

— MethodLabel for wire in wiring diagram.

Note: This function takes a port value, not a wire value.

`Catlab.CategoricalAlgebra.GraphCategories`

— ModuleCategories of graphs and other categorical and algebraic aspects of graphs.

`Catlab.Theories.ThSymmetricMonoidalCategory`

— ModuleTheory of (strict) *symmetric monoidal categories*

`Catlab.WiringDiagrams.WiringDiagramAlgebras`

— ModuleAlgebras of operads of wiring diagrams.

`Catlab.WiringDiagrams.WiringDiagramAlgebras.homomorphism_query`

— MethodCreate conjunctive query (a UWD) for finding homomorphisms out of a C-set.

Returns the query together with query parameters for the attributes. Homomorphisms from `X`

to `Y`

can be computed by:

`query(Y, homomorphism_query(X)...)`

`Catlab.WiringDiagrams.WiringDiagramAlgebras.oapply`

— FunctionCompose 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.

`Catlab.WiringDiagrams.WiringDiagramAlgebras.query`

— FunctionEvaluate 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.

`Catlab.Graphics.TikZ`

— ModuleAST and pretty printer for TikZ.

This module does not provide bindings to the TikZ LaTeX package. For that, see the TikzPictures.jl package: https://github.com/sisl/TikzPictures.jl

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.

`Catlab.Graphics.TikZ.pprint`

— MethodPretty-print the TikZ expression.

`Catlab.Theories.ThCompleteCategory`

— ModuleTheory 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".

`Catlab.CategoricalAlgebra.HomSearch`

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

`Catlab.CategoricalAlgebra.HomSearch.ACSetHomomorphismAlgorithm`

— TypeAlgorithm for finding homomorphisms between attributed $C$-sets.

`Catlab.CategoricalAlgebra.HomSearch.BacktrackingSearch`

— TypeFind 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.

`Catlab.CategoricalAlgebra.HomSearch.BacktrackingState`

— TypeInternal 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.

`Catlab.CategoricalAlgebra.HomSearch.HomomorphismQuery`

— TypeFind 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).

`Catlab.CategoricalAlgebra.HomSearch.SubobjectIterator`

— TypeEnumerate subobjects of an ACSet in order of largest to smallest (assumes no wandering variables).

`Catlab.CategoricalAlgebra.HomSearch.SubobjectIteratorState`

— Typeseen - any subobject we've seen so far to*recurse - frontier of subobjects we've yet to recursively explore to*yield - Subobjects which we've yet to yield

`Base.iterate`

— FunctionGiven 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.

`Catlab.CategoricalAlgebra.HomSearch.assign_elem!`

— MethodAttempt 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.

`Catlab.CategoricalAlgebra.HomSearch.can_assign_elem`

— MethodCheck whether element (c,x) can be assigned to (c,y) in current assignment.

`Catlab.CategoricalAlgebra.HomSearch.find_mrv_elem`

— MethodFind an unassigned element having the minimum remaining values (MRV).

`Catlab.CategoricalAlgebra.HomSearch.homomorphism`

— MethodFind 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`

.

`Catlab.CategoricalAlgebra.HomSearch.homomorphisms`

— MethodFind all homomorphisms between two attributed $C$-sets.

This function is at least as expensive as `homomorphism`

and when no homomorphisms exist, it is exactly as expensive.

`Catlab.CategoricalAlgebra.HomSearch.is_homomorphic`

— MethodIs the first attributed $C$-set homomorphic to the second?

This function generally reduces to `homomorphism`

but certain algorithms may have minor optimizations.

`Catlab.CategoricalAlgebra.HomSearch.is_isomorphic`

— MethodAre the two attributed $C$-sets isomorphic?

This function generally reduces to `isomorphism`

but certain algorithms may have minor optimizations.

`Catlab.CategoricalAlgebra.HomSearch.is_seen`

— MethodThis would be much more efficient with canonical isomorph

`Catlab.CategoricalAlgebra.HomSearch.isomorphism`

— MethodFind an isomorphism between two attributed $C$-sets, if one exists.

See `homomorphism`

for more information about the algorithms involved.

`Catlab.CategoricalAlgebra.HomSearch.isomorphisms`

— MethodFind all isomorphisms between two attributed $C$-sets.

This function is at least as expensive as `isomorphism`

and when no homomorphisms exist, it is exactly as expensive.

`Catlab.CategoricalAlgebra.HomSearch.maximum_common_subobject`

— MethodCompute 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.

`Catlab.CategoricalAlgebra.HomSearch.partial_assignments`

— MethodGet assignment pairs from partially specified component of C-set morphism.

`Catlab.CategoricalAlgebra.HomSearch.should_yield`

— MethodWe recurse only if there is nothing to yield or we have something to recurse on that is bigger than the biggest thing in our to-yield set.

`Catlab.CategoricalAlgebra.HomSearch.subobject_graph`

— MethodPreorder of subobjects via inclusion. Returns a graph + list of subobjects corresponding to its vertices. The subobjects are ordered by decreasing size (so it's topologically sorted)

`Catlab.CategoricalAlgebra.HomSearch.total_parts`

— MethodCompute 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).

`Catlab.CategoricalAlgebra.HomSearch.unassign_elem!`

— MethodUnassign the element (c,x) in the current assignment.

`Catlab.CategoricalAlgebra.HomSearch.@acset_transformation`

— MacroProvides 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
```

`Catlab.Theories.ThClosedMonoidalCategory`

— ModuleTheory of (symmetric) *closed monoidal categories*

`Catlab.Theories.ThDoubleCategory`

— ModuleTheory 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$.

`Catlab.Programs.GenerateJuliaPrograms`

— ModuleCompile or evaluate morphisms as Julia programs.

`Catlab.Programs.GenerateJuliaPrograms.Block`

— TypeA block of Julia code with input and output variables.

`Catlab.Programs.GenerateJuliaPrograms.CompileState`

— TypeInternal state for compilation of morphism into Julia code.

`Catlab.Programs.GenerateJuliaPrograms.compile_block`

— MethodCompile a morphism expression into a block of Julia code.

`Catlab.Programs.GenerateJuliaPrograms.compile_expr`

— MethodCompile a morphism expression into a Julia function expression.

`Catlab.Programs.GenerateJuliaPrograms.evaluate`

— MethodEvaluate 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`

.

`Catlab.Programs.GenerateJuliaPrograms.generator_expr`

— MethodGenerate Julia expression for evaluation of morphism generator.

`Catlab.Programs.GenerateJuliaPrograms.genvar`

— MethodGenerate a fresh variable (symbol).

This is basically `gensym`

with local, not global, symbol counting.

`Catlab.Programs.GenerateJuliaPrograms.input_exprs`

— MethodGenerate expressions for inputs to Julia code.

`Catlab.Programs.GenerateJuliaPrograms.make_return_value`

— MethodReturn a zero, one, or more values, following Julia conventions.

`Catlab.Programs.GenerateJuliaPrograms.to_function_expr`

— MethodConvert a block of Julia code into a Julia function expression.

`GATlab.Syntax.GATs.compile`

— MethodCompile a morphism expression into a Julia function.

`Catlab.Graphs.NamedGraphs`

— ModuleExtends 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.

`Catlab.Graphs.NamedGraphs.AbstractNamedGraph`

— TypeAbstract type for graph with named vertices and edges.

`Catlab.Graphs.NamedGraphs.NamedGraph`

— TypeGraph with named vertices and edges.

`Catlab.Graphs.NamedGraphs.edge_name`

— MethodName of an edge in a graph.

By default, the name of an edge is its ID.

`Catlab.Graphs.NamedGraphs.edge_named`

— MethodGet edge in graph with given name.

`Catlab.Graphs.NamedGraphs.has_edge_names`

— MethodWhether a graph has edge names distinct from its edge IDs.

`Catlab.Graphs.NamedGraphs.has_vertex_names`

— MethodWhether a graph has vertex names distinct from its vertex IDs.

`Catlab.Graphs.NamedGraphs.vertex_name`

— MethodName of a vertex in a graph.

By default, the name of a vertex is its ID.

`Catlab.Graphs.NamedGraphs.vertex_named`

— MethodGet vertex in graph with given name.

`Catlab.Theories.FreeCocartesianCategory`

— ModuleSyntax 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.

`Catlab.ACSetsGATsInterop`

— ModuleCompatibility module that integrates ACSets with GATs.

`Catlab.CategoricalAlgebra.Permutations`

— ModuleComputing with permutations: the computer algebra of the symmetric group.

`Catlab.CategoricalAlgebra.Permutations.adjacent_transpositions_by_bubble_sort!`

— MethodDecompose 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!`

.

`Catlab.CategoricalAlgebra.Permutations.adjacent_transpositions_by_insertion_sort!`

— MethodDecompose 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!`

.

`Catlab.CategoricalAlgebra.Permutations.cycles`

— MethodDecompose a permutation into its cycles.

Returns a vector of vectors, the cycles of the permutation.

`Catlab.CategoricalAlgebra.Permutations.permutation_to_expr`

— MethodConvert a typed permutation into a morphism expression.

Warning: The morphism expression is not simplified.

`Catlab.Theories.ThBicategoryRelations`

— ModuleTheory of *bicategories of relations*

TODO: The 2-morphisms are missing.

References:

- Carboni & Walters, 1987, "Cartesian bicategories I"
- Walters, 2009, blog post, "Categorical algebras of relations", http://rfcwalters.blogspot.com/2009/10/categorical-algebras-of-relations.html

`Catlab.Theories.ThSymmetricMonoidalDoubleCategory`

— ModuleTheory 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.