我正在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中没有“set x=something”的意思。但我知道有一个功能,我认为是相似的我想知道
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)))
)))
所以现在我不得不按照算法修改
assoc
和p
我想我可以用x
来做这件事,但我认为它只适用于地图。是否可以使用,是否有人可以推荐其他功能? 最佳答案
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)))))