Visualisation of lattice polynomials

The basic units of algebraic logic are lattice polynomials, while the basic units of algebraic geometry are ring polynomials. Unlike their ring counterparts, lattice polynomials can form a tree structure. This leads to the possibility of using tree visualisation methods on lattice polynomials. In order to make this visualisation more effective, I developed a simple color scheme:

• Meet: red
• Join: green

Green is typically considered a positive color while red is a negative color. So it makes sense that the join should be green while the meet is red. Every non-leaf node in a lattice polynomial is either a meet or join term, and so can be coloured coded accordingly. Due to associativity, a well formed lattice polynomial should always alternate between green and red at each level. In order to implement this, I used dorothy to create graphviz files from lattice polynomials.

(require '[dorothy.core :as dot])
(require '[dorothy.jvm :refer (render save! show!)])

(defn get-coordinates
  "Get the coordinates of the leaf nodes of an S-expression."
  [coll]

  (if (not (seq? coll))
    '(())
    (apply
      concat
      (map
        (fn [i]
          (map
            (fn [c]
              (cons i c))
            (get-coordinates (nth coll i))))
        (range (count coll))))))

(defn get-coordinate-value
  "Get the value of an S-expression at the given coordinate."
  [coll coordinate]

  (if (empty? coordinate)
    coll
    (get-coordinate-value
      (nth coll (first coordinate))
      (rest coordinate))))

(defn create-digraph
  "Create a digraph from the arithmetical form 
   of a lattice polynomial."
  [coll]

  (letfn [(create-vertex [coll coordinate]
            (let [v (get-coordinate-value coll coordinate)
                  cstr (.toString coordinate)]
              (cond
                (= v '*) [cstr {:label     ""
                                :fillcolor "crimson"
                                :style     "filled"}]
                (= v '+) [cstr {:label     ""
                                :fillcolor "green"
                                :style     "filled"}]
                :else [cstr {:label (.toString v)}])))
          (create-vertices [coll coordinates]
            (concat
              (map
                (partial create-vertex coll)
                coordinates)))
          (find-next-leaf [coll coordinate]
            (if (seq? (get-coordinate-value coll coordinate))
              (find-next-leaf coll (concat coordinate (list 0)))
              coordinate))
          (successor-edges [coordinate]
            (let [fixed-coordinate (if (&= (count coordinate) 1)
                                     '()
                                     (butlast coordinate))
                  parent-sequence (get-coordinate-value 
                                    coll 
                                    fixed-coordinate)]
              (map
                (fn [i]
                  [(.toString 
                     (seq (concat fixed-coordinate (list 0))))
                   (.toString 
                     (seq (find-next-leaf 
                            coll 
                           (concat fixed-coordinate (list i)))))])
                (range 1 (count parent-sequence)))))
          (create-edges [coll coordinates]
            (apply
              concat
              (for [i coordinates
                    :when (= (last i) 0)]
                (successor-edges i))))]
    (let [coordinates (get-coordinates coll)]
      (vec
        (concat
          (create-vertices coll coordinates)
          (create-edges coll coordinates))))))

In order to demonstrate this approach to lattice polynomial visualisation, I have prepared a couple of examples. In order to encode a lattice polynomial as an S-expression, I use the arithmetical syntax of defining the meet operation as multiplication and the join operation as addition. This follows from the fact that the meet operation is the product operation in a thin category, while the join operation is the coproduct.

(def expoly1
  '(+ (* a b)
      (* c (+ d e))))

This simple approach can be used to visualize arbitrarily large lattice polynomials, with an arbitrary number of variables and operations nested to any depth. Therefore, our second example is a bit larger then the first.

(def expoly2
  '(* (+ (* a b)
         (* c d)
         e)
      (+ (* f g) h)
      (+ i j k)
      l))

This demonstrates a way of visualising lattice polynomials in algebraic logic. Of course, we can often perform visualisations of a different sort for the ring polynomials in algebraic geometry: the visualisation of algebraic varieties formed by ring polynomials. In either case, visualisation techniques will always be important in logic and geometry.