14
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ What are you actually trying to achieve? This sounds a little like XY problem. \$\endgroup\$
    – msell
    Commented Apr 22, 2013 at 6:25
  • \$\begingroup\$ 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 =-) \$\endgroup\$
    – Mungoid
    Commented Apr 22, 2013 at 16:01

2 Answers 2

Reset to default
12
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Awesome, thats pretty much exactly what I am looking for! I'll have to give it a go. Thanks! \$\endgroup\$
    – Mungoid
    Commented Apr 22, 2013 at 15:58
  • \$\begingroup\$ I think this only works if you have a root node, but in this case that might be the case :D +1 \$\endgroup\$
    – Roy T.
    Commented Apr 22, 2013 at 16:02
  • \$\begingroup\$ 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. \$\endgroup\$
    – congusbongus
    Commented Apr 22, 2013 at 23:21
  • \$\begingroup\$ Yep it worked like a charm. Took a little bit of time to understand it but works perfect =-) \$\endgroup\$
    – Mungoid
    Commented Apr 23, 2013 at 19:10
  • \$\begingroup\$ Thanks for this, looks like something I could use too, I'm loving the algorithm to find the Center of a Tree. Very clever. \$\endgroup\$
    – oodavid
    Commented Oct 17, 2013 at 8:44
4
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Yep thats what i need. Would have never figured out what that was called. Thanks =-) \$\endgroup\$
    – Mungoid
    Commented Apr 22, 2013 at 15:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .