An Algebra For Graph Structures

Traditionally when creating a graph, all the vertices and nodes will need to be manually listed. Sometimes there are clever tricks or partial functions to improve readability, but in general it can be a clumsy process.

const nodes ['a' 'b', 'c'];
const edges = [
  ['a', 'b'],
  ['b', 'c'],  ['b', 'b'],  ['b', 'a'],
  ['c', 'a'],  ['c', 'c'],
];

The resultant graph from the above definition

There’s another more compact way to describe a graph. One of the most exciting graph packages that can simplify everything is Alga and its ports (available in Typescript, F#, Haskell, Scala, and probably more in the future). The core idea behind this is to express a graph with algebraic rules, not a listing of all edges.

There are two key operations:

Permits the merging of graphs without changing edges

Creates edges between all nodes in two graphs

Now complex structures can be created from algebraic rules, rather than a manual listing of every individual edge and node. Even complex graphs types like De Bruijn Graphs (used in tasks like genome sequencing) can be modeled with these simple operators.

One major benefit here is the ability to create graph theorems in every programming language, able to solve many problems with common ideas across disciplines and domains. The original paper by Andrey Mokhov entitled “Algebraic Graphs with Class (Functional Pearl)” outlines pages of possible ways to create useful structures, and the short 20 minute video below provides even more examples of possibilities to simplify models.

While the technique is still in its early stages, I’m very optimistic about the future of this approach and the way graphs are described. This opens new doorways and should prove to be exciting for anyone who like being on the ground floor of exciting new ideas.