1.2.0 permalink Arrow_down_16x16

dependency-list

clojure.contrib.graph

  • (dependency-list g)
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.

0 Examples top

Log in to add / edit an example.

See Also top

Log in to add a see also.

Plus_12x12 Minus_12x12 Source clojure/contrib/graph.clj:190 top

(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

Comments top

No comments for dependency-list. Log in to add a comment.