Created
March 4, 2013 11:05
-
-
Save MasseR/5081569 to your computer and use it in GitHub Desktop.
Topological sorting
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| (ns topological.core) | |
| (def testlist | |
| [{:depends #{2} :provides 3} | |
| {:depends #{2} :provides 1} | |
| {:depends #{} :provides 2} | |
| {:depends #{1} :provides 4} | |
| ]) | |
| (defn free-nodes [xs] | |
| (let [edges (apply clojure.set/union (map :depends xs))] | |
| (filter #(not (contains? edges (:provides %1))) xs))) | |
| (defn modify-graph [node input] | |
| (let [nodeid (:provides node) | |
| modify (fn [graph-node] | |
| (if (contains? (:depends graph-node) nodeid) | |
| (assoc graph-node :depends (disj (:depends graph-node) nodeid)) | |
| graph-node))] | |
| (map modify input))) | |
| (defn subsort [input free acc] | |
| (if (empty? free) | |
| acc | |
| (let [node (first free) | |
| output (cons node acc) | |
| new-graph (modify-graph node (filter #(not (= node %1)) input)) | |
| new-stack (free-nodes new-graph)] | |
| (recur new-graph new-stack output)))) | |
| (defn tsort [xs] | |
| (subsort xs (free-nodes xs) [])) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment