Implemented depth-first traversal.

davidrupp · Mar 23, 2013 · 381c4e4 · 381c4e4
1 parent 24b66e9
commit 381c4e4
Show file tree

Hide file tree

Showing 2 changed files with 21 additions and 8 deletions.
diff --git a/src/graffy/core.clj b/src/graffy/core.clj
@@ -7,7 +7,8 @@
   (all-edges [this])
   (neighbors [this n])
   (neighbor-list [this n])
-  (dft [this n]))
+  (dft [this n])
+  (bft [this n]))
 
 (defn make-graph []
   (let [state (atom {})]
@@ -41,6 +42,16 @@
               (if (contains? (into #{} acc) nxt)
                 (recur acc rst)
                 (recur (conj acc nxt) (apply list (concat (neighbor-list this nxt) rst))))))))
+      ;; N.B.: bft is exactly the same as dft, except for the order of the concat in the tail call
+      (bft [this n]
+        (loop [acc [] stack (list n)]
+          (if (zero? (count stack))
+            acc
+            (let [nxt (peek stack)
+                  rst (pop stack)]
+              (if (contains? (into #{} acc) nxt)
+                (recur acc rst)
+                (recur (conj acc nxt) (apply list (concat rst (neighbor-list this nxt))))))))) ; this is the only line that differs from dst
       (toString [_]
         (.toString @state)))))
 
diff --git a/test/graffy/core_test.clj b/test/graffy/core_test.clj
@@ -33,16 +33,18 @@
                 (add-edge :a :b))]
       (is (= #{[:a :b] [:b :a]} (into #{} (all-edges g)))))))
 
-(deftest test-dft
-  (testing "depth-first traversal"
+(deftest test-traversal
+  (testing "depth-first, breadth-first traversal"
     (let [g (-> (make-graph)
                 (add-edge 0 1)
                 (add-edge 0 2)
-                (add-edge 0 6)
                 (add-edge 0 5)
-                (add-edge 5 3)
-                (add-edge 5 4)
+                (add-edge 0 6)
                 (add-edge 3 4)
-                (add-edge 4 6))]
+                (add-edge 4 6)
+                (add-edge 5 3)
+                (add-edge 5 4))]
       (is (= [0 1 2 5 3 4 6] (dft g 0)))
-      (is (= [5 0 1 2 6 4 3] (dft g 5))))))
+      (is (= [5 0 1 2 6 4 3] (dft g 5)))
+      (is (= [0 1 2 5 6 3 4] (bft g 0)))
+      (is (= [5 0 3 4 1 2 6] (bft g 5))))))