As an alternative, if we're willing to rebuild the entire hierarchy, not just the subgraph that's affected by the underivation, we can just do this:
(defn easy-underive [h child parent] (let [oldParents (:parents h) childsParents (disj (clojure.set/union #{} (child oldParents)) parent) newParents (if (not-empty childsParents) (assoc oldParents child childsParents) (dissoc oldParents child)) derivation-seq (flatten (map #(cons (key %) (interpose (key %) (val %))) (seq newParents)))] (reduce #(apply derive (cons %1 %2)) (make-hierarchy) (partition 2 derivation-seq)))) It's less efficient, because it tosses out all of the information in the ancestor and descendant sets. But it is a good deal simpler -- 10 lines of code instead of 60 or so. For small hierarchies this would be fine. If anyone were to make large hierarchies which had to be modified efficiently, though, I think something like in the first message would be required. On Jun 15, 4:29 pm, Rob Lachlan <robertlach...@gmail.com> wrote: > Oh God. What broken formatting. Sorry about that. > > On Jun 15, 4:24 pm, Rob Lachlan <robertlach...@gmail.com> wrote: > > > > > I think that the underive function for removing hierarchy > > relationships between keywords is broken. I'll illustrate with an > > example and describe what I think the problems are. I've got some > > code for a function which (I hope!) performs underive correctly, and > > I'd love it if people had a look. > > > Consider a hierarchy with child-parent relationships: > > > :c -> :p1, :c -> :p2, :p1 -> :a1, :p1 -> :a2, :p2 -> :a2 > > > Which I'll illustrate with the world's worst ascii art: > > > a1 a2 > > | / | > > | / | > > | / | > > p1 p2 > > | / > > | / > > | / > > c > > > ; creating this hierarchy: > > user> (def h (reduce #(apply derive (cons %1 %2)) (make-hierarchy) > > [[:p1 :a1] [:p1 :a2] [:p2 :a2] [:c :p2] [:c :p1]])) > > #'user/h > > user> h > > {:parents {:c #{:p1 :p2}, :p2 #{:a2}, :p1 #{:a2 :a1}}, :ancestors {:c > > #{:p1 :p2 :a2 :a1}, :p2 #{:a2}, :p1 #{:a2 :a1}}, :descendants {:p1 > > #{:c}, :p2 #{:c}, :a2 #{:p1 :p2 :c}, :a1 #{:p1 :c}}} > > > Now the underive: > > > user> (underive h :c :p1) > > {:parent {:c #{:p2}, :p2 #{:a2}, :p1 #{:a2 :a1}}, :ancestors {:c > > #{:p2}, :p2 #{:a2}, :p1 #{:a2 :a1}}, :descendants {:p1 #{}, :p2 > > #{:c}, :a2 #{:p1 :p2}, :a1 #{:p1}}} > > > Problems: > > > Most seriously, it is incorrect: :c should still show up as a > > descendant of > > :a2, since :c is a child of :p2, and :p2 a child of :a2. Note that > > the > > parent map is correct, so it is the ancestor and descendant maps which > > are > > inconsistent. > > > Also, notice that the key for the parent map has changed from :parents > > to > > :parent, which causes calls to the parents function to return nil. > > > Also, keys which map to empty sets are left in each of the maps > > (parents, > > descendants and ancestors), with the result that equality tests could > > fail > > in some cases in which they would be true. > > > Potential fix, and request for code review: > > > I've written an underive-new function which appears to fix these > > problems, > > at least in the tests that I've done. > > >http://pastebin.com/eRiz5ihw > > > My approach is to identify the sets of tags in the hierarchy whose > > ancestors > > or descendants may be affected, remove their ancestor or descendant > > mappings, > > then rebuild them. In a call (underive h child parent), the child and > > all > > the child's descendants will need to have their ancestor mappings > > fixed. > > Similarly, the parent and all of the parent's ancestors will need to > > have > > their descendant mappings rebuilt. > > > (As an aside, the problem here is that our hierarchy can be a DAG > > rather > > a tree, because multiple inheritance is allowed. And therefore, for > > any > > ancestor/descendant relationship it's comparatively expensive to > > determine > > whether a particular parent-child edge is essential or not.) > > > Next, the two sets of interest (child + child's descendants, and > > parent + > > parent's ancestors) are sorted topologically. For the child + > > child's > > descendants, we can now rebuild the ancestor mappings by taking a tag > > from > > the top of the set, setting its ancestors to the union of tag's > > parents and > > parents' ancestors, and repeating the process on the next tag in > > topologically > > sorted order until all tags are consumed. The parent + parent's > > ancestors > > can be done in a similar way, except that a children function is > > required, and > > the tags must be topologically sorted in the reverse direction. > > > Some remarks: > > > An alternative approach would be to just recompute the whole ancestor > > and > > descendant maps for the whole hierarchy. This would be simpler, but > > for > > large hierarchies would be unnecessarily expensive. > > > The topological sort function which I wrote avoids recursion. If we > > wanted > > to allow multiple recursion, it could be simplified a bit, but I > > wanted to > > avoid stack consumption. > > > Anyway, I'd appreciate any suggestions and criticisms, since this is > > the > > first clojure code of mine that anyone has looked at. -- 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