Some graph implementations

graph.clj

(ns nines.mesh
  (:require [thi.ng.ndarray.core :as nd]))

(defprotocol Graph
  (add-node  [this x])
  (set-edge  [this [u v] val])
  (get-edge  [this [u v]])
  (del-edge  [this [u v]])
  (neighbors [this x]))

;; Adjacency matrix
;; ================

(defprotocol MatrixStore
  (set-at [this u v val])
  (get-at [this u v])
  (column [this u]))

(defrecord MatrixGraph [n fill index rev-index store]
  Graph
  (add-node [this x]
    (if (contains? index x)
      this
      (merge this {:n (inc n)
                   :index (assoc index x n)
                   :rev-index (assoc rev-index n x)})))
  (set-edge [this [u v] val]
    (let [safe (-> this
                   (add-node u)
                   (add-node v))
          {store :store {u' u v' v} :index} safe]
      (assoc safe :store (set-at store u' v' val))))
  (del-edge [this [u v]]
    (let [{u' u v' v} index]
      (assoc this :store (set-at store u' v' fill))))
  (get-edge [_ [u v]]
    (get-at store (index u) (index v)))
  (neighbors [_ x]
    (sequence
     (comp
      (map-indexed (fn [i rel] (if rel (rev-index i))))
      (filter identity))
     (column store (index x)))))

(defrecord NDStore [matrix]
  MatrixStore
  (set-at [this u v val]
    (assoc this :matrix
           (-> matrix
               (nd/set-at u v val)
               (nd/set-at v u val))))
  (get-at [this u v]
    (nd/get-at matrix u v))
  (column [this u]
    (nd/pick matrix u nil)))

(defrecord VectorStore [vec]
  MatrixStore
  (set-at [this u v val]
    (-> this
        (assoc-in [:vec u v] val)
        (assoc-in [:vec v u] val)))
  (get-at [this u v]
    (get-in vec [u v]))
  (column [this u]
    (get vec u)))

(defn make-nd-graph
  "Creates nd-darray backed graph based on adjacency matrix (of shape n by n).
  Uses thi.ng/ndarray for its storage, and hence the operations are mutative."
  [n]
  (MatrixGraph. 0 nil {} {}
                (NDStore. (nd/ndarray :generic (repeat (* n n) nil) [n n]))))

(defn make-vec-graph
  "Creates vector backed graph based on adjacency matrix (of shape n by n).
  Uses Clojure's persistent vectors for its storage."
  [n]
  (MatrixGraph. 0 nil {} {}
                (VectorStore. (vec (repeat n (vec (repeat n nil)))))))

;; Adjacency map
;; =============

(defrecord MapGraph [m]
  Graph
  (add-node [this x])
  (set-edge [this [u v] val]
    (-> this
        (assoc-in [:m u v] val)
        (assoc-in [:m v u] val)))
  (get-edge [_ [u v]]
    (get-in m [u v]))
  (del-edge [this [u v]]
    (let [us (-> m (get u) (dissoc v))
          vs (-> m (get v) (dissoc u))
          m' (if (empty? us)
               (dissoc m u)
               (assoc m u us))
          m' (if (empty? vs)
               (dissoc m' v)
               (assoc m' v vs))]
      (assoc this :m m')))
  (neighbors [_ x]
    (keys (get m x))))

(defn make-map-graph []
  (MapGraph. {}))

(def graph
  (reduce
   (fn [g [u v x]]
     (set-edge g [u v] x))
   (make-map-graph)
   [[:a :b 42]
    [:b :d 11]
    [:d :c "foo"]
    [:e :f "bar"]]))

(get-edge graph [:b :a])
(get-edge graph [:d :c])
(neighbors graph :b)