recursion - Tracking down issue with clojure implementation of Bron-Kerbosch non-pivot and pivoting algorithms? -
i having issues tracking down issue in clojure implementation of bron-kerbosch non-pivoting , pivoting algorithms.
here bron-kerbosch without pivoting (bk) 
here bk pivoting (bkp)
i have managed, so, bk without pivoting work. have verified through quite few sanity tests/graphs finds correct set of maximal cliques.
my issue lies in bk pivoting algorithm. not quite sure how can determine issue lies, , have assume issue how have implemented it.
here sscce of issue necessary functions http://pastebin.com/wm7dxvc8. below implementations of bk , bkp algorithms.
; bron-kerbosch 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)))))) ; bron-kerbosch 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))))))) most of time small simple random graph both algorithms work find correct maximal clique set.
fptests.core> (testallbk (random-graph 5 6)) starting test... timing evaluation of graph bk :"elapsed time: 0.098467 msecs" timing evaluation of graph bkp:"elapsed time: 0.144646 msecs" bk cliques count: 3 largest: 3 cliques: [#{0 4} #{1 4} #{1 3 2}] bkp cliques count: 3 largest: 3 cliques: [#{0 4} #{1 4} #{1 3 2}] though sometimes, 10%, bkp algorithm manages find more cliques bk algorithm. of times bkp has error reports 2 of same clique
fptests.core> (testallbk (random-graph 5 6)) starting test... timing evaluation of graph bk :"elapsed time: 0.102083 msecs" timing evaluation of graph bkp:"elapsed time: 0.097479 msecs" bk cliques count: 2 largest: 3 cliques: [#{0 1 4} #{0 3 2}] bkp cliques count: 3 largest: 3 cliques: [#{0 1 4} #{0 3 2} #{0 3 2}] but there instances reports 1 of correct cliques, seemingly "cutting" off 1 of them
fptests.core> (testallbk (random-graph 5 6)) starting test... timing evaluation of graph bk :"elapsed time: 0.076546 msecs" timing evaluation of graph bkp:"elapsed time: 0.079762 msecs" bk cliques count: 4 largest: 2 cliques: [#{0 1} #{0 3} #{1 2} #{4 3}] bkp cliques count: 4 largest: 2 cliques: [#{0 1} #{0 3} #{4 3} #{2}] when larger random graphs used bkp algorithm manages find less or more cliques bk
fptests.core> (testallbk (random-graph 500 600)) starting test... timing evaluation of graph bk :"elapsed time: 113.128014 msecs" timing evaluation of graph bkp:"elapsed time: 166.300653 msecs" bk cliques count: 631 largest: 3 bkp cliques count: 629 largest: 3 fptests.core> (testallbk (random-graph 500 600)) starting test... timing evaluation of graph bk :"elapsed time: 109.454454 msecs" timing evaluation of graph bkp:"elapsed time: 166.39116 msecs" bk cliques count: 641 largest: 3 bkp cliques count: 642 largest: 3 seeing number of cliques never far off 1 assume @ point in bkp algorithm implementation of set union, difference, , removing values set has edge cases not accounted for.
though, limited knowledge of clojure far has prevented me further analyzing issue might lie. seeing bk algorithm works graphs of size , loop statements in both bk , bkp algorithms same. think issue lies in choosing of pivot , calculation of u, nu, , pnu. again, knowledge seems correct me.
can more knowledgeable track down issue or point me in right direction?
Comments
Post a Comment