Graphs and C-sets I: What is a graph?

Graphs

For a category theorist, a graph G consists of two sets, a vertex set G(V) and an edge set G(E), together with two functions G(\operatorname{src}), G(\operatorname{tgt}): G(E) \to G(V). Every edge e \in G(E) in the graph has a source vertex e \cdot \operatorname{src}:= G(\operatorname{src})(e) and a target vertex e \cdot \operatorname{tgt}:= G(\operatorname{tgt})(e). Thus, a graph is directed, may have multiple edges between two vertices, and may have loops, making it what a graph theorist would call a “multidigraph.” Moreover, the edges are explicitly identified as the elements of an edge set, rather than being pairs of vertices. While this may seem strange, we will gradually see that it has many advantages.

In Catlab, the definition of a graph is captured by the schema:

using Catlab.CategoricalAlgebra

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

The names Ob and Hom are short for “object” and “morphism,” interpreted as sets and functions in this context. Having defined the schema for graphs, the module Graphs in Catlab creates a Julia data type for graphs like this:²

@acset_type Graph(SchGraph, index=[:src,:tgt])

Let’s create a graph using the generated interface.

using Catlab.CategoricalAlgebra
using Catlab.Graphs, Catlab.Graphics

g = Graph()
add_parts!(g, :V, 3)
add_parts!(g, :E, 4, src=[1,2,2,3], tgt=[2,3,3,3])
g

to_graphviz(g)

to_graphviz(g, node_labels=true, edge_labels=true)

As the visualization shows, edges 2, 3, and 4 are all incident to vertex 3 via the target map:

incident(g, 3, :tgt)

3-element Vector{Int64}:
 2
 3
 4

As a convenience, the Graphs module wraps the generated methods with an interface inspired by Graphs.jl, defining methods such as nv, ne, add_vertex!, add_edge!, inneighbors, and outneighbors. For example, the following code reduces to the code constructing the graph g above:

g = Graph()
add_vertices!(g, 3)
add_edges!(g, [1,2,2,3], [2,3,3,3])

Graphs as C-sets

Graphs are an example of a class of structures called \mathsf{C}-sets. This was just illustrated by code and will now be explained mathematically.

\mathsf{C}-sets are defined relative to a small category \mathsf{C}. In this context, the category \mathsf{C} is interpreted as a schema, describing the kinds of parts in the structure and the subpart relations between them. For example, the schema for graphs is the category \mathsf{Sch}(\mathsf{Graph}) presented by:

You may be used to thinking about large categories, such as the category \mathsf{Set} of all sets and functions, but the category \mathsf{Sch}(\mathsf{Graph}) is very small! It has exactly two objects, E and V, and two non-identity morphisms, \operatorname{src}: E \to V and \operatorname{tgt}: E \to V. The interpretation is that there are two kinds of parts, of type V and E. Parts of type V have no subparts, while parts of type E have two subparts of type V, called \operatorname{src} and \operatorname{tgt}.

Given a small category \mathsf{C}, a \mathsf{C}-set is a functor X: \mathsf{C} \to \mathsf{Set}.³ A \mathsf{C}-set X therefore consists of, for every object c \in \mathsf{C}, a set X(c), and for every morphism f: c \to d in \mathsf{C}, a function X(f): X(c) \to X(d), subject to the functoriality axioms. In particular, when \mathsf{C} = \mathsf{Sch}(\mathsf{Graph}), a \mathsf{C}-set is exactly a graph as previously defined.

Symmetric graphs

The formalism of \mathsf{C}-sets would be rather heavy if all we wanted to do was define a graph, but many other structures, graph-like and otherwise, can be defined as \mathsf{C}-sets (Spivak 2009). As a second example, we consider symmetric graphs, closely related to what graph theorists call “(undirected) multigraphs.”

The schema for symmetric graphs is the category \mathsf{Sch}(\mathsf{SGraph}) generated by the objects and morphisms

subject to the equations expressed by the commutative diagram

or equivalently the equations

\operatorname{inv}\operatorname{⨟}\operatorname{src}= \operatorname{tgt}, \qquad \operatorname{inv}\operatorname{⨟}\operatorname{tgt}= \operatorname{src}, \qquad \operatorname{inv}^2 = 1_E.

A symmetric graph is a \mathsf{Sch}(\mathsf{SGraph})-set. Unpacking this, a symmetric graph is a graph G together with an orientation-reversing involution on edges, G(\operatorname{inv}): G(E) \to G(E), which in turn means that

e \cdot \operatorname{inv}\cdot \operatorname{src}= e \cdot \operatorname{tgt}, \qquad e \cdot \operatorname{inv}\cdot \operatorname{tgt}= e \cdot \operatorname{src}, \qquad e \cdot \operatorname{inv}\cdot \operatorname{inv}= e, \qquad \forall e \in G(E).

Intuitively, a symmetric graph assigns every edge to another edge in the opposite direction, effectively making the edges undirected.

In Catlab, the schema for symmetric graphs is defined by extending the schema for graphs, and then the new schema is used to create a Julia data type for symmetric graphs:⁴

@present SchSymmetricGraph <: SchGraph begin
  inv::Hom(E,E)

  compose(inv,src) == tgt
  compose(inv,tgt) == src
  compose(inv,inv) == id(E)
end

@acset_type SymmetricGraph(SchSymmetricGraph, index=[:src])

Similarly to graphs, the Catlab Graphs module provides a convenient Graphs.jl-style interface for symmetric graphs. The interface takes care of adding edges in pairs related by the involution, allowing the symmetric graphs to be treated as undirected graphs. For example, the symmetric 4-cycle is constructed like this:

g = SymmetricGraph()
add_vertices!(g, 4)
add_edges!(g, [1,2,3,4], [2,3,4,1])
g

Symmetric graphs are visualized as undirected graphs, where the drawn edges are labeled by directed edge pairs.

 to_graphviz(g, prog="circo")

to_graphviz(g, prog="circo", node_labels=true, edge_labels=true)

In the next installment we’ll see how more exotic notions of graph are realized as \mathsf{C}-sets and data structures in Catlab.