These exported modules implement graphs as specified in Lawvere, Rosebrugh: Sets for mathematics.

Compact representation of the graph is:

• digraphs: left and right actions of a three-element non-trivial monoid on endomorphisms of the two-element set
• graphs : left and right actions of a four-element non-trivial monoid on endomorphisms of the two-element set

The graph representation is based on just single set which contains both vertices and edges. This means we have operation, isVertexM, for determining whether an element of the set is a vertex or an edge.

For non-mathematicians, think of a database table with three or four fields, where fields are called

• id
• source
• target
• invert

The invert field is not present in a digraph.

The monoid structure provides basic properties of source and target actions.

source . target == source

target . source == target

source . source == source

target . target == target

Think of the actions in terms of state machines, from any element, we can always ask for source and target, but above equations mean that for vertices,

isVertex v => source v == v

isVertex v => target v == v