# Depth-first search algorithm in clojure

## 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)))

(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
(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.

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])