(defn dependency-list
"Similar to a topological sort, this returns a vector of sets. The
set of nodes at index 0 are independent. The set at index 1 depend
on index 0; those at 2 depend on 0 and 1, and so on. Those withing
a set have no mutual dependencies. Assume the input graph (which
much be acyclic) has an edge a->b when a depends on b."
[g]
(let [step (fn [d]
(let [update (fn [n]
(inc (apply max -1 (map d (get-neighbors g n)))))]
(into {} (map (fn [[k v]] [k (update k)]) d))))
counts (fixed-point (zipmap (:nodes g) (repeat 0))
step
(inc (count (:nodes g)))
=)]
(fold-into-sets counts)))
Vars in
clojure.contrib.graph/dependency-list:
defn
let
Used in 0 other vars
Source
clojure/contrib/graph.clj:190
top
Comments top
No comments for dependency-list. Log in to add a comment.