If I understand you correctly, this is known as the "union-find" problem.
All you care about is whether two items are in the same component of the
graph. The key here is to keep track of two maps, one map from each item
to a "canonical item" in its component, and one map from each canonical
item to a list of all other items in its component. From a performance
standpoint, the most important thing is to make sure you always merge the
smaller component into the larger component.
Here's how I'd do it:
(def empty-component-graph {:keys->canonical {}, :canonical->components {}})
(defn register-same-as [{:keys [keys->canonical
canonical->components]
:as component-graph}
key1 key2]
(let [canonical1 (keys->canonical key1 key1)
canonical2 (keys->canonical key2 key2)]
(if (= canonical1 canonical2) component-graph ; already the same
(let [component1 (canonical->components canonical1 [canonical1])
component2 (canonical->components canonical2 [canonical2])
;swap if necessary so component1 is the smaller component
[canonical1 canonical2 component1 component2] (if (<= (count
component2) (count component2))
[canonical1
canonical2 component1 component2]
[canonical2
canonical1 component2 component1])
new-keys->canonical (into keys->canonical (for [item
component1] [item canonical2]))
new-canonical->components (-> canonical->components
(dissoc canonical1)
(assoc canonical2 (into component2
component1)))]
{:keys->canonical new-keys->canonical, :canonical->components
new-canonical->components}))))
(defn same-as? [{:keys [keys->canonical]} key1 key2]
(= (keys->canonical key1 key1) (keys->canonical key2 key2)))
To use:
(def components
(-> empty-component-graph
(register-same-as :x :a)
(register-same-as :a :b)
(register-same-as :c :y)
(register-same-as :y :b)))
(same-as? components :x :b)
--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
