algorithm - 如何在 Clojure 算法实现中处理多个变量？

Question

我是 Clojure 的新手，正在尝试通过在其中实现一些算法来学习。我正在编写的算法用于计算图形数据结构的节点中介中心性指标。

我尝试实现的算法(Brandes 算法)中的函数是这样的:

这里，V 是图的顶点，s 是我们尝试计算并返回最短路径指标 S 的起始节点， Pred 和 sigma

这是我通过使用 loom 得到的结果为每个起始节点 start 创建初始图 g:

 (defn ss-shortest-path     
   [g start]   
    (let [nodeset (disj (nodes g) start)
        pred (apply assoc {} (interleave (nodes g) (repeat nil)))
        dist (apply assoc {start 0} (interleave nodeset (repeat -1)))
        sigma (apply assoc {start 1} (interleave nodeset (repeat 0)))
        stack []]
    (loop [queue (conj clojure.lang.PersistentQueue/EMPTY start)]
      (if (empty? queue)
        {:sigma sigma
         :pred pred
         :stack stack}
        (let [v (peek queue)
              stack (conj stack v)]
          (doseq [w (successors g v)]
            (when (= (dist w) -1)
              (do
                (conj queue w)
                (assoc dist w (+ 1 (dist v)))))
            (when (= (dist w) (+ 1 (dist v)))
                  (do
                    (assoc sigma w (+ (sigma w) (sigma v)))
                    (assoc pred w v))))
            (recur (pop queue)))))))

我知道 Clojure 数据结构是不可变的，所以每次我在变量 pred、sigma、stack、dist 中调用 conj 或 assoc创建一个新副本，原始变量保持原样。

但是，我不想使用像 atoms、refs 这样的可变状态，因为我有一种感觉，那就是简单地复制我已经拥有的命令式风格知道。

因此，我正在寻求一些经验丰富的 Clojurists 的帮助，以帮助我以惯用的风格创建此函数。

提前致谢。

Answer 1

我会做两件主要的事情:首先，算法有一个由多个“变量”组成的状态(queue，stack ， ETC。)。我会首先使用不可变映射构造一个表示算法状态的函数，例如

(defn initialize-state [g start]
  (let [nodeset (disj (nodes g) start)]
    {:g g
     :nodeset nodeset
     :pred (apply assoc {} (interleave (nodes g) (repeat nil)))
     :dist (apply assoc {start 0} (interleave nodeset (repeat -1)))
     :sigma (apply assoc {start 1} (interleave nodeset (repeat 0)))
     :stack []
     :queue (conj clojure.lang.PersistentQueue/EMPTY start)
     :current-vertex nil}))

然后，我会在 REPL 中测试这张 map 是否针对 g 和 start 的各种选择正确初始化。

其次，我会将算法分解为多个小函数，这些函数将一个状态作为输入并返回一个状态作为输出，比如this(这段代码不起作用，您必须填写缺少的部分):

(defn next-vertex [state]
  {:pre [(state? state)]
   :post [(state? %)]}
  (let [v (peek (:queue state))]
    (-> state
        (update :stack conj v)
        (assoc :current-vertex v))))

(defn process-successor [state w]
  (let [dist-w (dist w)]
    (cond
      ;; fill in...
      )))

(defn process-successors [state]
  {:pre [(state? state)]
   :post [(state? %)]}
  (reduce
   process-successor
   state
   (successors (:g state) (:current-vertex state))))

(defn pop-queue [state]
  {:pre [(state? state)]
   :post [(state? %)]}
  (update state :queue pop))

带有 :pre 和 :post 键的映射是所谓的前置条件和后置条件，state? 函数可以是例如，实现为 (defn state? [x] (and (map? x) (contains? x :queue)))，就像完整性检查一样。

请注意，对于您编写的每个函数，您都可以在 REPL 中使用一些数据对其进行测试，以确保它在编写下一个函数之前能够正常工作。现在可以使用 comp 将所有这些函数包装到一个完整的状态转换中:

(def next-state (comp pop-queue process-successors next-vertex))

现在最终的算法是这样的:

(defn ss-shortest-path [g start]
  (loop [state (initialize-state g start)]
    (if (empty? (:queue state))
      state
      (recur (next-state state)))))

总而言之，如果您将算法分解成更小的部分，可以单独开发和验证，那么实现算法会容易得多。