{"id":393,"date":"2016-12-13T01:29:10","date_gmt":"2016-12-13T01:29:10","guid":{"rendered":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/?p=393"},"modified":"2017-11-16T10:57:29","modified_gmt":"2017-11-16T10:57:29","slug":"graphs-a-la-carte","status":"publish","type":"post","link":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/graphs-a-la-carte\/","title":{"rendered":"Graphs \u00e0 la carte"},"content":{"rendered":"

I received an overwhelming response to the\u00a0introductory blog post<\/a>\u00a0about\u00a0the algebra of graphs; thank you all for your remarks, questions and suggestions! In the second part of the series I will\u00a0show that\u00a0the algebra is not restricted only to directed graphs, but can be extended to axiomatically represent\u00a0undirected graphs, reachability and dependency graphs (i.e. preorders and partial orders), their various combinations, and even hypergraphs.<\/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

Why algebra?<\/h4>\n

Before we continue, I’d like to note\u00a0that any data structure for representing graphs (e.g. an edgelist, matrix-based representations, inductive graphs from the fgl library<\/a>,\u00a0GHC’s standard Data.Graph<\/code><\/strong><\/a>, etc.) can satisfy the axioms of the algebra with appropriate definitions\u00a0of empty<\/code><\/strong>, vertex<\/code><\/strong>, overlay<\/code> <\/strong>and connect<\/code><\/strong>, and I do not intend\u00a0to compare these implementations\u00a0against each other. I’m more interested in implementation-independent (polymorphic) functions that we\u00a0can\u00a0write and reuse, and in proving properties\u00a0of these functions using the laws of the algebra.\u00a0That’s why I think the algebra is worth studying.<\/p>\n

As a warm-up exercise, let’s\u00a0look at\u00a0a few more examples of such polymorphic graph functions. One of the threads<\/a>\u00a0in the reddit discussion was about the path graph<\/em> P4<\/sub><\/strong>: i.e. the graph with 4 vertices connected in a chain. Here is a function that can construct such path graphs<\/a> on a given list of vertices:<\/p>\n

path<\/span> ::<\/span> Graph<\/span> g<\/span> =><\/span> [Vertex<\/span> g<\/span>] -><\/span> g<\/span>\r\npath []<\/span>  =<\/span> empty\r\npath [x] =<\/span> vertex x\r\npath xs  =<\/span> fromEdgeList $<\/span> zip<\/span> xs (tail<\/span> xs)\r\n\r\np4<\/span> ::<\/span> (Graph<\/span> g<\/span>, Vertex<\/span> g<\/span> ~ Char<\/span>) =><\/span> g<\/span>\r\np4 =<\/span> path ['a'<\/span>,<\/span> 'b'<\/span>,<\/span> 'c'<\/span>,<\/span> 'd'<\/span>]\r\n<\/pre>\n
Note that graph\u00a0p4<\/code><\/strong> is also polymorphic: we\u00a0haven’t\u00a0committed to any particular data representation, but we know that the vertices of p4<\/code><\/strong> have type Char<\/code><\/strong>.<\/p>\n
If we connect the last vertex of a path to the first one, we get a circuit graph<\/em>, or a cycle<\/a>. Let’s express\u00a0this in terms of the path<\/code><\/strong> function:<\/p>\n
circuit<\/span> ::<\/span> Graph<\/span> g<\/span> =><\/span> [Vertex<\/span> g<\/span>] -><\/span> g<\/span>\r\ncircuit []<\/span>     =<\/span> empty\r\ncircuit (x:<\/span>xs) =<\/span> path $<\/span> [x] ++<\/span> xs ++<\/span> [x]\r\n\r\npentagon<\/span> ::<\/span> (Graph<\/span> g<\/span>, Vertex<\/span> g<\/span> ~ Int<\/span>) =><\/span> g<\/span>\r\npentagon =<\/span> circuit [1<\/span>..<\/span>5<\/span>]\r\n<\/pre>\n
From the definition we expect that a path is a subgraph of the corresponding circuit. Can we express this property in the algebra? Yes! It’s fairly standard to define a\u00a0\u2264 b as a + b = b for idempotent + and it turns out that this definition corresponds to the subgraph relation<\/em> on graphs:<\/p>\n
isSubgraphOf<\/span> ::<\/span> (Graph<\/span> g<\/span>, Eq<\/span> g<\/span>) =><\/span> g<\/span> -><\/span> g<\/span> -><\/span> Bool<\/span>\r\nisSubgraphOf x y =<\/span> overlay x y ==<\/span> y\r\n<\/pre>\n
We can\u00a0use QuickCheck to test that our implementation satisfies the property:<\/p>\n
\u03bb><\/span> quickCheck $<\/span> \\<\/span>xs -><\/span> path xs `isSubgraphOf`<\/span> (circuit xs ::<\/span> Basic<\/span> Int<\/span>)\r\n+++<\/span> OK<\/span>,<\/span> passed 100<\/span> tests.<\/span>\r\n<\/pre>\n
QuickCheck\u00a0can only test the\u00a0property w.r.t. a particular instance, in this case we chose Basic Int<\/code><\/strong>, but using the algebra we can prove that it holds for all law-abiding instances of Graph<\/code><\/strong> (I leave this as an exercise for the reader).<\/p>\n
As a final example, we will implement\u00a0Cartesian graph product<\/a>, usually denoted as\u00a0G\u00a0\"\\square\u00a0H, where the vertex set is VG<\/sub>\u00a0\u00d7 VH<\/sub> and vertex\u00a0(x, y)\u00a0is connected to vertex\u00a0(x’, y’)\u00a0if either x = x’ and y is connected to y’ in H, or y = y’ and x is connected to x’ in G:<\/p>\n
box<\/span> ::<\/span> (Functor<\/span> f<\/span>, Foldable<\/span> f<\/span>, Graph<\/span> (f<\/span> (a<\/span>,b<\/span>))) =><\/span> f<\/span> a<\/span> -><\/span> f<\/span> b<\/span> -><\/span> f<\/span> (a<\/span>,b<\/span>)\r\nbox x y =<\/span> foldr<\/span> overlay empty $<\/span> xs ++<\/span> ys\r\n  where<\/span>\r\n    xs =<\/span> map<\/span> (\\<\/span>b -><\/span> fmap<\/span> (,<\/span>b) x) $<\/span> toList y\r\n    ys =<\/span> map<\/span> (\\<\/span>a -><\/span> fmap<\/span> (a,<\/span>) y) $<\/span> toList x\r\n<\/pre>\n
The Cartesian product G\u00a0\"\\square\u00a0H\u00a0is assembled\u00a0by creating |VH<\/sub>| copies of graph G and overlaying them with |VG<\/sub>| copies of graph H. We get access to the list of graph vertices using toList<\/code><\/strong> from the Foldable<\/code><\/strong> instance and turn vertices of original graphs into pairs of vertices by\u00a0fmap<\/code><\/strong>\u00a0from the Functor<\/code><\/strong> instance.<\/p>\n
As you can see, the code is still implementation-independent, although it requires that the graph data type is a Functor<\/code><\/strong> and a Foldable<\/code><\/strong>.\u00a0Just like lists, trees and other containers, most graph data structures\u00a0have Functor<\/code><\/strong>, Foldable<\/code><\/strong>, Applicative<\/code><\/strong> and Monad<\/code><\/strong> instances (e.g.\u00a0our Basic<\/code><\/strong>\u00a0data type has them all). Here is how <\/code>pentagon `box` p4 <\/code><\/strong>looks:<\/p>\n
\"Cartesian<\/a><\/p>\n
(A side note: the type signature of box<\/code><\/strong>\u00a0reminds me of this blog post<\/a> by Edward Yang and makes me wonder if Functor<\/code><\/strong>, Foldable<\/code><\/strong>\u00a0plus idempotent and commutative\u00a0Monoid<\/code><\/strong> together imply Monoidal<\/code><\/strong>, as it seems that I only had to use empty<\/code><\/strong> and overlay<\/code><\/strong> from the Graph<\/code><\/strong> type class. This seems odd.)<\/p>\n
Undirected graphs<\/h4>\n
As I hinted in the previous blog post,\u00a0to switch from directed to undirected graphs it is sufficient to add the axiom of commutativity for the connect<\/em> operator.\u00a0For undirected graphs it makes sense to denote connect<\/em>\u00a0by \u2194 or \u2014, hence:<\/p>\n