Advertisement
Guest User

Clojure third imp issues

a guest
Apr 19th, 2015
362
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ; =================================================================
  2. ;       General graph functions (defines graph structure too)
  3. ; =================================================================
  4.  
  5. ; Creates and empty graph of size n
  6. (defn empty-graph [n]
  7.  (vec (repeat n #{})))
  8.  
  9. ; Adds a directed edge to a given graph
  10. (defn add-directed-edge [g n1 n2]
  11.  (let [n1-neighbors (g n1)]
  12.    (assoc g n1 (conj n1-neighbors n2))))
  13.  
  14. ; Credit Fred Annexstein
  15. ; Adds a "full" edge to a graph (both directions)
  16. (defn add-edge [g [n1 n2]]
  17.  (-> g
  18.      (add-directed-edge n1 n2)
  19.      (add-directed-edge n2 n1)))
  20.  
  21. ; Determines if a given graph contains a self loop
  22. (defn contains-self-loop? [graph]
  23.   (loop [curnode 0
  24.          curset (first graph)
  25.          restsets (rest graph)]
  26.     (cond (= 0 (count restsets)) (contains? curset curnode)
  27.           :else
  28.           (if (contains? curset curnode) true
  29.               (recur (inc curnode) (first restsets) (rest restsets))))))
  30.  
  31. ; ========================================
  32. ;       Used to create random graphs
  33. ; ========================================
  34.  
  35. ; Returns a random edge that does not loop to itself
  36. (defn random-no-loop-edge [n]
  37.   (let [n1 (rand-int n)
  38.         n2 (loop [possn2 (rand-int n)]
  39.              (if (not (= n1 possn2))
  40.                possn2
  41.                (recur (rand-int n))))]
  42.     (vector n1 n2)))
  43.  
  44. ; Creates a random graph with n nodes and e edges
  45. (defn random-graph [n e]
  46.     (reduce add-edge (empty-graph n)
  47.        (for [i (range e)] (random-no-loop-edge n))))
  48.  
  49. ; ======================================
  50. ;       Bron Kerbosch algorithm functions
  51. ; ======================================
  52.  
  53. ; Bron-Kerbosch with no pivot, second implementation
  54. (defn BK [r p x graph]
  55.   (if (and (empty? p) (empty? x))
  56.     [(set r)]
  57.     (loop [p p, x x, cliques []]
  58.       (if (empty? p)
  59.         cliques
  60.         (let [v (first p)
  61.               nv (graph v)
  62.               cliques (into cliques
  63.                             (BK (into r (list v))
  64.                                 (filter nv p)
  65.                                 (filter nv x)
  66.                                 graph))
  67.               p (rest p)
  68.               x (into x (list v))]
  69.           (recur p x cliques))))))
  70.  
  71. ; Helper function to call Bron-Kerbosch non-pivot, second implementation
  72. (defn get-BK [graph]
  73.   (BK (set '()) (set (doall (range (count graph)))) (set '()) graph))
  74.  
  75. ; Bron-Kerbosch with no pivot, third implementation (causes SO when called)
  76. (defn BK3 [r p x graph]
  77.       (if (and (empty? p) (empty? x))
  78.         [(set r)]
  79.         (loop [p p, x x, cliques []]
  80.           (if (empty? p)
  81.             cliques
  82.             (let [v (first p)
  83.                   nv (graph v)
  84.                   cliques (into cliques
  85.                                 (BK3 (clojure.set/union (set (list v)) r)
  86.                                      (clojure.set/difference p nv)
  87.                                      (clojure.set/difference x nv)
  88.                                      graph))
  89.                   p (rest p)
  90.                   x (clojure.set/union (set (list v)) x)]
  91.               (recur p x cliques))))))
  92.  
  93. ; Helper function to call Bron-Kerbosch non-pivot, third implementation
  94. (defn get-BK3 [graph]
  95.   (BK3 (set '()) (set (doall (range (count graph)))) (set '()) graph))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement