Depth-first Search Non-Reursive Implementation in Clojure

Question

I've created a non-recursive dfs implementation in Clojure. I'm using the wikipedia article on dfs as a guide. I'm very new to Clojure and functional programming in general. Any tips to improve readability, make the code more idiomatic, or improve performance would be very helpful. I'm aware there is already question about a recursive dfs implementation in Clojure, but I feel like this code is different enough to warrant a separate post.

(def graph {'a '(b c e) 'b '(a d f) 'c '(a g) 'd '(b) 'e '(a f) 'f '(b e)})

(defn label
  [v discovered]
  (cons v discovered))

(defn get-edges
  [g v]
  (get g v))

(defn labeled?
 [v discovered]
  (cond
    (some #(= v %) discovered) true
    :else false))

(defn build-stack
 [S edges]
  (concat S edges))


(defn dfs
  [g v]
   (loop
    [discovered '() S (cons v ())]
     (cond
      (empty? S) (reverse discovered)
      (labeled? (last S) discovered) (recur discovered (butlast S))
      :else 
       (recur
         (label (last S) discovered) 
         (build-stack (butlast S) (get-edges g (last S))))))) 

Answer 1

From the top ...

• The label function is a synonym for cons, as is build-stack for concat. Drop them.
• The get-edges function doesn't get edges. It gets the neighbouring vertices. Call it neighbours, or some such.

The labeled? function:

• It determines whether the first argument is a member of the collection second argument. So call it something generic like includes?.
• Swap the arguments around, so that it reads more naturally.
• Get rid of the explicit falses and trues. You usually can.

We end up with

(defn includes?
  [coll x]
  (some #(= x %) coll))

Now for the dfs function itself.

• Your local S is, as its name suggests, a stack. Use the other end of it - the front of the list. This gets rid of the slow last and butlast. You can't use Clojure's stack lingo - peek, pop, and conj - because there's a concat in there. So use first, next, and cons instead.
• If you use a vector instead of a list to accumulate discovered, you don't need the final reverse.
• (cons v ()) is just (list v)

The result is

(defn dfs
  [g v]
  (loop [discovered [], S (list v)]
    (cond
      (empty? S) discovered
      (includes? discovered (first S)) (recur discovered (rest S))
      :else (recur
              (conj discovered (first S))
              (concat (neighbours g (first S)) (rest S))))))

---

There's still a performance problem. Whenever it deals with a potentially new vertex, it uses includes? to do a linear search of discovered. For a graph of n vertices, this takes of the order of n^2 time.

The answer is to hold the discovered data twice:

• as a vector, for returning the answer; and
• as a set, for testing for presence.

This roughly doubles the amount of memory required, but reduces time required enormously (roughly to order of n).

I'll leave you to make the necessary changes to dfs.