Learning Clojure with TDD and Dijkstra

September 21, 2013

One of my recent goals has been to better understand functional programming. As a sub goal to this i wanted to first learn the basics of the Clojure language. To accomplish this i needed a small problem to solve, due to a recent interest in directed graphs i decided to try implementing Dijsktra’s shortest distance algorithm.

For this first step i wasn’t to concerned to doing things the “Clojure Way”, i just explored the API looking for the best fit way to accomplish what i wanted. So lets start with the first test…

Find the shortest distance between two directly connected vertex

This was the simplest test i could think of to which i could pass the test by returning the expected distance of the edge.

(deftest find-shortest-distance-between-two-connected-vertex
    (is (= 10 (shortest-distance graph :a :b))))

Find the shortest distance between two vertices which are connected via another vertex

This test forced my hand into implementing the ability to follow the first shortest path and then accumulate the distances for any new vertices that could be reached. I didn’t implement looking for the next shortest path as i felt it was too much. For now i was able to hard code the edge that was to be followed.

(deftest find-shortest-distance-between-two-vertices-which-are-connected-via-another-vertex
    (is (= 20 (shortest-distance graph :a :f))))

Find the shortest distance between two vertices which are connected via many other vertices

This test now forced my hand to implement the ability to find the next shortest path to follow and the functionality to follow it to the end of the graph. I still feel implementing the two together was a bit much of a leap, i would have liked faster feedback by implementing each bit separately.

(deftest find-shortest-distance-between-two-vertices-which-are-connected-via-many-other-vertices
    (is (= 30 (shortest-distance graph :a :c))))

Find the shortest distance between two vertices which are connected via many other vertices and has many possible routes

So far i was relying on the happy path of everything being on the shortest path through the graph. The next step was to make sure that it was finding the shortest path if there were many combinations of routes. This was done by making sure that any new distance to a vertex is less than the current distance before adding it to the output.

(deftest find-shortest-distance-between-two-vertices-which-are-connected-via-many-other-vertices-and-has-many-possible-routes
    (is (= 60 (shortest-distance graph :a :d))))

Finally checking some of the edge cases i could think of

The simple edge cases i could think of were, the inability to reach a end vertex and the end vertex being the start point

(deftest find-shortest-distance-between-two-vertices-which-are-not-connected-is-infinate
    (is (= inf (shortest-distance graph :a :e))))

(deftest find-shortest-distance-starting-and-ending-at-the-same-vertex
    (is (= 100 (shortest-distance graph :a :a))))

The Graph

(def graph {
    :a { :a inf :b 10  :c inf :d 80  :e inf :f inf :g 90  :h inf }
    :b { :a inf :b inf :c inf :d inf :e inf :f 10  :g inf :h inf }
    :c { :a inf :b inf :c inf :d 50  :e inf :f 50  :g inf :h 20  }
    :d { :a inf :b 10  :c inf :d inf :e inf :f inf :g 20  :h inf }
    :e { :a inf :b 50  :c inf :d inf :e inf :f inf :g 30  :h inf }
    :f { :a inf :b inf :c 10  :d 40  :e inf :f inf :g inf :h inf }
    :g { :a 20  :b inf :c inf :d inf :e inf :f inf :g inf :h inf }
    :h { :a inf :b inf :c inf :d inf :e inf :f inf :g inf :h inf }
})

The Code

Finally this is the resulting code from the above tests.

(def inf (Integer/MAX_VALUE))

(defn find-next-closest-vertex [shortest-distance-so-far unvisited-vertices]
    (reduce
        (fn [[lowest-vertex-name lowest-vertex-distance], vertex-name]
            (let [vertex-distance (shortest-distance-so-far vertex-name)]
                (if (< vertex-distance lowest-vertex-distance)
                    [vertex-name vertex-distance]
                    [lowest-vertex-name lowest-vertex-distance])))
        [(first unvisited-vertices) (shortest-distance-so-far (first unvisited-vertices))]
        unvisited-vertices))

(defn total-distance-so-far-to-vertex [shortest-distances-so-far current-vertex next-vertex-name distance-to-here]
    (assoc
     shortest-distances-so-far
      next-vertex-name
        (let [
         distance-to-next-vertex (+ distance-to-here (current-vertex next-vertex-name))
         curret-distance-to-vertex (shortest-distances-so-far next-vertex-name)]
          (if
         (< distance-to-next-vertex curret-distance-to-vertex)
         distance-to-next-vertex
         curret-distance-to-vertex))))

(defn recalculate-distances [shortest-distances-so-far unvisited-vertices distance-to-here current-vertex]
  (reduce
   (fn [new-shortest-distances-so-far, next-vertex-name] (total-distance-so-far-to-vertex new-shortest-distances-so-far current-vertex next-vertex-name distance-to-here))
   shortest-distances-so-far
    unvisited-vertices))

(defn calculate-shortest-distances-to-all-verticies [graph shortest-distances-so-far unvisited-vertices]
 (let [verticies-left-to-visit (count unvisited-vertices)]
   (if (= verticies-left-to-visit 0)
        shortest-distances-so-far
       (let [
            [next-closest-vertex-name next-closest-vertex-distance] (find-next-closest-vertex shortest-distances-so-far unvisited-vertices)
                next-cloesest-vertex (graph next-closest-vertex-name)
              new-shortest-distances-so-far (recalculate-distances shortest-distances-so-far unvisited-vertices next-closest-vertex-distance next-cloesest-vertex)
              new-unvisited-verticies (remove (fn [k] (= k next-closest-vertex-name)) unvisited-vertices)]
             (recur graph new-shortest-distances-so-far new-unvisited-verticies)))))

(defn shortest-distance [graph start end]
    (let [starting-vertex (graph start) unvisited-verticies (keys graph)]
        ((calculate-shortest-distances-to-all-verticies graph starting-vertex unvisited-verticies) end)))