I am looking for an (efficient) implementation of an algorithm for
heirarchical tree comparison.
How does the Eclipse Difference Browser (for Java) work, and where can
I find its implementation?
Oliver Wong - 14 Jul 2006 18:05 GMT
>I am looking for an (efficient) implementation of an algorithm for
> heirarchical tree comparison.
> How does the Eclipse Difference Browser (for Java) work, and where can
> I find its implementation?
Eclipse is open source, so you can just view the source for whatever
you're looking for. I don't know of any "hierarchical tree comparison"
feature in Eclipse though. Are you perhaps thinking of the three-way CVS
comparator?
- Oliver
Chris Smith - 15 Jul 2006 00:03 GMT
> I am looking for an (efficient) implementation of an algorithm for
> heirarchical tree comparison.
> How does the Eclipse Difference Browser (for Java) work, and where can
> I find its implementation?
If you mean "compare to...", that's not hierarchical at all. Algorthms
for diff-style programs (what Eclipse does there) are ubiquitous and
easily found by Google, but I don't think they meet your stated need.
If that's not what you mean, then can you clarify?

Signature
Chris Smith - Lead Software Developer / Technical Trainer
MindIQ Corporation
Chris Uppal - 15 Jul 2006 10:44 GMT
> I am looking for an (efficient) implementation of an algorithm for
> heirarchical tree comparison.
Very difficult in the general case. As far as I know this is still an open
research topic.
If you can restrict the problem a bit then you can convert it into a linear
diffing problem. Linear diffing is the subject of a /huge/ amount of research
(partly because the CS and genetics communities have tended to duplicate each
others efforts). I could point you at some of the papers, but it sounds as if
you are just looking for a ready-made implementation -- and there are quite a
few which are easy to find on the net.
If you can restrict it so that the children of each node have a fixed order
(alphabetical, say), and you don't want to consider the possibility that a node
may have moved from one subtree to another, then you can use a linear diff,
recursing into each sub-tree. Another way would be to linearise the entire
trees into a specific order, and then just do a big diff on the linear
representation. If you do that then you could choose to take the depth into
account, or to ignore it for these purposes.
-- chris