Created
September 3, 2011 18:00
-
-
Save Netpilgrim/1191537 to your computer and use it in GitHub Desktop.
Pre condition ignored
This file contains 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
(defrecord DirectedGraph [vertices edges weights] | |
;; A directed graph: 'vertices' is a sorted set of vertices, 'edges' is a map | |
;; from vertices to a sorted set of adjacent vertices, 'weights' is a map from | |
;; edges given as vertex tuple [from to] to weights. | |
Graph | |
(set-vertex [_ v] | |
(DirectedGraph. (conj vertices v) | |
(conj edges [v (sorted-set)]) | |
weights)) | |
(set-edge [this edge] | |
(set-edge this edge nil)) | |
(set-edge [_ [from to] weight] | |
{:pre [(some #{from} vertices) | |
(some #{to} vertices)]} | |
(DirectedGraph. vertices | |
(update-in edges [from] conj to) | |
(conj weights [[from to] weight]))) | |
(find-paths [this from to] | |
(find-paths this from to (constantly true))) | |
(find-paths [_ from to pred] | |
{:pre [(some #{from} vertices) | |
(some #{to} vertices)]} | |
(letfn [(children [[path visited v]] | |
(map (fn [child] | |
[(conj path [v child]) | |
(conj visited child) | |
child]) | |
(->> (edges v) | |
(remove visited) | |
(filter #(pred (weights [v %]))))))] | |
(map first (filter (comp #{to} peek) | |
(tree-seq (constantly true) | |
children | |
[[] #{from} from])))))) | |
;; Here the pre conditions are ignored: | |
(def where-are-the-vertices | |
(-> (DirectedGraph. (sorted-set) {} {}) | |
(set-edge [:x :y] nil))) | |
(defn set-edge2 [graph [from to] weight] | |
{:pre [(some #{from} (:vertices graph)) | |
(some #{to} (:vertices graph))]} | |
(DirectedGraph. (:vertices graph) | |
(update-in (:edges graph) [from] conj to) | |
(conj (:weights graph) [[from to] weight]))) | |
;; Here the pre conditions work: | |
(set-edge2 where-are-the-vertices [:foo :bar] nil) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment