sn0wleopard

> Indeed, I did say that it was a monad and not a `Monad`; math doesn't suffer from these implementation constraints. :-)

Ah, I see :-) Indeed, from the mathematical standpoint we can both inject a vertex into the graph type with `vertex`, and flatten a graph whose nodes are graphs (the monad `join`, not to be confused with graph `join` operation that I'm using). I haven't given this much thought before, thanks for noticing this.

> Oh, that makes more sense. Maybe it's worth even making just a throwaway remark to that effect?

I've added the following remark: "we will call such cliques covering the whole universe complete graphs". Hopefully this helps to clarify the naming convention.

> By the way, your code doesn't seem to give any way of producing inhabitants of `Vertex g`.

In fully polymorphic code (like clique) you indeed can't produce new inhabitants, or do anything else with the values of type `Vertex g`. However, if you know something about `Vertex g` then you can do certain things. For example, if we know that the type of vertices has `Ord` instance then we can compare them (as we do in `Relation`). And in very concrete code, e.g. operating on `Basic Int` values, you can create new inhabitants freely -- any number will do.

> Also, am I wrong to read `vertex` as a kind of `return`?

It is indeed very much like `return` or `pure`! We use it to inject a type into a sort of container type, in this case, into a graph type.

> I hope that I am not wrong to think that graphs should serve as just as good instances of monads as lists, if not better

Many `Graph` instances are `Monad`s. For example, `Basic` is a `Monad` (and many other things too). But on the other hand `Relation` is not a `Monad`, because it imposes the `Ord` constraint on the underlying type (and Haskell monads are not allowed that).

> While we're talking: thanks for this article; I enjoyed it a lot.

Thank you! I didn't expect so much interest to it, so I'm a bit overwhelmed to be honest :)

> My one suggestion is that I think that what you call a "clique" is usually called a "complete graph", with "clique" (implicitly, in G) reserved for subgraphs of G that happen to be complete.

Thanks, indeed "clique" may be not the best name... I decided to use it, because I would like to reserve "complete graph" to mean something like `clique [1..]` i.e. the complete graph on the whole universe. If we look from this perspective then something like `clique [1..10]` may look like a clique within some bigger graph. Anyway, I admit this may be confusing.

Thanks LolWolf! You mentioned a few interesting ideas about monotonicity/fixed-point theorems & computability/hardness and I'd very curious to know if you come up with anything on these fronts -- please drop me an email if you do!

Thank you for clarifying. I see how your construction works now.

JadeNB: This works but I believe only in the case with undirected graphs and if the graphs being connected do not have common vertices.

So, indeed there is a sort of de Morgan law:

a -- b = !(!a + !b) where ! is the graph edge-complement, a and b do not have common vertices, and -- is a commutative version of ->.

(Responding so late, because I was also "submitting too fast"!)

rjtobin, Sorry I don't understand what happens if the two graphs have common vertices?

For example, in the algebra I described, you can do 1 -> (1 + 2) and this represents a graph with vertices {1,2} and two edges (1,1) and (1,2). How would that work with your matrix join?

solidangle: Indeed, there are a lot of graph algebras out there, and I looked at many of them, including the Kleene Algebras. So far I haven't found any algebra with the decomposition axiom, but if you come across one, please let me know!

Why do I need the decomposition axiom? I haven't actually provided a motivation for it (or why I defined overlay and connect the way I did). So, here it is: just like LolWolf, I wanted to represent arbitrary graphs and only graphs using expressions, so expression x -> y -> z should be just a graph, and therefore I should be able to construct it from smaller pieces. But what should these pieces be? We can't make it equal to x -> y + y -> z because then our definition of -> would be partial, since it's not always possible to find 'the last node' (in this case y) that we need to connect to z (e.g. the left-hand side may be a cycle). The only choice that seems to work is to connect all vertices on the left-hand side to all vertices on the right hand side, which leads directly to the decomposition axiom.

LolWolf, thank you very much for 'defending' the algebra much better than I could possibly have defended it myself :-)

Just to add: I don't understand why we should compare the algebra and the matrix encoding suggested above. The latter is just one possible implementation (a model) of the former. It's a good, useful model. But the point of having an algebra is that we can abstract of details of particular implementation and instead focus on the laws that all such implementations satisfy. Sometimes these laws can be interesting by themselves (at least they are interesting to me).

I'm sad that you found my blog post snobbish. If you point out specifically which part you can't stand I'll see if I can make it better. But I'm afraid I can't remove the algebra part, as there will be nothing left!

Haskell is certainly not essential to understand or explain the algebra, but having an implementation (in any language!) helps to play with the algebra and experiment with possible models. I am a beginner in Haskell, and that's my current language of choice, as I'm keen to get better at it.

To respond to your comment about matrices: I'm pretty sure one can come up with a matrix-based model (instance) of the algebra. So, no arguments here. In fact, I'd be very interested to see such an instance, to add it to other instances I've found.

I'm the author of the blog post -- thank you for your comment! I was wondering whether anyone would be interested in a different version of the algebra that modells hypergraphs with k-edges. For example, you can change the decomposition axiom to: a.b.c.d = a.b.c + a.b.d + a.c.d + b.c.d, which allows you to have an algebraic structure with nodes, 2-edges (pairs of nodes), and 3-edges (triples of nodes). I can write about this in the following blog post if you are interested. (And I'd love to hear further thoughts from you on the connection to the boundary operator -- do get in touch by email!)

EDIT: Used dots (.) for the connect operator not to mess up with formatting.