Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm having a hard time trying to describe this in correct terms so I will just give as much detail as possible and hopefully someone knows what I'm trying to do =-)

I am trying to compare two node trees to determine how similar/different they are structure-wise. In my diagrams below, both examples have the same number of children, grandchildren, etc. In example 1, Root has a child with two children, but in example two, root does not.

I could probably figure out how to recursively loop through and count how many of each level there are and compare that, giving me an idea of how similar the trees are, but only doing it that way, it will look like they are identical, but in fact they aren't.

Anyone happen to know about this? Or even what the technical term for what this is?

Edit: Also, this is in C# and I am using Lists to store these objects and their children.

Example 1

enter image description here

Example 2

enter image description here

share|improve this question
1  
What are you actually trying to achieve? This sounds a little like XY problem. –  msell Apr 22 '13 at 6:25
    
Best way i can describe it is for comparing 'molecular' structures the user creates one molecule at a time. Example 1 would be a structure a user created and example 2 could be part of a list of predefined structures to help determine if the user created the correct structure. Root tree isomorphism is apparently what I was looking for =-) –  Mungoid Apr 22 '13 at 16:01

2 Answers 2

up vote 9 down vote accepted

What you are looking for is Rooted Tree Isomorphism, which is a specialised version of the Graph Isomorphism, except for trees and the root node is fixed.

The explanation given in this assignment uses two properties:

  • Have the same number of levels (distance between root and leaf nodes)
  • Each level has the same number of nodes

Using these two properties, work your way up from the leaves to the root, labelling each node with the number of children, in lexicographical order. For example, your Root in Example 1 will be labelled (0, 0, (0, 1)) - it has three children, the first/second have 0 children, and the third has 2 children which have 0 and 1 children respectively. Finally you just compare the root labels to see if the trees are the same.

I haven't done this kind of subject and I've only read this paper a few minutes ago so I can't vouch for its correctness; hope it helps anyway.

share|improve this answer
    
Awesome, thats pretty much exactly what I am looking for! I'll have to give it a go. Thanks! –  Mungoid Apr 22 '13 at 15:58
    
I think this only works if you have a root node, but in this case that might be the case :D +1 –  Roy T. Apr 22 '13 at 16:02
    
If the root node isn't given, you can still use this technique but try every root. When comparing two trees, this means repeating by up to n times. –  congusbongus Apr 22 '13 at 23:21
    
Yep it worked like a charm. Took a little bit of time to understand it but works perfect =-) –  Mungoid Apr 23 '13 at 19:10
    
Thanks for this, looks like something I could use too, I'm loving the algorithm to find the Center of a Tree. Very clever. –  oodavid Oct 17 '13 at 8:44

The problem to see if two graphs are logically the same is called Graph Isomorphishm so you might want so start from there.

Note that the general Graph Isomorphism problem is in NP however for this special case there might be a shortcut, I'm not sure since it seems logical that to know the differences you have to check if they are equal.

share|improve this answer
    
Yep thats what i need. Would have never figured out what that was called. Thanks =-) –  Mungoid Apr 22 '13 at 15:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.