在Clojure Bron-Kerbosch实现中正确使用集合 [英] Proper use of sets in Clojure Bron-Kerbosch implementation
问题描述
我目前正试图在我的Clojure实现Bron-Kerbosch算法并有困难时正确有效地使用集合和 clojure.set 命名空间。
我想重构目前的实作
[rpx graph]
（if（and（empty？p）（empty？x））
[（set r）]
（loop [pp，xx，cliques [ $ b（if（empty？p）
cliques
（let [v（first p）
nv（graph v）
cliques（into cliques
into r（list v））
（filter nv p）
（filter nv x）
graph））
p（rest p）
x ））]
（recur px cliques））））））
clojure.set 这样的命名空间
（defn BK3 [rpx graph ]
（if（and（empty？p）（empty？x））
[（set r）]
（loop [pp，xx，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）
图））
p p）
x（clojure.set / union（set（list v））x）]
（recur px cliques））））））
（defn get-BK3 [图形]
（BK3（set'（））（set（doall（range（count graph））））（set'（））graph））
虽然这个当前的实现导致了StackOverflow。以下是一个简短的SSCCE，其中包含所有必要的代码，用于运行函数。
有关首先和 rest 与 set ，可以使用第一不必要的顺序（但在算法中没有关系）和 disj 从集合中删除所选元素。
请注意，您可以通过＃{} 简化（set'（））。
以下是具有 clojure.set 的工作版本，具有非常快速的测试/ code> set 版本：
（require'[clojure.set：as s] ）
（defn BK4 [rpx graph]
（if（and（empty？p）（empty？x））
[r] ;; r已经是一个
（loop [pp，xx，cliques []]
（if（empty？p）
cliques
（let [v（first p）;; p是一个集合，首先不需要下一个序列
nv（graph v）;;从图中获取第v个集合
cliques（concat cliques
（BK4（conjrv）;; add v to the set r
（s / intersection p nv）
/ intersection x nv）
graph））]
（recur（disj pv）（conj xv）cliques））））））
（defn get-BK4 [graph]
（BK4＃{}（set（range（count graph）））＃{} graph））
$ b b
测试：
（let [graph（doall（random-graph 1000 1000））
bk时间（get-BK图））
bk4（time（get-BK4 graph））]
（if（= bk bk4）
（printlnSeems ok）
printlnko））
打印（在MBP 2,5 GHz Intel Core i7上） / p>
已用时间：243.533768毫秒
已用时间：19.228952毫秒
ok
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?
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
这篇关于在Clojure Bron-Kerbosch实现中正确使用集合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
