Categorical algebra

Free diagrams in a category.

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

Cospan of morphisms in a category.

A common special case of Multicospan. See also Span.

Decorate Cospan of morphisms for representing open networks.

Discrete diagram: a diagram whose only morphisms are identities.

Abstract type for free diagram of fixed shape.

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

Multispan of morphisms in a category.

A multispan is like a Span except that it may have a number of legs different than two. A colimit of this shape is a pushout.

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

Pair of parallel morphisms in a category.

A common special case of ParallelMorphisms.

Span of morphims in a category.

A common special case of Multispan. See also Cospan.

Limits and colimits in a category.

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

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

Colimit in a category.

Limit in a category.

Colimit of a diagram.

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

See also: limit

Compute pullback as composite of product and equalizer.

Compute pushout as composite of coproduct and coequalizer.

Limit of a diagram.

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

See also: colimit

Pullback of a pair of morphisms with common codomain.

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

Pushout of a pair of morphisms with common domain.

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

Universal property of (co)limits.

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

See also: limit, colimit.

Copairing of morphisms: universal property of coproducts/pushouts.

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

Coproduct of objects.

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

Unique morphism out of an initial object.

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

Unique morphism into a terminal object.

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

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

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

Initial object.

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

Pairing of morphisms: universal property of products/pullbacks.

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

Product of objects.

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

Terminal object.

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

Computing in the category of finite sets and functions.

Function between finite sets.

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

Function in FinSet defined by a callable Julia object.

To be evaluated lazily unless forced.

Function in FinSet represented explicitly by a vector.

The elements of the set are assumed to be {1,...,n}.

Finite set.

This generic type encompasses the category FinSet of finite sets and functions, through types FinSet{S} where S <: AbstractSet, as well as the skeleton of this category, through the type FinSet{Int}. In the latter case, the object FinSet(n) represents the set {1,...,n}.

Force evaluation of lazy function or relation.

Computing in the category of finite sets and relations, and its skeleton.

The rig of booleans.

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

Object in the category of finite sets and relations.

See also: FinSet.

Binary relation between finite sets.

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

Relation in FinRel defined by a callable Julia object.

Relation in FinRel represented by a boolean matrix.

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

Computing with permutations: the computer algebra of the symmetric group.

Decompose permutation into adjacent transpositions using bubble sort.

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

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

See also: decompose_permutation_by_insertion_sort!

Decompose permutation into adjacent transpositions using insertion sort.

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

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

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

See also: decompose_permutation_by_bubble_sort!

Convert a typed permutation into a morphism expression.

Warning: The morphism expression is not simplified.

Generate data structure for C-sets (copreshaves) and attributed C-sets.

Alias for the data type AttributedCSet.

Alias for the abstract type AbstractAttributedCSet.

Abstract type for C-sets.

The special case of AbstractAttributedCSet with no data attributes.

Data type for C-sets.

The special case of AttributedCSet with no data attributes.

Generate a data type for attributed C-sets from a schema.

In addition to the schema, you can specify which morphisms and data attributes are (uniquely) indexed using the keyword argument index (or unique_index). By default, no morphisms or data attributes are indexed.

See also: AbstractACSetType.

Generate an abstract type for attributed C-sets from a schema.

To generate a concrete type, use ACSetType.

Generate an abstract type for C-sets from a presentation of a category C.

To generate a concrete type, use CSetType.

Generate a data type for C-sets from a presentation of a category C.

In addition to the category, you can specify which morphisms are (uniquely) indexed using the keyword argument index (or unique_index). By default, no morphisms are indexed.

See also: AbstractCSetType.

Add part of given type to C-set, optionally setting its subparts.

Returns the ID of the added part.

See also: add_parts!.

Add parts of given type to C-set, optionally setting their subparts.

Returns the range of IDs for the added parts.

See also: add_part!.

Copy parts from one C-set into another.

All subparts among the selected parts, including any attached data, are preserved. Thus, if the selected parts form a sub-C-set, then the whole sub-C-set is preserved. On the other hand, if the selected parts do not form a sub-C-set, then some copied parts will have undefined subparts.

Whether a C-set has a part with the given name.

Whether a C-set has a subpart with the given name.

Get superparts incident to part in C-set.

Number of parts of given type in a C-set.

Mutate subpart of a part in a C-set.

Both single and vectorized assignment are supported.

See also: set_subparts!.

Mutate subparts of a part in a C-set.

Both single and vectorized assignment are supported.

See also: set_subpart!.

Get subpart of part in C-set.

Both single and vectorized access are supported.

Data structures for graphs, based on C-sets.

Support for graphs, symmetric graphs, and property graphs.

Abstract type for graph with properties.

Concrete types are PropertyGraph and SymmetricPropertyGraph.

Graph with properties.

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

See also: SymmetricPropertyGraph.

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