Graph Data Structure with Datalog QL

Since I started learning Common Lisp in late 2016 I have been working on several iterations of my own generative art framework. The first library was named snek. Some time later, snek was rewritten and renamed as weir. The most essential parts of these frameworks were a graph data structure, utilities for dealing with (primarily 2d/3d) vectors, as well as randomness.

After getting more comfortable with Common Lisp macros, and armed with some suggestions from my friend Jack Rusher, I started to rewrite the vector part of weir. In order to use the new vectors, weir was rewritten yet again.

Despite all the rewrites, some version of all this code has been used to make most of the art I have made in the period since then.

For the most part I have been pretty happy with it as well. But there has also been a number of things that didn't work very well. In particular, the graph had a number of issues that kept causing headaches.

As a result of this—ever so slight—obsession with building my own tools for things, I have once again committed programming crimes. This time I have written a new graph library called cl-grph. Writing a lot of kind of terrible code can be quite educational, and I have tried to improve on some of the mistakes of my (not so distant) past.

Immutable Data Structures

As many people have learned before me, dealing with state can be rather tedious. Mutating state even more so. Particularly when you have a series of complicated things you want to alter at the same time. Frequently without knowing up front whether it will work or not.

To improve on this I decided to use immutable data structures. This makes it trivial to access the state as it was before you started making any changes. If you discover any conflicts along the way, rolling back is simply a matter of not keeping the reference to the mutated state. Transactions are now almost trivial.

Immutable data structures have a few other neat properties as well. What immediately comes to mind is that they make it a lot easier to store multiple states of a structure as it is growing. Among other things this can be used for animation and debugging. Not to mention that it reduces the probability of causing unintended changes when sharing data from inside the library with the outside environment.

Datalog Compiler

Unlike my previous graph structures, the new graph is directed. This creates a few complications, but it is also extremely useful. It is now possible to represent much more complex information. Where previously I could only easily represent that two vertices are associated, I can now model detailed hierarchies, trees and transport networks. Which will certainly be useful.

Which brings me to another major difference. In the new graph structure the edge properties are an integral part of the data structure. Not just an afterthought. This makes it more seamless to propagate edge properties when manipulating the datastructure.

To utilise the graph structure more easily I have implemented a Datalog query compiler. Datalog is declarative logic programming language, with its roots in Prolog. I quite recommend looking into Datalog in more detail on your own. But I will give a small introduction to how my implementation works, using the following graph as an example.

Considering the example graph, we can write a Datalog query to return every edge:

; g is the current graph
(qry g :select (?x ?y)
       :where (?x _ ?y))
;;
;; ((0 7) (0 8) (1 2) (1 8)
;;  (2 7) (3 4) (3 6) (4 8)
;;  (5 7) (5 8) (6 7))

In this query we are effectively saying "select every pair of vertices (?x ?y), where vertex ?x has any (_) edge pointing at vertex ?y". The :where part must always contain at least one "triplet" like you see above. It can contain more complex expressions, as we will illustrate shortly.

Notice that the edges have direction, so (0 7) is distinct from (7 0). Also note that it is possible to have both directions of an edge present in the graph at the same time. We avoid that here for practical reasons. Likewise, it is possible to have conflicting properties on edges.

To select the combination of every edge, and its corresponding properties, we can do the following:

(qry g :select (?x ?p ?y)
       :where (?x ?p ?y))
;;
;; The result is sorted by property and
;; formatted slightly for readability:
;; ((6 :black 7) (5 :black 8)  (5 :black 7)
;;  (4 :black 8) (3 :black 6)  (3 :black 4)

;;  (5 :bold 8)  (5 :bold 7)   (2 :bold 7)
;;  (1 :bold 8)  (1 :bold 2)

;;  (6 :dots 7)  (5 :dots 8)  (5 :dots 7)
;;  (4 :dots 8)  (3 :dots 6)  (3 :dots 4)

;;  (2 :red 7)   (1 :red 8)   (1 :red 2)
;;  (0 :red 8)   (0 :red 7)

;;  (2 :solid 7) (1 :solid 8) (1 :solid 2)
;;  (0 :solid 8) (0 :solid 7)

;;  (6 :thin 7)  (4 :thin 8)  (3 :thin 6)
;;  (3 :thin 4)  (0 :thin 8)  (0 :thin 7))

We see that every edge is returned once for every property it has. If we want to select all :red edges that are :bold, we can do this instead:

(qry g :select (?x ?y)
       :where (and (?x :red ?y)
                   (?x :bold ?y)))
