current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 7 down vote favorite
2

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.

share|improve this question
up vote 5 down vote accepted

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])
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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