I attached the source code since indentation disappear when I paste code in mails.
Christophe Grand a écrit : > 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. > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
(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)