0
$\begingroup$

I am using AHU algorithm to detect if two rooted trees are isomorphic or not, and I used this algorithm, I have sent it to my teacher and my teacher put a comment that there is a mistake in this algorithm according to your example of trees, but I can not see where is my mistake?

you see the small yellow box it the image? that's the comment

enter image description here

and this is the example according to the image, in this part, I am supposed to assign tuples in the form of parentheses to the leaves of trees and from button to up to the root it gets children's parentheses

enter image description here

now I have to convert these parentheses to numbers, so I could obtain the canonical numbers of a tree... and then sort the number so for each tree I could have a unique number and compare these two numbers between then tree to check if they are similar or not

enter image description here

enter image description here

Here I have sorted the algorithm

enter image description here and here is the algorithm for converting the parentheses to numbers, but the thing I do not see is from my perspective this algorithm matches with the examples I have provided, but as you see in the first image, the little yellow box is the comment I have gotten from teacher that "there is a mistake here", and I don't know what is it

What do you think is my mistake?

$\endgroup$
12
  • $\begingroup$ Well, you don't sort your strings in the first example. Also, in step 9, you don't specify what $t$ is, and try to assign something new to $L$ it seems? Step 9 should read Give $v$ the tuple name "("L")" $\endgroup$
    – Vsotvep
    Commented Jul 13, 2019 at 13:01
  • $\begingroup$ Another thing is that you use both capital and small letters for your variables. This is sloppy, and would generally give errors if you feed such things to a computer (or a rigorous mathematician) $\endgroup$
    – Vsotvep
    Commented Jul 13, 2019 at 13:03
  • $\begingroup$ @Vsotvep Thank you man, the thing is there is no sorting happening for the first algorithm, it is just the series of parentheses.. I can sort only after they are converted to the numbers which is second algorithm, but about the t, you are right, I found it online, how can I fix it ? $\endgroup$
    – Sina M
    Commented Jul 13, 2019 at 13:33
  • $\begingroup$ @Vsotvep so if I rewrite it like that, would it be ok? i.imgur.com/9Tqo360l.png $\endgroup$
    – Sina M
    Commented Jul 13, 2019 at 13:44
  • 2
    $\begingroup$ @Vsotvep didn't know it, sorry... as you see I am quite new here, don't know the standard here and different from my culture. I will keep it in mind. $\endgroup$
    – Sina M
    Commented Jul 14, 2019 at 9:35

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .