1.2.0 permalink Arrow_down_16x16

component-graph

clojure.contrib.graph

  • (component-graph g)
  • (component-graph g sccs)
Given a graph, perhaps with cycles, return a reduced graph that is acyclic.
Each node in the new graph will be a set of nodes from the old.
These sets are the strongly connected components. Each edge will
be the union of the corresponding edges of the prior graph.

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:133 top

(defn component-graph
  "Given a graph, perhaps with cycles, return a reduced graph that is acyclic.
   Each node in the new graph will be a set of nodes from the old.
   These sets are the strongly connected components.  Each edge will
   be the union of the corresponding edges of the prior graph."
  ([g]
     (component-graph g (scc g)))
  ([g sccs]
     (let [find-node-set (fn [n]
                           (some #(if (% n) % nil) sccs))
           find-neighbors (fn [ns]
                            (let [nbs1 (map (partial get-neighbors g) ns)
                                  nbs2 (map set nbs1)
                                  nbs3 (apply union nbs2)]
                              (set (map find-node-set nbs3))))
           nm (into {} (map (fn [ns] [ns (find-neighbors ns)]) sccs))]
       (struct directed-graph (set sccs) nm))))
Vars in clojure.contrib.graph/component-graph: defn let set struct
Used in 0 other vars

Comments top

No comments for component-graph. Log in to add a comment.