(defn stratification-list
"Similar to dependency-list (see doc), except two graphs are
provided. The first is as dependency-list. The second (which may
have cycles) provides a partial-dependency relation. If node a
depends on node b (meaning an edge a->b exists) in the second
graph, node a must be equal or later in the sequence."
[g1 g2]
(assert (= (-> g1 :nodes set) (-> g2 :nodes set)))
(let [step (fn [d]
(let [update (fn [n]
(max (inc (apply max -1
(map d (get-neighbors g1 n))))
(apply max -1 (map d (get-neighbors g2 n)))))]
(into {} (map (fn [[k v]] [k (update k)]) d))))
counts (fixed-point (zipmap (:nodes g1) (repeat 0))
step
(inc (count (:nodes g1)))
=)]
(fold-into-sets counts)))
Used in 0 other vars
Source
clojure/contrib/graph.clj:207
top
Comments top
No comments for stratification-list. Log in to add a comment.