;;
;; ((2 7) (1 8) (1 2))

If you compare this result to the full list of properties and edges, you should be able to see a pattern; the three resulting edges are all listed in the full result with both a :red and a :bold property. In other words, the and clause performs a set intersection.

If you do the same query with or instead, you get the larger set of edges that are either a :red or :bold. This corresponds to the set union:

(qry g :select (?x ?y)
       :where (or (?x :red ?y)
                  (?x :bold ?y)))
;;
;; ((5 8) (5 7) (2 7) (1 8)
;;  (1 2) (0 8) (0 7))

(qry g :select (?x ?y)
       :where (and (or (?x :red ?y)
                       (?x :bold ?y))
                   (not (?x :dots ?y))))
;;
;; ((0 7) (0 8) (1 2) (1 8) (2 7))

That is, not is the set difference.

All the examples so far have effectively selected edges. But this is not necessary. To get all vertices we can write:

(qry g :select ?x
       :where (or (?x _ _)
                  (_ _ ?x)))
;;
;; (0 1 2 3 4 5 6 7 8)

If you for some reason only want even vertex indices, you can use a filter (%).

(qry g :select ?x
       :where (and (or (?x _ _)
                       (_ _ ?x))
                   (% (evenp ?x))))
;;
;; (0 2 4 6 8)

Filters are similar to not, but they support arbitrary code. You can reference all variables in the query as long as they are "bound" by :select.

What if you want all vertices that are associated with a :red edge? An immediate attempt at a query might be

(qry g :select ?x
       :where (?x :red _))
;;
;; (0 1 2)

We quickly see that there are some vertices missing. Remembering that the edges in the graph are directed, we can get the correct result with:

(qry g :select ?x
       :where (or (?x :red _)
                  (_ :red ?x)))
;;
;; (1 2 7 0 8)

Vertex properties are not supported in grph yet, but it is still possible to reference vertices directly. Here is a query that will find all vertices connected to v0:

(qry g :select ?x
       :where (or (0 _ ?x)
                  (?x _ 0)))
;;
;; (7 8)

If we need any part of the query to be more dynamic, it is possible to use the :in argument:

(let ((?v (rnd:rndi 9))) ; random integer
  (qry g :select ?x
         :in ?v
         :where (or (?v _ ?x)
                    (?x _ ?v))
         :collect (list ?x ?v)) ; return this list for every match
;;
;; which might yield:
;; ((0 7) (2 7) (5 7) (6 7))

Before we move on, note that dynamic input can be used for any variable in the query. But every triplet must have at least one free variable.

Queries and Mutation

This is by no means a comprehensive description of Datalog, but it's a pretty good start. To illustrate what the library can do a little bit further, here are two short examples of how to use queries to modify the graph.

Say you want to change a particular set of edges. The following query finds all :blue edges, deletes them, and makes reversed :green :bold edges instead:

; ^g references the mutated graph; g the initial
(qry g :select (?x ?y)
       :using ^g
       :where (?x :blue ?y)
       :then (progn (del! ^g ?x ?y)
                    (add! ^g ?y ?x '(:green :bold))))

Similarly, if you want to split all the :dots edges at a random point along the edge:

; p is the initial spatial data associated with the graph
; as above ^g and ^p are mutated in the query
(grph:qry g
  :select (?x ?y)
  :using (^g ^p)
  :where (?x :dots ?y)
  :collect (xgrph:2split! ^g ^p ?x ?y
             (veq:f2lerp (xgrph:2@ p ?x ?y) (rnd:rnd))))
;;
;; collects and yields the result of 2split!
;; In this case, the newly created vertices:
;; (9 10 11 12 13 14)

This looks more involved, and I won't go into details of how this works. I include it here at the end as an example of how I hope to experiment with this system further.

Idling

Hopefully I have been able to nudge your interest or imagination a tiny bit. I have yet to use this library a lot, but the artworks included in this article are all created using the new library (as well as cl-veq and weird).

The algorithm is named idling, and It is an amalgamation of a few different things I have experimented with at different times in the past. Including concave polygon triangulation, wide paths for plotter drawings and "spiraling" random walks.

There is an interesting dissonance in the juxtaposition of something that is obviously drawn by a computer, and something that someone might have drawn during an exceedingly boring meeting.

So far this is proving to be an interesting experiment, and I will explore it further.

EDIT: If you made it this far, you might also be interested in this post, where I use the query language for exporting to text files and SVG.