Proper use of sets in Clojure Bron-Kerbosch implementation

Question

I am currently trying to use sets and the clojure.set namespace properly and effectively in my Clojure implementation of the Bron-Kerbosch algorithm and having difficulties.

I am trying to refactor my current 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))))))

Into something that uses the clojure.set namespace as such

(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))))))

(defn get-BK3 [graph]
  (BK3 (set '()) (set (doall (range (count graph)))) (set '()) graph))

Though this current implementation causes a StackOverflow. Here is a short SSCCE with all of the necessary code to run evaluate the functions http://pastebin.com/PVxJidGB.

If I place a prn form before the (if (empty? p)) in the function I can see that the set p is changed once and never again, also that the set x is never added to. The following is printed and repeats until a stack overflow occurs.

finalproject.core> (get-BK3 (random-graph 10 20))
"P: " #{0 7 1 4 6 3 2 9 5 8} " X: " #{}
-----------------
"P: " #{0 7 4 6 3 2 9 8} " X: " #{}
-----------------
"P: " #{0 7 4 6 3 2 9 8} " X: " #{}
-----------------
"P: " #{0 7 4 6 3 2 9 8} " X: " #{}
-----------------
....

This must mean that at each recursive call to BK3 the set p does not have the set nv removed from it? Though reviewing the clojure.set/difference help page it should be doing just that? Did I read the page wrong or have some typo that is causing the stack overflow?

That is my first issue that I don't understand. My next issue is that first and rest do not return sets (#{0 1 2}) rather lists ((0 1 2)). Which if a list is passed to any of the clojure.set functions errors are thrown. Are there any alternatives to first and rest that return sets?

EDIT: Here is the pseudo-code implementation from Wikipedia with the proper set notion symbols. I guess my interpretation of the symbols might possibly be incorrect?

Answer 1

As answered by @michat, in the wikipedia formula the recursive call is with set intersection and not set difference, which are not the same. In mathematics, the matching function for clojure.set/difference is set complement.

For your question on first and rest with set, you can use first, that will yield an element which is not necessary the next in order (but it doesn't matter in the algo) and disj to remove the selected element from the set.

Note you can simplify (set '()) by #{}.

Following is a working version with clojure.set, with a very quick test/bench that shows some performance improvement with the set version:

(require '[clojure.set :as s])

(defn BK4 [r p x graph]
  (if (and (empty? p) (empty? x))
    [r] ;; r is already a set
    (loop [p p, x x, cliques []]
      (if (empty? p)
        cliques
        (let [v (first p) ;; p is a set, first is not necessary the next in sequence
              nv (graph v) ;; take v-th set from graph
              cliques (concat cliques
                            (BK4 (conj r v) ;; add v to the set r
                                 (s/intersection p nv)
                                 (s/intersection x nv)
                                 graph))]
          (recur (disj p v) (conj x v) cliques))))))

(defn get-BK4 [graph]
  (BK4 #{} (set (range (count graph))) #{} graph))

Test:

(let [graph (doall (random-graph 1000 1000))
      bk (time (get-BK graph))
      bk4 (time (get-BK4 graph))]
  (if (= bk bk4)
    (println "Seems ok")
    (println "ko")))

Prints (on a MBP 2,5 GHz Intel Core i7)

"Elapsed time: 243.533768 msecs"
"Elapsed time: 19.228952 msecs"
Seems ok

Answer 2

1. The recursive call in the pseudocode version of this algorithm from Wikipedia uses set intersection, not set difference. You can use clojure.set/intersection to compute the intersection of two persistent sets.

2. Set difference is used on the second line of the body of the for each loop. In your code, the corresponding expression is (rest p), but this generates a seq of all elements of p except (first p), not a set. You'll want to use (disj p (first p)) instead (or I suppose (disj p v), using the previously introduced local).

3. set/union and into are both overkill for adding a single element to a set – use conj instead.

Answer 3

Since you are having StackOverflow, then conceptually this can happen in your code:

(clojure.set/difference #{1,2,3,4,5} #{4})
#{1 3 2 5}
user> (clojure.set/difference #{1,2,3,5} #{4})
#{1 3 2 5}

where p is #{1 2 3 4 5} and nv is #{4}.

In recursion, p becomes #{1 3 2 5} and then again you get same v (because you do not have self loops and hence 4 was not v earlier..) and hence same nv #{4}

i.e. first of two sets are same..

user> (first #{1 2 3 4 5})
1
user> (first #{ 1 2 3 5})
1

and again same recursion.. and stackoverflow..