search

timtadh / zhang-shasha

Tree edit distance using the Zhang Shasha algorithm
Other
433 stars 63 forks source link

Second condition is redundant #3

Closed nesaro closed 13 years ago

nesaro commented 13 years ago

Hi Tim,

I was looking for a tree-diff algorithm, and I found your project. I've reviewed it for learning purposes, and if I understood the algorithm correctly, the second condition of the shared root case is always true if the first is true:

             if (A.lmds[i] == A.lmds[x] and B.lmds[j] == B.lmds[y] or
              (x == i and y == j)):

but:

(x == i and y == j) ---> A.lmds[i] == A.lmds[x] and B.lmds[j] == B.lmds[y]

In case I didn't understand your code properly, I'm sorry for the inconvenience. Thank you for your making your code available!

timtadh commented 13 years ago

Hi I will take a look at this more closely. I unfortunately lost my annotated version of the paper. So I will have to do some thinking. In any case I will test your change.

timtadh commented 13 years ago

You are correct. Tested and merged. Thanks for reading the code. Now for that bug I still haven't worked on...

nesaro commented 13 years ago

It was my pleasure. Good luck with that other bug!