Skip to content

Instantly share code, notes, and snippets.

@xfthhxk
Created April 19, 2021 02:04
Show Gist options
  • Save xfthhxk/3810ecfaae8f066e2162ab02108ccadb to your computer and use it in GitHub Desktop.
Save xfthhxk/3810ecfaae8f066e2162ab02108ccadb to your computer and use it in GitHub Desktop.
DFS & BFS in clojure
(ns graph)
(def graph
{:A {:children #{:E :B}
:population 200
:id :A}
:B {:children #{:A :C :E}
:population 300
:id :B}
:C {:children #{:B :D}
:population 150
:id :C}
:D {:children #{:E :C :F}
:population 593
:id :D}
:E {:children #{:B :A :D}
:population 1700
:id :E}
:F {:children #{:D}
:population 9
:id :F}})
(defn graph-search
[coll graph f ctx start]
(loop [coll (conj coll start)
visited #{}
ctx ctx]
(cond
(empty? coll) ctx
(visited (peek coll)) (recur (pop coll) visited ctx)
:else (let [curr (peek coll)
node (graph curr)
coll (into (pop coll) (:children node))
visited (conj visited curr)
ctx (f node ctx)]
(recur coll visited ctx)))))
(def bfs (partial graph-search clojure.lang.PersistentQueue/EMPTY))
(def dfs (partial graph-search []))
(defn collector
[{:keys [population] :as node} ctx]
(+ ctx population))
(bfs graph collector 0 :A)
(dfs graph collector 0 :A)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment