我正在Clojure中为一个班级项目实现Bron-Kerbosch算法，并且遇到了一些问题。问题出在算法的最后几行
BronKerbosch1(R, P, X):
if P and X are both empty:
report R as a maximal clique
for each vertex v in P:
BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
P := P \ {v} ;This line
X := X ⋃ {v} ;This line
我知道在Clojure中没有“设置x =某些东西”的感觉。但是确实知道有assoc我认为相似的功能。我想知道是否assoc适合完成我的实施。
在我的实现中，图形表示为
[#{1 3 2} #{0 3 2} #{0 1 3} #{0 1 2}]
其中第0个节点表示为向量中的第一个集合，而该集合中的值表示其他节点的边。因此，以上所示的图具有完整的4个节点（所有节点都连接到所有其他节点）。
到目前为止，我的算法实现是
(defn neighV [graph, v]
(let [ret-list (for [i (range (count graph)) :when (contains? (graph i) v)] i)]
ret-list))
(defn Bron-Kerbosch [r, p, x, graph, cliques]
(cond (and (empty? p) (empty? x)) (conj cliques r)
:else
(for [i (range (count p))]
(conj cliques (Bron-Kerbosch (conj r i) (disj p (neighV graph i) (disj x (neighV graph i)) graph cliques)))
)))
所以现在我被卡住了，p并且x按照算法。我认为可以使用assoc此功能，但我认为它仅适用于地图。可以使用，有人可以推荐其他功能吗？
assoc不会改变其论点。像Clojure中的所有其他其他基本收集操作一样，它会返回一个新的不可变收集。
为了“就地”进行更新，您将需要停止使用基本的Clojure数据类型，并使用诸如的本机Java类型java.util.HashSet。
另一个（也是首选）选项是重构算法，以便将所有更新传递给代码的下一次迭代或递归。
这是将您的代码调整为这种样式的最初尝试，但需要注意的是，可能需要从递归调用中提取内部修改：
(defn Bron-Kerbosch
[r p x graph cliques]
(if (every? empty? [p x])
(conj cliques r)
(reduce (fn [[cliques p x] v]
(let [neigh (neighV graph v)]
[(conj cliques
;; do we need to propagate updates to p and x
;; from this call back up to this scope?
(Bron-Kerbosch (conj r v)
(disj p neigh)
(disj x neigh)
graph
cliques))
;; here we pass on the new values for p and x
(disj p v)
(conj x v)]))
[cliques p x]
(range (count p)))))
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句