Hello, I'm new in clojure and lisp, and I have problem with making
this code elegant (or at least short).
This is Floyd-Warshall algorithm - very simple algorithm in imperative
form (3 nested for loops).
In clojure the best I've get so far is this monstrosity:
(defn create-graph [nodes distances]
{:nodes nodes :distances distances})
(defn processed [k i j D P]
(let
[S (+ (D [i k] 9999) (D [k j] 9999))]
(if
(< S (D [i j] 9999))
(do
[ (assoc D [i j] S)
(assoc P [i j] k)])
[D P])))
(defn shortest-path-before-k
[k n distances previous]
(loop [i 1 DP [distances previous]]
(if (< i n)
(recur
(+ i 1)
(loop [ j 1
[D P] DP]
(if (< j n)
(recur
(+ j 1)
(processed k i j D P))
[D P])))
DP)))
(defn Floyd-Warshall [G]
(let [n (count (G :nodes))]
(loop [k 1,
distances (G :distances),
previous {}]
(if
(< k n)
(let
[DP (shortest-path-before-k k n
distances previous)]
(recur (+ k 1) (first DP) (second DP)))
[distances previous]))))
;;data for testing
(def G
(create-graph
[0 1 2 3 4 5 6 7 8]
{ [0 1] 1, [0 3] 1,
[1 2] 1,
[2 0] 1,
[3 0] 1, [3 4] 1, [3 6] 1,
[4 5] 1,
[5 3] 1,
[6 3] 1, [6 7] 1,
[7 8] 1,
[8 6] 1}))
(Floyd-Warshall G)
How to do this the Right Way?
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
