aria42 a écrit :
> I decided to code Tarjan's Algorithm for finding all the
> strongly connected components of a graph (http://en.wikipedia.org/wiki/
> Tarjan's_strongly_connected_components_algorithm). I've written this
> code in Java and it's about a 100 lines. Sadly, my clojure version is
> about a 100 lines too. I am more-or-less translating my java code
> (which is more or less translated from Psuedo-Code), but I don't see a
> good way to make this problem more functional, but this is probably
> due to my imperative roots.
>
I don't think that using one hashmap to store, for each node, its index,
low-index, its on-stack state, its neighbours etc. is a good choice: you
should try to store these data into separate hashmaps — keyed on nodes.
Here is my attempt, translated from the wikipedia's pseudocode.
(defn tarjan [e v0]
(let [tarjan-helper
(fn self [v s indices lowlinks index sccs]
(let [main ; the body of the forall loop
(fn [[s indices lowlinks index sccs :as state] vp]
(cond
(nil? (indices vp)) ; Was successor v' visited?
(let [[s indices lowlinks index sccs]
(apply self vp state)
lowlinks (assoc lowlinks v (min (lowlinks v)
(lowlinks vp)))]
[s indices lowlinks index sccs])
(some #{vp} s) ; Is v' on the stack? (crude)
(let [lowlinks (assoc lowlinks v (min (lowlinks v)
(lowlinks vp)))]
[s indices lowlinks index sccs])
:else state))
; the forall loop is now a reduction on successors
[s indices lowlinks index sccs]
(reduce main [(cons v s)
(assoc indices v index)
(assoc lowlinks v index)
(inc index)
sccs] (e v))]
(if (= (lowlinks v) (indices v))
; conjoin the newly found scc to sccs and
; remove its vertices from the stack
(let [[a b] (split-with #(not= v %) s)
sccs (conj sccs (concat a [v]))]
[(rest b) indices lowlinks index sccs])
[s indices lowlinks index sccs])))]
(last (tarjan-helper v0 nil {} {} 0 []))))
(tarjan {:a [:b :c] :b [:c] :c [:a] :d [:e] :e [:a]} :e)
; returns [(:c :b :a) (:e)]
Christophe
--~--~---------~--~----~------------~-------~--~----~
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
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
-~----------~----~----~----~------~----~------~--~---
