{"id":280,"date":"2016-12-05T16:26:10","date_gmt":"2016-12-05T16:26:10","guid":{"rendered":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/?p=280"},"modified":"2017-11-16T10:56:26","modified_gmt":"2017-11-16T10:56:26","slug":"an-algebra-of-graphs","status":"publish","type":"post","link":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/an-algebra-of-graphs\/","title":{"rendered":"An algebra of graphs"},"content":{"rendered":"

Graph theory<\/a> is my favourite topic in mathematics and computing science and in this blog post I’ll introduce an algebra of graphs<\/em>\u00a0that I’ve been working on for a while. The algebra has become my go-to tool\u00a0for manipulating graphs and I hope you will find it useful too.<\/p>\n

The roots of this work\u00a0can be traced back to my CONCUR’09 conference submission\u00a0that was rightly rejected. I subsequently published a few application-specific papers gradually improving my understanding of the algebra. The most comprehensive description can be found\u00a0in ACM TECS<\/a> (a preprint is available here<\/a>). Here I’ll give a general introduction to the simplest version of the algebra of graphs and show how it can be implemented in Haskell.<\/p>\n

Update:<\/strong>\u00a0This series of blog posts was published as a functional pearl<\/a> at the Haskell Symposium 2017.<\/p>\n

<\/p>\n

Constructing\u00a0graphs<\/h3>\n

Let G<\/strong> be a set of graphs whose vertices come from a fixed universe. As an example, we can think of graphs whose vertices are\u00a0positive integers.\u00a0A graph g \u2208 G can be represented by a pair (V, E)<\/strong> where V is the set of its\u00a0vertices and E\u00a0\u2286 V \u00d7 V is the set of its edges.<\/p>\n

The simplest possible graph is the empty<\/em> graph. I\u00a0will be denoting it by\u00a0\u03b5<\/strong> in formulas and by empty<\/code><\/strong> in Haskell code. Hence, \u03b5 = (\u2205, \u2205) and \u03b5\u00a0\u2208 G.<\/p>\n

A graph with a single vertex v<\/em> will be\u00a0denoted simply by v<\/strong>. For example, 1\u00a0\u2208 G is a graph with a single vertex 1, that is ({1}, \u2205). In Haskell I’ll use\u00a0vertex<\/code><\/strong>\u00a0to lift a given vertex to the type of graphs.<\/p>\n

To construct bigger\u00a0graphs from the above primitives I’ll use two binary operators\u00a0overlay<\/em> and connect<\/em>, denoted by\u00a0+ and\u00a0\u2192, respectively.\u00a0The overlay + of two graphs is\u00a0defined as:<\/p>\n

(V1<\/sub>, E1<\/sub>) + (V2<\/sub>, E2<\/sub>) = (V1<\/sub> \u222a V2<\/sub>, E1<\/sub> \u222a E2<\/sub>)<\/p>\n

In words, the overlay of two graphs is simply the union of their vertices and edges.\u00a0The definition of connect \u2192\u00a0is similar:<\/p>\n

(V1<\/sub>, E1<\/sub>) \u2192 (V2<\/sub>, E2<\/sub>) = (V1<\/sub> \u222a V2<\/sub>, E1<\/sub> \u222a E2<\/sub>\u00a0\u222a V1<\/sub> \u00d7 V2<\/sub>)<\/p>\n

The difference is that when we connect two graphs, we add an edge from each vertex in the left argument\u00a0to each vertex in the right argument. Here are a few examples:<\/p>\n