Dijkstra's algorithm in Clojure

Question

I'm learning Clojure and I'm interested in areas that could be more idiomatic. The main function is below. If you're interested in the whole lib, check out this.

The function operates on a grid, which contains a finite number of cells. A cell is a single point in a grid. neighbours-of will get information about moving one step away from a given cell. The info is in the form of a set of neighbouring cells, and a map giving the cost of moving to a given neighbour.

The loop vars are open-nodes, which is a sorted list of cell/cost pairs, visited-cells, which is a set of cells we don't want to look at again, and parents, which is a map giving the parent of a given cell.

parents is used in create-route to produce a path as a list of cells.

It doesn't currently handle the no-route case, nor is it very optimal. I'm not worried about the first, but if you have hints on the latter then that would be great (that order-by is probably a hotspot for large grids). Mostly I'm interested in what is and is not idiomatic.

(defn navigate-to [grid start dest]
  "provides route from start to dest, not including start"
  (validate-cell grid start)
  (validate-cell grid dest)
  (loop [[{current-cell :cell current-cost :cost} & open-nodes] (list (traversal 0 start))
         visited-cells #{}
         parents {}]
    (if (= dest current-cell) 
      (create-route parents current-cell) 
      (let [;; traversals is list of {:cell :cost}
            {all-neighbours :neighbours traversals :traversals} (neighbours-of
                                                                 grid
                                                                 current-cell)
            unvisited-neighbours (set/difference all-neighbours visited-cells)
            ;; add current route cost to traversals:
            neighbour-total-distances (into {}
                                            (for [[neighbour cost] traversals]
                                              [neighbour (+ current-cost cost)]))
            ;; keep bigger distances
            ;; ...first merge in seen neighbours, keeping higher values
            better-neighbours (->> open-nodes
                                   (filter
                                    (fn [{open-cell :cell current-cost :cost :as open-node}]
                                      (and (contains? unvisited-neighbours open-cell)
                                           (> current-cost
                                              (neighbour-total-distances open-cell)))))
                                   (map #(% :cell))
                                   set)
            updated-open (map (fn [{open-cell :cell current-cost :cost :as open-node}]
                               (if (contains? better-neighbours open-cell)
                                 (traversal (neighbour-total-distances open-cell) open-cell)
                                 open-node))
                              open-nodes)
            updated-parents (reduce #(assoc %1 %2 current-cell) {} better-neighbours)
            ;; ...then create new neighbours
            all-open-cells (set (map #(% :cell) open-nodes))
            new-neighbours (set/difference unvisited-neighbours all-open-cells)
            new-open-nodes (map #(traversal (neighbour-total-distances %) %) new-neighbours)
            new-parents (reduce #(assoc %1 %2 current-cell) {} new-neighbours)]
        (recur (sort-by :cost (concat updated-open new-open-nodes))
               (conj visited-cells current-cell)
               (merge parents updated-parents new-parents))))))

Answer 1

On the idiomatic front this code is excellent. All looks good.

You should use a priority queue to implement Dijkstra's algorithm. It is both far more efficient, and also more concise. I would go so far as to say that the beauty of Dijkstra's algorithm is underpinned by the priority queue data structure (which in turn is underpinned by the concept of a heap). There is much written about these topics, so I won't expand on that here unless it is not clear why. Java has a priority queue implementation that you can use via interop.

You only need a open list of candidates (in a priority queue so you can efficiently take the next minimum distance expansion, efficiently update shorter candidates as discovered, and remove visited nodes), and one map of visited nodes parents (you currently have a set and a parents map, the set is just the keys of parents).

The add/update/remove operations on a priority queue don't need to be implemented by you (they are methods of the datastructure), so less code :)

Answer 2

Some changes I've made prompted by the style guide (https://github.com/bbatsov/clojure-style-guide):

• my docstrings were in the wrong place! They should be before the args [].
• replaced validate-cell (which was a function running through a bunch of asserts) with {:pre [(valid-cell? grid start) (valid-cell? grid dest)]}, which gives better error messages.
• replaced map #(% :cell) with just map :cell since it's a function when applied to maps