Correct Usage of Sets in Clojure Bron-Kerbosch Implementation
I am currently trying to efficiently and efficiently use sets and namespaces clojure.set
in my Clojure implementation of the Bron-Kerbosch algorithm and am having difficulty.
I am trying to refactor the 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))))))
That which uses the namespace clojure.set
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))
Although this current implementation calls StackOverflow. Here is a short SSCCE with all the code you need to do the function evaluation http://pastebin.com/PVxJidGB .
If I put the form prn
in front of (if (empty? p))
the function, I see that the set p
changes once and never again, also that the set is x
never added. Then it is printed and repeated 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 should mean that every recursive call will not remove BK3
the set p
from the set nv
? Although the clojure.set/difference
man page review should do just that? Did I read the page incorrectly or did I have a typo causing a stack overflow?
This is my first problem that I don't understand. My next problem is that first
and rest
sets ( #{0 1 2}
) do not return rather lists ( (0 1 2)
). Which, if the list is passed to any of the functions clojure.set
, errors are generated. Are there alternatives first
and rest
that return sets?
EDIT: Here is a pseudocode implementation from Wikipedia with the appropriate convention symbols. Think my interpretation of symbols might be wrong?
source to share
As @michat answered, in the wikipedia formula, the recursive call has a given intersection and does not set a difference that is not the same. In mathematics, the match function for clojure.set/difference
sets the complement .
For your question in first
and rest
with the help set
you can use first
which will give an element that is not needed in the following order (but it doesn't matter in the algo) and disj
to remove the selected element from the set.
Note that you can simplify (set '())
on #{}
.
Below is a working version c clojure.set
, with a very quick test / bench showing the performance improvement with the version set
:
(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")))
Printing (on MBP 2.5 GHz Intel Core i7)
"Elapsed time: 243.533768 msecs"
"Elapsed time: 19.228952 msecs"
Seems good
source to share
-
The recursive call in the pseudocode version of this algorithm from Wikipedia uses the specified intersection, not the specified difference. You can use
clojure.set/intersection
to compute the intersection of two constant sets. -
The set difference is used in the second line of the body for each cycle. In your code, there is a matching expression
(rest p)
, but this generates a seq of allp
except elements(first p)
, not a set. You want to use instead(disj p (first p))
(or I suppose(disj p v)
using the previously introduced local). -
set/union
andinto
are overkill for adding one item to a set - useconj
.
source to share
Since you have 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
- #{1 2 3 4 5}
, a nv
- #{4}
.
In recursion, p becomes #{1 3 2 5}
, and then you get the same thing v
(because you don't have autopilot and therefore 4 wasn't v
before ..) and therefore the samenv
#{4}
i.e. the first of the two sets is the same.
user> (first #{1 2 3 4 5})
1
user> (first #{ 1 2 3 5})
1
and again the same recursion .. and stackoverflow ..
source to share