[zodiac]

I'm curious about graph algorithms that are "higher order" than what the article describes - e.g. how does Datalog encode the fact that two graphs (given as two relation sets) are isomorphic? How do I write a graph isomorphism algorithm in Datalog, or e.g. enumerate all graphs that have 6 vertices?

[philzook]

This perhaps isn't what you're asking about, but a very useful thing to realize is that datalog or sql are quite useful for subgraph isomorphims aka graph patterm matching. One can compile the graph you're looking for into the rhs/query of a rule. This is probably only wise for small pattern graphs in large search target graphs.

There's interesting depth here in that constraint satisfaction problems can be modeled as finding homomorphisms (I associated this line of thought with Moshe Vardi and others). Big patterns into small targets tend to look like coloring problems or SAT, whereas small patterns into big targets look like queries. Isomorphism is right in the middle.

   tringle(X,Y,Z) :- edge(X,Y), edge(Y,Z), edge(Z,X).
   square(X,Y,Z,W) :- edge(X,Y), edge(Y,Z), edge(Z,W), edge(W,X).