I'm designing a scene graph system, where it is required to compare two trees. The trees are populated with individual objects, each with varied number of children; and they have a root.
Eg: Parent: Scene, Children: Bullet1, Bullet 2, Player
What is a good way to compare two such tree? I'm using C++ for the code.
Also, this question is an off-shoot from this question
Create a stack of node pairs for in-depth comparison.
Define an identifier you can use for quick comparison e.g. ID/name/model-path.
Shallow compare root nodes, if they match add them to stack.
For each pair in stack:
2.1. Sort children according to chosen identifier
2.2. Shallow compare children and add matches to stack.
Decide whether algorithm should be terminated on first mismatch or not (depending on required results).
If your nodes are themselves sub-trees (of smaller parts), you can apply the same algorithm to them.
Depends rather what you mean by "compare", but if you can (effectively) serialize your trees (or at least the properties of them you care about) to strings then the "Levenshtein distance" (or some other related "edit distance" or "string metric") between a pair of strings ought to tell you something useful about the similarities between them.
You can also have some fun with compression-based similarity metrics: if strings A and B compress to size a and b, but compressing the file C created by concatenating A and B compresses to size c, then c/(a+b) tells you something about how much duplicate information there was in the two files: the nearer to 1.0, the less benefit there was from compressing the files together and so the less similar they are (subject to caveats re file size and the maximum window your compressor works over anyway). Think this sort of approach is used by bioinformatics people but with it's information theoretic roots it ought to be more generally applicable.
