Shortest path using breadth first search in clojure

2
votes

I'm representing a tree

     A
    / \
   B   C
  /\    
 D  E

like [A [B [D] [E]] [C]] in a clojure vector. I need to use breadth first search to find the shortest path to a goal. My actual vector looks like this -

["33L" ["32R" ["31L" ["30R" [false]] ["11R" ["01L" ["00R" [true]]] ["00L" [false]]]] ["30L" [false]] ["22L" ["11R" ["01L" ["00R" [true]]] ["00L" [false]]] ["02R" ["01L" ["00R" [true]]] ["00L" [false]]]]] ["31R" ["30L" [false]] ["11L" ["01R" ["00L" [false]]] ["00R" [true]]]] ["22R" ["11L" ["01R" ["00L" [false]]] ["00R" [true]]] ["02L" ["01R" ["00L" [false]]] ["00R" [true]]]]]

All the nodes that end with a true are the ones I'm interested in. There are multiple nodes that end with true. I need to find the shortest path from "33L" which is the first node to the true node. For e.g If you look at the tree at the top and assume D is true and C is true. The shortest path from A that would lead me to a true node is A -> C

I figured out how to print all the nodes like they're being searched using a breadth first algorithm.

(defn bfs [& nodes]
    (if (seq nodes)
        (concat (map first nodes)
            (apply bfs (apply concat (map rest nodes))))))

Running it on my tree gives me - 

("33L" "32R" "31R" "22R" "31L" "30L" "22L" "30L" "11L" "11L" "02L" "30R" "11R" false "11R" "02R" false "01R" "00R" "01R" "00R" "01R" "00R" false "01L" "00L" "01L" "00L" "01L" "00L" "00L" true "00L" true "00L" true "00R" false "00R" false "00R" false false false false true true true)

which is exactly how a breadth first search would skim through the entire data set. However, I can't figure out how I'd find and print the shortest path to a true node. Before you ask me, I've already looked at other breadth first algorithms on stack overflow.

Update:

I've looked at clojure zipper and it solves my problem. However, it's depth first and I need something that's breadth first. Is there a way I could use the z/down, z/left, z/right functions to create a breadth first wrapper around it?

2
algorithmclojuretreebreadth-first-search

2 Answers

1
votes

Breadth first search is a search. Here you return the walk order and if you need a shortest path, then you have to modify a search algorithm implementation to track the path somehow. That means that each node you expand should have the information about the shortest path to it. You can do it manually by passing this information.

Also Clojure has almost built in zippers that allow to walk trees. You may want to use them.

(require '[clojure.zip :as z])

> (def a ["0" ["1L" [false] [false]] ["1R" [true]]])

> ;create a zipper where vector? is a branch and (vec (rest %)) are
> ;childrens
> (def ztree (z/zipper vector? (comp vec rest) nil a))
> ztree
[["0" ["1L" [false] [false]] ["1R" [true]]] nil]
> (vector? ztree) ;zipper is vector of your original vector and some aaditional info
true
> (meta ztree) ;here are the functions
{:zip/make-node nil, 
 :zip/children #<core$comp$fn__4192 clojure.core$comp$fn__4192@59bdcbda>,   
 :zip/branch? #<core$vector_QMARK_ clojure.core$vector_QMARK_@319449e4>}
> (-> ztree z/down z/down z/up z/right z/down) ;walk the tree
[[true] 
 {:l [], 
  :pnodes [["0" ["1L" [false] [false]] ["1R" [true]]] ["1R" [true]]],
  :ppath {:l [["1L" [false] [false]]], 
          :pnodes [["0" ["1L" [false] [false]] ["1R" [true]]]], 
          :ppath nil, 
          :r nil}, 
  :r nil}]

So you can see, how I manually walk a tree and zipper structure is a vector with current branch or node at first place and a map with left and right siblings in :l and :r, path to this node (not walk order) in :pnodes, parent zipper structure for this node in :ppath.

So is you use zippers then your path is tracked in :pnodes.

P.S. After your comment

If you need the implementation then here is like from the textbook:

(defn queue [& vals]
  (apply merge (clojure.lang.PersistentQueue/EMPTY) vals))

(defn bfs [tree]
  (loop [expanding (queue {:node tree
                           :path []})]
    (if (empty? expanding)
      nil
      (let [{[val & childs] :node
             p :path}
            (peek expanding)
            curr-path (conj p val)]
        (if (true? val)
          p
          (recur
           (apply merge (pop expanding)
                  (map #(hash-map :node %
                                  :path curr-path)
                       childs))))))))

> (bfs your-vector)
["33L" "31R" "11L" "00R"]

But looks like it's better to try to solve this yourself.

P.P.S. You can use zippers to walk as you want. Just modify your code to use zippers made above your tree and you will get both, walk order and shortest path.

0
votes

@JustAnotherCurious has the right answer, but I would have phrased the implementation of the BFS slightly differently, for a more idiomatic style (using when-let, instead of if, nil and let, and using nil-punning instead of empty? for instance). I also hid the data representation of the tree behind an interface, to make that easier to change, should it become necessary:

(defn goal? [[val]]
  (true? val))

(defn leaf? [tree]
  (= 1 (count tree)))

(defn tree-val [tree]
  (first tree))

(defn children [tree]
  (rest tree))

(defn queue [& vals]
  (apply conj clojure.lang.PersistentQueue/EMPTY vals))

(defn bfs [root]
  (loop [q (queue {:tree root :path []})]
    (when-let [{:keys [tree path]} (peek q)]
      (cond
        (goal? tree) path
        (leaf? tree) (recur (pop q))
        :else
        (let [new-path (conj path (tree-val tree))
              wrap     (fn [t] {:tree t :path new-path})]
          (recur (->> (children tree)
                      (map wrap)
                      (apply conj (pop q)))))))))