Advertisement
Guest User

BronKClojure

a guest
Mar 28th, 2015
328
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. (defn empty-graph [n]
  3.  (vec (repeat n #{})))
  4.  
  5. (defn add-directed-edge [g n1 n2]
  6.  (let [n1-neighbors (g n1)]
  7.    (assoc g n1 (conj n1-neighbors n2))))
  8.  
  9. (defn add-edge [g [n1 n2]]
  10.  (-> g
  11.      (add-directed-edge n1 n2)
  12.      (add-directed-edge n2 n1)))
  13.  
  14. (defn sanity1 []
  15.   (let [edgelist '([0 1] [0 2] [1 2] [1 3])]
  16.     (reduce add-edge (empty-graph 4) edgelist)))
  17.  
  18. (defn neighV [graph nodenum]
  19.   (let [ret-list (for [i (range (count graph)) :when (contains? (graph i) nodenum)] i)]
  20.     ret-list))
  21.  
  22. (defn BK-Call [graph]
  23.   (Bron-Kerbosch '() '(range (count graph)) '() graph '()))
  24.  
  25. (defn Bron-Kerbosch [r p x graph cliques]
  26.   (cond (and (empty? p) (empty? x)) (conj cliques r)
  27.         :else
  28.         (let [neigh (neighV graph (dec (count p)))]
  29.           (loop [loop-clq '(cliques)
  30.                  loop-cnt '(dec (count p))
  31.                  loop-p '(p)
  32.                  loop-x '(x)]
  33.             (cond (= -1 loop-cnt) loop-clq
  34.                   :else
  35.                   (recur (conj loop-clq (Bron-Kerbosch (conj r loop-cnt) (conj p neigh) (disj x neigh)))
  36.                          (dec loop-cnt)
  37.                          (disj p loop-cnt)
  38.                          (conj x loop-cnt)))))))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement