public
Last active

Dependency graph iteration. (Part of lib to come soon)

  • Download Gist
graph.clj
Clojure
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
(defn iterate
([graph]
(iterate graph {}))
([graph state]
(iterate graph state
(->> graph
:topo-sort
(remove nil?)
first
fnk->key)))
([graph state start-key]
(let [start-fn (key->fnk graph start-key)
dependents (deps/transitive-dependents graph start-fn)
deps (conj (set (mapcat (partial deps/transitive-dependencies graph)
(conj dependents start-fn )))
start-fn)
calc? (conj (union deps dependents) start-fn)
calc-topo (filter calc? (:topo-sort graph))]
(-> state
(iterate* calc-topo update-deps deps)
(iterate* calc-topo update-dependents dependents)))))
sample.clj
Clojure
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
(def g
{:a 1
:d/b 2
:b/a (fnk [a] (* a 7))
:x (fnk [b/a [d/b 2] [c 3]] (+ b/a d/b c))})
 
(def cg (compile-graph g))
 
(iterate cg)
; => {:x 12, :b/a 7, :d/b 2, :a 1}
 
(iterate cg {:a 7 :x 15} :a)
; => {:d/b 2, :b/a 49, :x 54, :a 7}
 
(iterate cg {:b/a 11 :a 7 :x 15} :x)
; => {:d/b 2, :x 15, :a 7, :b/a 11}
visualized.svg
XML
1
<?xml version="1.0" encoding="UTF-8" standalone="no"?><svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" contentScriptType="text/ecmascript" width="610" zoomAndPan="magnify" contentStyleType="text/css" height="110" preserveAspectRatio="xMidYMid meet" overflow="visible" version="1.0"><defs><marker refX="10" refY="5" markerUnits="strokeWidth" orient="auto" id="lacij-end-arrow-marker" markerHeight="10" viewBox="0 0 10 10" preserveAspectRatio="xMidYMid meet" markerWidth="14"><polyline points="0,0 10,5 0,10 1,5"/></marker></defs><g id="graph0"><g><g><path style=" stroke: #000000; stroke-width: 1; " d=" M505.0,55.0 L305.0,85.0 M305.0,85.0 Z"/><line y2="85.0" marker-end="url(#lacij-end-arrow-marker)" style=" stroke: #000000; stroke-width: 1; " x1="305.0" x2="105.0" y1="85.0"/></g><text x="305.0" y="70.0" style=" dominant-baseline: central; " text-anchor="middle"/></g><g id=":x-:b/a"><line y2="25.0" marker-end="url(#lacij-end-arrow-marker)" style=" stroke: #000000; stroke-width: 1; " x1="505.0" x2="355.0" y1="35.0"/></g><g id=":b/a-:a"><line y2="25.0" marker-end="url(#lacij-end-arrow-marker)" style=" stroke: #000000; stroke-width: 1; " x1="255.0" x2="105.0" y1="25.0"/></g><g id="x" transform="translate(505.0, 35.0)"><rect style=" fill: white; stroke: black; " width="100" height="40"/><text x="50" font-size="12" y="20" style=" dominant-baseline: central; " text-anchor="middle">:x</text></g><g id="a" transform="translate(5.0, 5.0)"><rect style=" fill: white; stroke: black; " width="100" height="40"/><text x="50" font-size="12" y="20" style=" dominant-baseline: central; " text-anchor="middle">:a</text></g><g id="b" transform="translate(5.0, 65.0)"><rect style=" fill: white; stroke: black; " width="100" height="40"/><text x="50" font-size="12" y="20" style=" dominant-baseline: central; " text-anchor="middle">:d/b</text></g><g id="a" transform="translate(255.0, 5.0)"><rect style=" fill: white; stroke: black; " width="100" height="40"/><text x="50" font-size="12" y="20" style=" dominant-baseline: central; " text-anchor="middle">:b/a</text></g></g></svg>

Now with cached :topo-sort in compile-graph. (Part of lib to come soon)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.