1. 20

The paper presents a minimalistic and elegant approach to working with graphs in Haskell. It is built on a rigorous mathematical foundation — an algebra of graphs — that allows us to apply equational reasoning for proving the correctness of graph transformation algorithms. Algebraic graphs let us avoid partial functions typically caused by ‘malformed graphs’ that contain an edge referring to anon-existent vertex. This helps to liberate APIs of existing graph libraries from partial functions.The algebra of graphs can represent directed, undirected, reflexive and transitive graphs, as well as hypergraphs, by appropriately choosing the set of underlying axioms. The flexibility of the approach is demonstrated by developing a library for constructing and transforming polymorphic graphs


  2. 3

    Of note, from the last page:

    This paper has not addressed edge-labelled graphs. In particular, there is no known extension of the presented algebra characterising graphs with arbitrary vertex and edge labels. …

    … However, Mokhov and Khomenko [2014] give an algebraic characterisation for graphs labelled with Boolean functions, which can be generalised to labels that form a semiring. We found that one can represent edge-labelled graphs by functions from labels to graphs.

    1. 4

      Neuron (a Zettelkasten note-taking software, based on Markdown files) uses an algebraic graph library (written by Mokohv in Haskell) that supports edge-labels, but neuron required vertex and edge labelled graph – edge-label for storing link context (like in Roam), and vertex-label for storing the note metadata. Here’s some background discussion on this for anyone curious: https://github.com/snowleopard/alga/issues/183

    2. 2

      Efficiency is a major concern. From the last page:

      There are no known efficient implementations of fundamental graph algorithms, such as depth-first search, that work directly on the algebraic core. Therefore, we need to translate core expressions to conventional graph representations, such as adjacency lists, and utilise existing graph libraries, which may be suboptimal for certain algorithmic problems.