Advertisement
Guest User

Untitled

a guest
Dec 19th, 2019
254
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. (defn bfs
  3.     "Return `graph` with each vertex's `:parent` property updated."
  4.     [graph start]
  5.     (loop [discovered clojure.lang.PersistentQueue/EMPTY
  6.                discovered-map {(:key start) true}
  7.                u start
  8.          new-graph graph]
  9.         (if (nil? u)
  10.       ;; Base case: all vertices have been explored
  11.             new-graph
  12.       ;; Queue any of the current node's neighbors that haven't been
  13.       ;; discovered
  14.             (let [neighbor-keys
  15.                     (filter #(not (contains? discovered-map %))
  16.                               (:connections u))
  17.                     neighbors
  18.                     (map #(assoc
  19.                    (get-vertex graph %) :parent (:key u))
  20.                            neighbor-keys)
  21.                     new-discovered
  22.                     (as-> discovered ds
  23.                         (into clojure.lang.PersistentQueue/EMPTY
  24.                     (concat ds neighbors)))]
  25.         ;; Further processing of `u` or the `(u, v)` edges can go here
  26.         (println (str "Exploring vertex " (:key u) ", neighbors: "
  27.                       (join ", " neighbor-keys)))        
  28.         ;; Proceed to exploring the next vertice, adding `u`'s
  29.         ;; neighbors to the discovered pile
  30.         (recur
  31.                  (pop new-discovered)
  32.                  (into discovered-map
  33.                            (map #(hash-map % true) neighbor-keys))
  34.                  (peek new-discovered)
  35.          ;; Update each of `u`'s neighbors to show `u` is the parent
  36.          (reduce #(assoc-in %1 [:vertices %2 :parent] (:key u))
  37.                  new-graph
  38.                  neighbor-keys))))))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement