ClojureBKvsBKP

; =================================================================
;       General graph functions (defines graph structure too)
; =================================================================

; Creates and empty graph of size n
(defn empty-graph [n]
 (vec (repeat n #{})))

; Adds a directed edge to a given graph
(defn add-directed-edge [g n1 n2]
 (let [n1-neighbors (g n1)]
   (assoc g n1 (conj n1-neighbors n2))))

; Credit Fred Annexstein
; Adds a "full" edge to a graph (both directions)
(defn add-edge [g [n1 n2]]
 (-> g
     (add-directed-edge n1 n2)
     (add-directed-edge n2 n1)))

; Determines if a given graph contains a self loop
(defn contains-self-loop? [graph]
  (loop [curnode 0
         curset (first graph)
         restsets (rest graph)]
    (cond (= 0 (count restsets)) (contains? curset curnode)
          :else
          (if (contains? curset curnode) true
              (recur (inc curnode) (first restsets) (rest restsets))))))

; ========================================
;       Used to create random graphs
; ========================================

; Returns a random edge that does not loop to itself
(defn random-no-loop-edge [n]
  (let [n1 (rand-int n)
        n2 (loop [possn2 (rand-int n)]
             (if (not (= n1 possn2))
               possn2
               (recur (rand-int n))))]
    (vector n1 n2)))

; Creates a random graph with n nodes and e edges
(defn random-graph [n e]
    (reduce add-edge (empty-graph n)
       (for [i (range e)] (random-no-loop-edge n))))


; ======================================
;       Start of the project code
; ======================================

; ===== Bron Kerbosch algorithm functions =====

; Given a vector of sets = cliques = [#{1 2 3} #{4 5 6}]
; Will return a vector of cliques that have the maximum clique size
(defn get-max-cliques [cliqueset]
  (cond (= 1 (count cliqueset)) [(first cliqueset)]
        :else
        (loop [maxset (list (first cliqueset))
               curset (first (rest cliqueset))
               restsets (rest (rest cliqueset))]
          (let [curcnt (count curset)
                maxcnt (count (first maxset))
                newmax (cond (> curcnt maxcnt) (list curset)
                             (= curcnt maxcnt) (cons curset maxset)
                             :else maxset)]
            (cond (= 0 (count restsets)) newmax
                  :else (recur newmax (first restsets) (rest restsets)))))))


; Bron-Kerbosch with no pivot
(defn BK [r p x graph]
  (if (and (empty? p) (empty? x))
    [(set r)]
    (loop [p p, x x, cliques []]
      (if (empty? p)
        cliques
        (let [v (first p)
              nv (graph v)
              cliques (into cliques
                            (BK (into r (list v))
                                (filter nv p)
                                (filter nv x)
                                graph))
              p (rest p)
              x (into x (list v))]
          (recur p x cliques))))))

; Helper function to call Bron-Kerbosch non-pivot
(defn get-BK [graph]
  (BK (set '()) (set (doall (range (count graph)))) (set '()) graph))

; Bron-Kerbosch with pivoting
(defn BKP [r p x graph]
  (if (and (empty? p) (empty? x))
    [(set r)]
    (let [u (first (into p x))
          nu (graph u)
          pnu (remove #(some (partial = %) nu) p)]
      (loop [p p, pnu pnu, x x, cliques []]
        (if (empty? pnu)
          cliques
          (let [v (first pnu)
                nv (graph v)
                cliques (into cliques
                              (BKP (into r (list v))
                                   (filter nv p)
                                   (filter nv x)
                                   graph))
                p (rest p)
                x (into x (list v))]
            (recur p (rest pnu) x cliques)))))))

; Helper function to call Bron-Kerbosch with pivoting
(defn get-BKP [graph]
  (BKP (set '()) (set (doall (range (count graph)))) (set '()) graph))



; =======================================
;  Used to test BK versus BKP algorithms
; =======================================

(defn testallbk [graph]
  (println "Starting test...")
  (print "Timing evaluation of graph with BK :")
  (cond (contains-self-loop? graph) (println "\nGraph contains self loop, terminating")
        :else
        (let [bk1 (time (get-BK graph))]
          (print "Timing evaluation of graph with BKP:")
          (let [bk2 (time (get-BKP graph))]
                (println "BK  cliques count:" (count bk1) " Largest: " (count (first (get-max-cliques bk1))))
                (println "BKP cliques count:" (count bk2) " Largest: " (count (first (get-max-cliques bk2))))))))