Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- (defn bfs
- "Return `graph` with each vertex's `:parent` property updated."
- [graph start]
- (loop [discovered clojure.lang.PersistentQueue/EMPTY
- discovered-map {(:key start) true}
- u start
- new-graph graph]
- (if (nil? u)
- ;; Base case: all vertices have been explored
- new-graph
- ;; Queue any of the current node's neighbors that haven't been
- ;; discovered
- (let [neighbor-keys
- (filter #(not (contains? discovered-map %))
- (:connections u))
- neighbors
- (map #(assoc
- (get-vertex graph %) :parent (:key u))
- neighbor-keys)
- new-discovered
- (as-> discovered ds
- (into clojure.lang.PersistentQueue/EMPTY
- (concat ds neighbors)))]
- ;; Further processing of `u` or the `(u, v)` edges can go here
- (println (str "Exploring vertex " (:key u) ", neighbors: "
- (join ", " neighbor-keys)))
- ;; Proceed to exploring the next vertice, adding `u`'s
- ;; neighbors to the discovered pile
- (recur
- (pop new-discovered)
- (into discovered-map
- (map #(hash-map % true) neighbor-keys))
- (peek new-discovered)
- ;; Update each of `u`'s neighbors to show `u` is the parent
- (reduce #(assoc-in %1 [:vertices %2 :parent] (:key u))
- new-graph
- neighbor-keys))))))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement