# Efficient way to compare scene-graph trees

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

• On top of my head, could one just compare the 2 adjacency matrices? Jun 27 '12 at 16:14
• Is your scene graph a graph or a tree? What are you comparing? Jun 27 '12 at 16:25
• @EmmadKareem: Well, how do you suggest the adjacency matrices be populated? Jun 27 '12 at 16:25
• @DannyVarod: It is a tree ( I use 'graph' here to suggest the scene graph ). I'm comparing two such graphs, drawn from different scenes to find where they exactly differ. Jun 27 '12 at 16:26
• I know what scene graphs are. Most of the ones I have scene were trees. My question is what are you comparing e.g. items, positions, changes within the objects themselves (moved parts, changed colors). If you are comparing items, are you comparing them by name, by model, ... Jun 27 '12 at 16:42

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.

1. Shallow compare root nodes, if they match add them to stack.

2. 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.

• Thanks, but I've already implemented it that way. I was actually looking for alternative approaches to this. Jun 28 '12 at 6:41
• You should write what you have already tried in the question, not wait for answers. Jun 28 '12 at 7:43

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.