Skip to content

Latest commit

 

History

History
99 lines (88 loc) · 3.3 KB

unionfind.org

File metadata and controls

99 lines (88 loc) · 3.3 KB

Contents

Namespace: thi.ng.dstruct.unionfind

Protocol definition

(defprotocol PUnionFind
  (register [_ p])
  (unregister [_ p])
  (canonical [_ p])
  (canonical? [_ p])
  (set-canonical [_ p q])
  (disjoint-components [_])
  (component [_ p])
  (union [_ [p q]] [_ p q])
  (unified? [_ p q]))

Disjoint Set

(deftype DisjointSet [index components]
  PUnionFind
  (canonical [_ p]
    (if (get components p) p (get index p)))
  (canonical? [_ p] (get components p))
  (set-canonical
    [_ p q]
    (let [canon (canonical _ p)
          comp  (get components canon)]
      (if (comp q)
        (DisjointSet.
         (reduce #(assoc %1 %2 q) (dissoc index q) (disj comp q))
         (-> components (dissoc canon) (assoc q comp)))
        (throw
         (new #?(:clj IllegalArgumentException :cljs js/Error)
              (str p " not unified with " q))))))
  (unified? [_ p q]
    (= (get index p p) (get index q q)))
  (component [_ p]
    (get components (canonical _ p)))
  (disjoint-components [_]
    (vals components))
  (register
    [_ p]
    (if (canonical _ p) _
        (DisjointSet. (assoc index p p) (assoc components p #{p}))))
  (unregister [_ p]
    (if (canonical _ p)
      (if-let [comp (get components p)]
        (let [comp (disj comp p)]
          (if-let [q (first comp)]
            (DisjointSet.
             (reduce #(assoc % %2 q) (dissoc index p q) (disj comp q))
             (-> components (dissoc p) (assoc q comp)))
            (DisjointSet. (dissoc index p) (dissoc components p))))
        (DisjointSet. (dissoc index p) (update components (get index p) disj p)))
      _))
  (union [_ p q]
    (let [canonp (get index p p)
          canonq (get index q q)]
      (if (= canonp canonq) _
          (let [compp (or (get components canonp) #{canonp})
                compq (or (get components canonq) #{canonq})
                [canonp canonq compp compq] (if (<= (count compp) (count compq))
                                              [canonp canonq compp compq]
                                              [canonq canonp compq compp])]
            (DisjointSet.
             (loop [idx (transient index), i compp]
               (if i
                 (recur (conj! idx [(first i) canonq]) (next i))
                 (persistent! idx)))
             (-> components
                 (dissoc canonp)
                 (assoc canonq (into compq compp))))))))
  Object
  (toString [_] (pr-str {:index index :components components})))

(defn disjoint-set
  ([] (DisjointSet. {} {}))
  ([xs] (reduce #(apply union % %2) (DisjointSet. {} {}) xs)))

Complete namespace definition

(ns thi.ng.dstruct.unionfind)

<<protos>>

<<disj-set>>