7
\$\begingroup\$

Context

As an exercise for myself (I'm learning clojure). I wanted to implement the Depth-first search algorithm.

How I did it

Using recursion

(def graph 
  {:s {:a 3 :d 4}
   :a {:s 3 :d 5 :b 4}
   :b {:a 4 :e 5 :c 4} 
   :c {:b 4} 
   :d {:s 4 :a 5 :e 2} 
   :e {:d 2 :b 5 :f 4} 
   :f {:e 4 :g 1}})

(def stack [[:s]])

(def goal :g)

(defn cost [Graph start goal]
  (goal (start Graph)))

(defn hasloop? [path]
  (not (= (count path) (count (set path)))))

(defn atgoal? [path]
  (= goal (last path)))

(defn solved? [stack]
  (some true? (map atgoal? stack)))

(defn addtopath [path node]
    (conj path node))

(defn pop* [stack]
    (last stack))


(defn findpath [stack]
    (if (not (solved? stack))
        (let [first* (pop* stack) l (last first*) ] 
                (findpath (drop-last 
                    (remove hasloop?  (lazy-cat
                                            (map #(addtopath first* %) 
                                            (keys (l graph))) stack)))))
        [(first stack)]))

How to use

(findpath stack)

Question

I'm really really interested in how this code can be improved. Both in readability, efficiency and performance.

\$\endgroup\$
5
\$\begingroup\$

I wrote the modified version of your findpath function using recursion:

(defn- dfs
  [graph goal]
  (fn search
    [path visited]
    (let [current (peek path)]
      (if (= goal current)
        [path]
        (->> current graph keys
             (remove visited)
             (mapcat #(search (conj path %) (conj visited %))))))))

(defn findpath
  "Returns a lazy sequence of all directed paths from start to goal
  within graph."
  [graph start goal]
  ((dfs graph goal) [start] #{start}))

Instead of using your hasloop? function, my search function keeps track of visited nodes in order to avoid visiting the same node twice. It seems to work for your settings:

user> (def graph 
  {:s {:a 3 :d 4}
   :a {:s 3 :d 5 :b 4}
   :b {:a 4 :e 5 :c 4} 
   :c {:b 4} 
   :d {:s 4 :a 5 :e 2} 
   :e {:d 2 :b 5 :f 4} 
   :f {:e 4 :g 1}})
user> (findpath graph :s :g)
([:s :a :b :e :f :g] [:s :a :d :e :f :g] [:s :d :a :b :e :f :g] [:s :d :e :f :g])
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.