Woah formatting! :-)
This is just a formatting cleanup...
Mostly I pressed ctrl+alt+q in emacs.
I also removed some commas and made things more uniform in a couple
places
---------------
(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))
[(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}))
--------
For readability's sake, you can probably do some stuff as well, by
making it less nested.
One way to do this is to 'unroll' it using let statements, so that it
has a more imperative look...
You don't have to nest the loop inside the recur, you can bind the
result in a let then pass it to recur.
(Only nest statements that make sense to nest... things that serve a
similar purpose).
You can also break this sort of thing up more by using lexically bound
functions.
Another thing is that I like to stick to dashed-out-lowercase for the
lisp code and only use CamelCase when I'm referring to Java calls. I
personally probably wouldn't name a function Floyd-Warshall, but
rather floyd-warshall (but that is somewhat a relic of my common lisp
sensibilities). Same with the variables in the loops, I would probably
stick to one case.
But anyway, I didn't do much, i'm sure someone else can do better! :)
On Sep 14, 5:48 pm, ajuc <aju...@gmail.com> wrote:
> 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 clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
