Skip to content

Instantly share code, notes, and snippets.

@Netpilgrim
Created September 3, 2011 18:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Netpilgrim/1191537 to your computer and use it in GitHub Desktop.
Save Netpilgrim/1191537 to your computer and use it in GitHub Desktop.
Pre condition ignored
(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