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
