5
\$\begingroup\$

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))))))) 
\$\endgroup\$
  • 1
    \$\begingroup\$ "but I feel like this code is different enough to warrant a separate post." Don't worry, you almost have to copy the question verbatim to make it a duplicate on Code Review. As long as the code is yours, it doesn't matter whether it solves the same problem others have already done a hundred times. \$\endgroup\$ – Mast Aug 20 '17 at 12:19
  • 2
    \$\begingroup\$ do you want to implement dfs to learn clojure? if you want to make thing done, you can use tree-seq \$\endgroup\$ – minhtuannguyen Aug 26 '17 at 16:41
  • \$\begingroup\$ Yes, I'd like to learn Clojure. I'll look at tree-seq. Thanks \$\endgroup\$ – cwithmichael Aug 26 '17 at 18:47
2
\$\begingroup\$

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.

\$\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.