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 <[email protected]> wrote:
> Oh God. What broken formatting. Sorry about that.
>
> On Jun 15, 4:24 pm, Rob Lachlan <[email protected]> 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 [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
