Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ; =================================================================
- ; 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))))
- ; ======================================
- ; Bron Kerbosch algorithm functions
- ; ======================================
- ; Bron-Kerbosch with no pivot, second implementation
- (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, second implementation
- (defn get-BK [graph]
- (BK (set '()) (set (doall (range (count graph)))) (set '()) graph))
- ; Bron-Kerbosch with no pivot, third implementation (causes SO when called)
- (defn BK3 [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
- (BK3 (clojure.set/union (set (list v)) r)
- (clojure.set/difference p nv)
- (clojure.set/difference x nv)
- graph))
- p (rest p)
- x (clojure.set/union (set (list v)) x)]
- (recur p x cliques))))))
- ; Helper function to call Bron-Kerbosch non-pivot, third implementation
- (defn get-BK3 [graph]
- (BK3 (set '()) (set (doall (range (count graph)))) (set '()) graph))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement