(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))))
Used in 0 other vars
Source
clojure/contrib/graph.clj:133
top
Comments top
No comments for component-graph. Log in to add a comment.